基于遗传算法的TSP问题求解

《基于遗传算法的TSP问题求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的TSP问题求解摘要TSP(TravelingSalesmanProblem)问题又称巡回旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了遗传算法的基本原理、特点及其基本实现技术；论述了遗传算法在编码表示和遗传算子(包括选择算子、交叉算子和变异算子)等方面的应用情况，分别指出5种常用的编码方法的优点和缺点；然后针对TSP问题提出基于贪婪算法思想的算子设计(包括交叉算子和变异算子)，并且利用MATLAB工具进行编程实现，文中对每个算法提供完整

2、的MATLAB代码，最后利用本文提供的算法进行50城市的TSP问题求解试验，分析了基本遗传算法的4个运行参数:群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，通过比较两种选择策略(概率选择策略和最佳保存策略)对试验结果的影响来说明选择策略选用的重要性；最后简单说明了混合遗传算法在求解TSP问题中的应用,并对遗传算法解决TSP问题的前景进行了展望。关键词：TSP遗传算法MATLAB贪婪算法I基于遗传算法的TSP问题求解AbstractTSP(Travel

3、ingSalesmanProblem)isatypicalNP-completeproblemandgeneticalgorithm(GA)istheperfectmethodforsolvingNP-completeproblem.Thebasictheories,characteristicsandthebasictechniquesofGAarefirstintroducedinthispaper.Thentheencodingmodelandgeneticoperators(includ

4、ingselectionoperation,crossoveroperationandmutationoperation)aboutGAinsolvingTSParediscussed.Theadvantagesanddisadvantagesofvariousencodingmethodarerespectivelyindicated,andtheapplicationofthethreebasicgeneticoperatorsiselaborated.Thengiventhedesigno

5、foperation(includingcrossoveroperationandmutationoperation)whichbasedongreedyalgorithminsolvingTSP,andcompileredbyMATLABtools,givenallMATLABcodesofeachalgorithm.Finallyaccordingtothegivenalgorithmwhichisusedtosolve50citiesofTSPinthispaper,theresultsa

6、ndefficienciesareinfluencedbyfourparametersinthebasicgeneticalgorithm:thesizeofpopulation,terminategeneration,crosserprobabilityandmutationprobability.Andbycomparingtheimpactoftwoselectionstrategy(ProportionalModelandBestPreservationModel)onthetestre

7、sultstoillustratetheimportanceofselectionstrategy.AndtheprospectforthefutureofgeneticalgorithminsolvingTSPismade.Keywords:TSPgeneticalgorithmMTALABgreedyalgorithmII基于遗传算法的TSP问题求解目录第一章前言.................................................................

8、...................................11.1遗传算法简介....................................................................错误！未定义书签。1.2TSP问题及其研究意义......................................................................................1第二章遗传算法....................