遺傳算法在TSP問(wèn)題上的應(yīng)用

《遺傳算法在TSP問(wèn)題上的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、遺傳算法在TSP問(wèn)題上的應(yīng)用摘要旅行商問(wèn)題(TravellingSalesmanProblem，TSP)是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，也是一個(gè)NP完全題，其在實(shí)際中的應(yīng)用非常廣泛，例如在超大規(guī)模集成芯片制造、印刷電路板制造、機(jī)器人控制等領(lǐng)域。因此，研究者一直在努力尋找一種既有高質(zhì)量的解，又能快速收斂的最佳或近似算法。傳統(tǒng)的求解方法有貪婪算法、局部搜索法、分支定界法、多邊交換調(diào)整法、支撐樹(shù)加倍法等。近年來(lái)，出現(xiàn)了一些仿生類優(yōu)化算法，如遺傳算法、螞蟻算法、模擬退火、神經(jīng)網(wǎng)絡(luò)等。這些算法與一些經(jīng)典組合優(yōu)化算法的有機(jī)結(jié)合在很大程度上改進(jìn)了算法的收斂速度，提高了解的質(zhì)量。本文探索將遺傳算法融合在TSP

2、問(wèn)題的求解中，主要工作如下：(1)概述了旅行商問(wèn)題的研究背景、研究現(xiàn)狀、目的、意義及本文的主要工作，闡述了遺傳算法及其特點(diǎn)、基礎(chǔ)理論以及其研究現(xiàn)狀。(2)概述了旅行商問(wèn)題的定義、數(shù)學(xué)模型及分類，重點(diǎn)討論了幾種經(jīng)典的旅行商問(wèn)題的求解算法。(3)提出一種基于遺傳算法和優(yōu)化策略的求解TSP問(wèn)題的混合算法，算法中設(shè)計(jì)兩種交叉算子并且采用兩算子結(jié)合使用的方法，使子代更好繼承了父代的優(yōu)秀基因，實(shí)驗(yàn)及分析表明了該算法的有效性。關(guān)鍵詞：遺傳算法，旅行商問(wèn)題，交叉算子，變異算子GeneticAlgorithmanditsapplicationinTravellingSalesmanProblemAbstr

3、actTSP(TravellingSalesmanProblem，TSP)isaclassiccombinatorialoptimizationproblems，isalsoaNPcompleteproblem，andhasbeenwidelyusedinpractice．forexample，inmanufacturingultra-large—scaleintegratedchip，producingprintedcircuitboard，controllingrobotsandSOon．Therefore，researcherskeepsearchingabestapproxima

4、tionalgorithmwhichhasnotonlyhigh—qualitysolutionbutafastconvergence．Traditionalmethodsincludegreedyalgorithm，localsearchalgorithm，branchandboundalgorithm，themultilateralexchangeofadjustmentalgorithmandspanningtreedoublingalgorithmetc．Inrecentyears，sometypesofbionicoptimizationalgorithmhasarisen，s

5、uchasgeneticalgorithm，antalgorithm，simulatedannealing，neuralnetworks．Thecombinationofthosenewalgorithmandclassicalcombinatorialoptimizationalgorithmcouldgreatlyimprovebothconvergencerateandresolutionquality．ThisarticleexploreshowtointegrategeneticalgorithmintosolutionofTSP,themajorworkareasfollow

6、s：(1)Theresearchingbackground，situation，purpose，significanceofTSPareintroduced，andcharacteristics、basictheoryandcurrentresearchingstatusofgeneticalgorithmarealsodescribed．(2)Depictthedefinition、digitalmoduleandclassificationofTSPandtakefocusonseveralkindsofclassicalgorithmsforTSE(3)Thisarticlesti

7、llpresentsahybridTSPalgorithmwhichbasedongeneticalgorithmandoptimizationstrategy．Twoconjunctivelyusedcrossoveroperatorsaregiventoinheritexcellentgenesfromparents．Atlast，theexperimentresultsireprovetheefficiencyofthisal