遗传算法毕业论文

1、目录1 引言12 问题描述23 基于遗传算法TSP算法23.1 基于遗传算法的TSP算法总体框架23.2算法的详细设计33.2.1 解空间的表示方式33.2.2 种群初始化4适应度函数4选择操作4交叉操作5变异操作6进化逆转操作63.3 实验结果分析74 基于模拟退火算法的TSP算法104.1 SA算法的实现过程104.2 算法流程图104.3模拟退火算法的实现过程104.4实验结果115 对两种算法的评价145.1遗传算法优缺点145.2 模拟退火算法的优缺点156结语15参考文献17附录：19 廊坊师范学院本科生毕业论文论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途

2、 论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市-珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题. 本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制 利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解. 关键词： 遗传算法；模拟退火算法；TSP；最

3、短路径；Title： TSP Algorithm Based on Genetic Algorithm or Simulated Annealing Algorithm for Solving the Shortest Journey of 10 CitiesAbstract：TSP problem is a classic NP problem about combinatorial optimization This article takes a travel agency looking for the shortest trip of ten tourist cities in Ch

4、inaZhuhai， Xi'an， Hangzhou， Lhasa， Beijing， Lijiang， Kunming， Chengdu， Luoyang and Weihai for instance，and solves this problem by TSP algorithm based on genetic algorithm and simulated annealing algorithm The article gives the implementations of every operator of genetic algorithm and simulated

5、annealing algorithm and demonstrates the architecture and the implementation mechanism of the solving system based on MATLAB I program and operate the results by MATLAB software，and compare the results based on genetic algorithm and simulated annealing algorithmAnd describe their advantages and disa

6、dvantages so that choose the most appropriate TSP algorithm to achieve the optimal solution for the shortest pathKeywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path1 引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距

7、离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承

8、了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解 模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程其中，加温过程对应算法设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降这里能量的变化就是目标函数，要得到的最优解就是能量最低态Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱2

9、 问题描述本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海，根据全程路径最短为目的，制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决，寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标，下表为这十个城市的位置坐标如表2-1所示.表2-1 10个城市的位置坐标城市编号X坐标Y坐标城市编号X坐标Y坐标122.31113.58626.86100.23234.37108.95724.89102.83330.29120.16830.59104.07429.6691.14934.65112.46539.95116.4

10、1103753122.133 基于遗传算法TSP算法3.1 基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离直接相连.遗传算法TSP问题的流程图如图2-1所示.N初始种群实际问题参数集计算适应度编码 选择适应度高的染色体交叉变异新种群进化逆转代数满足终止条件Y解决实际问题解码图2-1算法流程框架图3.2算法的详细设计 解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP

11、问题的解的表示，因为它要求特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）.给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法.它是最自然、最接近人类思维的表示法.因此对十大旅游城市按照珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海顺序依次编号为1，2，3，4，5，6，7，8，9，10，例如，下面的路径（闭合的）：512436798105表示从城市5出发，经过1，2，4，3，6，7，9，8，10最后回到城市5的一条路径，可以自然地用一维数组来表示：（5，1，2，4，3，6，7，9，8，10）10个旅游城市的T

12、SP问题，如果将种群规模设为200，则解空间就用二维数组来表示：Path20010 种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销.10个城市TSP问题，可以选择小规模的种群（例如200），种群初始化时，先产生1，2，10的一条规则路径，然后在这条路径中随机选两个数，将它们交换位置，这样做若干次（本文采用200次），保证这条路径变成了一条随机的路径.以这条随机路径为基础，对一些随机的位，做两两交换，这样产生了一个个体；同样地产生种群里其它的个体.3.2.3适应度函数适应度表明个体或解的优劣性，不同的问题，适应度函数的定义方式也不同，本文设为一个采

13、用整数编码的染色体，为城市到城市的欧氏距离，则该个体的适应度为： （1）即适应度函数为恰好走遍10个城市，在回到出发城市的总距离的倒数.优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质.求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的最优解.3.2.4选择操作选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中，将选择算子作用于群体，从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代；个体被选中的概率与适应度值有关，适应度值越大，被选中的概率也就越大，而适应度值越大

