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

1畢業(yè)設(shè)計(jì)(論文)學(xué)院信息工程學(xué)院專(zhuān)業(yè)計(jì)算機(jī)科學(xué)技術(shù)與應(yīng)用班級(jí)1625姓名徐東2007年4月15日2目錄摘要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變異算子.122.6運(yùn)行參數(shù).122.7約束條件的處理方法.132.8遺傳算法流程圖.14第三章遺傳算法在TSP上的應(yīng)用153.1TSP問(wèn)題的建模與描述.153.2對(duì)TSP的遺傳基因編碼方法.163.3針對(duì)TSP的遺傳操作算子.173.3.1選擇算子.173.3.1.1輪盤(pán)賭選擇.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ù).2734.2測(cè)試結(jié)果.274.3結(jié)果分析.27摘要TSP(TravelingSalesmanProblem)旅行商問(wèn)題是一類(lèi)典型的NP完全問(wèn)題，遺傳算法是解決NP問(wèn)題的一種較理想的方法。文章首先介紹了基本遺傳算法的基本原理、特點(diǎn)及其基本實(shí)現(xiàn)技術(shù)；接著針對(duì)TSP問(wèn)題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應(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)過(guò)多次的測(cè)試設(shè)定出了它們一組比較合理的取值。最后，簡(jiǎn)單說(shuō)明了混合遺傳算法在求解TSP問(wèn)題中的應(yīng)用并對(duì)遺傳算法解決TSP問(wèn)題的前景提出了展望。關(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