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

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

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

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

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

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

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

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

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

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

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

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

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

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

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