14、的染色体越优质.本案例选择轮盘赌法，即基于适应度比例的选择策略，个体被选中的概率为： （2）其中，为个体的适应度值；N为种群个体数目.3.2.5交叉操作交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性，交叉体现了信息交换的思想利用不同映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程： （1）产生两个1，10区间的随机整数和，确定两个位置，对两个位置的中间数据进行交叉，如， 5 1 2 4 3 6 7 9 8 10 10 6 2 3 5 8 9 4 1 7交叉为： * 1 2 3 5 8 9 * * 10 10 * 2 4 3

15、6 7 * 1 * （2）交叉后，对同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字（带*的位置）采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射.结果为：4 1 2 3 5 8 9 6 7 10 10 5 2 4 3 6 7 8 1 9交叉是希望不同的个体在产生下一代时，能够结合各自的优势基因，产生更好质量的下一代.3.2.6变异操作变异可以看作是外界对种群的影响.变异是为了引入新的因素，希望个体在外界的作用下，能够实现自我优化，生好的基因.将变异算子作用于群体.即是对群体中的个体串的某些基因位置上的基因值作变动.变异算子采用了简单的倒序变换，以10城市为例，随机的产生

16、两个小于10的整数，对某个个体进行分割，假设， ，将分割段倒序并放回原来的位置即可，如下数组所示：5 1 2 4 3 6 7 9 8 10得到的新解为：5 1 2 7 3 6 4 9 8 10由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的.这种简单反序可以保证后代仍然是一条合法途径.进化逆转操作为了改善遗传算法的局部搜索能力，在选择、交叉、变异之后引进连续多次的进化逆转操作，这里的“进化”是指逆转算子的单方向性，即只有经逆转后，适应度值有所提高的才接受下来，否则逆转无效.产生两个1，10区间

17、内的随机整数和，确定两个位置，将其对换位置，例如，5 1 2 4 3 6 7 9 8 10进化逆转后为：5 1 2 7 3 6 4 9 8 10对每个个体进行交叉变异，然后代入适应度函数进行评估，x选择出适应值大的个体进行下一代交叉和变异以及进化逆转操作循环操作：判断是否满足设定的最大遗传代数MAXGEN，不满足则跳入适应度值计算；否则结束遗传操作.3.3 实验结果分析 1-10的十个数字按顺序为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海的编号.利用各城市坐标构成的的矩阵及初始化随机值和DrawPath函数画出闭合路径图，为优化前的随机路线轨迹图，如图3-1所示：图 3-1随机

18、路线轨迹图图中三角标注的数字6代表起点，依次按照箭头方向遍历，最终再次回到起点6初始种群中的一个随机值:6>3>7>8>5>1>2>4>9>10>6总距离：165.2494对照1-10数字编号所代表的的城市，随机路线为:丽江>杭州>昆明>成都>北京>珠海>西安>拉萨>洛阳>威海>丽江优化后的最优路线图如图3-2所示：图3-2 最优路线图最优解:4>6>7>1>3>10>5>9>2>8>4总距离：77.1532即最优路

19、线如下所示：拉萨>丽江>昆明>珠海>杭州>威海>北京>洛阳>西安>成都>拉萨此遗传算法在解决TSP问题过程中的优化迭代过程如下图3-3所示：图3-3 优化过程其中横坐标表示迭代次数，纵坐标为优化过程中路线长度.由该优化过程图可知，优化前后路径长度有了很大的改进，20代以后路径长度基本上已经保持不变了，可以认为是最优解了.总距离由原来的165.2494变为77.1532，降低为原来的46.69%，表明利用遗传算法解决TSP问题可以起到较好的作用4 基于模拟退火算法的TSP算法4.1 SA算法的实现过程4.2 算法流程图NNcount=0

20、k=1解变换得新解s2设置控制参数 初始解 新的，k=k+1 M准则判断是否接受新解count=count+1,T=qTk>L?Y?输出当前解结束Y图4-1模拟退火算法求解流程框图4.3模拟退火算法的实现过程（1）控制参数的设置需要设置的主要控制参数有降温速率、取初始温度足够大，令=，任取初始解，确定每个时的迭代次数，即Metropolis链长L，如图表4-1所示表4-1参数设定降温速率初始温度结束温度链长0.910000.001500（2）初始解对于10个城市的TSP问题，得到的解为一个排序，其中每个数字为对应城市的编号，10个城市的TSP问题1，2，3，4，5，6，7，8，9，10，

