遺傳算法的理論基礎(chǔ)

遺傳算法的理論基礎(chǔ)第一頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理模式定理是由Holland所提出的，其目的是從理論上解釋遺傳算法的有效性。Holland的模式定理是針對(duì)簡(jiǎn)單遺傳算法(SGA)而言的，即假定在遺傳算法中，種群的規(guī)模不變，使用二進(jìn)制編碼、基于適應(yīng)值比例的選擇策略、單點(diǎn)雜交算子和通常的變異算子。第二頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理字符集{0,1,*}上的一個(gè)字符串稱為一個(gè)模式在一個(gè)模式中，*表示一個(gè)不確定的字符，即表示0或1，所以一個(gè)模式可以表示一個(gè)二進(jìn)制位串的集合。例模式*0101表示集合{00101,10101}，而模式0**1*表示集合{00010，00011，00110，00111，01010，01011，01110，01111}。在一個(gè)模式中，字符0或1所出現(xiàn)的位置稱為確定位置，字符*所出現(xiàn)的位置稱為不確定位置。第三頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理模式H中確定位置的個(gè)數(shù)稱為模式H的階,記為例模式H中第一個(gè)確定位置與最后一個(gè)確定位置之間的距離稱為模式H的定義長(zhǎng)度，記為例設(shè)s是一個(gè)長(zhǎng)度為的二進(jìn)制位串，H是一個(gè)長(zhǎng)度為的模式，若則稱s與模式H匹配。

第四頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理二進(jìn)制位串00與下列模式匹配：00，*0，0*，**二進(jìn)制位串110與下列模式匹配：110,*10,1*0,11*,**0,*1*,1**,***.定義假設(shè)表示SGA在第t代時(shí)的種群，f為SGA所使用的適應(yīng)函數(shù)，H為任一模式，則稱P(t)中與模式H匹配的個(gè)體的平均適應(yīng)值為模式H在第t代的適應(yīng)值，記為即有第五頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理例假定當(dāng)前種群中的個(gè)體及適應(yīng)值如表1所示，則模式H及其適應(yīng)值如表2所示。個(gè)體適應(yīng)值1011000101105123表1個(gè)體及其適應(yīng)值Hf(H,t)*****0*1**00(5+1+2+3)/4=2.75(1+2+3)/3=2(2+3)/2=2.51/1=1表2模式及其適應(yīng)值第六頁(yè)，共二十四頁(yè)，編輯于2023年，星期二7.1模式定理定理7.1(模式定理)設(shè)表示SGA在第t代時(shí)的種群，SGA的雜交概率和變異概率分別為和H為任一模式，表示第t代種群中與H匹配個(gè)體的個(gè)數(shù)，則有估計(jì)式其中為P(t)中個(gè)體的平均適應(yīng)值，為個(gè)體的編碼長(zhǎng)度。第七頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理證首先考慮選擇對(duì)模式H的影響。

由于SGA采用基于適應(yīng)值比例的選擇策略，所以在第t代種群P(t)中，與H匹配的個(gè)體被選擇作為父體的個(gè)數(shù)的期望值為第八頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理再考慮雜交算子對(duì)模式的影響。雜交算子隨機(jī)地選取1到中的一個(gè)位置，并交換兩個(gè)父體中所選取位置右邊的子串。顯然，若選取的雜交位置不在模式H的第一個(gè)確定位置和最后一個(gè)確定位置之間，那么原來屬于H中的個(gè)體經(jīng)雜交后仍然屬于H。若所選取的雜交位置在模式H的第一個(gè)確定位置和最后一個(gè)確定位置之間，那么原來屬于H中的個(gè)體經(jīng)雜交后有可能不再屬于H。第九頁(yè)，共二十四頁(yè)，編輯于2023年，星期二例如

那么有若111000與101011進(jìn)行雜交，且隨機(jī)選擇的雜交位置為3，雜交后所得到的兩個(gè)后代分別為111011和101000，這兩個(gè)后代均不屬于H。第十頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理原來屬于H中的個(gè)體經(jīng)雜交后也有可能仍然屬于H。例如若在上面的例子中111000與001100進(jìn)行雜交，雜交位置仍為3，那么雜交后所得到的兩個(gè)子串為111100和001000，其中后代111100仍然屬于H。屬于模式H的個(gè)體經(jīng)雜交后不屬于模式H的概率至多為第十一頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理屬于模式H的個(gè)體經(jīng)雜交后仍屬于模式H的概率至少為由于選擇和雜交是相互獨(dú)立的，所以經(jīng)過選擇和雜交后種群中近似地有個(gè)與H匹配的個(gè)體

第十二頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理最后討論變異算子對(duì)模式H的影響。對(duì)于一個(gè)屬于模式H的個(gè)體v，變異算子以概率對(duì)v的每一位相互獨(dú)立地進(jìn)行變異，當(dāng)且僅當(dāng)變異算子在H的個(gè)確定位置上不對(duì)v進(jìn)行變異時(shí)，經(jīng)變異算子后所得到的個(gè)體仍然屬于H。由于對(duì)某一位不進(jìn)行變異的概率為，于是屬于模式H中個(gè)體v經(jīng)變異后仍然屬于模式H的概率為第十三頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理經(jīng)選擇、雜交、變異操作后，第t+1代中包含模式H的個(gè)體數(shù)目有以下估計(jì)式：第十四頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理推論在SGA中，定義長(zhǎng)度較短、低階且適應(yīng)值大于種群平均適應(yīng)值的模式H，在種群中的數(shù)目呈指數(shù)增長(zhǎng)

證設(shè)對(duì)任意都有其中為一個(gè)常數(shù)。并設(shè)第十五頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.1模式定理當(dāng)時(shí)，由定理知

于是推論成立。第十六頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析

定義設(shè)是遺傳算法當(dāng)代數(shù)為t時(shí)的種群，為適應(yīng)函數(shù)，表示種群的最優(yōu)適應(yīng)值，表示全局最優(yōu)適應(yīng)值。若則稱遺傳算法依概率收斂于全局最優(yōu)解。第十七頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析第十八頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析定理7.2若雜交概率和變異概率滿足適應(yīng)函數(shù)不恒等于一個(gè)常數(shù)，則SGA不能依概率收斂于全局最優(yōu)解。

第十九頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析定理7.2說明了簡(jiǎn)單遺傳算法不能依概率收斂到全局最優(yōu)解，但只要對(duì)簡(jiǎn)單遺傳算法作一點(diǎn)改動(dòng)，每次將當(dāng)前找到的最好解保留下來，在算法結(jié)束后，將所保留的最好解作為問題的最優(yōu)解或近似最優(yōu)解輸出，則可證明修改后的遺傳算法依概率收斂到全局最優(yōu)解。改進(jìn)后的簡(jiǎn)單遺傳算法描述如下：

第二十頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析第二十一頁(yè)，共二十四頁(yè)，編輯于2023年，星期二6.2基于有限馬爾可夫鏈的收斂性分析定理7.3改進(jìn)后的簡(jiǎn)單遺傳算法依概率收斂到全局最優(yōu)解。

第二十二頁(yè)，共二十四頁(yè)，編輯于2023年，星期二演化計(jì)算讀書報(bào)告題目(下列題目選擇之一)1

用遺傳算法或演化策略求解下列優(yōu)化問題(n=2)

并研究問題的維數(shù)對(duì)算法性能的影響。2

使用路徑表示設(shè)計(jì)并實(shí)現(xiàn)一個(gè)求解具有30個(gè)城市