資源描述：
《探析遺傳算法在tsp上的應(yīng)用及改進(jìn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、分類號：-】墮生LY978327長安大學(xué)碩士學(xué)位論文遺傳算法在TSP上的應(yīng)用及改進(jìn)指導(dǎo)教師姓名．益塞盤堂盔魚二到整蕉申請學(xué)位級別亟±學(xué)科名稱鑾通信息工程丞蕉劍論文提交日期塑!：!論文答辯日期型生!且!目答辯委員會主席：學(xué)位論文評閱人：摘要旅行商問題(TSP)是著名的NP完全難題，也是組合優(yōu)化、計(jì)算機(jī)科學(xué)界經(jīng)典的問題之一。因此對TsP尋找出實(shí)際而又有效的算法，就具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。而遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，具有簡單、通用、穩(wěn)健等特性，能依概率收斂到問題的全局最優(yōu)解。這就是本文提出的改進(jìn)遺傳算法求解TSP的目的
2、和意義。本文從旅行商問題的概述出發(fā)，介紹了TsP的數(shù)學(xué)描述與分類，在原有的基礎(chǔ)上，對TSP作了更細(xì)致的分類；介紹了遺傳算法的基本概念、原理、步驟及意義，將遺傳算法的一些主要的操作過程用數(shù)學(xué)形式表示，使其變得簡單而又公式化；通過依賴于遺傳操作的基本遺傳機(jī)理的敘述，為以后算法的改進(jìn)打下理論基礎(chǔ)。本文主要工作如下：(1)分析了影響遺傳算法性能的一些重要參數(shù)，通過基本遺傳算法(SGA)對不同種群規(guī)模的磚P問題分別進(jìn)行計(jì)算機(jī)模擬仿真，討論了基本遺傳算法在求解TsP中存在的不足。(2)針對現(xiàn)有的遺傳算法的不足和髑P本身的特點(diǎn)，提出了三種改進(jìn)的混合遺傳算法(HGA)。首先提
3、出了混合遺傳算法I(HGAI)，在HGAI中采用了依概率近鄰法，用其生成的初始種群優(yōu)于隨機(jī)產(chǎn)生初始種群，較近鄰法略差，但個體多樣性水平優(yōu)于近鄰法，而且生成的初始種群的隨機(jī)路徑的總長度服從正態(tài)分布。將依概率的近鄰法和邊重組交叉算子與啟發(fā)式變異算子結(jié)合起來得到HGAI。其次為了進(jìn)一步改進(jìn)其性能，保證算法的全局收斂性，混合遺傳算法Ⅱ(HGAⅡ)應(yīng)用改良圈算法及最大容許停滯代數(shù)，不僅避免了HGAI中終止進(jìn)化代數(shù)的選取問題，而且大大加快了算法的收斂速度，使算法具有很好的魯棒性。同時(shí)在HGAII中采取杰出者記錄與“父子混合”選擇策略以及隨機(jī)因素控制參數(shù)口，從理論上保證了算
4、法的全局收斂性．最后在混合遺傳算法Ⅲ(HGAⅢ)中引入多元回歸分析中的三均值的概念對遺傳算法的控制參數(shù)進(jìn)行動態(tài)調(diào)整，從而克服用不變的控制參數(shù)來控制遺傳進(jìn)化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。(3)對設(shè)計(jì)出的三種混合遺傳算法通過數(shù)據(jù)進(jìn)行了計(jì)算機(jī)仿真模擬，對算法的性能進(jìn)行了分析測試。關(guān)鍵詞：遺傳算法旅行商問題混合遺傳算法NPCMasterDegreeDissenati佃AppHcaHOnandImprOV哪entofGene6cAJgOrithminSoIVingTSPCandidate：XueH蛆弘址供e細(xì)ork∞mputin曲D
5、irect腳byZhangBaiyich粕g’姐Unive腭i饑】
6、【i’an7l00691hvelingsalesm姐Problem∞P)h觴becomethewell·lmo、】l，nnondete鋤jnisticpolynomialcompletenessp叱zle，itisalsOoncoftheworldtypical鋤binationoptimization卸dcomputersdenccprObl鋤．Therefore，句1dingoutp刪cal鋤dcffidenta190ritllmh叢翹imponantthcoretical勰wcll觴pr
7、actical印pli齟tionsi口ificancc．neG∞eticalgoritllmiSaldndofmdomse砌ingme∞dsimulatiIlgbiolo百calnaturalselectionaIldgencticmechanism，whicbnotonlyh舔mecharacteristicofbeingsinIple，ullivers吐粕dsklble，butalsoconVcrgcthegIobalsoIutionb齬edonprobability．ThisistheVer)，purposeofmcntiollingtheimpraVe
8、dg∞etica190ritlIIIltosolveTSPiIIthisessay．TheessaystanswiththcgeneralaccoumofTSP，explainsthemathematicaldescription卸dd舔sificationofTSP．0ntheorigiIIaIb嬲is，mcessaymdethorou曲d勰si丘cati∞ofTsP；neessayill仃0ducedtlleb嬲icc0Ⅱ唧t，principle，p烈剃ureandsi印訪啪ccofthcgcneticalgorithm．Italsodisplaycd∞m
9、emajorpmccssinmatll
