【正文】 .................................. 1 旅行商問題 ......................................................... 1 研究意義 ........................................................... 1 論文的組織結(jié)構(gòu) ..................................................... 1 第 2章 遺傳算法理論概述 ................................................... 2 遺傳算法的起源和發(fā)展 ............................................... 2 遺傳算法基本原理 ................................................... 3 遺傳算法的基本步驟 ................................................. 4 遺傳算法的流程圖 ................................................... 4 遺傳算法的特點(diǎn) ..................................................... 5 遺傳算法的應(yīng)用 ..................................................... 6 第 3章 TSP 問題及研究的基本方法 ............................................ 8 TSP 問題概述 ....................................................... 8 TSP 的應(yīng)用與價值 ................................................... 8 TSP 問題的數(shù)學(xué)模型 ................................................. 9 TSP 問題的分類 ..................................................... 9 現(xiàn)有的求解 TSP問題的幾種算法 ...................................... 10 第 4章 遺傳算法在 TSP 的應(yīng)用 .............................................. 12 遺傳算法在 TSP 上的應(yīng)用 ............................................ 12 算法的實(shí)現(xiàn) ........................................................ 12 編碼 .............................................................. 12 初始化種群 ........................................................ 13 適應(yīng)度函數(shù) ........................................................ 13 選擇操作 .......................................................... 13 交叉操作 .......................................................... 15 變異操作 .......................................................... 17 實(shí)驗(yàn)結(jié)果 .......................................................... 18 結(jié) 論 ................................................................... 20 展望 ..................................................................... 20 參 考 文 獻(xiàn) .............................................................. 21 致 謝 ................................................................... 22 附錄程序 ................................................................. 23 I 摘要 TSP 問題 (Traveling Salesman Problem)是已知有 n個城市，現(xiàn)有一推銷員必須遍訪這 n 個城市，且每個城市只能訪問一次，最后又必須返回出發(fā)城市。 研究意義 旅行商問題是一個理想化的問題，大多數(shù)對于此問題的研究都不是為了直接的實(shí)際應(yīng)用，但這些研究可以經(jīng)轉(zhuǎn)化 后用于許多現(xiàn)實(shí)的組合優(yōu)化問題。生物要想生存下來，就必須進(jìn)行生存斗爭。 1967 年，他的學(xué)生 Bagley J． D．首次提出“遺傳算法”一詞，并發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子。這個過程導(dǎo)致種群象自然進(jìn)化一樣，后代種群比前代更加適應(yīng)于環(huán)境，末代種群中最優(yōu)個體經(jīng)過解碼 (Decoding)，可以作為問題的近似最優(yōu)解。福建農(nóng)林大學(xué)本科畢業(yè)論文 6 進(jìn)化算法的這種自組織、自適應(yīng)特征，使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。 (1)函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳 算法進(jìn)行性能評價的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和 高維 函數(shù)、單峰函數(shù)和多峰函數(shù)等。對提到的實(shí)例，圖中的節(jié)點(diǎn)將通過地理位置順序連接，而且連接兩節(jié)點(diǎn)的路徑的長度是公制的。雖然陳述起來很簡單 ，但求解卻很困難，它一直是運(yùn)籌學(xué)中最富挑戰(zhàn)性的問題之一，且已經(jīng)被證明是 NP 完全問題。 (1)禁忌搜索算法 禁忌搜索算法是局部領(lǐng)域搜索算法的推廣，主要思想是標(biāo)記已經(jīng)得到的局部最優(yōu)解，并在進(jìn)一步的迭代中避開這些局部最優(yōu)解。 福建農(nóng)林大學(xué)本科畢業(yè)論文 12 第 4 章 遺傳算法在 TSP 的應(yīng)用 法在 TSP上的應(yīng)用 在遺傳算法研究中， TSP 問題已被廣泛地用于評價不同的遺傳操作及選擇機(jī)制的性能。 void CalFitness(PTSP city) { int i,j。 (4) 期望值方法。jPOPSIZEamp。 crossNum=int(POPSIZE*pc)。j++) { do { selCity=rand()%(POPSIZE)。 （ 3）交叉概率過小會導(dǎo)致產(chǎn)生新個體的速度變慢，而導(dǎo)致收斂速度降低。 同時本文能成功完成，要感謝我的導(dǎo)師：賴賢偉老師。 }TSP,*PTSP。 for(i=0。iPOPSIZE。 for(i=0。h++) { for(i=1。 if(genePoint[0]genePoint[1]) {temp1=genePoint[0]。h2。!(igenePoint[0]amp。 copyCityXuhToCityColony(tempcityxuh,tempXuh,city)。 do { tempXuh[1]=rand()%(POPSIZE1)。 福建農(nóng)林大學(xué)本科畢業(yè)論文 31 }while(changePoint[0]==changePoint[1]||changePoint[0]==0||changePoint[1]==0||changePoint[0]changePoint[1]3)。 crossNum=int(POPSIZE*pc)。flaglike==0。 } } for(i=1。j=genePoint[1])) { if(cityCross[k][j]==cityCross[(k+1)%2][i]) { ++samePoint。 int tempcityxuh[2][CITY_NUM+1]。 } } } } return。 /*if(citycolony[fromc][i]9||citycolony[fromc][i]1) { i=i。 福建農(nóng)林大學(xué)本科畢業(yè)論文 25 } citycolony[i][j]=r。i=num。//最優(yōu)城市路徑序列 double BestFitness。 (3)遺傳算法不是求解 TSP 問題的唯一方法，當(dāng)然，也未經(jīng)過驗(yàn)證是最好的辦法。 （ 2）變異率取值過小，就會導(dǎo)致算法容易陷入局 部收斂。 如圖 42 所示： 42 變異操作示意圖 代碼： void Mutation(PTSP city,double pm) {//變異概率是 pm int changePoint[2],temp,j。 遺傳交叉的主要目的是子代盡可能地繼承父代的優(yōu)秀基因。iPOPSIZE。選擇操作的目的是為了避免基因缺失，提高全局收斂性和計算效率。 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時，生物學(xué)家常常使用適應(yīng)度這個術(shù)語來衡量某個物種對環(huán)境的適應(yīng)率。 (4)人工神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò) (Artificial Neural Network， ANN)，是由大量處理單元即神經(jīng)元 (Neurons)互相連接而成的網(wǎng)絡(luò)，對人腦進(jìn)行抽象，簡化和模擬的一種工程系統(tǒng) ，反映人腦的基 本特性 。傳統(tǒng)算法有精確算法和近似優(yōu)化算法，精確算法又有線性規(guī)劃方法、動態(tài)規(guī)劃方法、分支定界方法等，而近似算法有插入法、最近鄰算法、 ropt 算法、混合算法、概率算法等。為了通過 TSP 解決這個時間的節(jié)約問題，對每個節(jié)點(diǎn)做了簡化，用需要鉆孔的位置來代替，而邊用節(jié)點(diǎn)之間的距離來代替。但是遺憾的 是，計算復(fù)雜性理論給予我們的結(jié)論卻是，這種可能性尚屬未知 。 (4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)化規(guī)則。主要區(qū)別在于 (1)自組織、自適應(yīng)和自學(xué)習(xí)性。每個個體實(shí)際上是染色體(Chromosome)帶有特征的實(shí)體。生物體自身通過對基因的復(fù)制和交叉即基因分離、基因自由組合和基因連鎖互換的操作使其性狀的遺傳得到選擇和控制。遺傳算法正是從大自然的杰作 —— 生物進(jìn) 化論中得到的靈感和啟迪 ，其基本思想是Darwin 進(jìn)化論和 Mendel 的遺傳學(xué)說。旅行商問題是一個比較古老的問題，最早可追溯到 Euler 提出的騎士旅行問題，同時它也是個“新問題 ，因?yàn)橛嬎愕膹?fù)雜性 較高，人們一直在嘗試用新的方法來改進(jìn)求解該問題的復(fù)雜度。本人完全意識到本聲明的法律 后果由本人承擔(dān)。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。 TSP 問題是一個具有廣泛的應(yīng)用背景和重要理論價值的組合優(yōu)化問題，它是一個典型的 NP 問題。 Darwin 進(jìn)化論最核心的是自然選擇學(xué)說 。同時，通過基因重組、基因變異和染色體在結(jié)構(gòu)和數(shù)目上的變異產(chǎn)生豐富多彩的變異現(xiàn)象。作為多個基因的集合，單個染色體是遺傳物質(zhì)的主要載體，其在種群中的命運(yùn)由其基因組合決定。應(yīng)用遺傳算法求解問題時，在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。 (5)遺傳算法可以更加直接的應(yīng)用。 TSP的應(yīng)用與價值 TSP 在現(xiàn)實(shí)生活中有很多應(yīng)用。 福建農(nóng)林大學(xué)本科畢業(yè)論文 9 TSP問題的數(shù)學(xué)模型 TSP 問題的數(shù)學(xué)模型如下：設(shè)有 n個城 市，尋找一條巡回路徑 T=(t1， t2，．．．， tn)，使得下列目標(biāo)函數(shù)最?。? f(T)= ???1n1di(ti,ti+1)+d(tn,t1) 其中 ti為 城 市號，取值為 1 到 n 之間的自然數(shù)， d(i,j)為城市 i 和城市 j 之間的距離，對于對稱式 TSP，有 d(i， j)=d(j， i)。