目录
一、实习内容 ......................................................................................... 2
二、主要改进内容 ................................................................................. 2
（一）工程的建立 ........................................................................... 2
（二）变量的定义 ........................................................................... 3
（三）函数的声明及文件的定义 ................................................... 4
（四）init()函数的主要修改部分 .................................................... 5
（五）position(int *tmp,int C) 函数的主要修改部分 .................... 7
（六）tempTest(int i) 函数的主要修改部分 .................................. 8
（七）printBest(long GenNum,long Ni) 函数的主要修改部分 ....... 9
（八）mapped()函数的主要修改部分 .......................................... 10
（九）LastCP()函数的主要修改部分 ............................................ 11
（十）main()函数的主要修改部分 ............................................... 11
三、实现结果 ....................................................................................... 15
四、心得体会 ....................................................................................... 16
五、源代码 ........................................................................................... 16
李贝 20121004169 c#程序设计课程报告
一、实习内容
TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。
迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
本次作业的内容是将一个TSP算法的c语言程序改成c#，除了原始的改进外可以使用面向对象的多线程改进。
二、主要改进内容
（一）工程的建立
因为在本次作业中我只是把原有的c语言程序改进成了c#的黑框程序，所以建立的是普通的控制台应用程序，如果要用到界面，那应该建立windows窗体应用程序。建立好工程后会出现一些整体的框架如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
}
}
}
但是在程序中我们要用到文件的打开和读取，所以需要加上using System.IO的命名空间。
2
李贝 20121004169 c#程序设计课程报告
（二）变量的定义
在变量的定义过程中c#与c主要的不同就是宏定义、数组的定义，在c#中是没有宏定义的，需要用到static，数组的定义格式也与c语言完全不相同，在其他整形或其他类型的变量差别不大，只是要特别注意在定义前需要加上static。在程序中由于path函数一直有错误，所以在这里先定义一个临时的一维数组Colony存放colony数组中的一行数据。由于在c#中并没有clock_t类型，所以在这里先定义长整型的时间，在后面会用到datatime类型来替换clock_t类型。在后面的函数中也有变量的定义，规则均与此处一样，所以后面不再详细说明改进的变量定义部分。
1、c语言中的变量定义
#define FILE_PATH "e:\\cnc144.txt","r" //数据文件名
#define N_COLONY 300 // N_COLONY>=xColony
#define CITY 144 // CITY>=xCity
//--------------------------------------------//
int xColony=300; //##// 个体数
int xCity=198;
double edgeSpeed=30; //##// 临界速度
double probab1=0.02; //##// 变异概率
double probab2=0.05; //##// 映射概率 //0.04(80) 0.03(50) 0.015(80) 0.05(50);
long NOCHANGE=200000; //##// 最大停止改变代数
long maxGen=300000; //##// 停机代数
int colony[N_COLONY][CITY];
double cityXY[CITY][2];
double city_dis[CITY][CITY];
double dis_p[N_COLONY];
double sumbest,sumTemp;
double speed;
int temp[CITY],ibest;
clock_t timeStart,timeNow,timeTemp;
long GenNum,Ni;
2、c#中的变量定义
static string FILE_PATH = "e:\\cnc144.txt"; //数据文件名
static int N_COLONY = 300; // N_COLONY>=xColony
static int CITY = 144; // CITY>=xCity
//--------------------------------------------//
3
李贝 20121004169 c#程序设计课程报告 static int xColony = 300; //##// 个体数
static int xCity = 198;
static double edgeSpeed = 30; //##// 临界速度
static double probab1 = 0.02; //##// 变异概率
static double probab2 = 0.05; //##// 映射概率//0.04(80) 0.03(50) 0.015(80) 0.05(50);
static long NOCHANGE = 200000; //##// 最大停止改变代数
static long maxGen = 300000; //##// 停机代数
static int[] Colony = new int[N_COLONY];
static int[,] colony = new int[N_COLONY, CITY];
static double[,] cityXY = new double[CITY, 2];
static double[,] city_dis = new double[CITY, CITY];
static double[] dis_p = new double[N_COLONY];
static double sumbest, sumTemp;
static double speed;
static int[] temp = new int[CITY];
static int ibest;
static long timeStart, timeNow, timeTemp;
static long GenNum, Ni;
static int[] sign = new int[CITY];
（三）函数的声明及文件的定义
在函数声明时，c#必须在函数前加上static，否则会报错。在c#中没有FILE类型，所以必须用FileStream替换。
1、c语言中的函数的声明及文件的定义
void init();
int position(int *tmp,int C);
void invert(int pos_start,int pos_end);
void printBest(long GenNum,long Ni);
void tempTest(int i);
void mapped();
void LastCP();
double path(int tmp[],int k1,int k2);
FILE *fpme;
2、c#中的函数的声明及文件的定义
static void init();
static int position(int[] tmp, int C);
static void invert(int pos_start, int pos_end);
4
李贝 20121004169 c#程序设计课程报告 static void printBest(long GenNum, long Ni);
static void tempTest(int i);
static void mapped();
static void LastCP();
static double path(int [] tmp,int k1,int k2);
FileStream File = new FileStream(FILE_PATH, FileMode.OpenOrCreate);
（四）init()函数的主要修改部分
在变量的定义上除了数组的定义之外与c语言没有太大的不同，在函数体里由于init()函数里面含有很多for循环，而c语言的for循环与c#的for循环并没有差别，所以init()函数改进不大，只是在函数体中有涉及到数组的部分在格式上有改进，程序如下：
1、c语言中的init()函数
void init()
{ int i,j,t,sign,mod,array[CITY];
double x,y;
double d;
FILE *fp;
srand( (unsigned)time( NULL ) );
if((fp=fopen(FILE_PATH))==NULL)exit(0);
fscanf(fp,"%d",&xCity);
for(i=0;i<xCity;i++) /* init cityXY[][] */
{ fscanf(fp,"%Lf%Lf",&x,&y);
cityXY[i][0]=x;
cityXY[i][1]=y;
}
fclose(fp);
for(i=0;i<xCity;i++) /* init city_dis[] */
for(j=0;j<xCity;j++)
{ if(j>i)
{ d=(cityXY[i][0]-cityXY[j][0])*(cityXY[i][0]-cityXY[j][0])*1.0+
(cityXY[i][1]-cityXY[j][1])*(cityXY[i][1]-cityXY[j][1])*1.0;
city_dis[i][j]=sqrt(d);
continue;
}
if(j==i) {city_dis[i][j]=0;continue;}
if(j<i) city_dis[i][j]=city_dis[j][i];
}
5
李贝 20121004169 c#程序设计课程报告 mod=xCity;
for(i=0;i<xCity;i++)array[i]=i; // init colony[][]
for(i=0;i<xColony;i++,mod=xCity)
for(j=0;j<xCity;j++)
{ sign=rand()%mod;
colony[i][j]=array[sign];
t=array[mod-1];
array[mod-1]=array[sign];
array[sign]=t;
mod--;
if(mod==1) colony[i][++j]=array[0];
}
for(i=0;i<xColony;i++) /* init dis_p[] */
{ dis_p[i]=0;
for(j=0;j<xCity-1;j++)
dis_p[i]=dis_p[i]+city_dis[*(*(colony+i)+j)][*(*(colony+i)+j+1)];
dis_p[i]=dis_p[i]+city_dis[**(colony+i)][*(*(colony+i)+xCity-1)];
}
ibest=0;sumbest=dis_p[0]; /* init ibest & sumbest */
sumTemp=sumbest*5;
speed=100000000;
GenNum=0; Ni=0; /* initialize GunNum & Ni */
printf("init success!!!\n");
}
2、c#中的init()函数
void init()
{
int i, j, t, sign, mod;
int[] array = new int[CITY];
double x, y;
double d;
for (i = 0; i < xCity; i++) /* init city_dis[] */
for (j = 0; j < xCity; j++)
{
if (j > i)
{
d = (cityXY[i, 0] - cityXY[j, 0]) * (cityXY[i, 0] - cityXY[j, 0]) * 1.0 +
6
李贝 20121004169 c#程序设计课程报告 (cityXY[i, 1] - cityXY[j, 1]) * (cityXY[i, 1] - cityXY[j, 1]) * 1.0; city_dis[i, j] = Math.Sqrt(d);
continue;
}
if (j == i) { city_dis[i, j] = 0; continue; }
if (j < i) city_dis[i, j] = city_dis[j, i];
}
mod = xCity;
for (i = 0; i < xCity; i++) array[i] = i; // init colony[][]
for (i = 0; i < xColony; i++, mod = xCity)
for (j = 0; j < xCity; j++)
{
sign = new Random().Next() % mod;
colony[i, j] = array[sign];
t = array[mod - 1];
array[mod - 1] = array[sign];
array[sign] = t;
mod--;
if (mod == 1) colony[i, ++j] = array[0];
}
for (i = 0; i < xColony; i++) /* init dis_p[] */
{
dis_p[i] = 0;
for (j = 0; j < xCity - 1; j++)
dis_p[i] = dis_p[i] + city_dis[colony[i, j], colony[i, j + 1]];
dis_p[i] = dis_p[i] + city_dis[colony[i, 0], colony[i, xCity - 1]];
}
ibest = 0; sumbest = dis_p[0]; /* init ibest & sumbest */
sumTemp = sumbest * 5;
speed = 100000000;
GenNum = 0; Ni = 0; /* initialize GunNum & Ni */
Console.WriteLine("init success!!!\n");
}
（五）position(int *tmp,int C) 函数的主要修改部分
在这个函数中主要需要改进的地方时指针，因为C#是不支持指针的，所以在定义的时候就将tmp定义为一个一维数组，并将if(*(tmp+j)==C)改为if((tmp[j])==C)。
7
李贝 20121004169 c#程序设计课程报告
1、c语言中的position(int *tmp,int C)函数
int position(int *tmp,int C)
{ int j;
for(j=0;j<xCity;j++)
if(*(tmp+j)==C)break;
return(j);
}
2、c#中的position(int *tmp,int C)函数
int position(int[] tmp,int C)
{ int j;
for(j=0;j<xCity;j++)
if((tmp[j])==C)break;
return(j);
}
（六）tempTest(int i) 函数的主要修改部分
在tempTest(int i)函数中主要需要改进的就是时间的表示，在c语言中是没有clock_t类型的，所以只能用datatime类型代替，这是在c#的库里面可以找到的，并将CLOCKS_PER_SEC改为固定值1000。
1、c语言中的tempTest(int i)函数
void tempTest(int i)
{ int j; double dt;
for(j=0;j<xCity;j++)colony[i][j]=temp[j];
if((int)sumbest>(int)dis_p[i])
{ sumbest=dis_p[i];ibest=i;Ni=0;
timeNow=clock();
dt=(double)(timeNow-timeTemp)/CLOCKS_PER_SEC;
if(dt>0.1)
{ speed=(sumTemp-sumbest)/dt;
sumTemp=sumbest;
timeTemp=timeNow;
}
printf("\n%f %4.2f %10.1f",sumbest,(double)(timeNow-timeStart)/CLOCKS_PER_SEC,speed);
}
}
2、c# 中的tempTest(int i)函数
8
李贝 20121004169 c#程序设计课程报告 void tempTest(int i)
{ int j; double dt;
for(j=0;j<xCity;j++)colony[i,j]=temp[j];
if((int)sumbest>(int)dis_p[i])
{ sumbest=dis_p[i];ibest=i;Ni=0;
timeNow=System.DateTime.Now.Millisecond;
dt=(double)(timeNow-timeTemp)/1000;
if(dt>0.1)
{ speed=(sumTemp-sumbest)/dt;
sumTemp=sumbest;
timeTemp=timeNow;
}
Console.WriteLine("\n%f%4.2f%10.1f",sumbest,(double)(timeNow-timeStart)/1000,speed);
}
}
（七）printBest(long GenNum,long Ni) 函数的主要修改部分
这个函数主要的作用是输出最好的结果，所以改进的部分主要是输出语句及文件的读取，这里文件的读取采用的是File.Exists函数和 File.Create函数。
1、c语言中的printBest(long GenNum,long Ni)函数
void printBest(long GenNum,long Ni)
{
int i;
printf("\n CITY %d\t\tN_COLONY %d",CITY,N_COLONY);
printf("\n maxGen %d\t\ttime %4.2f seconds",maxGen,(double)(timeNow-timeStart)/CLOCKS_PER_SEC);
printf("\n probab %g\t\tdistance %f",probab2,sumbest);
printf("\n GenNum %d\t\tNo change %Ld\n\n",GenNum,Ni);
for(i=0;i<xCity;i++)
{ if(i%10==0 && i!=0){ printf("\n");}
printf("%5d",colony[ibest][i]+1);
}
printf("\n\n");
if((fpme=fopen("result198.txt","a"))==NULL)exit(0);
fprintf(fpme,"\n CITY %d\t\tN_COLONY %d",CITY,N_COLONY);
fprintf(fpme,"\n maxGen %d\t\ttime %4.2f seconds",maxGen,(double)(timeNow-timeStart)/CLOCKS_PER_SEC);
9
李贝 20121004169 c#程序设计课程报告 fprintf(fpme,"\n probab %g\t\tdistance %f",probab2,sumbest);
fprintf(fpme,"\n GenNum %d\t\tNo change %Ld\n\n",GenNum,Ni);
fclose(fpme);
}
2、c# 中的printBest(long GenNum,long Ni)函数
void printBest(long GenNum,long Ni)
{
int i;
Console.WriteLine("\n CITY %d\t\tN_COLONY %d",CITY,N_COLONY);
Console.WriteLine("\n maxGen %d\t\ttime %4.2f seconds",maxGen,(double)(timeNow-timeStart)/1000);
Console.WriteLine("\n probab %g\t\tdistance %f",probab2,sumbest);
Console.WriteLine("\n GenNum %d\t\tNo change %Ld\n\n",GenNum,Ni); for(i=0;i<xCity;i++)
{ if(i%10==0 && i!=0){ Console.WriteLine("\n");}
Console.WriteLine("%5d",colony[ibest,i]+1);
}
Console.WriteLine("\n\n");
FileStream strme;
if(!File.Exists(FILE_PATH)){
strme = File.Create(FILE_PATH);
}
Else
{strme = new FileStream(FILE_PATH,FileMode.CreateNew);}
StreamWriter writer = new StreamWriter(strme);
writer.WriteLine("\n CITY "+CITY+"\t\tN_COLONY "+N_COLONY+"");
writer.WriteLine("\n maxGen "+maxGen+"\t\ttime "+(timeNow-timeStart)/1000+" seconds");
writer.WriteLine("\n probab "+probab2+"\t\tdistance "+sumbest+"");
writer.WriteLine("\n GenNum "+GenNum+"\t\tNo change "+Ni+"\n\n");
}
（八）mapped()函数的主要修改部分
这个函数主要改进的是随机函数的部分，在c#里面不能直接使用rand()函数
生成随机数，而应该使用Random().Next()函数，这里主要给改进的程序：
1、修改前的随机函数
i=rand()%xColony;
j=rand()%xColony;
10
李贝 20121004169 c#程序设计课程报告
start=rand()%xCity;
end=(start+rand()%180+20)%xCity; //rand()%xCity;
2、修改后的随机函数
i = new Random().Next() % xColony;
j=new Random().Next()%xColony;
start=new Random().Next()%xCity;
end=(start+new Random().Next()%180+20)%xCity; //new Random().Next()%xCity;
（九）LastCP()函数的主要修改部分
在这个函数中修改的主要是输出语句和随机函数，path函数中的参数也需要改变，这里给出修改过的程序：
1、输出语句
修改前：
printf("+");
printf("\n%f O K !!!",sumbest);
修改后：
Console.WriteLine("+");
Console.WriteLine("\n" + sumbest + " O K !!!");
2、随机函数
修改前：
for(k1=0;k1<xCity-1;k1+=rand()%4+1)
修改后：
for(k1=0;k1<xCity-1;k1+=new Random().Next()%4+1)
3、path函数中的参数
修改前：
dc = path(colony[i], j1, j2);
修改后：
dc = path(Colony[i], j1, j2);
（十）main()函数的主要修改部分
在c#中没有register类型，所以这里直接用整型，函数体中有用到随机函数
11
李贝 20121004169 c#程序设计课程报告
的地方也需要用Random().Next()函数。
1、c语言中的main()函数
void main()
{
register int C1,j,k,pos_C,pos_C1; int k1,k2,l1,l2,pos_flag,icount;
register double disChange;
static i=0;
timeStart=timeNow=timeTemp=clock(); init();
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^//
for(;;)
{ for(j=0;j<xCity;j++)temp[j]=colony[i][j];
disChange=0;pos_flag=0;
pos_C=rand()%xCity;
for(;;)
{
if((rand()/32768.0)<probab1) //内变异算子
{ do pos_C1=rand()%xCity;while (pos_C1==pos_C);
C1=colony[i][pos_C1];
}
else
{ do j=rand()%xColony;while(j==i);
k=position(colony[j],temp[pos_C]);
C1=colony[j][(k+1)%xCity];
pos_C1=position(temp,C1);
}
if( speed>edgeSpeed && pos_C1<pos_C+2)break; ///////////////////////
if((pos_C+1)%xCity==pos_C1 || (pos_C-1+xCity)%xCity==pos_C1 )break;
k1=temp[pos_C]; k2=temp[(pos_C+1)%xCity]; l1=temp[pos_C1];
l2=temp[(pos_C1+1)%xCity];
disChange+=city_dis[k1][l1]+city_dis[k2][l2]-city_dis[k1][k2]-city_dis[l1][l2];
invert(pos_C,pos_C1); pos_flag++;if(pos_flag>xCity-1)break; ////////////
pos_C++; if(pos_C>=xCity)pos_C=0; /**********************/
if( speed<edgeSpeed && disChange<0) { dis_p[i]+=disChange; disChange=0;
tempTest(i);} //每有改变就计算
}
if(speed>=edgeSpeed && disChange<0 ) {dis_p[i]+=disChange;disChange=0;
12
李贝 20121004169 c#程序设计课程报告 tempTest(i);} /////speed>=1500 &&
i++;
if(i>=xColony)
{ Ni++; GenNum++;i=0;
probab1=0.02*(1-GenNum*0.01/maxGen); //内逆转概率逐渐减小 if( speed<edgeSpeed && (rand()/32767.0<probab2) ) //
{ mapped();
probab2=0.05*(GenNum*2.0/maxGen+1); //部分交换概率逐渐增大 }
if(NOCHANGE-Ni<1) LastCP(); //5可改
if(GenNum>=maxGen || Ni>=NOCHANGE ) { printf("\n-------------------");printBest(GenNum,Ni); exit(1); }
}
}
}
2、c# 中的main()函数
static void Main(string[] args)
{
int C1, j, k, pos_C, pos_C1; int k1, k2, l1, l2, pos_flag, icount;
double disChange;
int i = 0;
// timeStart=timeNow=timeTemp=clock(); init();
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^//
for (; ; )
{
for (j = 0; j < xCity; j++)
temp[j] = colony[i, j];
disChange = 0; pos_flag = 0;
pos_C = new Random().Next()% xCity;
for (; ; )
{
if ((new Random().Next()/ 32768.0) < probab1) //内变异算子 {
do pos_C1 = new Random().Next() % xCity; while (pos_C1 == pos_C); C1 = colony[i,pos_C1];
}
else
{
do j = new Random().Next() % xColony; while (j == i);
k = position(colony[j],temp[pos_C]);
13
李贝 20121004169 c#程序设计课程报告
C1 = colony[j,(k + 1) % xCity];
pos_C1 = position(temp, C1);
}
if (speed > edgeSpeed && pos_C1 < pos_C + 2) break; ///////////////////////
if ((pos_C + 1) % xCity == pos_C1 || (pos_C - 1 + xCity) % xCity ==
pos_C1) break;
k1 = temp[pos_C]; k2 = temp[(pos_C + 1) % xCity]; l1 = temp[pos_C1];
l2 = temp[(pos_C1 + 1) % xCity];
disChange += city_dis[k1,l1] + city_dis[k2,l2] - city_dis[k1,k2] -
city_dis[l1,l2];
invert(pos_C, pos_C1); pos_flag++; if (pos_flag > xCity - 1) break;
////////////
pos_C++; if (pos_C >= xCity) pos_C = 0; /**********************/
if (speed < edgeSpeed && disChange < 0) { dis_p[i] += disChange;
disChange = 0; tempTest(i); } //每有改变就计算
}
if (speed >= edgeSpeed && disChange < 0) { dis_p[i] += disChange;
disChange = 0; tempTest(i); } /////speed>=1500 &&
i++;
if (i >= xColony)
{
Ni++; GenNum++; i = 0;
probab1 = 0.02 * (1 - GenNum * 0.01 / maxGen)//内逆转概率逐渐减
小
if (speed < edgeSpeed && (new Random().Next() / 32767.0 < probab2))
{
mapped();
probab2 = 0.05 * (GenNum * 2.0 / maxGen + 1); //部分交换概
率逐渐增大
}
if (NOCHANGE - Ni < 1) LastCP(); //5可改
if (GenNum >= maxGen || Ni >= NOCHANGE)
{ Console.WriteLine("\n-------------------"); printBest(GenNum, Ni); exit(1); }
}
}
}
14
李贝 20121004169 c#程序设计课程报告
三、实现结果
15
李贝 20121004169 c#程序设计课程报告
四、心得体会
这次作业是除了上课实习之外第一次正式的接触c#，以前听同学还有学长说c#不是很难，老师在上课的时候也一直强调如果之前有了c语言和c++的基础，学习c#就会相对轻松一些。所以在接触这种语言的时候并没有心理上的畏惧，反而是抱着很大的信心去学习的。
在这次作业里面，遇到了很多困难，不过基本上在书上或者网上都有相应的解释，有很多错误在买的参考书籍里面都没有提到过，在网上搜了之后发现不只是我大家都遇到了这种问题，并作出了详细的解答，而且这个程序里面让我们修改的部分并不是特别多，把c#里面独有的格式修改之后，有一个大的部分需要注意，就是系统一直提示数组里的索引有错误，问了同学之后，才知道可以用交错数组或者是定义一个临时的一维数组来解决。
这次作业给我的最大的感受就是学习一门语言仅仅靠上课的知识和书本上的内容是远远不够的，更需要的是我们动手的能力和查询资料的能力，毕竟我们现在做的是很初级的东西，我们遇到的问题大家都遇到过，所以一般都能够解决，狮子啊不能解决也可以去问同学或老师。
五、源代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication1
{
class Program
{
static string FILE_PATH = "e:\\cnc144.txt"; //数据文件名
static int N_COLONY = 300; // N_COLONY>=xColony
static int CITY = 144; // CITY>=xCity
//--------------------------------------------//
static int xColony = 300; //##// 个体数
static int xCity = 198;
static double edgeSpeed = 30; //##// 临界速度
static double probab1 = 0.02; //##// 变异概率
static double probab2 = 0.05; //##// 映射概率 //0.04(80) 0.03(50)
16
李贝 20121004169 c#程序设计课程报告 0.015(80) 0.05(50);
static long NOCHANGE = 200000; //##// 最大停止改变代数
static long maxGen = 300000; //##// 停机代数
static int[] Colony = new int[N_COLONY];
static int[,] colony = new int[N_COLONY, CITY];
static double[,] cityXY = new double[CITY, 2];
static double[,] city_dis = new double[CITY, CITY];
static double[] dis_p = new double[N_COLONY];
static double sumbest, sumTemp;
static double speed;
static int[] temp = new int[CITY];
static int ibest;
static long timeStart,timeNow,timeTemp;
static long GenNum, Ni;
File FILE;
static void Main(string[] args)
{
int C1, j, k, pos_C, pos_C1; int k1, k2, l1, l2, pos_flag, icount;
double disChange;
int i = 0;
// timeStart=timeNow=timeTemp=clock(); init();
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^//
for (; ; )
{
for (j = 0; j < xCity; j++)
temp[j] = colony[i, j];
disChange = 0; pos_flag = 0;
pos_C = new Random().Next()% xCity;
for (; ; )
{
if ((new Random().Next()/ 32768.0) < probab1) //内变异算子
{
do pos_C1 = new Random().Next() % xCity; while (pos_C1 == pos_C);
C1 = colony[i,pos_C1];
}
else
{
17
李贝 20121004169 c#程序设计课程报告
do j = new Random().Next() % xColony; while (j == i);
k = position(colony[j],temp[pos_C]);
C1 = colony[j,(k + 1) % xCity];
pos_C1 = position(temp, C1);
}
if (speed > edgeSpeed && pos_C1 < pos_C + 2) break; ///////////////////////
if ((pos_C + 1) % xCity == pos_C1 || (pos_C - 1 + xCity) %
xCity == pos_C1) break;
k1 = temp[pos_C]; k2 = temp[(pos_C + 1) % xCity]; l1 =
temp[pos_C1]; l2 = temp[(pos_C1 + 1) % xCity];
disChange += city_dis[k1,l1] + city_dis[k2,l2] - city_dis[k1,k2]
- city_dis[l1,l2];
invert(pos_C, pos_C1); pos_flag++; if (pos_flag > xCity - 1)
break; ////////////
pos_C++; if (pos_C >= xCity) pos_C = 0; /**********************/
if (speed < edgeSpeed && disChange < 0) { dis_p[i] +=
disChange; disChange = 0; tempTest(i); } //每有改变就计算
}
if (speed >= edgeSpeed && disChange < 0) { dis_p[i] += disChange;
disChange = 0; tempTest(i); } /////speed>=1500 &&
i++;
if (i >= xColony)
{
Ni++; GenNum++; i = 0;
probab1 = 0.02 * (1 - GenNum * 0.01 / maxGen); //
内逆转概率逐渐减小
if (speed < edgeSpeed && (new Random().Next() / 32767.0
< probab2)) //
{
mapped();
probab2 = 0.05 * (GenNum * 2.0 / maxGen + 1); //
部分交换概率逐渐增大
}
if (NOCHANGE - Ni < 1) LastCP(); //5可改
if (GenNum >= maxGen || Ni >= NOCHANGE)
{ Console.WriteLine("\n-------------------"); printBest(GenNum, Ni); exit(1); }
}
}
18
李贝 20121004169 c#程序设计课程报告 }
void init()
{ int i,j,t,sign,mod;
int[] array =new int[CITY];
double x,y;
double d;
//FILE *fp;
//if((fp=fopen(FILE_PATH))==NULL)exit(0);
//fscanf(fp,"%d",&xCity);
//for(i=0;i<xCity;i++) /* init cityXY[,] */
//{ fscanf(fp,"%Lf%Lf",&x,&y);
// cityXY[i,0]=x;
// cityXY[i,1]=y;
//}
//fclose(fp);
for(i=0;i<xCity;i++) /* init city_dis[] */
for(j=0;j<xCity;j++)
{ if(j>i)
{ d=(cityXY[i,0]-cityXY[j,0])*(cityXY[i,0]-cityXY[j,0])*1.0+
(cityXY[i,1]-cityXY[j,1])*(cityXY[i,1]-cityXY[j,1])*1.0;
city_dis[i,j]=Math.Sqrt(d);
continue;
}
if(j==i) {city_dis[i,j]=0;continue;}
if(j<i) city_dis[i,j]=city_dis[j,i];
}
mod=xCity;
for(i=0;i<xCity;i++)array[i]=i; // init colony[][]
for(i=0;i<xColony;i++,mod=xCity)
for(j=0;j<xCity;j++)
{
sign = new Random().Next() % mod;
colony[i,j]=array[sign];
t=array[mod-1];
array[mod-1]=array[sign];
array[sign]=t;
mod--;
if(mod==1) colony[i,++j]=array[0];
19
李贝 20121004169 c#程序设计课程报告 }
for(i=0;i<xColony;i++) /* init dis_p[] */
{ dis_p[i]=0;
for(j=0;j<xCity-1;j++)
dis_p[i] = dis_p[i] + city_dis[colony[i, j], colony[i,j+1]];
dis_p[i] = dis_p[i] + city_dis[colony[i,0], colony[i, xCity - 1]];
}
ibest=0;sumbest=dis_p[0]; /* init ibest & sumbest */
sumTemp=sumbest*5;
speed=100000000;
GenNum=0; Ni=0; /* initialize GunNum & Ni */
Console.WriteLine("init success!!!\n");
}
void invert(int pos_start,int pos_end)
{ int j,k,t;
if(pos_start<pos_end)
{ j=pos_start+1; k=pos_end;
for(;j<=k;j++,k--)
{ t=temp[j]; temp[j]=temp[k]; temp[k]=t; }
}
else
{
if(xCity-1-pos_start<=pos_end+1)
{ j=pos_end;k=pos_start+1;
for(;k<xCity;j--,k++)
{ t=temp[j];temp[j]=temp[k];temp[k]=t; }
k=0;
for(;k<=j;k++,j--)
{ t=temp[j]; temp[j]=temp[k];temp[k]=t; }
}
else
{ j=pos_end;k=pos_start+1;
for(;j>=0;j--,k++)
{ t=temp[j];temp[j]=temp[k];temp[k]=t; }
j=xCity-1;
for(;k<=j;k++,j--)
{ t=temp[j];temp[j]=temp[k]; temp[k]=t; }
20
李贝 20121004169 c#程序设计课程报告 }
}
}
int position(int[] tmp,int C)
{ int j;
for(j=0;j<xCity;j++)
if((tmp[j])==C)break;
return(j);
}
void tempTest(int i)
{ int j; double dt;
for(j=0;j<xCity;j++)colony[i,j]=temp[j];
if((int)sumbest>(int)dis_p[i])
{ sumbest=dis_p[i];ibest=i;Ni=0;
timeNow=System.DateTime.Now.Millisecond;
dt=(double)(timeNow-timeTemp)/1000;
if(dt>0.1)
{ speed=(sumTemp-sumbest)/dt;
sumTemp=sumbest;
timeTemp=timeNow;
}
Console.WriteLine("\n%f %4.2f %10.1f",sumbest,(double)(timeNow-timeStart)/1000,speed);
}
}
void printBest(long GenNum,long Ni)
{
int i;
Console.WriteLine("\n
CITY %d\t\tN_COLONY %d",CITY,N_COLONY);
Console.WriteLine("\n maxGen %d\t\ttime %4.2f seconds",maxGen,(double)(timeNow-timeStart)/1000);
Console.WriteLine("\n
probab %g\t\tdistance %f",probab2,sumbest);
Console.WriteLine("\n GenNum %d\t\tNo change %Ld\n\n",GenNum,Ni);
for(i=0;i<xCity;i++)
{ if(i%10==0 && i!=0){ Console.WriteLine("\n");}
21
李贝 20121004169 c#程序设计课程报告 Console.WriteLine("%5d",colony[ibest,i]+1);
}
Console.WriteLine("\n\n");
FileStream strme;
if(!File.Exists(FILE_PATH)){
strme = File.Create(FILE_PATH);
}else{
strme = new FileStream(FILE_PATH,FileMode.CreateNew);
}
StreamWriter writer = new StreamWriter(strme);
writer.WriteLine("\n CITY "+CITY+"\t\tN_COLONY "+N_COLONY+"");
writer.WriteLine("\n maxGen "+maxGen+"\t\ttime "+(timeNow-timeStart)/1000+" seconds");
writer.WriteLine("\n probab "+probab2+"\t\tdistance "+sumbest+"");
writer.WriteLine("\n GenNum "+GenNum+"\t\tNo change "+Ni+"\n\n");
}
void mapped()
{ int start,end,i,j,k,kt,t,disPlace,kDC,kC;
double temp_dis=0;
i = new Random().Next() % xColony;
j=new Random().Next()%xColony;
if(i==j)return;
if(dis_p[i]<dis_p[j])
{ t=i;i=j;j=t; }
for(k=0;k<xCity;k++)temp[k]=colony[i,k];
/////////////////
start=new Random().Next()%xCity;
end=(start+new Random().Next()%180+20)%xCity; //new Random().Next()%xCity;
kt=position(temp,colony[j,start]); //部分映射一二位同
disPlace=kt-start;
if(temp[(kt+1)%xCity]==colony[j,(start+1)%xCity])
{
if(start<end)
for(k=start;k<=end;k++)
22
李贝 20121004169 c#程序设计课程报告 { kDC=(k+disPlace)%xCity;
if(temp[kDC]==colony[j,k])continue;
t=position(temp,colony[j,k]);
temp[t]=temp[kDC];
temp[kDC]=colony[j,k];
}
else
for(k=start;k<=xCity+end;k++)
{ kDC=(k+disPlace)%xCity; kC=k%xCity;
if(temp[kDC]==colony[j,kC])continue;
t=position(temp,colony[j,kC]);
temp[t]=temp[kDC];
temp[kDC]=colony[j,kC];
}
}
else
{ if(temp[(kt-1+xCity)%xCity]==colony[j,(start+1)%xCity])
{ if(start<end)
for(k=kt=start;k<=end;k++,kt--)
{ kDC=(kt+xCity+disPlace)%xCity;
if(temp[kDC]==colony[j,k])continue;
t=position(temp,colony[j,k]);
temp[t]=temp[kDC];
temp[kDC]=colony[j,k];
}
else
for(k=kt=start;k<=end+xCity;k++,kt--)
{ kDC=(kt+xCity+disPlace)%xCity; kC=k%xCity;
if(temp[kDC]==colony[j,kC])continue;
t=position(temp,colony[j,kC]);
temp[t]=temp[kDC];
temp[kDC]=colony[j,kC];
}
}
else return;
}
for(j=0;j<xCity-1;j++)
temp_dis=temp_dis+city_dis[temp[j],temp[j+1]];
temp_dis=temp_dis+city_dis[temp[0],temp[xCity-1]];
dis_p[i]=temp_dis;
/*********/
tempTest(i);
23
李贝 20121004169 c#程序设计课程报告 }
void LastCP()
{ int i,k,j1,j2,k1,k2,turn,length; double dc,temp_dis=0,change=0;
Console.WriteLine("+");
for(k=0;k<xCity;k++)temp[k]=colony[ibest,k];
for(turn=0;turn<xCity/10;turn++) //可改
{ for(k1=0;k1<xCity-1;k1+=new Random().Next()%4+1) // new Random().Next()%9+1可改
{ for(i=1;i<xColony;i++)
{ if(i==ibest)continue;
for(k=0;k<xCity;k++)
;
j1=position(colony[i],temp[k1]);
k2=k1;j2=j1;
for(length=0;length<xCity/2;length++) // 70 xCity/3+10可改
{ k2=(++k2)%xCity; j2=(++j2)%xCity;
//sign[temp[k2]]=1;
if(temp[k2]==colony[i,j2] && length>1)break; // 5 xCity/10可改
}
if(temp[k2]!=colony[i,j2])continue;
k=j1;
do k=(k+1)%xCity;
while (sign[colony[i,k]]==1);
if( (j1<j2 && k<j2) || (j1>j2 && (k>j1 || k<j2)) )continue; temp_dis=path(temp,k1,k2);
dc = path(Colony[i], j1, j2);
if(temp_dis>dc)
{ for(k=1;k<=length;k++)
temp[(k1+k)%xCity]=colony[i,(j1+k)%xCity];
change+=dc-temp_dis;
}
}
}
}
if(change<0)
{ for(k=0;k<xCity;k++)colony[ibest,k]=temp[k];
dis_p[ibest]+=change;
sumbest=dis_p[ibest];
Console.WriteLine("\n" + sumbest + " O K !!!");
}
24
李贝 20121004169 c#程序设计课程报告 }
double path(int[] tmp,int k1,int k2)
{ int j,t1,t2; double temp_dis=0;
if(k2>k1)
for(j=k1;j<k2;j++)
temp_dis+=city_dis[tmp[j],tmp[j+1]];
else
for(j=k1;j<k2+xCity;j++)
{ t1=j%xCity; t2=(j+1)%xCity;
temp_dis+=city_dis[tmp[t1],tmp[t2]];
}
return temp_dis;
}
}
}
25