《遗传算法求解TSP问题报告》由会员分享，可在线阅读，更多相关《遗传算法求解TSP问题报告（7页珍藏版）》请在金锄头文库上搜索。
1、遗传算法求解TSP问题实验报告一、实验要求：以旅行商问题(TSP)为例做模拟进化搜索技术实验，并提交实验研究报告。二、实验思路：bool fnCreateRandomGene();/产生随机基因bool fnGeneAberrance();/基因变异bool fnGeneMix();/基因交叉产生新的个体测试并淘汰适应度低的个体bool fnEvalAll();/测试所有基因的适应度int fnEvalOne(T &Gene);/测试某一个基因的适应度void Crossover( int nFatherA, int nFatherB);void fnDispProbability();/显示
2、每个个体的权值Crossover。两染色体的交叉实现输入参数： 1、nFatherA父染色体A2、nFatherB父染色体B3、nMode交叉方式返回值： 空注：现有交叉方式1、常规交叉方式，该方式比现代计算方法(邢文训等编著)p178给出的“非 常规码的常规交配法”稍复杂些。书中只随机选择一个交配位，两个后代交配 位之前的基因分别继承双亲的交配位之前的基因。本程序中，是随机选择两个 不相同的交配位，后代在这两个交配位之间继承双亲在这两个交配位之间的基 因如父 A 1 2 3 I 4 5 6 7 I 8 9 10父 B 4 7 8 I 3 2 5 9 I 1 6 10子 A 8 3 2 I 4
3、 5 6 7 I 9 1 10 子 B 1 4 6 I 3 2 5 9 I 7 8 102、贪心交叉方式(Greedy Crossover),具体算法可参见谢胜利，等求解TSP问题的一种改进的遗传算法J .计算机工程与应用2002(8):58245.三、实验代码：#include #include#include #include #include#include #include #include def.h#include TSP.hvoid main()ifstream input_file;ofstream output_file;time_t time1,time2;int _GEN
4、ERATION_AMOUNT;int times;int _CITY_AMOUNT=-1;int ii,j,k;std:vector x;std:vector y;char readfile50;const char* writefile=tsp.txt;double tempx10000,tempy10000;coutvv打开城市坐标文件：；cinreadfile;input_file.open(readfile);if(!input_file)coutvv打开错误！；return;coutvv读入城市坐标vvendl;while(1)if(!input_fileeof()_CITY_AMO
5、UNT+;input_filetempx_CITY_AMOUNTtempy_CITY_AMOUNT; if(tempx_CITY_AMOUNTv0|tempy_CITY_AMOUNTv0) coutvv文件格式有误！；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*_
6、CITY_AMOUNT)； for(k=0；kv_CITY_AMOUNT；k+)xk=tempxk；yk=tempyk；coutvv已存入的城市信息为:vvendl; for(ii=0；iiv_CITY_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
7、=lpCityDistancej*_CITY_AMOUNT+k =sqrt(xk-xj)*(xk-xj)+(yk-yj)*(yk-yj);coutvv输入进化代数:vvendl;cintimes;coutvv输入种群大小:(大于城市个数小于10O00)vvendl;cin _GENERATION_AMOUNT;while(_GENERATION_AMOUNT=1OOOO|_GENERATION_AMOUNTv _CITY_AMOUNT)coutvv种群数输入错误!请重新输入(大于城市个数小于10000)vvendl;cin _GENERATION_AMOUNT;Csgav_CONTAINER,
8、_CONTAINER_PCUnit(times,_GENERATION_AMOUNT,_CITY_AMOUNT);/初始化time1=time(NULL);/开始遗传算法 if(!CUnit.fnCreateRandomGene()/ 产 生 随 机 基 因/产生随机的基因exit(0);/循环基因编译,杂交,淘汰过程CUnit.fnEvalAll(); /测试所有基因的适应度for ( int i = 0; itimes; +i )/CUnitinDispProbabilityO;/显示每个个体的权值CUnit.fnGeneAberrance(); / 基 因 变 异 /基因变异/CUnit
9、inDispProbabilityO;/显示每个个体的权值CUnit.fnGeneMix();/交叉产生新的个体测试并淘汰适应度低 的个体 /基因杂交CUnit.fnEvalAll();/测试所有基因的适应度/每隔_DISP_INTERVAL显示一次结果if ( (i+1)%_DISP_INTERVAL = 0 II i = 0) cout 第 i+1 代 endl;CUnit.fnDispProbability();CUnit.fnDispHistoryMin();CUnit.fnDispHistoryMin(); time2=time(NULL);coutnn 计算用时为:vvdiffti
10、me(time2,time1)vvsvvendl;四、实验结果：IX親 斗邨生肆甘“78SmH*滴41蛊甘“269067 爵喩甘 “4 |5 |6 |7 |8 |9 IX |2 |0 |3 |4 獭765床*41蟲甘“3 05236mH*滴41蛊甘“269067 爵喩甘 “4 |5 |6 |7 |8 |9 IX |2 |0 |3 |4M770 才*兮斗型甘“2L7822m_t*滴41蛊甘“269067 爵喩甘 “4 |5 |6 |7 |8 |9 IX |2 |0 |3 |4 -删亠，4|蛊甘“277822 )2 2)6 6 )9 9 )0 0 6 6*I I )V 7 :5 5I IV 7 :6 6 ：I IV V )7 7I IV V )8 8 )I IV V ) 9 9 )I IV V 1 11 IV V2 2
