实验报告用遗传算法解决旅行商问题简单实现

《实验报告用遗传算法解决旅行商问题简单实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告：用遗传算法解决旅行商问题的简单实现实验目的：编写程序实现用遗传算法解决旅行商问题，研究遗传算法的工作原理和收敛性质。实验者：问题描述：TSP是一个具有广泛应用背景和重要理论价值的组合优化难题，TSP问题可以简单的描述为：已知N个城市之间的相互距离．现有一个旅行商必须遍历这N个城市，并且每个城市只能访一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使旅行路线的总长度最短？本次实验的目标问题中国大陆31个大城市的公路旅行商问题，数据来源是《中国大城市公路里程表》（后附）。需求分析：TSP已经被证明是一个NP—Ha

2、rd问题，即找不到一种算法能在多项式时间内求得问题的最优解。利用遗传算法，在一定时间内求得近似最优解的可能性比较大。实验目标是：1）设计用遗传算法解决TSP问题的程序；2）求出该TSP问题的（近似）最短路程；3）求得相应的城市遍历序列；4）检查算法收敛性，求解决该问题的（近似）最优遗传参数。算法分析：1．算法基本流程初始群体生成选择交叉变异群体适应度计算结束输出结果YN计算适应度并输出1．编码策略与初始群体设定TSP的一般编码策略主要有二进制表示、次序表示、路径表示、矩阵表示和边表示等。而路径编码是最直观的方式，以城市序号作为遗传基

3、因。在本实验中，我们用一个N维向量来表示一个个体，N是城市总数，元素表示城市遍历顺序，以最后一个到达的城市为结束。则群体用一个N*POP的矩阵表示，POP为群体中的人口（个体数）。初始群体在空间中自动生成。2．适应度函数及结束条件适应度函数采用题目的目标函数——路径的总路程（包括回到出发点）。适应度越低，个体越优秀。由于暂时无法先验估计收敛性和目标结果，所以以一个参数，最大遗传代数MAXGEN作为程序结束控制。3．遗传算子设计遗传算子的设计方法主要有两大类：自然算法和贪心算法。自然算法是以大自然的进化规律为依据，大体采用“优胜劣汰”

4、的机制来进行遗传；贪心算法则是以迅速收敛为目标，对个体进行更严格的选择和遗传处理。本实验中，为了更好地研究遗传算法的内部原理和收敛性质，我们偏向采用自然算法设计算子。以下是各算子的设计：选择算子在遗传个体的选择上，我们先人工保留最优种子，再采用轮盘赌法选择保留一部分个体，用轮盘赌法的理由是在“择优录取”的原则上增加选择的随机性。在轮盘赌过程中，如果按适应度来划分，将导致适应度高的劣质个体被选择的概率更大，于是我们设计了一个变换，用最坏适应度减去该个体的适应度，再进行轮盘赌选择。另外，为了保持群体的“生命力”，我们在选择的同时又引入随

5、机的新个体，与保留的个体进行“杂交”，产生下一代。交叉算子我们采用的是Davis等提出顺序交叉、双亲双子遗传的算法。随机选择两个交叉点A、B（0

6、结果序列和相关参数。文件名galog.txt。程序结构概要#defineCITYSIZE31/*城市规模*/#definePOPSIZE100/*种群大小*/#defineMAXGENS20000/*最大代数*/#definePXOVER0.1/*交叉概率*/#definePMUTATION0.05/*突变概率*/doublecitys[CITYSIZE][CITYSIZE];/*城市数据*/structgenotype/*个体基因组*/intpath[CITYSIZE]doublefitness/*　适应度*/doublerfit

7、ness/*相对适应度*/doublecfitness/*累积适应度*/voidinitialize(void);　　　　　/*　初始化　*/voidrandpath(genotype>);/*　产生随机路径　*/voidevaluate(void);/*　计算适应度　*/voidkeep_the_best(void);/*　保留最优个体　*/voidelitist(void);/*　保留最优个体　*/voidswap(int&,int&);/*　交换　*/voidselect(void);/*　选择　*/voidcrossov

8、er(void);/*　交叉　*/voidXover(int,int);/*　顺序交叉，由crossover()函数调用　*/voidmutate(void);/*　突变　*/voidreport(void);/*　报告，用于输出结果