遗传算法求解TSP问题报告

1、遗传算法求解TSP问题实验报告一、实验要求：以旅行商问题(TSP)为例做模拟进化搜索技术实验，并提交实验研究报告。二、实验思路：boolfnCreateRandomGene();/产生随机基因boolfnGeneAberrance();/基因变异boolfnGeneMix();/基因交叉产生新的个体测试并淘汰适应度低的个体boolfnEvalAll();/测试所有基因的适应度intfnEvalOne(T&Gene);/测试某一个基因的适应度voidCrossover(intnFatherA,intnFatherB);voidfnDispProbability();/显示每个个体的权值Cross

2、over。两染色体的交叉实现输入参数：1、nFatherA父染色体A2、nFatherB父染色体B3、nMode交叉方式返回值：空注：现有交叉方式1、常规交叉方式，该方式比现代计算方法(邢文训等编著)p178给出的“非常规码的常规交配法”稍复杂些。书中只随机选择一个交配位，两个后代交配位之前的基因分别继承双亲的交配位之前的基因。本程序中，是随机选择两个不相同的交配位，后代在这两个交配位之间继承双亲在这两个交配位之间的基因如父A123I4567I8910父B478I3259I1610子A832I4567I9110子B146I3259I78102、贪心交叉方式(GreedyCrossover),具

3、体算法可参见谢胜利，等求解TSP问题的一种改进的遗传算法J.计算机工程与应用2002(8):58245.三、实验代码：#include#include#include#include#include#include#include#includedef.h#includeTSP.hvoidmain()ifstreaminput_file;ofstreamoutput_file;time_ttime1,time2;int_GENERATION_AMOUNT;inttimes;int_CITY_AMOUNT=-1;intii,j,k;std:vectorx;std:vectory;charread

4、file50;constchar*writefile=tsp.txt;doubletempx10000,tempy10000;coutvv打开城市坐标文件：；cinreadfile;input_file.open(readfile);if(!input_file)coutvv打开错误！；return;coutvv读入城市坐标vvendl;while(1)if(!input_fileeof()_CITY_AMOUNT+;input_filetempx_CITY_AMOUNTtempy_CITY_AMOUNT;if(tempx_CITY_AMOUNTv0|tempy_CITY_AMOUNTv0)c

5、outvv文件格式有误！；return;elsebreak;if(_CITY_AMOUNT=-1)coutvv文件格式有误！；return;input_file.close()；_CITY_AMOUNT=_CITY_AMOUNT+1；x.reserve(_CITY_AMOUNT)；y.reserve(_CITY_AMOUNT)；lpCityDistance.reserve(_CITY_AMOUNT*_CITY_AMOUNT)；for(k=0；kv_CITY_AMOUNT；k+)xk=tempxk；yk=tempyk；coutvv已存入的城市信息为:vvendl;for(ii=0；iiv_CIT

6、Y_AMOUNT；ii+)coutvv第vvii+1vv个城市vv(vvxiivv,vvyiivv)vvendl;lpCityDistance.clear();for(k=0;kv_CITY_AMOUNT;k+)lpCityDistancek*_CITY_AMOUNT+k=0;for(j=k+1;jv_CITY_AMOUNT;j+)lpCityDistancek*_CITY_AMOUNT+j=lpCityDistancej*_CITY_AMOUNT+k=sqrt(xk-xj)*(xk-xj)+(yk-yj)*(yk-yj);coutvv输入进化代数:vvendl;cintimes;coutvv

7、输入种群大小:(大于城市个数小于10O00)vvendl;cin_GENERATION_AMOUNT;while(_GENERATION_AMOUNT=1OOOO|_GENERATION_AMOUNTv_CITY_AMOUNT)coutvv种群数输入错误!请重新输入(大于城市个数小于10000)vvendl;cin_GENERATION_AMOUNT;Csgav_CONTAINER,_CONTAINER_PCUnit(times,_GENERATION_AMOUNT,_CITY_AMOUNT);/初始化time1=time(NULL);/开始遗传算法if(!CUnit.fnCreateRand

8、omGene()/产生随机基因/产生随机的基因exit(0);/循环基因编译,杂交,淘汰过程CUnit.fnEvalAll();/测试所有基因的适应度for(inti=0;itimes;+i)/CUnitinDispProbabilityO;/显示每个个体的权值CUnit.fnGeneAberrance();/基因变异/基因变异/CUnitinDispProbabilityO;/显示每个个体的权值CUnit.fnGeneMix();/交叉产生新的个体测试并淘汰适应度低的个体/基因杂交CUnit.fnEvalAll();/测试所有基因的适应度/每隔_DISP_INTERVAL显示一次结果if(i

9、+1)%_DISP_INTERVAL=0IIi=0)cout第i+1代endl;CUnit.fnDispProbability();CUnit.fnDispHistoryMin();CUnit.fnDispHistoryMin();time2=time(NULL);coutnn计算用时为:vvdifftime(time2,time1)vvsvvendl;四、实验结果：IX親斗邨生肆甘“78SmH*滴41蛊甘“269067爵喩甘“4|5|6|7|8|9IX|2|0|3|4獭765床*41蟲甘“305236mH*滴41蛊甘“269067爵喩甘“4|5|6|7|8|9IX|2|0|3|4M770才*兮斗型甘