遗传算法求解tsp问题报告

《遗传算法求解tsp问题报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、;//显示每个个体的权值Crossover()——两染色体的交叉实现输入参数：1、nFatherA父染色体A2、nFatherB父染色体B3、nMode交叉方式返回值：空注：现有交叉方式1、常规交叉方式，该方式比《现代计算方法》（邢文训等编著）p178给出的“非常规码的常规交配法”稍复杂些。书中只随机选择一个交配位，两个后代交配位之前的基因分别继承双亲的交配位之前的基因。本程序中，是随机选择两个不相同的交配位，后代在这两个交配位之间继承双亲在这两个交配位之间的基因如父A123

3、4567

4、8910父B478

5、3259

6、1610子A832

7、4567

8、9110子B146

9、325

10、9

11、78102、贪心交叉方式（GreedyCrossover），具体算法可参见谢胜利,等.求解ＴＳＰ问题的一种改进的遗传算法[Ｊ].计算机工程与应用,2002(8):58～245.三、实验代码：#include#include#include#include#include#include#include#include"def.h"#include"TSP.h"voidmain(){ifstreaminput_file;ofstreamoutp

12、ut_file;time_ttime1,time2;int_GENERATION_AMOUNT;inttimes;int_CITY_AMOUNT=-1;intii,j,k;std::vectorx;std::vectory;charreadfile[50];constchar*writefile="tsp.txt";doubletempx[10000],tempy[10000];cout<<"打开城市坐标文件：";cin>>readfile;input_file.open(readfile);if(!input_file){cout<<"打

13、开错误！";return;}cout<<"读入城市坐标........"<>tempx[_CITY_AMOUNT]>>tempy[_CITY_AMOUNT];if(tempx[_CITY_AMOUNT]<0

14、

15、tempy[_CITY_AMOUNT]<0){cout<<"文件格式有误！";return;}}elsebreak;}if(_CITY_AMOUNT==-1){cout<<"文件格式有误！";return;}input_file.close(

16、);_CITY_AMOUNT=_CITY_AMOUNT+1;x.reserve(_CITY_AMOUNT);y.reserve(_CITY_AMOUNT);lpCityDistance.reserve(_CITY_AMOUNT*_CITY_AMOUNT);for(k=0;k<_CITY_AMOUNT;k++){x[k]=tempx[k];y[k]=tempy[k];}cout<<"已存入的城市信息为:"<

17、)"<