遺傳算法及應(yīng)用補

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

Darwin的進化論：

優(yōu)勝劣汰，適者生存。

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

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

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

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

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

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

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

初始種群的產(chǎn)生

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

01101、11000、01000、10011

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3)遺傳算法通過目標函數(shù)來計算適配度，而不需要其它的推導(dǎo)和附屬信息，從而對問題的依賴性較?。?/p>

4)遺傳算法使用概率的轉(zhuǎn)變規(guī)則，而不是確定性的規(guī)則；

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

6)遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，因而應(yīng)用范圍很廣；

7)遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。

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

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

1,*}可以構(gòu)造出任意一種模式。

第十六頁，共三十一頁，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，則總共有種模式?？梢娔Ｊ降臄?shù)量要大于串的數(shù)量。

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

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

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

或?qū)懗桑ǎ保┢渲衒(H)表示在世代t時對應(yīng)于模式H

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

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

(2)

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

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

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

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

一般情況若設(shè)交叉的概率力，則上式變?yōu)?/p>

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

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

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

第二十六頁，共三十一頁，2022年，8月28日26四、遺傳算法的模式理論綜合考慮上述復(fù)制、交叉及變異操作，可得特定模式H的數(shù)量改變?yōu)?/p>

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

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

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

(1)自適應(yīng)變異

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

(2)優(yōu)秀個體保護法

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

(3)移民法

：用交叉產(chǎn)生出的個體替換上一代中適應(yīng)度低的個體，繼而