C#语言编写的基于遗传算法的旅行销售员问题的程序namespace TSP
{
//数据文件格式:
//第一行有两个数据:矩阵行数 矩阵列数
//接下来的行的数据:行 列 该行该列的元素值
//注意数据与数据之间是用空格隔开的,没有给出的矩阵的某些位置的值用0来代替
using System;
using System.IO;
class TestClass
{
private static Floyd test2=new Floyd();
public static void Test1()
{
double [,]Mat;
Mat=LSMat.LoadDoubleDataFile(@"d:\c#\data01.txt");
//显示Mat
for(int i=0;i<=Mat.GetUpperBound(0);i++)
{
for(int j=0;j<=Mat.GetUpperBound(1);j++)
Console.Write("{0}\t",Mat[i,j]);
Console.Write("\n");
}
LSMat.SaveDataFile(@"d:\c#\datas01.txt",Mat);
}
public static void Test2(string DataFileName)
{
test2.MinFloyd(DataFileName);
Console.WriteLine("----------- 输出结果 ----------");
for(int i=0;i for(int j=0;j {
Console.Write("{0}:\t",test2.GetDistance(i,j));
Console.WriteLine(test2.GetPath(i,j));
}
Console.WriteLine("------------- 结束 ------------");
}
public static void Main(string[] args)
{
//Test1(); //运行LSMat类的测试函数
//Test2(@"d:\c#\data01.txt");
int []t;
t=RandNumber.RandDifferInt(90);
for(int i=0;i {
Console.Write("{0} ",t[i]);
if(i%10==9) Console.Write("\n");
}
}
}
/* 下面是TSP问题的遗传算法实现类
* */
class Ga
{
/*
private int N; //群体规模
private int Length; //个体长度
private double Pc; //交叉概率
private double Pm; //变异概率
private int MaxGene; //最大迭代代数
private int []MinIndividual; //当前代的最好个体指针
private double MinValue; //到当前代至最好个体的适应度值
private double [,]Buf1;
*/
}
class RandNumber
{
// 返回low与high之间的number个随机整数(包括low和high)
public static int[] RandInt(int low,int high,int number)
{
Random rr=new Random();
int []randvec;
randvec=new int[number];
for(int i=0;i randvec[i]=rr.Next()%(high-low+1)+low;
return randvec;
}
// 返回low与high之间的number(number小于high-low+1)个不同的随机整数(包括low和high)
public static int[] RandDifferInt(int low,int high,int number)
{
if(number>high-low+1) number=high-low+1;
Random rr=new Random();
int []randvec;
randvec=new int[number];
randvec[0]=rr.Next()%(high-low+1)+low;
int randi; //存储中间过程产生的随机整数
bool IsDiffer;//用于判断新产生的随机整数是否与以前产生的相同,若不同为真,否则为假
for(int i=1;i {
while(true)
{
randi=rr.Next()%(high-low+1)+low;
IsDiffer=true; //设定为真
for(int j=0;j {
if(randi==randvec[j])
{
IsDiffer=false; //相同为假
break;
}
}
if(IsDiffer)
{
randvec[i]=randi;
break;
}
}
}
return randvec;
}
// 返回low与high之间的high-low+1个不同的随机整数(包括low和high)
public static int[] RandDifferInt(int low,int high)
{
return RandDifferInt(low,high,high-low+1);
}
// 返回0与high之间的high+1个不同的随机整数(包括0和high)
public static int[] RandDifferInt(int high)
{
return RandDifferInt(0,high,high+1);
}
}
/* 下面是Floyd算法类
* */
class Floyd
{
private double [,]Distance; //图的距离矩阵
private int [,]Path; //图的最短路径的紧前顶点矩阵
public int GetDotN() //获得顶点数
{
return Path.GetLength(0);
}
public double GetDistance(int i,int j) //获得顶点i到顶点j的最短距离
{
return Distance[i,j];
}
public string GetPath(int ni,int nj)
{
int []pathReverse;
pathReverse=new int[Path.GetLength(0)];
pathReverse[0]=Path[ni,nj];
int k=0;
while(pathReverse[k]!=ni)
{
k++;
pathReverse[k]=Path[ni,pathReverse[k-1]];
}
string path=pathReverse[k].ToString();
string str1="-->";
for(int i=k-1;i>=0;i--)
{
path+=(str1+pathReverse[i].ToString());
}
path+=(str1+nj.ToString());
return path;
}
public void MinFloyd(string DataFileName)
{
double [,]CostMat;
CostMat=LSMat.LoadDoubleDataFile(DataFileName);
MinFloyd(CostMat);
}
//Floyd算法的实现
//CostMat是图的权值矩阵
public void MinFloyd(double [,]CostMat)
{
int nn;
nn=CostMat.GetLength(0); //获得图的顶点个数
for(int i=0;i for(int j=0;j {
if(CostMat[i,j]==0)
CostMat[i,j]=10e+100;
}
Distance=new double[nn,nn];
Path=new int[nn,nn];
//初始化Path,Distance
for(int i=0;i {
for(int j=0;j {
Path[i,j]=i;
Distance[i,j]=CostMat[i,j];
}
Distance[i,i]=0.0;
}
for(int k=0;k for(int i=0;i for(int j=0;j {
double a1,a2;
a1=Distance[i,j];
a2=Distance[i,k]+Distance[k,j];
if(a1>a2)
{
Distance[i,j]=a2;
Path[i,j]=Path[k,j];
}
}
}
}
class LSMat
{
//从数据文件中获取二维矩阵
public static double[,] LoadDoubleDataFile(string DataFileName)
{
FileStream fs; //文件指针
fs=File.Open(DataFileName,FileMode.Open,FileAccess.Read); //以只读方式打开数据文件
StreamReader r=new StreamReader(fs);//创建读入流
string str;
str=r.ReadLine(); //读入数据文件的第一行
double []rowcolv; //定义一维数组
rowcolv=StringToDouble(str); //把特定字符串转换为一维数组
double [,]Mat; //定义二维数组
Mat=new double[(int)rowcolv[0],(int)rowcolv[1]]; //创建二维数组Mat
while(r.Peek()>-1) //当到达数据文件尾时结束循环
{
str=r.ReadLine(); //读入数据文件当前行字符串
rowcolv=StringToDouble(str);//把特定字符串转换为一维数组
Mat[(int)rowcolv[0],(int)rowcolv[1]]=rowcolv[2]; //为二维数组赋值
}
fs.Close(); //关闭数据文件指针
return Mat; //返回二维数组
}
//从数据文件中获取二维矩阵
public static int[,] LoadIntleDataFile(string DataFileName)
{
FileStream fs; //文件指针
fs=File.Open(DataFileName,FileMode.Open,FileAccess.Read); //以只读方式打开数据文件
StreamReader r=new StreamReader(fs);//创建读入流
string str;
str=r.ReadLine(); //读入数据文件的第一行
int []rowcolv; //定义一维数组
rowcolv=StringToInt(str); //把特定字符串转换为一维数组
int [,]Mat; //定义二维数组
Mat=new int[(int)rowcolv[0],(int)rowcolv[1]]; //创建二维数组Mat
while(r.Peek()>-1) //当到达数据文件尾时结束循环
{
str=r.ReadLine(); //读入数据文件当前行字符串
rowcolv=StringToInt(str);//把特定字符串转换为一维数组
Mat[(int)rowcolv[0],(int)rowcolv[1]]=rowcolv[2]; //为二维数组赋值
}
fs.Close(); //关闭数据文件指针
return Mat; //返回二维数组
}
//把双精度型数据矩阵存入指定文件中
public static void SaveDataFile(string DataFileName,double [,]Mat)
{
FileStream fs;//文件指针
fs=File.Open(DataFileName,FileMode.OpenOrCreate,FileAccess.Write);//创建并打开文件指针
StreamWriter w=new StreamWriter(fs);//创建写入文件流
string str;//定义字符串
string str2=" ";//创建一个空格字符串
str=Mat.GetLength(0).ToString()+str2+Mat.GetLength(1);// 行和列字符串
w.WriteLine(str);//写入该字符串
//把每个元素写入文件
for(int i=Mat.GetLowerBound(0);i<=Mat.GetUpperBound(0);i++)
for(int j=Mat.GetLowerBound(1);j<=Mat.GetUpperBound(1);j++)
{
str=i.ToString()+str2+j.ToString()+str2+Mat[i,j].ToString();
w.WriteLine(str);
}
w.Close();//关闭写文件流
}
//把整型数据矩阵存入指定文件中
public static void SaveDataFile(string DataFileName,int [,]Mat)
{
FileStream fs;//文件指针
fs=File.Open(DataFileName,FileMode.OpenOrCreate,FileAccess.Write);//创建并打开文件指针
StreamWriter w=new StreamWriter(fs);//创建写入文件流
string str;//定义字符串
string str2=" ";//创建一个空格字符串
str=Mat.GetLength(0).ToString()+str2+Mat.GetLength(1);// 行和列字符串
w.WriteLine(str);//写入该字符串
//把每个元素写入文件
for(int i=Mat.GetLowerBound(0);i<=Mat.GetUpperBound(0);i++)
for(int j=Mat.GetLowerBound(1);j<=Mat.GetUpperBound(1);j++)
{
str=i.ToString()+str2+j.ToString()+str2+Mat[i,j].ToString();
w.WriteLine(str);
}
w.Close();//关闭写文件流
}
private static double[] StringToDouble(string str)
{
double []Mat; //定义一维数组
Mat=new Double[3]; //创建一维数组
string str1=null; //创建空字符串
int index1=0; //创建一个整型数并赋0
if(str[0]==' ') //如果字符串的首字符为空
{
//本循环目的是找到第一个不为“空格”的字符的索引,并把它赋给index1
for(int i=1;i {
if(str[i]!=' ')
{
index1=i;
break;
}
}
}
//下面循环的目的是以空格为分界符找出所有子字符串,同时把这些子字符串转换成双精度浮点数
int k=0;//标志着目前的子字符串的序号,从0开始记数
for(int i=index1;i {
if(str[i]==' '||i>=(str.Length-1)) //如果第i个字符为“空格”或者已到字符串结尾
{
//如果已到字符串结尾并且该字符不为“空格”,则把最后的字符加到最后的子字符串中
if(i>=(str.Length-1)&&(str[i]!=' '))
str1+=str[i];
Mat[k]=double.