【文章內(nèi)容簡介】 動 n次輪盤，可以獲得 n次轉(zhuǎn)盤停止時指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個體被選中。概率越大所占轉(zhuǎn)盤面積越大，被選中的機率越大。 (2) 最優(yōu)保存策略選擇 (Elitist selection) 在遺傳算法的運 行過程中，通過對個體進行交叉、變異等遺傳操作而不斷產(chǎn)生新的個體，雖然隨著群體的進化過程會產(chǎn)生出越來越多的優(yōu)良個體，但由于遺傳操作的隨機性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個體。我們希望適應(yīng)度最好的個體要盡可能的保存到下一代群體中，為達(dá)到這個目的我們使用最優(yōu)保存策略進化模型。 (3) 排序選擇方法（ Rankbased selection） 主要思想是：對群體中的所有個體按其適應(yīng)度大小進行排序，基于這個排序來分配各個個體被選中的概率。 (4) 比例選擇 (proportional selection) 個體被選中的概率與其適應(yīng)度大小成正比。由于隨機操作的原因，這種選擇方法的選擇誤差較大，有時連適應(yīng)度高的個體也選不上。 (5) 確定式采樣選擇（ Determinstic Sampling selection） 基本思想是按照一種確定的方式進行選擇操作。 (6) 無回放隨機選擇（ Expected value selection） 根據(jù)每個個體在下一代群體中的生存期望值來進行隨機選擇運算。 (7) 隨機聯(lián)賽選擇 (Stuchastic Tournament Selection) 每次選取幾個適應(yīng)度最高的一個個體 遺傳到下一代群體中。 交叉算子 在生物的自然進化中，兩個同源染色體通過交配而重組，形成新的染色體，從而產(chǎn)生新的個體或物種。模仿這個環(huán)節(jié)，在遺傳算法中也使用交叉算子來產(chǎn)生新個體。交叉運算是指兩個相互配對的染色體按某種方式交換其部分基因，從而形成新個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 單點交叉算子 最常用的交叉算子是單點交叉算子。它是在個體編碼串中只隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分染色體 。 例如：以下 兩個個體在第四個基因座之后進行單點交叉運算，得到兩個新個體： 單點交叉的重要特點是：若鄰接基因座之間的關(guān)系能夠提供較好的個體性狀和較高的個體適應(yīng)度的話，則單點交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。 雙點交叉算子 雙點交叉 (Twopoint Crossover)：是指在個體編碼串中隨機設(shè)置了兩個交叉點，然后進行部分基因交換。 雙點交叉的具體操作過程是： (1) 在相互配對的兩個個體編碼中隨機設(shè)置兩個交叉點。 (2) 交換兩個個體在所設(shè)定的兩個交叉點之間的部分染色體。 例如 ：以下兩個個體在第二、四個基因座之間進行交叉運算，得到兩個新個體： 均勻交叉算子 均勻交叉 (Uniform Crossover)：是指兩個配對個體的每個基因 座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。 例例 如如 ：： 以以 下下 兩兩 個個 個個 體體 進進 行行 交交 叉叉 運運 算算 ， 得得 到到 兩兩 個個 新新 個個 體體 ：： 部分映射交叉 (PMX)算子 整個交叉操作由兩步來完成 :首先對個體編碼 串進行常規(guī)的雙點交叉操作。然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個基因座的基因值。交叉對象一般是符號編 碼表示的個體。 例如 ： 以下兩個個體選取第三 、 六個基因座之后進行交叉運算，得到兩個新個體： 順序交叉（ Order Crossover）算子 主要思想：先進行常規(guī)的雙點交叉，然后進行個體巡回順序的有效順序修改，修改時 要盡量維持個點原有的相對訪問順序。 例如 :以下兩個個體選取第三、六個基因座之后進行交叉運算，得到兩個新個體： 變異算子 在生物的遺傳和自然進化中，其細(xì)胞分裂復(fù)制環(huán)節(jié)有可能會因為某些偶然因素的影響而產(chǎn)生一些復(fù)制差錯，就會導(dǎo)致生物的某些基因發(fā) 生某種變異，從而產(chǎn)生新的染色體，表現(xiàn)出新的生物性狀。在遺傳算法中的變異運算，是指將基因座上的基因值用該基因座的等位基因來替換，從而產(chǎn)生新個體。從遺傳運算過程中產(chǎn)生新個體的能力方面來說，交叉運算是產(chǎn)生新個體的主要方法，它決定了遺傳算法的全局搜索能力；而變異運算只是產(chǎn)生新個體的輔助方法，但它也是一個必不可少的運算步驟，因為它決定了遺傳算法的局部搜索能力。它們共同完成對搜索空間的全局搜索和局部搜索，使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。 變異算子有以下兩個作用： (1) 改善遺傳算法的局部搜索能 力。 (2) 維持群體多樣性，防止早熟現(xiàn)象。 較常用的基本位變異、均勻變異、邊界變異、非均勻變異和高斯變異等。 運行參數(shù) 在遺傳算法中需要選擇的運行參數(shù)主要有個體編碼串長度 l、群體大小 M、交叉概率 pc、變異概率 pm、 、終止代數(shù) T、代溝 G等。 (1) 編碼串長度 L。使用二進制編碼時，編碼串長度 l的選取與問題所要求的求解精度有關(guān)；使用浮點數(shù)編碼時，編碼串長度 l與決策變量的個數(shù) n相等；使用符號變量來表示個體時。編碼串長度 l由問題的編碼方式來確定；另外，也可以使用變長度的編碼來表示個體。 (2) 群體大小 M表示群體中所含個體的數(shù)量。當(dāng) M較小時，可提高遺傳算法的運算速度，卻降低了群體的多樣性，有可能會引起遺傳算法早熟現(xiàn)象；而當(dāng) M較大時，又會使得遺傳算法的運行效率降低。一般的建議范圍是 20～ 100。 (3) 交叉概率 pc。交叉操作是產(chǎn)生新個體的主要方法，一般應(yīng)取較大值，但取值過大的話，它會破壞群體中的優(yōu)良模式，對進化運算反而產(chǎn)生不利影響；取值過小的話，產(chǎn)生新個體的速度較慢。一般取 ～ 。 (4) 變異概率 pm。取值較大，雖然能產(chǎn)生較多的新個體，但有可能破壞掉很多的較好模式，使得遺傳算法的性能近似于隨機 搜索算法的性能；取值過大的話，則變異操作產(chǎn)生新個體的能力和抑制早熟的能力就差。一般取 ～ 。 (5) 終止代數(shù) T。表示遺傳算法運行到指定的進化代數(shù)之后就停止，并將當(dāng)前群體中的最佳個體作為所求問題的最優(yōu)解輸出。一般為 100～ 1000。 (6) 代溝 G。表示每一代群體中被替換掉的個體中所占的百分率，即每一代中有 (M G個個體被替換掉 )。 約束條件的處理方法 主要有搜索空間限定法、可行解變換法、罰函數(shù)法。 遺傳算法流程圖 通過前幾節(jié)的了解，容易看出遺傳算法的流程可用 下圖進行描述： 圖 21遺傳算法流程圖 第３章 遺傳算法在 TSP上的應(yīng)用 TSP問題的建模與描述 TSP問題屬于 NP完全問題，給定一組 n個城市和他們兩兩之間地直達(dá)距離，尋找一條閉合的旅程，使得每個城市剛好經(jīng)過一次而且總的旅行距離最短。 TSP問題的描述很簡單，簡言之就是尋找一條最短的遍歷 n個城市的路徑，或者說搜索整數(shù)子集 X = { 1， 2， … ， n} ( X 的元素表示對 n個城市的編號 ) 的一個排列л ( X) = { v1， v2， … ， vn},使 T = ∑ d( vi， vi + 1) + d( vi， vn) 取最小值。式中的 d ( vi， vi + 1) 表示城市 vi 到城市 vi + 1 的距離。 產(chǎn)生初始種群的方法通常有兩種。一種是完全隨機的方法產(chǎn)生，它適合與對問題的解無任何先驗知識的情況 。另一種是某些先驗知識可轉(zhuǎn)變?yōu)楸仨殱M足一組要求，然后在滿足這些要求的解中再隨機地選取樣本。這樣選擇 初始種群可使遺傳算法更快地到達(dá)最優(yōu)解。下面給出了 C語言描述的完全隨機產(chǎn)生新種群的函數(shù)。 GenerateInitialPopulation() /*random*/ { int x,y。 /* Seed the randomnumber generator with current time so that * the numbers will be different every time we run. */ srand( (unsigned)time( NULL) )。 for(x=0。xPOPSIZE。x++) { for(y=0。yPathlength。y++) { if(y==0) code[x][y]=1。 else code[x][y]=rand()%(Pathlengthy)+1。 } } for(x=0。xPOPSIZE。x++) code_path(x)。 for(x=0。xPOPSIZE。x++) { printf(%3d ,x+1)。 for(y=0。yPathlength。y++) printf(%3d,code[x][y]) 。 printf(\n)。 } } 對 TSP的遺傳基因編碼方法 在遺傳算法的應(yīng)用中 ， 遺傳基因的編碼是一個很重要的問題 。 對遺傳基因進行編碼時 ， 要考慮到是否適合或有利于交叉和變異操作 。 在遺傳算法中有兩種基于串的基因編碼形式 ， 一種是基于二進制的遺傳算法 (binary coded GA)， 一種是基于順序的遺傳算法 (the orderbased GA)。 在求解 TSP問題時 ， 采用基于二進制的遺傳算法 ， 基于二進制的遺傳算法不利于交叉和變異操作 。 在求解 TSP問題時 ， 1985年 ， Grefenstette[9]等提出了基于順序表示 (ordinal representation)的遺傳基因編碼方法 。 順序表示是指所有城市依次排列構(gòu)成一個順序表 (order list)， 對于一條旅程 ， 可以依旅行經(jīng)過順序處理每個城市 ， 每個城市在順序表中的順序就是一個遺傳因子的表示 ， 每處理完一個城市 ， 從順序表中去掉該城市。處理完所有城市以后 ， 將每個城市的遺傳因子表示連接起來 ，就是一條旅程的基因表示 。 例如 ， 順序表 C = (1， 2， 3， 4， 5， 6， 7， 8， 9)，一條旅程為 517894632。 按照這種編碼方法 ， 這條旅程的編碼為表 L=(5 1 5 5 5 3 3 3 2 1)。 但是這種表 示方法 ， 在進行單點交叉的時候 ， 交叉點右側(cè)部分的旅程發(fā)生了隨機變化 ， 但是交叉點左側(cè)部分的旅程未發(fā)生改變 ， 由于存在這樣的缺點 ， 所以順序表示的方法的適用性存在一定的問題。 path_code(int n) /*path change into code */ { int b[MaxPathlength]。 int i,j,k。 for(i=0。iMaxPathlength。i++) b[i]=0。 for(i=0。iPathlength。i++) { k=0。 for(j=1。jPathlength+1。j++) { if((b[j]==0)) { if(population[n].Path[i]==j) { code[n][i]=jk。 b[j]=1。 break。 } } else k++。 } } } 針對 TSP的遺傳操作算子 選擇算子 對于求解 TSP問題 ， 常用的選擇機制有輪盤賭選擇 (roulette wheel selection)機制 ， 最佳個體保存 (elitist model)選擇機制 ， 期望值模型(expected value model)機制 ， 排序模型 (rankbased model)選擇機制 ， 聯(lián)賽選擇模型 (tournament selection model)機制 ， 排擠模型 (crowding model)等 。 遺傳算法中一個要求解決的問題是如何防止“早熟”收斂現(xiàn)象 。 為了保證遺傳算法的全局收斂性 ， 就要維持群體中個體的多樣性 ， 避免有效基因的丟失 。 Rudolhp C[4]提出采用精英選擇策略即保持群體中最好的個體不丟失 ， 以保證算法的收斂性 。Konstantin Boukreev[5]采用聯(lián)賽選擇方法和最優(yōu)個體保存方法相結(jié)合的方法 ，通過在 VC++ TSP問題的遺傳算法 ， 取得了很好的效果 。謝勝利等提出濃度控制策略 ， 當(dāng)某種個體的濃度超過給定的濃度閥值時減少該種個體的數(shù)量 ， 使之控制在給定的濃度閥值之內(nèi) ， 并隨機產(chǎn)生新的個體以補足種群的規(guī)模 ， 他們通過實驗證明該策略很好的解決了遺傳算法中群體的多樣性問題 。 在該遺傳算法中用到的輪盤賭選擇和最佳個體保存策略。 輪盤賭選擇 (roulette wheel selection) 個體適應(yīng)度按比例轉(zhuǎn)換為 選中概率，將輪盤分成 n個扇區(qū)進行 n次選擇，產(chǎn)生n個 0～ 1之間的隨機數(shù)相當(dāng)于轉(zhuǎn)動 n次輪盤，可以獲得 n次轉(zhuǎn)盤停止時指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個體被選中。概率越大所占轉(zhuǎn)盤面積越大，被選