華南理工大學(xué)最優(yōu)化理論-第十二章遺傳算法講義課件

第三篇 智能優(yōu)化方法

第12章遺傳算法

遺傳算法（geneticalgorithm，簡稱GA）是模擬自然界生物進化的一種隨機、并行和自適應(yīng)搜索算法。遺傳算法的術(shù)語借鑒于自然遺傳學(xué)。它由賀蘭德（Holland）提出，最初用于研究自然系統(tǒng)的適應(yīng)過程和設(shè)計具有自適應(yīng)性能的軟件。它將優(yōu)化參數(shù)表示成的編碼串群體，根據(jù)適應(yīng)度函數(shù)進行選擇、交叉和變異遺傳操作。遺傳算法廣泛應(yīng)用于自動控制、規(guī)劃設(shè)計、組合優(yōu)化、圖象處理、機器學(xué)習(xí)、信號處理、人工生命等領(lǐng)域。遺傳算法是以達爾文的自然選擇學(xué)說為基礎(chǔ)發(fā)展起來的。自然選擇學(xué)說包括以下三個方面：（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個體之間的差異，稱為變異。變異是隨機發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留下來，不具有適應(yīng)性變異的個體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個體進行篩選，使適適應(yīng)度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。遺傳算法的特點

（1）遺傳算法是對參數(shù)的編碼進行操作，而非對參數(shù)本身，這就是使得我們在優(yōu)化計算過程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進化等機理；（2）遺傳算法同時使用多個搜索點的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個初始點開始最優(yōu)解的迭代搜索過程，單個搜索點所提供的信息不多，搜索效率不高，有時甚至使搜索過程局限于局部最優(yōu)解而停滯不前。

遺傳算法從由很多個體組成的一個初始群體開始最優(yōu)解的搜索過程，而不是從一個單一的個體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標函數(shù)值，而且需要目標函數(shù)的導(dǎo)數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數(shù)值變換來的適應(yīng)度函數(shù)值，就可以確定進一步的搜索方向和搜索范圍，無需目標函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。

遺傳算法可應(yīng)用于目標函數(shù)無法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等。（4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉、變異等運算都是以一種概率的方式來進行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進化過程的進行，遺傳算法新的群體會更多地產(chǎn)生出許多新的優(yōu)良的個體。（5）遺傳算法在解空間進行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機搜索；（6）遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因而應(yīng)用范圍較廣；（7）遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度，適合大規(guī)模復(fù)雜問題的優(yōu)化。

遺傳算法的基本形式遺傳算法要求有：一個染色體表示用來對參數(shù)空間編碼；一個解稱為一個符號串或染色體；一個適度函數(shù)用于估價所有的染色體；一組遺傳操作用于產(chǎn)生新的染色體；一組概率用于控制遺傳操作。交叉概率和變異概率。遺傳算法它在每一次迭代時都擁有一組解答。這組解答最初是隨機生成的。在每次迭代時又有一組新的解答由模擬進化和繼承的遺傳操作生成。每個解答都由一個目標函數(shù)給予評價，而且這一過程不斷重復(fù)，直至達到某種形式上的收斂。新的一組解答不但可以有選擇地保留一些目標函數(shù)值高的舊的解答，而且可以包括一些經(jīng)由其它解答結(jié)合而得的新的解答。遺傳算法成功的關(guān)鍵在于符號串表示和遺傳操作的設(shè)計。下一節(jié)介紹一種具有三個簡單操作的遺傳算法。

12.1遺傳算法實現(xiàn)遺傳算法（GA）的一次迭代稱為一代，每一代都擁有一組解。新的一組解不但可以有選擇地保留一些適度值高的舊的解，而且可以包括一些由其它解結(jié)合得到新的解。最初的一組解（初始群體，原始祖先）是隨機生成的，之后的每組新解由遺傳操作生成。每個解都通過一個與目標函數(shù)相關(guān)的適應(yīng)度函數(shù)給予評價，通過遺傳過程不斷重復(fù)，達到收斂，而獲得問題的最優(yōu)解。12.1.1編碼、染色體和基因1．編碼在二進制遺傳算法中，自變量是以二進制字符串的形式表示，因此需要通過編碼將空間坐標轉(zhuǎn)換成相應(yīng)的數(shù)字串，這就是編碼。例如，一個三維正整數(shù)優(yōu)化問題的各自變量均滿足0xi15，它的一個解為x=[5,7,0]。在二進制遺傳算法中，這個解對應(yīng)的寫成：x=[010101110000]。那么，010101110000就是解x的對應(yīng)編碼。2．染色體與基因在遺傳算法中，為了與生物遺傳規(guī)律對應(yīng)，每一個解被稱為一個個體，它對應(yīng)的編碼稱作染色體（或者基因串），如前面的010101110000就是個體x的染色體。對組成染色體每一個編碼元素稱為基因，相應(yīng)的染色體010101110000有12個基因。當優(yōu)化問題的維數(shù)和自變量的范圍不同時，個體的編碼的長度也就不同。例如10011001101000110111是某個個體的染色體，它的基因位數(shù)為20，或者說該染色體的長度為l=20。3．Hamming懸崖在二進制編碼中，主要的一個問題是存在Hamming懸崖（Hammingcliff）。在10進制中，255+1=256。而在二進制中，如果染色體的位數(shù)一定，它的最大數(shù)值+1得到的是染色體的最小數(shù)值。例如，對八位的二進制數(shù)：11111111+0000001=00000000，它們產(chǎn)生了255的差距，并稱為Hamming距離。比如編碼盤用格雷碼，保證1次僅有一位翻轉(zhuǎn)。Hamming懸崖為了翻越Hamming懸崖，個體的所有位上的基因需要同時改變。由于二進制編碼的遺傳操作實現(xiàn)翻越懸崖的可能性非常小，這會計算時可能會出現(xiàn)停滯不前。為此，對于多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，可采用十進制的實數(shù)編碼遺傳算法改進這一缺陷。12.1.2初始群體

