2022年遗传算法解决TSP问题 .pdf

遗传算法解决 TSP问题（C+版）遗传算法流程：交叉，编译，计算适应度，保存最优个体。其中交叉过程是选择最优的两个染色体进行交叉操作，本文采用的是轮盘赌算法。#include#include#include usingnamespace std;#define population 200/种群数量#define pc 0.9/交叉的概率#define pm 0.1/变异的概率#define count 200/迭代的次数#define num 10/城市的数量int*city;/存放每个个体的访问顺序int path1010=/0,1,2,3,4,5,6,7,8,9 0,23,93,18,40,34,13,75,50,35,/0 23,0,75,4,72,74,36,57,36,22,/1 93,75,0,64,21,73,51,25,74,89,/2 18,4,64,0,55,52,8,10,67,1,/3 40,72,21,55,0,43,64,6,99,74,/4 34,74,73,52,43,0,43,66,52,39,/5 13,36,51,8,64,43,0,16,57,94,/6 75,57,25,10,6,66,16,0,23,11,/7 50,36,74,67,99,52,57,23,0,42,/8 35,22,89,1,74,39,94,11,42,0/9;int*dis;/存放每个个体的访问顺序下的路径长度double*fitness;/存放灭个个体的适应度intmin_dis=1000000;intmin_index=-1;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -int*min_path;/初始化种群voidinit()int*a=newint num;for(inti=0;i num;i+)ai=i;city=newint*population;for(inti=0;i population;i+)cityi=newint num;for(inti=0;i=0;j-)int n=rand()%(j+1);/产出的数是 0-j,保证交换的后面的数不会再被交换swap(aj,an);/保证 a里面全是 0-(num-1)的数，无重复的数，只是顺序颠倒cityij=aj;delete a;dis=newint population;fitness=newdouble population;min_path=newint num;/计算适应度void compute()/cout do compute now.endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -double total=0;for(inti=0;i population;i+)/计算每种情况下，路径的长度disi=0;int a=cityi0,b;for(int j=1;j num;j+)b=cityij;disi+=pathab;a=b;disi+=pathbcityi0;fitnessi=1.0/disi;/以距离的倒数作为适应度函数值total+=fitnessi;/选择适应度高的物种，采用轮盘赌算法int select()double total=0;for(inti=0;i population;i+)total+=fitnessi;double size=rand()/(double)RAND_MAX *total;/保证不产生0/cout size size endl;double sum=0;inti=0;while(sum=size&ipopulation)sum+=fitness+i;return -i;/返回被选中的个体名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -intgetMinDis()int result=dis0;int index=0;for(inti=1;i disi)result=disi;index=i;return index;intgetMaxDis()int result=dis0;int index=0;for(inti=1;i population;i+)if(result disi)result=disi;index=i;return index;void save()intcurrent_min_index=getMinDis();intcurrent_max_index=getMaxDis();if(discurrent_min_index min_dis)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -min_dis=discurrent_min_index;for(inti=0;i num;i+)min_pathi=citycurrent_min_indexi;/cout current min dis is:min_disendl;else for(inti=0;i num;i+)citycurrent_max_indexi=min_pathi;discurrent_max_index=min_dis;fitnesscurrent_max_index=1.0/min_dis;/最优保存算法boolisExist(intvalue,int*array,intlen)for(inti=0;i len;i+)if(value =array i)returntrue;returnfalse;void convert(intp1,intp2,int*src,int*dst)intlen=p2-p1+1;int*temp=newint len;for(inti=p1;i=p2;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -tempi-p1=srci;int j=(p2+1)%num;for(inti=1;i=num;i+)int index=(i+p2)%num;if(!isExist(dstindex,temp,len)dstj=dstindex;j=(j+1)%num;for(inti=p1;i=p2;i+)dsti=srci;delete temp;/交叉，采用次序交叉算法void cross()/cout do cross now.endl;for(int k=0;k population;k+=2)int a=select();int b=select();while (a=b)b=select();/保证被选中的个体不是一样的/cout same b endl;/cout choose popuilation a b endl;double p=rand()/double(RAND_MAX);/cout cross rate is p endl;int*a1=newint num;int*a2=newint num;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -int*b1=newint num;int*b2=newint num;for(inti=0;i num;i+)a1i=cityai;a2i=citybi;b1i=a2i;b2i=a1i;if(ppc)/满足交叉条件/选择交叉的两点，并保证p1p2)swap(p1,p2);/cout choose pos p1 p2 endl;/开始交叉convert(p1,p2,a1,b1);convert(p1,p2,a2,b2);for(inti=0;i num;i+)cityki=b1i;cityk+1i=b2i;else for(inti=0;i num;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -cityki=a1i;cityk+1i=a2i;delete a1;delete a2;delete b1;delete b2;/变异,采用对换操作进行变异voidmorphis()/cout do morphis now.endl;for(inti=0;i population;i+)double p=rand()/double(RAND_MAX);/cout morphis rate is p endl;if(ppm)/执行变异 int a=-1,b=-1;while (a=b)a=rand()%num;b=rand()%num;swap(cityia,cityib);intgetdis()/compute();int result=dis0;int index=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -for(inti=1;i disi)result=disi;index=i;return result;/释放申请的数组的空间void dispose()for(inti=0;i population;i+)delete cityi;delete city;delete dis;delete fitness;int main()init();/初始化种群inti=0;srand(time(0);compute();while(icount)cross();/交叉morphis();/变异compute();/计算适应度save();/保存当前最优的个体/cout count i+endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -coutgetdis();/输出结果/coutmin_index ;if(+i%10=0)coutendl;compute();cout min distance is:min_disendl;for(inti=0;i num;i+)coutmin_pathi ;coutendl;dispose();/释放空间return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -