《遗传算法求解TSP问题报告.doc》由会员分享，可在线阅读，更多相关《遗传算法求解TSP问题报告.doc（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 | 4 5 6 7 | 8 9 10父 B 4 7 8 | 3 2 5 9 | 1 6 10子 A
3、8 3 2 | 4 5 6 7 | 9 1 10子 B 1 4 6 | 3 2 5 9 | 7 8 102、贪心交叉方式( Greedy Crossover)，具体算法可参见谢胜利，等求解TSP问题的一种改进的遗传算法J .计算机工程与应用，2002(8):58245.三、 实验代码： #include <fstream> #include<iostream> #include <vector> #include <algorithm>#include<math.h>#include <time.h>#include &l
4、t;stdlib.h>#include "def.h"#include "TSP.h"void main()ifstream input_file;ofstream output_file;time_t time1,time2;int _GENERATION_AMOUNT;int times;int _CITY_AMOUNT=-1;int ii,j,k;std:vector<double> x;std:vector<double> y;char readfile50;const char* writefile="t
5、sp.txt"double tempx10000,tempy10000;coutvv"打开城市坐标文件："cin>>readfile;input_file.open(readfile);if(!input_file)coutvv"打开错误！"；return;coutvv"读入城市坐标"vvendl;while(1)if(!input_file.eof()_CITY_AMOUNT+;input_file>>tempx_CITY_AMOUNT>>tempy_CITY_AMOUNT; if(te
6、mpx_CITY_AMOUNTv0|tempy_CITY_AMOUNTv0)coutvv"文件格式有误！"；return;elsebreak;if( _CITY_AMOUNT=-1)cout<<" 文件格式有误！ "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;k<
7、;_CITY_AMOUNT;k+)xk=tempxk;yk=tempyk;coutvv"已存入的城市信息为："vvendl; for(ii=0;ii<_CITY_AMOUNT;ii+)coutvv"第"vvii+lvv"个城市"vv"("vvxiivv","vvyiivv")"vvendl;lpCityDistance.clear(); for(k=0;kv_CITY_AMOUNT;k+) lpCityDistancek*_CITY_AMOUNT+k=0; for(j=
8、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;cin>>times;coutvv"输入种群大小:(大于城市个数小于10000)"vvendl;cin>> _GENERATION_AMOUNT; while(_GENERATION_AMOUNT>=10000|_GENERATION_AMOU
9、NTv _CITY_AMOUNT)coutvv"种群数输入错误！请重新输入(大于城市个数小于10000)"vvendl;cin>> _GENERATION_AMOUNT;Csgav_CONTAINER,_CONTAINER_P>CUnit(times,_GENERATION_AMOUNT,_CITY_AMOUNT);/初始化time1=time(NULL);/开始遗传算法if(！CUnit.fnCreateRandomGene()/ 产 生 随 机 基 因/产生随机的基因 exit(0);/循环基因编译 ,杂交 ,淘汰过程CUnit.fnEvalAll()
10、; /测试所有基因的适应度for ( int i = 0; i<times; +i )/CUnit.fnDispProbability();/ 显示每个个体的权值 CUnit.fnGeneAberrance(); / 基 因 变 异 /基因变异/CUnit.fnDispProbability();/ 显示每个个体的权值 CUnit.fnGeneMix();/ 交叉产生新的个体测试并淘汰适应度低 的个体 /基因杂交CUnit.fnEvalAll(); / 测试所有基因的适应度/ 每隔 _DISP_INTERV AL 显示一次结果if ( (i+1)%_DISP_INTERV AL = 0
11、| i = 0)cout << "第" << i+1 << " 代" <<endl;CUnit.fnDispProbability();CUnit.fnDispHistoryMin(); CUnit.fnDispHistoryMin(); time2=time(NULL);cout<<"nn 计算用时为 :"<<difftime(time2,time1)<<"s"<<endl;四、 实验结果：TrTrTrTrS9X8Z:雕比厶、嘔e®M E 0 z TT 6 8 ' 9 s Ylti$069 竽hkm*<T-ft<feG*6tr烈采送床毛、喘E 0 z TT 6 8 ' 9 s Ylti$069 竽hkm*<T-ft<fe S9X8Z:雕比厶、<E 0 z TT 6 8 ' 9 s Ylti$069 竽hkm*<T-ft<feEl0lzlS9X8Z:雕比厶、嘔PC 6 8 dx 9 s 丫阳里 49069竽雕比戰<9*<母量HdllIlil<驚