同其他優(yōu)化方法類似，遺傳算法也需要有初始解。遺傳算法的初始解是隨機生成的一組解，稱為初始群體。在初始群體中，個體數(shù)目M越大，搜索范圍就越廣，效果也就越好，但是每代遺傳操作時間也會越長，運行效率也較低；反之M越小，搜索的范圍越窄，每代遺傳操作的時間越短，遺傳算法的運算速度就可以提高，但降低了群體的多樣性，有可能會引起遺傳算法的早熟現(xiàn)象（即無法獲得全局最優(yōu)解）。通常M的范圍可以取20~100。初始群體初始群體構(gòu)成了最原始的遺傳搜索空間。由于初始群體中的個體是隨機產(chǎn)生的，每個個體的基因常采用均勻分布的隨機數(shù)來生成，因此初始群體中的個體素質(zhì)一般不會太好，即它們的目標函數(shù)值與最優(yōu)解差距較遠。遺傳算法就是要從初始群體出發(fā)，通過遺傳操作，擇優(yōu)汰劣，最后得到優(yōu)秀的群體與個體（問題的最優(yōu)解）。12.1.3適應(yīng)度函數(shù)與適度值為體現(xiàn)染色體的適應(yīng)能力而引入的對每個染色體進行度量的函數(shù)，叫做適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是根據(jù)在優(yōu)化問題中給出的目標函數(shù)，通過一定的轉(zhuǎn)換規(guī)則得到的。對一個群體中第i個染色體，通過對其目標函數(shù)值轉(zhuǎn)換所得到的數(shù)值稱為適度值，用fi

表示。適應(yīng)度函數(shù)與適度值(續(xù))由于在遺傳算法中，一次迭代后得到的是一個群體，用群體中每一個個體適度值構(gòu)成的比例系數(shù)（稱為存活率）作為確定個體是否應(yīng)該被遺傳到下一代的依據(jù)。用Σfi

表示一個群體的適度值總和，第i個染色體的適度值fi

占總值的比例fi/Σfi

被視為該染色體在下一代中可能存活的概率，即存活率。如表12-1給出的由5個個體組成的一個群體的適度值表，并按各染色體適度值fi

所占總值的比例計算得到相應(yīng)的存活率

適度值假定一個群體有6個符號串，而且它們的適度值如下：

12.1.4遺傳操作遺傳操作通過模擬進化和繼承過程而生成符號串（新的或舊的）。繁殖、交叉和突變是三個簡單遺傳操作，它們在實際應(yīng)用中給出了很好的結(jié)果。12.1.1繁殖（復(fù)制）在大自然中，生命力最強的物種征服弱小的物種以確保其生存。運用這一適者生存的法則，繁殖操作在舊的群體中“隨機”選擇符號串生成一個新的群體。選擇并不是完全隨機的，它基于一個符號串相對于整個群體的適度值。

繁殖實現(xiàn)上述選擇過程的一種方法是偏置輪盤。每個符號串在輪盤上占有一格，而格的大小則與符號串的適度值成正比。在選擇一個新的符號串時，先轉(zhuǎn)動輪盤，待輪盤停下，落在之標記處的格所對應(yīng)的符號串被選中。遺傳操作（續(xù)）遺傳操作（續(xù)）圖12.1.1勾畫出了上例中的輪盤。輪盤轉(zhuǎn)動6次生成一代新的群體，且符號串的期望組合為基于期望次數(shù)，新的群體可能是

