【文章內(nèi)容簡(jiǎn)介】 應(yīng)個(gè)體的目標(biāo)函數(shù)值。 (3)根據(jù)最優(yōu)化問(wèn)題的類(lèi)型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。 但是，在僅用適應(yīng)度函數(shù)來(lái)計(jì)算個(gè)體適應(yīng)度時(shí) ,有些遺傳算法收斂很快 ,有些遺傳算法收斂很慢，因此在運(yùn)行到不同的階段時(shí)須對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。 適應(yīng)度尺度變換 (Fitness Scaling):對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小變換。 個(gè)體適應(yīng)度尺度變換的三種方法： 線性尺度變換公式如下： 14 F＇ =aF+b F— 原適應(yīng)度； F＇ — 尺度變換后的新適應(yīng)度； a和 b— 系數(shù)。 乘冪尺度變換公式如下： F＇ =F ? 冪指數(shù) n與所求解的問(wèn)題有關(guān)。 指數(shù)尺度變換公式如下： F＇ =exp(β F) 系數(shù)β決定了選擇的強(qiáng)制性。 選擇算子 遺 傳算法中使用選擇算子（也叫復(fù)制算子 Reproduction Operator）來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代的概率較小。遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。 選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)上。選擇的主要目的為了避免基因缺失、提高全局收斂性和計(jì)算效率。有以下幾種常用的選擇算子的操作方法：比例選擇、最優(yōu)保存策略、確定式采樣選擇、無(wú)放回隨機(jī)選擇、無(wú)放回余數(shù)隨機(jī)選擇、排序選擇和隨機(jī)聯(lián)賽選擇等。 最常用的 幾種選擇策略有以下幾種： (1) 輪盤(pán)賭選擇 (Roulette Wheel Selection) 個(gè)體適應(yīng)度按比例轉(zhuǎn)換為選中概率，將輪盤(pán)分成 n個(gè)扇區(qū)進(jìn)行 n次選擇，產(chǎn)生 n個(gè) 0～ 1之間的隨機(jī)數(shù)相當(dāng)于轉(zhuǎn)動(dòng) n次輪盤(pán)，可以獲得 n次轉(zhuǎn)盤(pán)停止時(shí)指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個(gè)體被選中。概率越大所占轉(zhuǎn)盤(pán)面積越大，被選中的機(jī)率越大。 (2) 最優(yōu)保存策略選擇 (Elitist selection) 在遺傳算法的運(yùn)行過(guò)程中，通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷產(chǎn)生新的個(gè)體，雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)生出越來(lái)越多的 優(yōu)良個(gè)體，但由于遺傳操作的隨機(jī)性，它們 15 也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個(gè)體。我們希望適應(yīng)度最好的個(gè)體要盡可能的保存到下一代群體中，為達(dá)到這個(gè)目的我們使用最優(yōu)保存策略進(jìn)化模型。 (3) 排序選擇方法（ Rankbased selection） 主要思想是：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。 (4) 比例選擇 (proportional selection) 個(gè)體被選中的概率與其適應(yīng)度大小成正比。由于隨機(jī)操作的原因，這種選擇方法的選擇誤差較大，有時(shí)連適應(yīng)度高的個(gè) 體也選不上。 (5) 確定式采樣選擇（ Determinstic Sampling selection） 基本思想是按照一種確定的方式進(jìn)行選擇操作。 (6) 無(wú)回放隨機(jī)選擇（ Expected value selection） 根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望值來(lái)進(jìn)行隨機(jī)選擇運(yùn)算。 (7) 隨機(jī)聯(lián)賽選擇 (Stuchastic Tournament Selection) 每次選取幾個(gè)適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。 交叉算子 在生物的自然進(jìn)化中，兩個(gè)同源染色體通過(guò)交配而重組，形成新的染色 體，從而產(chǎn)生新的個(gè)體或物種。模仿這個(gè)環(huán)節(jié)，在遺傳算法中也使用交叉算子來(lái)產(chǎn)生新個(gè)體。交叉運(yùn)算是指兩個(gè)相互配對(duì)的染色體按某種方式交換其部分基因，從而形成新個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 單點(diǎn)交叉算子 最常用的交叉算子是單點(diǎn)交叉算子。它是在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體 。 例如：以下兩個(gè)個(gè)體在第四個(gè)基因座之后進(jìn)行單點(diǎn)交叉運(yùn)算，得到兩個(gè)新個(gè)體： 16 單點(diǎn)交叉的重要特點(diǎn)是：若鄰接基因座之 間的關(guān)系能夠提供較好的個(gè)體性狀和較高的個(gè)體適應(yīng)度的話，則單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小。 雙點(diǎn)交叉算子 雙點(diǎn)交叉 (Twopoint Crossover)：是指在個(gè)體編碼串中隨機(jī)設(shè)置了兩個(gè)交叉點(diǎn)，然后進(jìn)行部分基因交換。 雙點(diǎn)交叉的具體操作過(guò)程是： (1) 在相互配對(duì)的兩個(gè)個(gè)體編碼中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。 (2) 交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。 例如：以下兩個(gè)個(gè)體在第二、四個(gè)基因座之間進(jìn)行交叉運(yùn)算，得到兩個(gè)新個(gè)體： 均勻交叉算子 均勻 交叉 (Uniform Crossover)：是指兩個(gè)配對(duì)個(gè)體的每個(gè)基因 座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。 例例 如如 ：： 以以 下下 兩兩 個(gè)個(gè) 個(gè)個(gè) 體體 進(jìn)進(jìn) 行行 交交 叉叉 運(yùn)運(yùn) 算算 ， 得得 到到 兩兩 個(gè)個(gè) 新新 個(gè)個(gè) 體體 ：： 部分映射交叉 (PMX)算子 整個(gè)交叉操作由兩步來(lái)完成 :首先對(duì)個(gè)體編碼 串進(jìn)行常規(guī)的雙點(diǎn)交叉操作。然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來(lái)修改交叉區(qū)域之外的各個(gè)基因座的基因值。交叉對(duì)象一般是符號(hào)編碼表示的個(gè)體。 例如 ： 以下兩個(gè)個(gè)體選取第三 、 六個(gè)基因座之后進(jìn)行交叉運(yùn)算，得到兩個(gè)新個(gè)體： 17 順序交叉（ Order Crossover）算子 主要思想：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個(gè)體巡回順序的有效順序修改，修改時(shí) 要盡量維持個(gè)點(diǎn)原有的相對(duì)訪問(wèn)順序。 例如 :以下兩個(gè)個(gè)體選取第三、六個(gè)基因座之后進(jìn)行交叉運(yùn)算，得到兩個(gè)新個(gè)體： 變異算子 在生物的遺傳和自然進(jìn)化中，其細(xì)胞分裂復(fù)制環(huán)節(jié)有可能會(huì)因?yàn)槟承┡既灰蛩氐挠绊懚a(chǎn)生一些復(fù)制差錯(cuò)，就會(huì)導(dǎo)致生物的某些基因發(fā)生某種變異，從而產(chǎn)生新的染色體，表現(xiàn)出新的生物性狀。在遺傳算法中的變異運(yùn)算，是指將基因座上的基因值用該基 因座的等位基因來(lái)替換，從而產(chǎn)生新個(gè)體。從遺傳運(yùn)算過(guò)程中產(chǎn)生新個(gè)體的能力方面來(lái)說(shuō)，交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力；而變異運(yùn)算只是產(chǎn)生新個(gè)體的輔助方法，但它也是一個(gè)必不可少的運(yùn)算步驟，因?yàn)樗鼪Q定了遺傳算法的局部搜索能力。它們共同完成對(duì)搜索空間的全局搜索和局部搜索，使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問(wèn)題的尋優(yōu)過(guò)程。 變異算子有以下兩個(gè)作用： (1) 改善遺傳算法的局部搜索能力。 (2) 維持群體多樣性，防止早熟現(xiàn)象。 較常用的基本位變異、均勻變異、邊界變異、非均勻變異和高斯變 異等。 運(yùn)行參數(shù) 在遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個(gè)體編碼串長(zhǎng)度 l、群體大小 M、交叉概率 pc、變異概率 pm、 、終止代數(shù) T、代溝 G等。 18 (1) 編碼串長(zhǎng)度 L。使用二進(jìn)制編碼時(shí)，編碼串長(zhǎng)度 l的選取與問(wèn)題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí)，編碼串長(zhǎng)度 l與決策變量的個(gè)數(shù) n相等；使用符號(hào)變量來(lái)表示個(gè)體時(shí)。編碼串長(zhǎng)度 l由問(wèn)題的編碼方式來(lái)確定；另外，也可以使用變長(zhǎng)度的編碼來(lái)表示個(gè)體。 (2) 群體大小 M表示群體中所含個(gè)體的數(shù)量。當(dāng) M較小時(shí)，可提高遺傳算法的運(yùn)算速度，卻降低了群體的多樣性，有可能會(huì)引起遺傳 算法早熟現(xiàn)象；而當(dāng) M較大時(shí)，又會(huì)使得遺傳算法的運(yùn)行效率降低。一般的建議范圍是 20～ 100。 (3) 交叉概率 pc。交叉操作是產(chǎn)生新個(gè)體的主要方法，一般應(yīng)取較大值，但取值過(guò)大的話，它會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算反而產(chǎn)生不利影響；取值過(guò)小的話，產(chǎn)生新個(gè)體的速度較慢。一般取 ～ 。 (4) 變異概率 pm。取值較大，雖然能產(chǎn)生較多的新個(gè)體，但有可能破壞掉很多的較好模式，使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；取值過(guò)大的話，則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟的能力就差。一般取 ～ 。 (5) 終止代數(shù) T。表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。一般為 100～ 1000。 (6) 代溝 G。表示每一代群體中被替換掉的個(gè)體中所占的百分率，即每一代中有 (M G個(gè)個(gè)體被替換掉 )。 約束條件的處理方法 主要有搜索空間限定法、可行解變換法、罰函數(shù)法。 19 遺傳算法流程圖 通過(guò)前幾節(jié)的了解，容易看出遺傳算法的流程可用下圖進(jìn)行描述： 圖 21遺傳算法流程圖 20 第３章 遺傳算法在 TSP上的應(yīng)用 TSP問(wèn)題的建模與描述 TSP問(wèn)題屬于 NP完全問(wèn)題，給定一組 n個(gè)城市和他們兩兩之間地直達(dá)距離，尋找一條閉合的旅程，使得每個(gè)城市剛好經(jīng)過(guò)一次而且總的旅行距離最短。 TSP問(wèn)題的描述很簡(jiǎn)單，簡(jiǎn)言之就是尋找一條最短的遍歷 n個(gè)城市的路徑，或者說(shuō)搜索整數(shù)子集 X = { 1， 2， … ， n} ( X 的元素表示對(duì) n個(gè)城市的編號(hào) ) 的一個(gè)排列л ( X) = { v1， v2， … ， vn},使 T = ∑ d( vi， vi + 1) + d( vi， vn) 取最小值。式中的 d ( vi， vi + 1) 表示城市 vi 到城市 vi + 1 的距離。 產(chǎn)生初始種群的方法通常有兩種。一種是完全隨機(jī)的方法產(chǎn)生，它適合與對(duì)問(wèn)題的解無(wú)任何先驗(yàn)知識(shí)的情況 。另一種是某些先驗(yàn)知識(shí)可轉(zhuǎn)變?yōu)楸仨殱M足一組要求，然后在滿足這些要求的解中再隨機(jī)地選取樣本。這樣選擇 初始種群可使遺傳算法更快地到達(dá)最優(yōu)解。下面給出了 C語(yǔ)言描述的完全隨機(jī)產(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)。 21 for(y=0。yPathlength。y++) printf(%3d,code[x][y]) 。 printf(\n)。 } } 對(duì) TSP的遺傳基因編碼方法 在遺傳算法的應(yīng)用中 ， 遺傳基因的編碼是一個(gè)很重要的問(wèn)題 。 對(duì)遺傳基因進(jìn)行編碼時(shí) ，要考慮到 是否適合或有利于交叉和變異操作 。 在遺傳算法中有兩種基于串的基因編碼形式 ， 一種是基于二進(jìn)制的遺傳算法 (binary coded GA)， 一種是基于順序的遺傳算法 (the orderbased GA)。 在求解 TSP問(wèn)題時(shí) ， 采用基于二進(jìn)制的遺傳算法 ， 基于二進(jìn)制的遺傳算法不利于交叉和變異操作 。 在求解 TSP問(wèn)題時(shí) ， 1985年 ， Grefenstette[9]等提出了基于順序表示 (ordinal representation)的遺傳基因編碼方法 。 順序表示是指所有城市依次排列構(gòu)成一個(gè)順序表(order list)， 對(duì)于 一條旅程 ， 可以依旅行經(jīng)過(guò)順序處理每個(gè)城市 ， 每個(gè)城市在順序表中的順序就是一個(gè)遺傳因子的表示 ， 每處理完一個(gè)城市 ， 從順序表中去掉該城市。處理完所有城市以后 ， 將每個(gè)城市的遺傳因子表示連接起來(lái) ， 就是一條旅程的基因表示 。 例如 ， 順序表 C = (1， 2， 3， 4， 5， 6， 7， 8， 9)， 一條旅程為 517894632。 按照這種編碼方法 ， 這條旅程的編碼為表 L=(5 1 5 5 5 3 3 3 2 1)。 但是這種表示方法 ， 在進(jìn)行單點(diǎn)交叉的時(shí)候 ， 交叉點(diǎn)右側(cè)部分的旅程發(fā)生了隨機(jī)變化 ， 但是交叉點(diǎn)左側(cè)部分的旅程未發(fā)生改變 ， 由 于存在這樣的缺點(diǎn) ， 所以順序表示的方法的適用性存在一定的問(wèn)題。 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) 22 { code[n][i]=jk