遗传算法解决TSP问题 C++、MFC界面编程 - 图文(5)

本科毕业设计说明书（论文）

}

int CTestDlg2::Max(double eval[100]) { }

3.1.6 交叉操作

int n; int ii=0; double comp[100];

for(ii=0;ii<=99;ii++){comp[ii]=eval[ii];} int n =0; int ii=0; double comp[100];

for(ii=0;ii<=99;ii++){comp[ii]=eval[ii];}

第 17 页 共 32 页

for(ii=1;ii<=99;ii++){if(comp[0]>comp[ii]){comp[0]=comp[ii];}} for(ii=0;ii<=99;ii++){if(comp[0]==eval[ii]){n=ii;break;}} return n;

for(ii=1;ii<=99;ii++){if(comp[0]

采用访问顺序编码后。如果采用简单的一点杂交或者多点杂交，就会产生非法路径。如：若采用一点杂交，随机杂交处为4：0 1 2 3 4| 5 6 7 8 9； 9 8 7 6 5| 4 3 2 1 0。杂交后的个体为：0 1 2 3 4 4 3 2 1 0；9 8 7 6 5 5 6 7 8 9。导致某些城市访问了不止1次。不符合TSP问题的定义。所以本文采用次序交叉来弥补这一缺陷。

次序交叉(OX,ORDER CROSSOVER):由Davis等人提出OX算法。次序杂交算法首先随机地在上代群体中选择两个杂交点，再交换杂交段，其他位置根据保持上代城市的相对次序来确定。例如：

A1[10]={0,1,2,3,4,5,6,7,8,9} A2[10]={9,8,7,6,5,4,3,2,1,0}随机杂交点为3和5。首先交换杂交段。

B1[10]={#,#,#|6,5,4|#,#,#,#}

本科毕业设计说明书（论文）

B2[10]={#,#,#|3,4,5|#,#,#,#}

第 18 页 共 32 页

从B1的第二个杂交点开始6-7-8-9-0-1-2-3-4-5，去除杂交段中的6,5,4。变成7-8-9-0-1-2-3。一次顺序从第二个杂交点开始填入得:

B1[10]={1,2,3,6,5,4,7,8,9,0} 同理得:B2[10]={8,7,6,3,4,5,2,1,0,9} 本文采用上述交叉算法，代码如下：

个体p;

double ww=0;

ww=(double)rand()/RAND_MAX; o=select(gailv,city); p=select(gailv,city); while(o==p) {

p=select(gailv,city);//由于2次选择了同一个个体重新选择一个

}

for(i=0;i<=9;i++){A1[i]=city[o][i];} for(i=0;i<=9;i++){A2[i]=city[p][i];} if(ww<=pcross)//条件成立则，发生交叉 { int p1 =-1; int p2 =-1; while(p1==p2) { p1=rand()%(9)+1; p2=rand()%(9)+1;

} if(p1>p2) { temp1=p1;

p1=p2;

本科毕业设计说明书（论文）

} else { }

int xy=0; }

for(i=p1; i<=p2;i++) { }

convert(p1,p2,A1,B1); convert(p1,p2,A2,B2); int xy=0;

B1[i] = A2[i]; B2[i] = A1[i]; p2=temp1;

第 19 页 共 32 页

for( xy=0;xy<=9;xy++){city1[k][xy]=B1[xy];} for( xy=0;xy<=9;xy++){city1[k+1][xy]=B2[xy];}

for( xy=0;xy<=9;xy++){city1[k][xy]=A1[xy];} for( xy=0;xy<=9;xy++){city1[k+1][xy]=A2[xy];}

其中的convert(p1,p2,A1,B1)函数打代码如下：

void CTestDlg2::convert(int pos1,int pos2,int *so,int *dest) {

int temp[10];

int ii = 0; int jj = 0; int kk = 0;

for(ii=0; ii<10; ii++) { }

temp[ii] = so[(ii+pos2+1)];

本科毕业设计说明书（论文）

}

for(kk=0; kk<(10-(pos2-pos1)-1); kk++) { }

dest[(kk+pos2+1)] = temp[kk]; for(ii=0; ii<10; ii++) { } jj = 0; ii = 0; while(jj<10) { }

if(temp[jj] != 100) { } jj++;

temp[ii] = temp[jj]; ii++;

for(jj=pos1; jj<=pos2; jj++) { }

if(temp[ii] == dest[jj]) { }

temp[ii] = 100; break;

第 20 页 共 32 页

本科毕业设计说明书（论文）

3.1.7 变异操作

第 21 页 共 32 页

在遗传算法中，变异操作并不是最主要的。遗传算法强调的是杂交功能。变异操作是改善遗传算法的局部搜索能力和维持群体的多样性防止早熟现象。针对TSP问题，陈国良等介绍了四种主要的变异技术：（1）点位变异，变异仅以某一很小的概率对串的某些位值变异；（2）逆转变异，在串中随机选择两点，再将这两点内的内容按反序插入到原来的位置中。（3）对换操作，随机选择两个交换点，使交换点处的码值交换。这种变异操作在TSP问题中常被采用.(4) 插入变异，从串中随机选择1个码，将此码插入随机选择的插入点之后。

本文采用对换变异操作，代码如下： void CTestDlg2::bianyi(int bianyi[10]) { int trasfs;

for(kk=1;kk<=2;kk++) {

ii=rand(); jj=rand();

while(ii==jj){ jj=rand();} trasfs=bianyi[jj]; int ii=0; int jj=0; int kk=0;

bianyi[jj]=bianyi[ii]; }

bianyi[ii]=trasfs;

此外，对于变异操作还有一些变体形式，如Sushil Jouis提出的贪心对换变异、谢胜利[15]等提出倒位变异算子。

3.2 不同参数下的计算结果对比

3.2.1 初始种群10和100的对比

理论上，在遗传算法中初始种群的个数决定了种群个体的多样性。初始种群过少会导致程序陷入局部最优，而无法得到近似最优解。增加种群个数可以避免进入局部

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库遗传算法解决TSP问题 C++、MFC界面编程 - 图文(5)在线全文阅读。