{A,A,A,B,C,C}很明顯，如果繁殖操作被重復(fù)運用，適度值較高的符號串最終會在整個群體中占據(jù)主導(dǎo)地位。由于繁殖操作并不生成新的符號串，需要其它操作以探究新的解答。遺傳操作—交叉交叉操作利用了來自不同符號串的基因經(jīng)由交叉而混合以產(chǎn)生新符號串的概念。由于基因表達了符號串的特性，如果不同符號串的“好的”特性得以結(jié)合，所得符號串可能會有更好的特性。假定一個符號串的基因被排成一條直線，則兩個符號串的交叉可按如下步驟進行（見圖12.1.2）：

遺傳操作—交叉

（1）隨機選擇一個將每個符號串斷開為兩部分的點（截點）。（2）交換符號串的后一部分。兩個具有其父母雙方基因成分的符號串由此生成。這一交叉操作是交換信息、生成新解的簡單而有效的方法。需要注意的是，如果整個群體只有一種符號串，交叉操作不會生成任何新的符號串。交叉和變異若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。遺傳操作—變異12.1.3突變突變操作隨機選取符號串中的一個基因并將其改變?yōu)橐粋€不同的等位基因以生成一個新的符號串。它將可變性引入群體，從而提供逃脫局部最小值的手段。注意，一個僅應(yīng)用突變操作的算法等同于隨機搜索。

遺傳操作的步驟因為突變操作可以有很強的破壞性，并非總要用到它，而是由一個突變概率（pm）來控制。與此類似的，交叉操作的運用也由交叉概率（pc）來控制。一個簡單的遺傳算法可歸納如下：（1）生成一個具有m個符號串的起始群體。（2）重復(fù)步驟（3）直至解答的適度值收斂。（3）生成一個新的m符號串群體。步驟如下：①應(yīng)用繁殖操作兩次，亦即用輪盤選出兩個符號串。②如果pc>rand[0,1]，則應(yīng)用交叉操作于這一對符號串。

遺傳操作的步驟③如果pm>rand[0,1]，則應(yīng)用突變操作于這一對符號串④將生成的兩個符號串加入新的群體。遺傳算法一般解題步驟如下：1) 基因編碼按照近代染色體理論的假設(shè)，基因是遺傳的基本單元，它具有自體繁殖和變異的各種性質(zhì)。基因編碼則是以一定的二進制碼來完成。一個二進制碼代表一個整數(shù)。如以三個二進制來編碼，則000-111相應(yīng)地對應(yīng)于整數(shù)0-7；至于設(shè)計變量的取值，則應(yīng)通過某種編碼—數(shù)值的一對應(yīng)關(guān)系來相應(yīng)獲得。

簡單遺傳操作步驟

2)產(chǎn)生祖先每一位祖先即是一個原始群。若干個祖先就構(gòu)成了最原始的群體。一般而言，未經(jīng)精選的原始群體中的祖先的素質(zhì)都有很差，GA的任務(wù)就是要從這些祖先出發(fā)，模擬生物進化過程，擇優(yōu)汰劣，最后得出非常優(yōu)秀的群體與個體，以滿足優(yōu)化的要求。3) 評價個體優(yōu)劣適應(yīng)度函數(shù)4) 選種：這一步模擬生物進化的自然選擇功能，是GA的關(guān)鍵所在。選種就是按一定規(guī)則從原始群體中隨機選取若干對個體作為繁殖后代的雙親。

簡單遺傳操作步驟5) 雜交：它交換雙親的基因鏈碼信息，以構(gòu)成新一代的優(yōu)化個體。6) 突變：它用以模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變。其方法是以一定的概率選取群體中若干個體，對已選取的每個個體，隨機選取某一位或若干位，將選中的某一位或若干位的數(shù)碼進行翻轉(zhuǎn)。7) 群體重新組合。8) 給出最優(yōu)解重復(fù)步4至步7，直至群體適應(yīng)度趨于穩(wěn)定。從最終穩(wěn)定的群體中取最好的個體作為GA所得的最優(yōu)解，算法終止。

簡單遺傳操作步驟由4-6步可產(chǎn)生一代新的群體。一般而言，新的群體個數(shù)少于上一代的群體個數(shù)。為維持群體規(guī)模，必須從上一代群體中選取一些素質(zhì)好的群體直接進入下一代（杰出個體保護法）。同時，為確保新的群體確實具有較上一代群體好的平均素質(zhì)，新的群體中的較差個體也應(yīng)為上一代群體中的杰出個體所取代。