21、则|1|2|3|4|5|6|7|8|9|10就为一个合法解，采用随机排列的方法产生一个初始解（3）解变换生成新解通过对当前解进行变换，产生新路径的数组即新解，这里采用的变换是产生随机数的方法来产生将要交换的两个城市，用二邻域变换法产生新的路径，即新的可行解.例如n=10时，产生两个1，10范围内的随机整数和确定两个位置，将其对换位置，如=4， =75 1 2 4 3 6 7 9 8 10得到的新解为：5 1 2 7 3 6 4 9 8 10（4）Metropolis准则若路径长度函数为，则当前解的路径为，新解的路径为，路径差为=-，则Metropolis准则为： （3）若，则接受作为新的当前解

22、，即；否则计算的接受概率，即随机产生的（0，1）区间上均匀分布的随机数rand，若，也接受作为新的当前解，；否则保留当前解（5）降温利用降温速率q进行降温，即T=qT，则T小于结束温度，则停止迭代输出当前解为最优解，结束程序，否则按衰减函数衰减后逐渐降低控制温度，重复Metropolis过程，继续迭代，直至满足结束准则，求出最优解4.4实验结果利用各城市坐标构成的的矩阵及初始化随机值和DrawPath函数分别画出优化前的随机路径轨迹图与优化后的最优闭合路径图，以及优化过程图并利用计时器记录了运行结果所花费的时间为优化前的随机路线轨迹图，如图4-2所示.图4-2 随机路线轨迹图初始种群中的一个随

23、机值:8>1>7>4>3>6>10>2>9>5>8总距离：149.0742优化后的最优路线轨迹图如图4-3所示.图4-3 最优路线轨迹图最优解:9>2>8>4>6>7>1>3>10>5>9总距离：77.1532即最优路线如下所示：洛阳>西安>成都>拉萨>丽江>昆明>珠海>杭州>威海>北京>洛阳本次运行的时间如下所示：Elapsed time is 12.232553 seconds.优化过程如图4-4所示:图4-4

24、优化过程由图4-4可以看出，优化前后的路径长度得到很大的改进，由优化前的149.0742变为77.1532，变为原来的51.75%，50代以后路径长度基本上已经保持不变了，可以认为是最优解了. 5 对两种算法的评价5.1遗传算法优缺点遗传算法优点： （1）对可行解表示的广泛性；（2）群体搜索特性；（3）不需要辅助信息；（4）内在启发式随机搜索特性；（5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪音的情况下，也能以很大的概率找到全局最优解；（6）遗传算法具有固有的并行性和并行计算能力；（7）遗传算法具有可扩展性，易于同别的技术混合遗传算法缺点：（1

25、）编码不规则或编码存在表示的不规则性；（2）单一的遗传算法编码不能全面的将优化问题的约束表示出来；（3）遗传算法通常的效率比比其他传统的优化方法低；（4）遗传算法容易出现过早收敛；（5）遗传算法对算法的精度，可信度，计算复杂性等方面，还没有有效的定量分析方法5.2 模拟退火算法的优缺点模拟退火法优点：（1）它能够处理具有任意程度的非线性、不连续性、随机性的目标函数；（2）目标函数可以具有任意的边界条件和约束；（3）比其他线性优化方法，SA的编程工作量小，且易于实现；（4）统计上可以保证找到全局最优解模拟退火算法缺点：（1）找到最优解需要耗费非常多的时间；（2）相对于其他一些技术对某一个具体问题

26、的求解需要更困难的参数调整；（3）使用不当致使降温过快，导致模拟退火变为了模拟淬火（SQ），而SQ是无法从统计学上保证找到最优解的6结语遗传算法利用自然界的“物竞天择、适者生存”的演化法则，把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体.实践证明， 遗传算法在搜索优秀解的过程中模拟生物遗传，实现优中选优的过程，在解空间中快速收敛到优秀解.遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能.模拟退火算法是利用自适应启发式概率性搜索的算法，可以用以求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大的概率求

