遺傳算法及應用補第一頁，共三十一頁，2022年，8月28日1一、遺傳算法的基本原理

Darwin的進化論：

優勝劣汰，適者生存。

Mendel的基因遺傳學：遺傳是作為一種指令碼封裝在每個細胞中，并以基因的形式包含在染色體中，每個基因有特殊的位置并控制某個特殊的性質，每個基因產生的個體對環境有一定的適應性，基因雜交和基因突變可能產生對環境適應性更強的后代，通過優勝劣汰的自然選擇，適應值高的基因結構就保存下來。

第二頁，共三十一頁，2022年，8月28日2一、遺傳算法的基本原理遺傳算法將問題的求解表示成“染色體”（用編碼表示字符串）。該算法從一群“染色體”串出發，將它們置于問題的“環境”中，根據適者生存的原則，從中選擇出適應環境的“染色體”進行復制，通過交叉、變異兩種基因操作產生出新的一代更適應環境的“染色體”種群。隨著算法的運行，優良的品質被逐漸保留并加以組合，從而不斷產生出更佳的個體。

第三頁，共三十一頁，2022年，8月28日3一、遺傳算法的基本原理常規的尋優方法主要有三種類型：解析法：間接法是通過讓目標函數的梯度為零，進而求解一組非線性方程來尋求局部極值。直接法是使梯度信息按最陡的方向逐次運動來尋求局部極值，它即為通常所稱的爬山法。

枚舉法：可尋找到全局極值，不需要目標函數連續光滑。

隨機法：搜索空間中隨機地漫游并隨時記錄下所取得的最好結果。

第四頁，共三十一頁，2022年，8月28日4二、遺傳算法的基本操作設需要求解的優化問題為尋找當自變量x在0～31之間取整數值時函數f(x)=x2的最大值。

第一步：準備工作“染色體”串的編碼采用二進制數來對其進行編碼，可用5位數來表示。例如01010對應x=10，11111對應x=31。

初始種群的產生

設種群大小為4，即含有4個個體，則需按位隨機生成4個5位二進制串：

01101、11000、01000、10011

第五頁，共三十一頁，2022年，8月28日5(一)復制操作

復制(Copy)亦稱再生(Reproduction)或選擇(Selection)，復制過程是個體串按照它們的適配度進行復制。本例中目標函數值即可用作適配度。

按照適配度進行串復制的含義是適配度越大的串，在下一代中將有更多的機會提供一個或多個子孫。

第六頁，共三十一頁，2022年，8月28日6種群的初始串及對應的適配度

序號串X值適配度占整體的百分數%期望的復制數實際得到的復制數1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23總計1170100.04.00平均29325.01.00最大值57649.01.97第七頁，共三十一頁，2022年，8月28日7經復制后的新的種群為01101110001100010011串1被復制了一次串2被復制了兩次串3被淘汰串4也被復制了一次(一)復制操作

第八頁，共三十一頁，2022年，8月28日8種群的初始串及對應的適配度

序號串X值適配度占整體的百分數%期望的復制數實際得到的復制數1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231總計1170100.04.004平均29325.01.001最大值57649.01.972第九頁，共三十一頁，2022年，8月28日9(二)交叉操作

交叉(Crossover)操作可分為兩步：第一步—將新復制產生的匹配池中的成員隨機兩兩匹配。第二步—進行交叉繁殖。設串的長度為l，則串的l個數字位之間的空隙標記為1，2，…，l-１。隨機地從[1，l-1]中選取一整數位置k，則將兩個父母串中從位置k到串末尾的子串互相交換，而形成兩個新串。第十頁，共三十一頁，2022年，8月28日10本例中初始種群的兩個個體

假定從１到４間選取隨機數，得到k＝４，那么經過交叉操作之后將得到如下兩個新串(二)交叉操作

第十一頁，共三十一頁，2022年，8月28日11新串號匹配池匹配對象交叉點新種群x值適配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256總計1754平均439最大值729交叉操作

第十二頁，共三十一頁，2022年，8月28日12(三)變異

變異(Mutation)是以很小的概率隨機地改變一個串位的值。變異的概率通常是很小的，一般只有千分之幾。變異操作相對于復制和交叉操作而言，是處于相對次要的地位，其目的是為了防止丟失一些有用的遺傳因子，變異操作可以起到恢復串位多樣性的作用。

第十三頁，共三十一頁，2022年，8月28日13二、遺傳算法的基本操作在經過一次復制、交叉和變異操作后，最優的和平均的目標函數值均有所提高。種群的平均適配度從293增至439，最大的適配度從575增至729。可見每經過這祥的一次遺傳算法步驟，問題的解便朝著最優解方向前進了一步。第十四頁，共三十一頁，2022年，8月28日14三、遺傳算法的特點1)遺傳算法是對參數的編碼進行操作，而不是對參數本身；

2)遺傳算法是從許多初始點開始并行操作，因而可以有效地防止搜索過程收斂于局部最優解，而且有較大的可能求得全部最優解；

3)遺傳算法通過目標函數來計算適配度，而不需要其它的推導和附屬信息，從而對問題的依賴性較??；

4)遺傳算法使用概率的轉變規則，而不是確定性的規則；

5)遺傳算法在解空間內不是盲目地窮舉或完全隨機測試，而是一種啟發式搜索，其搜索效率往往優于其它方法；

