1、遗传算法求解 TSP 问题实验报告一、实验要求：以旅行商问题（TSP ）为例做模拟进化搜索技术实验，并提交实验研究报告。二、实验思路：bool fnCreateRandomGene(); /产生随机基因bool fnGeneAberrance(); /基因变异bool fnGeneMix(); /基因交叉产生新的个体测试并淘汰适应度低的个体bool fnEvalAll(); /测试所有基因的适应度int fnEvalOne(T /测试某一个基因的适应度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 8
3、 3 2 | 4 5 6 7 | 9 1 10子 B 1 4 6 | 3 2 5 9 | 7 8 102、贪心交叉方式（Greedy Crossover） ，具体算法可参见 谢胜利,等.求解问题的一种改进的遗传算法.计算机工程与应用,2002(8):58245.三、实验代码：#include #include#include #include #include#include #include #include “def.h“#include “TSP.h“void main()ifstream input_file;ofstream output_file;time_t time1,time
4、2;int _GENERATION_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;coutreadfile;input_file.open(readfile);if(!input_file)couttempx_CITY_AMOUNTtempy_CITY_AMOUNT;if(tempx_CITY_AMOUNTtimes;cout _GENERA
5、TION_AMOUNT;while(_GENERATION_AMOUNT=10000|_GENERATION_AMOUNT _GENERATION_AMOUNT;Csga CUnit(times,_GENERATION_AMOUNT,_CITY_AMOUNT); /初始化time1=time(NULL);/开始遗传算法if(!CUnit.fnCreateRandomGene() /产生随机基因 /产生随机的基因 exit(0);/循环基因编译,杂交,淘汰过程CUnit.fnEvalAll(); /测试所有基因的适应度for ( int i = 0; itimes; +i )/CUnit.fnD
6、ispProbability();/显示每个个体的权值CUnit.fnGeneAberrance(); /基因变异 /基因变异/CUnit.fnDispProbability();/显示每个个体的权值CUnit.fnGeneMix();/交叉产生新的个体测试并淘汰适应度低的个体 /基因杂交CUnit.fnEvalAll(); /测试所有基因的适应度 / 每隔_DISP_INTERVAL 显示一次结果if ( (i+1)%_DISP_INTERVAL = 0 | i = 0)cout “第“ i+1 “ 代“ endl;CUnit.fnDispProbability();CUnit.fnDispHistoryMin();CUnit.fnDispHistoryMin();time2=time(NULL);cout“nn 计算用时为:“difftime(time2,time1)“s“endl;四、实验结果：