27、得全局最优解，并且能处理不同类型的优化设计变量（离散的，连续的，混合型的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求利用Metropolis算法适当地控制温度的下降过程，在优化问题中具有很强的竞争力，但是其优化过程效率略低于遗传算法因此，解空间较小的情况下，遗传算法与模拟退火算法均可采用，但是解空间较大时，考虑结果运行时间，应采用遗传算法参考文献1毕晓君.信息智能处理技术M.北京:电子工业出版社.2010.2储理才.基于MATLAB的遗传算法程序设计及TSP问题求解J.集美大学学报：2001，6（01）：14-193代桂平，王勇，侯亚荣.基于遗传算法的TSP问题求解算法及其系统J

28、.微计算机信息，2010（04）：15-16，194Negnevistsky，M.顾力栩，沈晋惠译.人工智能智能系统指南M.北京:机械工业出版社.2010. 5任春玉.基于混合遗传算法的 问题优化研究J.哈尔滨商业大学学报.2007.6 Michalewicz Z. Genetic Algorithms +Data Structure=Evolution Programs. Springer-Verlag， Berlin. 20117 易敬， 王平， 李哲. 基于遗传算法的 TSP 问题研究J. 信息技术， 2006， 30(7): 110-112.8邓辉文.离散数学M.北京:清华大学出版社.

29、2006.9刘雁兵，刘付显.基于遗传算法的 TSP 问题求解与仿真J.电光与控制.2007.10张春霞，王蕊.基于遗传算法求解 TSP 问题的算法设计J.安阳工学院学报.2007.11郑阿奇.MATLAB 实用教程M.北京:电子工业出版社.2004.12李飞，白艳萍.用遗传算法求解旅行商问题J.中北大学学报.2007.13翟梅梅.基于交叉算子改进的遗传算法求解 TSP 问题J.淮南师范学院学报.2009.14Merz P.A comparison of recombination operators forthe traveling salesman problemA.Proceedings

30、of the Genetic and Evolutionary Conference.200715 周涛. 基于改进遗传算法的 TSP 问题研究J. 微电子学与计算机， 2006， 23(10): 104-107.16Jung S， Moon B R. Toward Minimal Restriction of Genetic Encoding and Crossovers for the Two-Dimensional Euclidean TSP J.IEEE Transactions on Evolutionary Computation， 2011，6 ( 12) :55756517Ts

31、ai Cheng-Fa ， Tsai Chun-Wei ， Yang Tzer . A Modified Multiple-Searching Method to Genetic Algorithms for Solving Traveling Salesman ProblemJ.IEEE Transactions on Systems ，Man and Cybernetics ，2011 ，3 (10) :61218 Write A H. Genetic Algorithms for Real Parameter Optimization. FoundationofGeneticAlgori

32、thms.Sanmateo，GA.2010:205-218附录：遗传算法的TSP方法代码：1 种群初始化函数InitPop的代码：% 初始化种群%输入：% NIND：种群大小% N： 个体染色体长度（这里为城市的个数） %输出：%初始种群function Chrom=InitPop(NIND,N)Chrom=zeros(NIND,N);%用于存储种群for i=1:NIND Chrom(i,:)=randperm(N);%随机生成初始种群end2 种群个体的适应度函数Fitness的代码:% 适配值函数 %输入：%个体的长度（TSP的距离）%输出：%个体的适应度值function FitnV=

33、Fitness(len)FitnV=1./len;3选择操作函数的Select的代码：% 选择操作%输入%Chrom 种群%FitnV 适应度值%GGAP：代沟%输出%SelCh 被选择的个体function SelCh=Select(Chrom,FitnV,GGAP)NIND=size(Chrom,1);NSel=max(floor(NIND*GGAP+.5),2);ChrIx=Sus(FitnV,NSel);SelCh=Chrom(ChrIx,:);其中，函数Sus的代码为：% 输入:%FitnV 个体的适应度值%Nsel 被选择个体的数目% 输出:%NewChrIx 被选择个体的索引号f

