資源描述：
《遺傳算法在求解tsp問題—免費(fèi)畢業(yè)設(shè)計(jì)論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、畢業(yè)設(shè)計(jì)(論文)學(xué)院信息工程學(xué)院專業(yè)計(jì)算機(jī)科學(xué)技術(shù)與應(yīng)用班級(jí)姓名年月日目錄摘要IAbstractII引言1第一章基本遺傳算法21.1遺傳算法的產(chǎn)生及發(fā)展31.2基本原理31.3遺傳算法的特點(diǎn)31.4基本遺傳算法描述51.5遺傳算法構(gòu)造流程6第二章遺傳算法的實(shí)現(xiàn)技術(shù)62.1編碼方法72.1.1二進(jìn)制編碼72.1.2格雷碼編碼72.1.3符點(diǎn)數(shù)編碼82.1.4參數(shù)編碼82.2適應(yīng)度函數(shù)102.3選擇算子102.4交叉算子102.4.1單點(diǎn)交叉算子102.4.2雙點(diǎn)交叉算子112.4.3均勻交叉算子112.4.4部分映射交叉112.4.5順序交叉122.5變異
2、算子122.6運(yùn)行參數(shù)122.7約束條件的處理方法132.8遺傳算法流程圖14第三章遺傳算法在TSP上的應(yīng)用153.1 TSP問題的建模與描述153.2對(duì)TSP的遺傳基因編碼方法163.3針對(duì)TSP的遺傳操作算子173.3.1選擇算子173.3.1.1 輪盤賭選擇173.3.1.2 最優(yōu)保存策略選擇173.3.2交叉算子203.3.2.1單點(diǎn)交叉203.3.2.2部分映射交叉213.3.3變異算子233.4TSP的混和遺傳算法26第四章實(shí)例分析274.1測(cè)試數(shù)據(jù)274.2測(cè)試結(jié)果274.3結(jié)果分析27摘要TSP(TravelingSalesmanProb
3、lem)旅行商問題是一類典型的NP完全問題，遺傳算法是解決NP問題的一種較理想的方法。文章首先介紹了基本遺傳算法的基本原理、特點(diǎn)及其基本實(shí)現(xiàn)技術(shù)；接著針對(duì)TSP問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應(yīng)用情況，分別指出幾種常用的編碼方法的優(yōu)點(diǎn)和缺點(diǎn)，并且結(jié)合TSP的運(yùn)行實(shí)例詳細(xì)分析了基本遺傳算法的4個(gè)運(yùn)行參數(shù)群體大小、遺傳算法的終止進(jìn)化代數(shù)、交叉概率、變異概率，對(duì)遺傳算法的求解結(jié)果和求解效率的影響，經(jīng)過多次的測(cè)試設(shè)定出了它們一組比較合理的取值。最后，簡(jiǎn)單說明了混合遺傳算法在求解TSP問題中的應(yīng)用并對(duì)遺傳
4、算法解決TSP問題的前景提出了展望。關(guān)鍵詞：TSP遺傳算法遺傳算子編碼AbstractTSP(TravelingSalesmanProblem)isatypicalNP-completeproblemandgeneticalgorithm(GA)istheperfectmethodforsolvingNP-completeproblem.Thebasictheories,characteristicsandthebasictechniquesofGAarefirstintroduced.Thentheencodingmodelandgeneticoper
5、ators(includingselectionoperation,crossoveroperationandmutationoperation)aboutGAinsolvingTSParediscussed.Theadvantagesanddisadvantagesofvariousencodingmethodarerespectivelyindicated,andtheapplicationofthethreebasicgeneticoperatorsiselaborated.Accordingtothegivendata,theresultsand
6、efficienciesareinfluencedbyfourparametersinthebasicgeneticalgorithm:thesizeofpopulation,terminategeneration,crosserprobabilityandmutationprobability.Adjusttheparameters,runandtryforbetterones.Atlast,theapplicationofhybridgeneticalgorithmisbrieflypresented.Itispointedoutthatabette
7、rcrossoverormutationroutinecanbefoundoutwhichretainsthestructurefromtheparentchromosomesandstillendsupwithalegaltourinthechildchromosomes,whichleadstoabettersolutionthaneverbefore.AndtheprospectforthefutureofgeneticalgorithminsolvingTSPismade.Keywords:TSPgeneticalgorithmgeneticop
8、eratorsencoding引言現(xiàn)代科學(xué)理論研究與實(shí)踐中存在著大量與優(yōu)化、自適
