遗传算法（GA）毕业论文.docx

遗传算法（GA）毕业论文.docx旅行商问题(TravellingSalesmanProblem,简称TSP)是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。遗传算法(GA)是求解旅行商问题(TSP)的常用方法之一。针对中国旅行商问题(CTSP),本文利用遗传算法的全局搜索能力进行组合优化问题求解,设计一种大比例的优秀个体保护的大变异遗传算法,并使用MATLAB语言进行了实际的编程求解,编程中的各个模块分别实现了选择、交叉、变异等关键环节。用编制的程序快速求解出了满足的结果,用本文设计的遗传算法的思路和编程程序是正确的。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。关键词:遗传算法;CTSP;最短路径;MATLABAbstractThetravelingsalesmanproblem(TSP)isawel1-pleteproblem,,itishardtofindaprecisionresult,(GA),icalgorithm"sglobalsearchingproterty,akindofbigprobabi1ityvariation,icalgorithmisputforward,,,:icAlgorithm(GA);ChineseTravelingSalesmanProblem(CTSP);TheShortestPath;MATLAB目录摘要 IAbstract 11绪论 11CTSP数学模型及常用算法 21 TSP的数学模型 22 TSP问题的常用求解方法 (GA) (SA) (ACO) (TS) (PSO) 43CTSP问题的数学模型,目前最优解 52用遗传算法SGA求解CTSP问题 71遗传算法求解框架 72种群初始化和计算适应度 83遗传算子 83. 1 选择算子 83. 2交叉算子 83. 3变异算子 93. 4 终止判断 9MATLAB简介与特点 111 MATLAB简介 112 MATLAB的特点 11用MATLAB求解CSTP问题 141 种群初始化 142计算适应度 184. 4. 1交叉概率的选择 184. 4. 2交叉算法实现 . 5. 1变异概率的选择 194. 5. 2变异算法实现 196路径输出 205实验结论及分析 231实验结论 232需要进一步解决的问题 24致谢 26主要参考文献 27旅行商问题(TravellingSalesmanProblem,简称TSP)是一个典型的组合优化问题,并且是一个NP难题,遗传算法(GA)、模拟退火算法(SA)等算法是求解这类问题的常用方法。首先,提出了CTSP问题,并建立CTSP问题的数学模型,列举常用的几种求解旅行商问题的解法,给出目前求解出这个问题的最优解。其矢用遗传算法求解CTSP问题。针对中国旅行商问题(CTSP),设计了选择(Selection)交叉(Crossover)变异(Mutation)遗传算法的改进策略。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。再次,选择工具实现用遗传算法求解旅行商问题,在这次设计过程中,我们选择了MATLAB作为我们处理这个问题的工具,因为旅行商问题是一个数学问题,MATLAB是一个专门解决数学问题的数学软件,并且提供了遗传算法工具箱(我们程序中用到的很多代码都来自于遗传算法工具箱