基于遗传算法的TSP求解研究

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

1、贵州大学硕士学位论文基于遗传算法的TSP求解研究姓名：李均涛申请学位级别：硕士专业：计算机软件与理论指导教师：李祥19990325致谢Is28367衷心感谢导师李祥教授!从论文的选题、可行性研究、文献的收集、到研究工作的开展，特别是论文的撰写，老师给予了无微不至的关怀，提出了许多建设性的意见。导师的认真、严谨、踏实的科研作风和渊博的学识，使我受益非浅。今后唯有加倍努力，以报答导师的培育之情。最后，感谢所有关心和帮助过我的人们!谢谢!①摘要TSP是组合优化中最为著名的问题，它综合了一大类组合优化问题的典型特征，并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、x一射线结晶学、机器人控

2、制等高科技领域。由NP一完全理论，TSP属于NP难问题，用常规的搜索方法无法有效地求解。但如今正迅速发展的按自然法则计算的思想在求解大规模组合优化问题时表现出非凡的潜力。其中的一个分枝——遗传算法以其独有的魅力吸引了越来越多的研究者。经典遗传算法的主要特点在于它的简单性和鲁棒性，几乎不需要知道所求问题的任何知识；但也正是由于这一点。遗传算法不能利用问题本身的信息，影响了求解具体问题时的效率。同时经典遗传算法也存在过早收敛的缺陷。本文对经典遗传算法进行改进，并结合TSP的特点及其原有算法，提出一种高效的求解TSP的混合遗传算法。求解TSP的经典遗传算法初始化原始种群时=般采甩两种克式：一随机

3、选取和使用局部搜索算法获得原始个体。但两者均不尽如人意。前者所得种群很少包含好的模式，致使随后的遗传操作难以使种群得到进化；而后者将增加大量的时间开销，使算法对大规模的TSP无能为力。改用快速的常规算法初始化种群可成为一种折衷方案。本文采用作者修改的插入法初始化种群，在不降低原始个体适应性的情况下，缩短算法所需时间。经典遗传算法存有过早收敛的弊端，其根本原因是群体失去多样性后的近亲交配。本文采用小群体并行育种和间歇突变的策略，在一定程度上解决了这一问题。根据TSP的特点，本文对遗传操作和选择策略的各个环节作了细致的探讨，采取不定长基因、共点基因段作为遗传操作的单位，在保持群体多样性的情况下

4、，促进种群的进化，并保证算法的收敛。最后，本文在VC++4．0环境下实现了文中改进的算法，并通过一些著名的TSP实例对算法的试验性能进行分析和验证。关键词旅行商问题(TSP)，NP一完全理论，插入法，局部搜索算法，按自然法则计算，遗传算法，遗传操作，选择策略，vc++程序设计。③AbstractTravelingSalesmanProblem(TSP)iSthewell—knowncombinationoptimizingproblem，itcolligatesdxeclassicaltypicalityofatypeofcombinationoptimizingproblem—andex

5、istsinVLSIchipma；mfacture、printingcircuitdesign、X—raycrystallograph)，、robotcontrolandmanyotherhigh—techfields．AccordingtoNP．completedtheory,TSPbelongstoNPH．itcan’tbesolvedbyroutinesearchmethods，anddifferentlypcsofsolutionsnmstbeemployed．Geneticalgorithm(GA)isshowingitspotentialinsolvinglargecombin

6、ationoptimizingproblemmoreandmore．TheclassicalGAissimpleandrobust，ithardlyneedanyknowledgeoftheproblemwillbesolved；buttbisaffectsGA’Ssearchingcapability．Intilesametime，TileclassicalGAhassonmdeficiency．Tiffspaperwillimproveitinsomelneasnl℃．TheclassicalGAofsolvingTSPgenerallyu∞twomethodstoobtaintheo

7、riginalindividual：selectrandomizingorUSeloca[search．metbe山ButneitherofthemiSunsatisfactorylnthispaperWeUSeimprovedinsertmetlmdinitializetilepopulation．itcutsbortthetimeofalgorithm．Thereismaladyofconvergencctooear