用遗传算法求解tsp问题

《用遗传算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东大学硕士学位论文用遗传算法求解TSP问题姓名：任昊南申请学位级别：硕士专业：计算机技术指导教师：邱洪泽;王良20080405LII东大学硕士学位论文—■■■■——■—■■——■——■——————●——■●●曼●一I1I1一II，l_■■■—■●摘要巡回旅行商问题(TSP)是一个组合优化方面的问题，已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求

2、解TSP问题的优化算法应运而生了，本文所用到的遗传算法也在其中。遗传算法是一种高效智能搜索方法，并行遗传算法是遗传算法研究中的一个重要方向。并行遗传算法能够提供各种大型计算问题的解决方案。Java语言提供了对并发的语言级支持，这个特性是Java的伟大创新之一，同时为并行遗传算法的设计提供了最佳的技术支持。在收集国内外相关资料，阅读了相关文献的基础上，本文系统地阐述了遗传算法的构成原理。介绍了作者借助Java语言实现的一种应用“轮盘赌’’选择操作，顺序交叉操作以及启发式变异操作求解TSP问题的遗传算法。在了解和掌握并行遗传算法

3、的基本概念和工作原理后，针对TSP问题，提出了两种基于并行遗传算法的求解方法。第一章介绍了课题的研究背景、研究的可行性和意义，并行遗传算法的基本理论以及所面对的问题。此外还介绍TTSP问题的研究现状，并对论文内容进行了概括性综述。第二章介绍了遗传算法及并行遗传算法模型第三章介绍了遗传算法求解TSP问题的基本理论，提出了一种求解TSP问题的串行遗传算法模型，结合实例分析了该算法的创新之处。第四章介绍了两种求解TSP问题的并行遗传算法模型，详细地论述了采用这两种并行模型求解TSP问题的过程。分别分析了这两种遗传算法的创新之处，并

4、通过实例对它们之间的性能进行了比较。第五章总结了整个研究工作，并对研究的方向进行了展望。关键词：遗传算法，并行遗传算法，组合优化问题，巡回旅行商问题，“轮盘赌”选择。顺序交叉山东大学硕士学位论文ABSTRACTTSP(TravelingSalosmanProblem)iSaproblemofcombinationoptimizationwithsimpledefinitionbutdi伍culttobesolved,w}1ichattractsmanyresearchersinvariousfieldsincludingma

5、them撕CS，physits，biologyandartificialintelligence(m)．Ithasbecomeandwillcontinuetobecomeastandardproblemtotestanewalgorithmofcombinationoptimization．Theoreticallyspeaking，theenumerationnotonlycallsolveTSP1．’,butalsocallgetthebestanswer．ButtoalcompmersnowadaysitShardy

6、toobtainitsbestanswerinsuchhugeresearchingspacebyusingcommonenumeration．Therefore．allkindsofalgorithmstosolveTSPemergedbecauseofdemand．Amongofthem，GeneticAlgorithm(GA)isoneofadvancedtechnologies．GeneticAlgorithm(GA)arepowerfulsearchtechniques．Parallelgeneticalgorit

7、hm(PGA)isoneofthemainresearchfieldsofgeneticalgorithms．Itcallefficientlysatisfythemultipleneedsoflarge-scalecomputingonanetworkofworkstationclusters．Javalanguageprovidesaparallellevelwiththelanguagesupport,ⅡlischaracteristiciSoneofJava'sgreatinnovation．andforthedes

8、ignofparallelgeneticalgorithmprovidesthebesttechnicalsupport。Inthecollectionofrelevantinfonnationathomeandabroad,readtherelatedliteratureonthebas