12.1.5終止遺傳算法是一個反復(fù)迭代的隨機搜索過程。因此，需要給出停止條件使過程終止，并從最終穩(wěn)定的群體中取最好的個體作為GA所得的最優(yōu)解。遺傳操作的終止條件可以有如下幾種方式：根據(jù)終止進化代數(shù)N，一般取值范圍為100~500；根據(jù)適度值的最小偏差滿足要求的偏差范圍；根據(jù)適度值的變化趨勢，當適度值逐漸趨于緩和或者停止時終止遺傳操作，即群體中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適度值在連續(xù)若干代基本沒有改進后即可停止。在滿足終止條件后，輸出群體中最優(yōu)適度值的染色體作為問題的最優(yōu)解。遺傳算法流程圖

12.2 遺傳算法示例12.2.1 數(shù)值優(yōu)化問題以一簡單的例子來說明遺傳算的求解過程。求下面優(yōu)化問題的最優(yōu)解：minf(x)＝x1+x2+x3

s.t.7x1153x265x310解：按遺傳算法的求解步驟：1.取群體個數(shù)為3個，初始個體（x1,x2,x3

）分別為：x1=(11,5,10)、x2=(8,6,9)與x3=(13,4,7)

。2.將三個初始個體按二進制編碼：12.2 示例（續(xù)）由于自變量的三個分量的最大值是15，因此可以采用4位數(shù)的二進制碼。將三個初始個體按二進制編碼：

101101011010

x1=(11,5,10)100001101001

x2=(8,6,9)110101000111

x3=(13,4,7)3.交叉對x1和x2進行單點交叉，生成新個體x4和x5，而x3不變，則產(chǎn)生的新個體為：1011 0101 1001

x4=(11,5,9)

10000110 1010

x5=(8,6,10)12.2 示例（續(xù)）4.變異對x4個體的第4、12位進行變異，將該兩位置上的1變?yōu)?，從而產(chǎn)生新個體x6：

1011 0101 1001

x4=(11,5,9)

新個體為1010 0101 1000 x6=(10,5,8)這里應(yīng)該注意：變異位的選擇是隨機的，但是要使經(jīng)過變異操作之后的優(yōu)化變量要滿足約束條件。示例（續(xù)）5．選擇下一代群體到現(xiàn)在為止，初始群體的3個個體為：x1=(11,5,10)、x2=(8,6,9)、x3=(13,4,7)。由進化操作產(chǎn)生了3個新個體，它們分別為：x4=(11,5,9)、x5=(8,6,10)、x6=(10,5,8)。生成共6個個體的群體，按數(shù)值優(yōu)化目標函數(shù)可計算得到它們對應(yīng)的目標函數(shù)值為f(x1)=26、f(x2)=23、f(x3)=24、f(x4)=25、f(x5)=24和f(x6)=23。選適當?shù)倪m應(yīng)度函數(shù)，并計算適度值。因為，優(yōu)化目標函數(shù)是三個分量的和，且要求尋找最小值，從約束條件可知3個自變量都不大于15，因此可以選擇適應(yīng)度函數(shù)為fi=50-f(xi)，

當前群體各個體數(shù)據(jù)表12.2 示例（續(xù)）試利用遺傳算法求解下面函數(shù)的最大值，要求自變量x要精確到0.00001。

其中

圖12.2.1給出了函數(shù)f(x)在變量x取值[-2,2]時的曲線。f的最大值1.501564對應(yīng)于x=-0.507179。

12.2 示例（續(xù)）1．編碼方法首先要用一個二值量表達x。若x的取值范圍為[a,b]，變換到二進制編碼的長度為l，則分辨率應(yīng)為一個20位的二值數(shù)的分辨率是每位[(2-(-2)]/(220-1)=0.00000381470.00001，滿足精度要求。將式（12-4）中的變量域[-2,2]離散化為00000000000000000000到11111111111111111111的二進制編碼。2．解碼方法

根據(jù)編碼方法，采用20位的二進制進行編碼，則二值數(shù)的范圍為[0,1048575]。則由二進制編碼轉(zhuǎn)換為變量的公式為：式中，v是[0,1048575]中的一個二值數(shù)。例如，v1=(10111011011001101001)

x1=0.927100112v2=(00110010110111100010)

x2=1.1895667933．確定適度值由目標函數(shù)式（12-4）可知，目標函數(shù)的f(x)的值總大于0，并且優(yōu)化目標是求函數(shù)的最大值，因此可將函數(shù)值作為適應(yīng)度函數(shù)。即有：4．遺傳操作在運用遺傳算法求解式（12-4）給出的函數(shù)的最大值時，用到了選擇、交叉和變異等三個遺傳操作。交叉操作：可由上節(jié)給出的偏置輪盤實現(xiàn)。交叉操作將兩個二值量在截斷點位置互換末尾部分基因，生成兩個新的二值量。在這里采用最簡單的交叉形式，即隨機選取兩相鄰位之間作為截點，交換兩個二值量在截斷點后的尾部以獲取兩個新的向量。遺傳操作（續(xù)）例如，若選取截斷點如下：

v1=(101110