6)遺傳算法對于待尋優的函數基本無限制，因而應用范圍很廣；

7)遺傳算法更適合大規模復雜問題的優化。

第十五頁，共三十一頁，2022年，8月28日15四、遺傳算法的模式理論

某些子串模式(schemata)在遺傳算法的運行中起著關鍵的作用。在上面的例子中，樣本串第1位的“1”使得適配度比較大，首位為“1”的子串可以表示成這樣的模式：1****其中*是通配符，它既可代表“1”，也可代表“0”。用｛0,

1,*}可以構造出任意一種模式。

第十六頁，共三十一頁，2022年，8月28日16四、遺傳算法的模式理論稱一個模式與一個特定的串相匹配是指：該模式中的1與串中的1相匹配模式中的0與串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配兩個串：00100，00000模式*11*0匹配四個串：01100，01110，11100，11110第十七頁，共三十一頁，2022年，8月28日17四、遺傳算法的模式理論對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。對一般的問題，若串的基為k，長度為l，則總共有種模式。可見模式的數量要大于串的數量。

第十八頁，共三十一頁，2022年，8月28日18四、遺傳算法的模式理論一般地，一個串中包含種模式。例如串11111是個模式的成員，因為它可以與每個串位是1或*的任一模式相匹配。因此，對于大小為n的種群則包含有到n×種模式。設一個7位二進制串可以用如下的符號來表示這里每個代表一個二值特性(也稱為基因)。

第十九頁，共三十一頁，2022年，8月28日19四、遺傳算法的模式理論引入兩個模式的屬性定義：模式次數和定義長度。一個模式H的次數由O(H)表示，它等于模式中固定串位的個數。例如模式H＝011*1**，其次數為4，記為O(H)=4。模式H的長度定義為模式中第一個確定位置和最后一個確定位置之間的距離，用符號(H)表示。例如模式H＝011*1**，其中第一個確定位置是1，最后一個位置是5，所以(H)=5-1=4。若模式H＝******0，則(H)=0。

第二十頁，共三十一頁，2022年，8月28日20(一)復制對模式的影響在某一世代t，種群A(t)包含有m個特定模式，記為m=m(H,t)在復制過程中，A(t)中的任何一個串以概率被選中進行復制。因此可以期望在復制完成后，在t+1世代，特定模式H的數量將變為

或寫成（１）其中f(H)表示在世代t時對應于模式H

的串的平均適配度。是整個種群的平均適配度。第二十一頁，共三十一頁，2022年，8月28日21(一)復制對模式的影響為了進一步分析高于平均適配度的模式數量增長，設

c>0則上面的方程可改寫為如下的差分方程假定c為常數，可得

(2)

可見，對于高于平均適配度的模式數量將呈指數形式增長。

第二十二頁，共三十一頁，2022年，8月28日22(二)交叉對模式的影響

交叉過程是串之間的有組織的然而又是隨機的信息交換，它在創建新結構的同時，最低限度地破壞復制過程所選擇的高適配度模式。考察一個l＝7的串以及此串所包含的兩個代表模式。A＝0111000

第二十三頁，共三十一頁，2022年，8月28日23(二)交叉對模式的影響推廣到一般情況，可以計算出任何模式的交叉存活概率的下限為中大于號表示當交叉點落入定義長度內時也存在模式不被破壞的可能性。

一般情況若設交叉的概率力，則上式變為

(3)第二十四頁，共三十一頁，2022年，8月28日24若綜合考慮復制和交叉的影響，特定模式在下一代中的數量可用下式來估計

(4)可見，對于那些高于平均適配度且具有短的定義長度的模式將更多地出現在下一代中。

(二)交叉對模式的影響第二十五頁，共三十一頁，2022年，8月28日25(三)變異對模式的影響

第二十六頁，共三十一頁，2022年，8月28日26四、遺傳算法的模式理論綜合考慮上述復制、交叉及變異操作，可得特定模式H的數量改變為

(6)第二十七頁，共三十一頁，2022年，8月28日27五、遺傳算法中的參數選擇

初始種群的大小n:選擇較大數目的初始種群可以同時處理更多的解，因此容易找到全局的最優解，其缺點是增加了每次迭代所需要的時間。交叉概率pc：交叉概率的選擇決定了交叉操作的頻率。頻率越高，可以越快地收斂到最有希望的最優解區域；但是太高的頻率也可能導致收斂于一個解。變異概率pm：變異概率通常只取較小的數值，一般為0.001～0.1。若選取高的變異率，一方面可以增加樣本模式的多樣性，另一方面可能引起不穩定，但是若選取太小的變異概率，則可能難于找到全局的最優解。

第二十八頁，共三十一頁，2022年，8月28日28六、遺傳算法的改進

(1)自適應變異

:在交叉之前，以海明(Hamming)距離測定雙親基因碼的差異，根據測定值決定后代的變異概率。若雙親的差異較小，則選取較大的變異概率。

(2)優秀個體保護法

：對于每代中一定數量的最優個體，使之直接進入下一代。這樣可以防止優秀個體由于選擇、交叉或變異中的偶然因素而被破壞掉。

(3)移民法

：用交叉產生出的個體替換上一代中適應度低的個體，繼而