34、unction NewChrIx = Sus(FitnV,Nsel)Nind,ans = size(FitnV);cumfit = cumsum(FitnV);trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)');Mf = cumfit(:, ones(1, Nsel);Mt = trials(:, ones(1, Nind)'NewChrIx, ans = find(Mt < Mf & zeros(1, Nsel); Mf(1:Nind-1, :) <= Mt);ans, shuf = sort(rand(

35、Nsel, 1);NewChrIx = NewChrIx(shuf);4 交叉操作函数Recombin的代码:% 交叉操作% 输入%SelCh 被选择的个体%Pc 交叉概率%输出：% SelCh 交叉后的个体function SelCh=Recombin(SelCh,Pc)NSel=size(SelCh,1);for i=1:2:NSel-mod(NSel,2) if Pc>=rand %交叉概率Pc SelCh(i,:),SelCh(i+1,:)=intercross(SelCh(i,:),SelCh(i+1,:); endend%输入：%a和b为两个待交叉的个体%输出：%a和b为交叉

36、后得到的两个个体其中intercross函数代码：function a,b=intercross(a,b)L=length(a);r1=randsrc(1,1,1:L);r2=randsrc(1,1,1:L);if r1=r2 a0=a;b0=b; s=min(r1,r2); e=max(r1,r2); for i=s:e a1=a;b1=b; a(i)=b0(i); b(i)=a0(i); x=find(a=a(i); y=find(b=b(i); i1=x(x=i); i2=y(y=i); if isempty(i1) a(i1)=a1(i); end if isempty(i2) b(i

37、2)=b1(i); end endend5变异操作函数Mutate的代码：% 变异操作%输入：%SelCh 被选择的个体%Pm 变异概率%输出：% SelCh 变异后的个体function SelCh=Mutate(SelCh,Pm)NSel,L=size(SelCh);for i=1:NSel if Pm>=rand R=randperm(L); SelCh(i,R(1:2)=SelCh(i,R(2:-1:1); endend6进化逆转操作函数Reverse代码：% 进化逆转函数%输入%SelCh 被选择的个体%D 个城市的距离矩阵%输出%SelCh 进化逆转后的个体function

38、SelCh=Reverse(SelCh,D)row,col=size(SelCh);ObjV=PathLength(D,SelCh); %计算路径长度SelCh1=SelCh;for i=1:row r1=randsrc(1,1,1:col); r2=randsrc(1,1,1:col); mininverse=min(r1 r2); maxinverse=max(r1 r2); SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:-1:mininverse);endObjV1=PathLength(D,SelCh1); %计算路径长度ind

39、ex=ObjV1<ObjV;SelCh(index,:)=SelCh1(index,:);7画出所给路线的轨迹图函数DrawPath的代码：% 画路径函数%输入% Chrom 待画路径 % X 各城市坐标位置function DrawPath(Chrom,X)R=Chrom(1,:) Chrom(1,1); %一个随机解(个体)figure;hold onplot(X(:,1),X(:,2),'o','color',0.5,0.5,0.5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','Mark

40、erSize',20)for i=1:size(X,1) text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',1,0,0);endA=X(R,:);row=size(A,1);for i=2:row arrowx,arrowy = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2);%坐标转换 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',0,0,1);endhold offxlabel

41、('横坐标')ylabel('纵坐标')title('轨迹图')box on8遗传算法的主函数代码：%遗传算法求解TSP问题(为选择操作从新设计后程序)%输入：%D 距离矩阵%NIND 为种群个数%X 参数是中国10个城市的坐标(初始给定)%MAXGEN 为停止代数，遗传到第MAXGEN代时程序停止,MAXGEN的具体取值视问题的规模和耗费的时间而定%m 为适值淘汰加速指数,最好取为1,2,3,4,不宜太大%Pc 交叉概率%Pm 变异概率%输出：%R 为最短路径%Rlength 为路径长度clearclcclose allX=22.31113.5

42、8 34.37108.95 30.29120.16 29.6691.14 39.95116.41 26.86100.23 24.89102.83 30.59104.07 34.65112.46 37.53122.13;D=Distanse(X); %生成距离矩阵N=size(D,1); %城市个数% 遗传参数NIND=100; %种群大小MAXGEN=200; %最大遗传代数Pc=0.9; %交叉概率Pm=0.05; %变异概率GGAP=0.9; %代沟% 初始化种群Chrom=InitPop(NIND,N);% 画出随机解的路径图DrawPath(Chrom(1,:),X)titlepaus

43、e(0.0001)% 输出随机解的路径和总距离disp('初始种群中的一个随机值:')OutputPath(Chrom(1,:);Rlength=PathLength(D,Chrom(1,:);disp('总距离：',num2str(Rlength);disp('')% 优化gen=0;figure;hold on;box onxlim(0,MAXGEN)title('优化过程')xlabel('代数')ylabel('最优值')ObjV=PathLength(D,Chrom); %计算路径长度pr

44、eObjV=min(ObjV);while gen<MAXGEN % 计算适应度 ObjV=PathLength(D,Chrom); %计算路径长度 % fprintf('%d %1.10fn',gen,min(ObjV) line(gen-1,gen,preObjV,min(ObjV);pause(0.0001) preObjV=min(ObjV); FitnV=Fitness(ObjV); % 选择 SelCh=Select(Chrom,FitnV,GGAP); % 交叉操作 SelCh=Recombin(SelCh,Pc); % 变异 SelCh=Mutate(Se

45、lCh,Pm); % 逆转操作 SelCh=Reverse(SelCh,D); % 重插入子代的新种群 Chrom=Reins(Chrom,SelCh,ObjV); % 更新迭代次数 gen=gen+1 ;end% 画出最优解的路径图ObjV=PathLength(D,Chrom); %计算路径长度minObjV,minInd=min(ObjV);DrawPath(Chrom(minInd(1),:),X)% 输出最优解的路径和总距离disp('最优解:')p=OutputPath(Chrom(minInd(1),:);disp('总距离：',num2str(O

46、bjV(minInd(1);disp('-')其中用到的函数如下：计算距离函数Distence代码：% 计算两两城市之间的距离%输入 a 各城市的位置坐标%输出 D 两两城市之间的距离function D=Distanse(a)row=size(a,1);D=zeros(row,row);for i=1:row for j=i+1:row D(i,j)=(a(i,1)-a(j,1)2+(a(i,2)-a(j,2)2)0.5; D(j,i)=D(i,j); endend输出路线函数OutputPath代码：% 输出路径函数%输入：R 路径function p=OutputPath

47、(R)R=R,R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,'>',num2str(R(i);enddisp(p)计算个体路线长度函数PathLength代码：% 计算各个体的路径长度% 输入：% D 两两城市之间的距离% Chrom 个体的轨迹function len=PathLength(D,Chrom)row,col=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NIND p=Chrom(i,:) Chrom(i,1); i1=p(1:end-1); i2=p(

48、2:end); len(i,1)=sum(D(i1-1)*col+i2);end重插入子代得到新种群的函数Reins代码：% 重插入子代的新种群 %输入： %Chrom 父代的种群 %SelCh 子代种群 %ObjV 父代适应度 %输出 % Chrom 组合父代与子代后得到的新种群function Chrom=Reins(Chrom,SelCh,ObjV)NIND=size(Chrom,1);NSel=size(SelCh,1);TobjV,index=sort(ObjV);Chrom=Chrom(index(1:NIND-NSel),:);SelCh;模拟退火算法的TSP方法代码：生成新解：

49、function S2=NewAnswer(S1)% 输入% S1:当前解% 输出% S2：新解N=length(S1);S2=S1; a=round(rand(1,2)*(N-1)+1); W=S2(a(1);S2(a(1)=S2(a(2);S2(a(2)=W; Metropolis准则函数function S,R=Metropolis(S1,S2,D,T)% 输入% S1： 当前解% S2: 新解% D: 距离矩阵（两两城市的之间的距离）% T: 当前温度% 输出% S： 下一个当前解% R： 下一个当前解的路线距离%R1=PathLength(D,S1); %计算路线长度N=length

50、(S1); %得到城市的个数R2=PathLength(D,S2); %计算路线长度dC=R2-R1; %计算能力之差if dC<0 %如果能力降低 接受新路线 S=S2; R=R2;elseif exp(-dC/T)>=rand %以exp(-dC/T)概率接受新路线 S=S2; R=R2;else %不接受新路线 S=S1; R=R1;Endfunction varargout = dsxy2figxy(varargin)if length(varargin1) = 1 && ishandle(varargin1) . && strcmp(get

51、(varargin1,'type'),'axes') hAx = varargin1; varargin = varargin(2:end);else hAx = gca;end;if length(varargin) = 1 pos = varargin1;else x,y = deal(varargin:);endaxun = get(hAx,'Units');set(hAx,'Units','normalized'); axpos = get(hAx,'Position');axlim = axis(hAx);axwidth = diff(axlim(1:2);axheight = diff(axlim(3:4);if exist('x','var') varargout1