遺傳算法在求解TSP問題畢業(yè)論文.doc

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