遗传算法的TSP-(旅行商问题)的求解

智能优化计算及应用课考核论文第1页遗传算法的TSP(旅行商问题)的求解学生姓名：宗满意指导老师：乔立红摘要TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异算子进行了算法设计，最后在MATLAB软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点[1]。关键词：遗传算法；TSP问题；MATLAB软件智能优化计算及应用课考核论文第2页SOLVINGTSP(TravellingSalesmanProblem)BASEDONGENETICALGORITHMAuthor:ZongMan-yiTutor:QiaoLi-hongAbstractTSP(TravelingSalesmanProblem)isatypicalNPcompleteproblem,geneticalgorithmistheperfectmethodforsolvingNPcompleteproblem.ThispaperusegeneticalgorithmintheMATLABsoftwaretosolvetheatypicalTSPproblem.ItprobesintotherealizationofgeneticoperatorprogramthroughTSPsolvingbygeneticalgorithm,designtheeachfunctionofeachgeneticoperator(select,intercross,mutate).Finally,WeprogramminMatlablanguageanddiscussthecharacteristicofgeneticalgorithminsolvingTSPKeywords:geneticalgorithm;TSPMatlab;智能优化计算及应用课考核论文第3页目录引言....................................................................41GA概述..........................................................42旅行商问题(TSP)..................................................43用遗传算法解决旅行商问题.........................................54论文的主要构成....................................................5遗传算法的设计..........................................................61问题分析...........................................................62总体设计..........................................................73详细设计..........................................................83.1编码与随机和初始群体生成..............................................................................................................................83.2城市位置及距离矩阵和适应度函数..................................................................................................................83.4选择...................................................................................................................................................................93.4交叉...................................................................................................................................................................93.5变异.................................................................................................................................................................103.6群体的跟新和终止条件...................................................................................................................................10MATLAB编程验证........................................................111MATLAB计算........................................................112算法分析优化......................................................13结论...................................................................15参考文献...............................................................16智能优化计算及应用课考核论文第4页引言1GA概述遗传算法(GeneticAlgorithm,GA)是由美国J.Holland教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点,使其成为21世纪智能计算核心技术之一。进入80年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的话题[2]。2旅行商问题(TSP)一个有名的组合优化问题就是旅行商问题(TravellingSalesmanProblem,TSP)。TSP问题是典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法,故而利用遗传算法求解这类问题是有效的。假设平面上有n个点代表n个城市的位置,寻找一条最短的闭合路径,使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形,或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n-1)!个,因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说,城市间距可以满足三角不等式,也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。是一个典型的优化组合问题[3]。智能优化计算及应用课考核论文第5页3用遗传算法解决旅行商问题目前针对TSP问题有许多种解法，较为常用的算法有神经网络法、列表寻优法、二叉树描述法、模拟退火法和遗传算法等等。遗传算法是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过选择、遗传、变异和免疫等作用机制，使每个个体的适应性提高。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。提出的TSP问题包括31个城市的编号和各自的位置。本文针对这个TSP问题进行了遗传算法的编程和求解。4论文的主要构成本论文在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异、免疫等算子进行了算法设计，最后在MATLAB软件上进行编程实现。智能优化计算及应用课考核论文第6页遗传算法的设计1问题分析TSP问题的描述十分简单,简言之,就是寻找一条最短的遍历n个城市的最短路径,或者说搜索自然数子集X={1,2,⋯,n}(X的元素表示对n个城市的编号)的一个排列π(X)={V1,V2,⋯,Vn},使len=∑d(Vi,Vi+1)+d(V1,Vn)取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.（图1）[3]本实例中设定了我国31个省会城市，当一个旅行商彼遍历了所有城市后回到出发城市，求其最短路径的走法。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的，31个城市所有路径个数是30！个。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。本文针对这个TSP问题进行了遗传算法的编程和求解。智能优化计算及应用课考核论文第7页2总体设计标准的遗传算法包括群体的初始化，选择，交叉，变异操作。其主要步骤可描述如下[1]：（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。（2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。（3）根据适配值大小以一定方式执行选择操作。（4）按交叉概率Pc执行交叉操作.（5）按变异概率Pm执行变异操作。（6）返回步骤（2）。本TSP问题的遗传算法总体设计选择交叉变异N2N2跟新群体N最优解加入下次迭代1随机路径产生随机路径使群体数目不变N-N2-1产生初始群体N随机产生初始群，计算各个个体的适配值依适配值大小选择变异交叉算法是否达到收敛NPc=rand?Pm=rand?YY输出YNN（图2）标准遗传算法的流程图智能优化计算及应用课考核论文第8页（图3）总体设计说明：（1）本算法的判断结束准则是固定指定了迭代的次数当算法达到迭代次数时，算法结束，输出当前的最优解（2）在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中TSP解越来越好（不会变差）。（3）在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。3详细设计3.1编码与随机和初始群体生成给所有城市编码，以城市的遍历次序作为遗传算法的编码。在MATLAB中使用randperm(N)产生一个1×N的矩阵（N为所有城市的个数，本例中为31）为一个随机路径。利用n×N矩阵存储n个随机群体产生初始群体。3.2城市位置及距离矩阵和适应度函数城市的位置为编译前指定，也可以使用随机生成的坐标参数。距离矩阵使用一个N×N矩阵D存储，D（i，j）代表城市i和城市j之间的距离。D（i，j）=sqrt(（Xi-Xj）.^2+(Yi-Yj).^2)在该问题的求解中，