遗传算法及其在TSP问题中的应用研究

《遗传算法及其在TSP问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、贵州大学硕士学位论文遗传算法及其在TSP问题中的应用研究姓名：李薇申请学位级别：硕士专业：计算机应用技术指导教师：王力20080401贵州大学2008届硕士毕业论文摘要遗传算法(GeneticAlgorithms，简称GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。TSP问题(TravelingSalesmanProblem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出

2、发城市。要安排其访问次序，使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一，也是一个测试算法优劣性的标准问题，且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时，很不容易得到最优解。近年来，研究者们陆续采用了一些新的算法，如遗传算法、模拟退火、神经网络和蚂蚁算法等，取得了较好的效果。本文的主要工作和创新点：l、在设计交叉算子和变异算子的过程中，利用了最短路径的数学性质和统计学规律，设计出改进的启发式顺序交叉算子和启发式变异算子，并与既有的OX、CX、ERC等算子进行了比较和分析。对基因规模、变

3、异概率和交叉概率随着代数的增加而变化的动态性质进行了实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行了分析。2、在程序实现时，大量利用了STL和Boost的既有数据结构和算法，并利用了设计模式的知识，使程序的实现更加灵活高效。3、将改进的遗传算法应用于机械加工的孔群加工顺序模拟中，取得了良好的效果。关键词：遗传算法；TSP问题；启发式OX：孔群加工；路径优化3贵州大学2008届硕：t：毕业论文AppliedResearchofGeneticAlgorithmanditsUsinginTravelingSalesmanProblemJISummarYGeneticAlgorithm(

4、GA)isallalgorithmwhichishighlyparallel，stochasticandauto—adaptedsearching．Itisprofitsfromonekindwhichthebiologicalchoiceandtheevolutionmechanism．Especially,itqualifiesinthequestionsthatcomplexandnon-linearfortraditionsearchingalgorithm．Itstwomostmajoroutstandingfeaturesareconcealparallelismandtheglo

5、balsearch．Tothegeneticalgorithmandtheapplicationresearchofitisonehotspotoftheintelligentcomputationstratosphere．TheTSPquestionisoneofmostclassicalNP—hardcombinationoptimizationquestions，anditisalsoastandardquestiontotestalgorithmperformance．Inthereality,therealemanyapplicationquestionscanbesummedupo

6、rconvertedintoTSEThereforesolvethisproblemissignificancewithboththetheoryandpractical．Tolarge-scaleproblems，thetraditionalsolutionmethodistooinadequate．Inrecentyears，theresearchershaveusedsomenewalgorithms，suchasGA，SA，andAS．111eyachievedgoodresultsbythesealgorithms．Themainworkandinnovations：1．Usedth

7、emostshort-path'smathematicsnatureandstatisticsruletodesigningcrossoveroperatorandmutationoperator,andobtainedheuristicordercrossoveroperatorandheuristicmutationoperator,andcomparedtheseoperatorswithO