遗传算法（GA）毕业论文

《遗传算法（GA）毕业论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、旅行商问题(TravellingSalesmanProblem,简称TSP)是一个典型的组合优化问题，并且是一个NP难题，其可能的路径总数与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有重要的意义。遗传算法(GA)是求解旅行商问题(TSP)的常用方法之一。针对中国旅行商问题(CTSP),本文利用遗传算法的全局搜索能力进行组合优化问题求解，设计一种大比例的优秀个体保护的大变异遗传算法，并使用MATLAB语言进行了实际的编程求解，编程中的各个模块分别实现了选择

2、、交叉、变异等关键环节。用编制的程序快速求解出了满足的结果，用本文设计的遗传算法的思路和编程程序是正确的。用该策略迅速找到了CTSP最优解，该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。关键词：遗传算法；CTSP;最短路径；MATLABAbstractThetravelingsalesmanproblem(TSP)isawel1-knownNPcompleteproblem,It9sincreasedbyexponentialn.So,itish

3、ardtofindaprecisionresult,anditisveryimportanttosearchforthenearresult.Thegeneticalgorithm(GA)isoneoftheidealmethodsinsolvingit.ForCTSP,Accordingtogeneticalgorithm"sglobalsearchingproterty,akindofbigprobabi1ityvariation，sgeneticalgorithmisputforward,whic

4、hcopiesbigproportionoffittest.InMATLAB,thetypicalChinesetravelingsalesmanproblemiscomputedandtheresultshowsthethoughtandprogramiscorrect.ThebestpathforCTSPisfoundquicklythroughthealgorithm.Thebestpath15378kmisget,theresultisthebestsofar.Keywords:TheGenet

5、icAlgorithm(GA);ChineseTravelingSalesmanProblem(CTSP);TheShortestPath;MATLAB目录摘要IAbstract11绪论11CTSP数学模型及常用算法21.1TSP的数学模型21.2TSP问题的常用求解方法21.2.1遗传算法（GA）21.2.2模拟退火算法（SA）31.2.3蚁群算法（ACO）31.2.4禁忌搜索（TS）41.2.5粒子群优化算法（PSO）41.3CTSP问题的数学模型，目前最优解51.3.1CTSP的数学建模51.3.

6、2CTSP目前最优解52用遗传算法SGA求解CTSP问题72.1遗传算法求解框架72.2种群初始化和计算适应度82.2.1种群初始化82.2.2计算适应度82.3遗传算子82.3.1选择算子82.3.2交叉算子82.3.3变异算子92.3.4终止判断93MATLAB简介与特点113.1MATLAB简介113.2MATLAB的特点114用MATLAB求解CSTP问题141.1种群初始化141.2计算适应度144.3选择算子144.3.1计算选择算子的过程144.3.2选择算子计算的代码实现154.4交叉算

7、子184.4.1交叉概率的选择184.4.2交叉算法实现184.5变异算子194.5.1变异概率的选择194.5.2变异算法实现194.6路径输出205实验结论及分析235.1实验结论232.2需要进一步解决的问题24致谢26主要参考文献27旅行商问题(TravellingSalesmanProblem,简称TSP)是一个典型的组合优化问题，并且是一个NP难题，遗传算法(GA)、模拟退火算法(SA)等算法是求解这类问题的常用方法。首先，提出了CTSP问题，并建立CTSP问题的数学模型，列举常用的几种求解

8、旅行商问题的解法，给出目前求解出这个问题的最优解。其矢用遗传算法求解CTSP问题。针对中国旅行商问题(CTSP),设计了选择(Selection)交叉(Crossover)变异(Mutation)遗传算法的改进策略。用该策略迅速找到了CTSP最优解，该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。再次，选择工具实现用遗传算法求解旅行商问题，在这次设计过程中，我们选择了MATLAB作为我