欢迎来到天天文库
浏览记录
ID:46223059
大小:277.06 KB
页数:28页
时间:2019-11-21
《遗传算法(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作为我
此文档下载收益归作者所有