資源描述:
《遺傳算法在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