1、第5章 遺傳算法,華南理工大學(xué)電子與信息學(xué)院,內(nèi)容提要,1. 遺傳算法概述 2. 遺傳算法收斂性分析 3. 遺傳算法的改進(jìn) 4. 遺傳算法的應(yīng)用,智能優(yōu)化算法又稱現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)且適合于并行處理的算法。 這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。 遺傳算法屬于智能優(yōu)化算法之一。,智能優(yōu)化算法概述,常用的智能優(yōu)化算法,遺傳算法 模擬退火算法 禁忌搜索算法 粒子群算法 蟻群算法 ,智能優(yōu)化算法的特點(diǎn),從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個求解空間中探索最優(yōu)解。 求解的過程通常是一個迭代的過程，即不

2、是一步就完成。 由于它們可以把搜索空間擴(kuò)展到整個問題空間，因而具有全局優(yōu)化性能。,遺傳算法概述,遺傳算法是由美國的J. Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性中首先提出的。 借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。 模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象。,在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 基本遺傳算法（Simple Genetic Algorithms，GA)又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），

3、是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。,遺傳算法概述,基本遺傳算法的組成,（1）編碼（產(chǎn)生初始種群） （2）適應(yīng)度函數(shù) （3）遺傳算子（選擇、交叉、變異） （4）運(yùn)行參數(shù),編碼,遺傳算法（GA）通過某種編碼機(jī)制把對象抽象為由特定符號按一定順序排成的串。 正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。 基本遺傳算法（SGA）使用二進(jìn)制串進(jìn)行編碼。,求下列一元函數(shù)的最大值：,其中x-1, 2 ，求解結(jié)果精確到6位小數(shù)。,編碼示例,分析 區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為310

4、6等份。 又因為221 3106 222 ，所以二進(jìn)制編碼長度至少需要22位。 編碼過程實質(zhì)是將區(qū)間-1，2內(nèi)對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進(jìn)制串（b21b20b19b18b0）。,101010111111101011000,編碼示例,編碼與實數(shù)的轉(zhuǎn)換,基因型：1000101110110101000111,表現(xiàn)型：0.637197,編碼,解碼,個體（染色體）,基因,初始種群,基本遺傳算法（SGA）采用隨機(jī)方法生成若干個個體的集合，該集合稱為初始種群。 初始種群中個體的數(shù)量稱為種群規(guī)模。,適應(yīng)度函數(shù),遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。 適應(yīng)度函數(shù)是遺傳

5、算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。,選擇算子,遺傳算法使用選擇運(yùn)算對個體進(jìn)行優(yōu)勝劣汰操作。 適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。 選擇操作的任務(wù)就是從父代群體中選取一些個體，遺傳到下一代群體。 基本遺傳算法（SGA）中選擇算子采用輪盤賭選擇方法。,一等獎,二等獎,三等獎,四等獎,輪盤賭選擇方法,輪盤賭選擇方法,輪盤賭選擇又稱比例選擇算子，其基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。 設(shè)群體大小為N，個體xi 的適應(yīng)度為 f(xi)，則個體xi的選擇概率為：,輪盤賭選擇法

6、可用如下過程模擬來實現(xiàn)： (1)在0, 1內(nèi)產(chǎn)生一個均勻分布的隨機(jī)數(shù)r。 (2)若rq1,則染色體x1被選中。 (3)若qk-1rqk(2kN), 則染色體xk被選中。 其中的qi稱為染色體xi (i=1, 2, , n)的積累概率, 其計算公式為,輪盤賭選擇方法,積累概率實例：,輪盤賭選擇方法,積累概率,概率,輪盤賭選擇方法,輪盤賭選擇方法的實現(xiàn)步驟: （1）計算群體中所有個體的適應(yīng)度值； （2）計算每個個體的選擇概率； （3）計算積累概率； （4）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個個體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個個體是否遺傳到下一代群體中。,輪盤賭選擇方法,例如

7、，有染色體 s1= 13 (01101) s2= 24 (11000) s3= 8 (01000) s4= 19 (10011) 假定適應(yīng)度為f (s)=s2 ，則 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361,染色體的選擇概率為,染色體的累計概率為,例如設(shè)從區(qū)間0, 1中產(chǎn)生4個隨機(jī)數(shù): r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503,交叉算子,交叉運(yùn)算，是指對兩個

8、相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。 交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 基本遺傳算法（SGA）中交叉算子采用單點(diǎn)交叉算子。,單點(diǎn)交叉運(yùn)算,交叉前： 01000|01110000000010000 11100|00000111111000101 交叉后： 01000|00000111111000101 11100|01110000000010000,交叉點(diǎn),變異算子,變異運(yùn)算，是指改變個體編碼串中的某些基因值，從而形成新的個體。 變異運(yùn)算是產(chǎn)生新個體的輔助方法，決定遺傳算法的局部

9、搜索能力，保持種群多樣性。 交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 基本遺傳算法（SGA）中變異算子采用基本位變異算子。,基本位變異算子是指對個體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。 對于二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，若原有基因值為1，則將其變?yōu)? 。,變異算子,基本位變異算子的執(zhí)行過程,變異前： 000001110000000010000 變異后： 000001110001000010000,變異點(diǎn),運(yùn)行參數(shù),（1）M ：種群規(guī)模 （2）T ： 遺傳運(yùn)算的終止進(jìn)化代數(shù) （3）Pc

10、：交叉概率 （4）Pm ：變異概率,基本遺傳算法的框圖,遺傳算法的特點(diǎn),（1）群體搜索，易于并行化處理； （2）不是盲目窮舉，而是啟發(fā)式搜索； （3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。,遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。 與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。,遺傳算法收斂性分析,種群規(guī)模對收斂性的影響,通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差。 種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩

11、慢。,選擇操作對收斂性的影響,選擇操作使高適應(yīng)度個體以更大的概率生存，從而提高遺傳算法的全局收斂性。 如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。,交叉概率對收斂性的影響,交叉操作作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。 交叉概率太大時，種群中個體更新快，會造成高適應(yīng)度值的個體很快被破壞掉。 概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。,變異概率對收斂性的影響,變異操作是對種群模式的擾動，有利于增加種群的多樣性 。 變異概率太小則很難產(chǎn)生新模式。 變異

12、概率太大則會使遺傳算法成為隨機(jī)搜索算法。,遺傳算法的本質(zhì),遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。 通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。,遺傳算法進(jìn)化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運(yùn)算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。,遺傳算法的改進(jìn),遺傳欺騙問題,局部最優(yōu),全局最優(yōu),0 A B x,y,遺傳算法的改進(jìn)途徑,（1）對編碼方式的改進(jìn) （2）對遺傳算子的改進(jìn) （3）對控制參數(shù)的改進(jìn) （4）

13、對執(zhí)行策略的改進(jìn),對編碼方式的改進(jìn),二進(jìn)制編碼優(yōu)點(diǎn)在于編碼、解碼操作簡單，交叉、變異等操作便于實現(xiàn)，缺點(diǎn)在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴(kuò)大，遺傳算法的性能降低。 格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題 ，浮點(diǎn)數(shù)編碼改善了遺傳算法的計算復(fù)雜性 。,對遺傳算子的改進(jìn)排序選擇,（1） 對所有個體按其適應(yīng)度進(jìn)行降序排序； （2） 根據(jù)具體求解問題，設(shè)計一個概率分配表，將概率值按排列次序分配給各個體； （3） 以各個體的概率值作為其遺傳到下一代的概率，用賭盤選擇法來產(chǎn)生下一代群體。 適應(yīng)度排序： 625， 462， 284， 221， 98 概率分配： 0.30，0.25，0.2

14、0，0.15，0.10,對遺傳算子的改進(jìn)均勻交叉,（1） 隨機(jī)產(chǎn)生一個編碼長度相同的二進(jìn)制屏蔽字P = W1W2Wn ； （2） 按下列規(guī)則從A、B兩個父代產(chǎn)生兩個子代X、Y： 若Wi = 0，則X的第i個基因繼承A的對應(yīng)基因，Y的第i個基因繼承B的對應(yīng)基因； 若Wi = 1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。,屏蔽字：0 1 0 1 0 0 0 父代A： 0 1 0 0 1 1 1 父代B： 1 0 1 1 1 1 0 子代X： 0 0 0 1 1 1 1 子代Y： 1 1 1 0 1 1 0,對遺傳算子的改進(jìn)均勻交叉,對遺傳算子的改進(jìn)逆序變異,變異前： 9 4 8

15、| 7 3 6 5 | 1 2 變異后： 9 4 8 | 5 6 3 7 | 1 2,對控制參數(shù)的改進(jìn),Schaffer建議的最優(yōu)參數(shù)范圍是： M = 20 100， T = 100 500， Pc = 0.4 0.9， Pm = 0.001 0.01。 改進(jìn)方式是參數(shù)自適應(yīng)調(diào)整。,對執(zhí)行策略的改進(jìn),混合遺傳算法 免疫遺傳算法 小生境遺傳算法 單親遺傳算法 并行遺傳算法,（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機(jī)器學(xué)習(xí) （7）人工生命 （8）數(shù)據(jù)挖掘,遺傳算法的應(yīng)用,已知x為整數(shù)，利用遺傳算法求解區(qū)間0, 31上的二次函數(shù)y=x2的最大值。,遺傳算

16、法的應(yīng)用舉例,遺傳算法的應(yīng)用舉例,分析 原問題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使 y 取最大值的點(diǎn) a 的問題。 個體：0, 31 中的任意點(diǎn)x 適應(yīng)度：函數(shù)值f(x)=x2 解空間：區(qū)間0, 31 這樣, 只要能給出個體x的適當(dāng)染色體編碼, 該問題就可以用遺傳算法來解決。,解 (1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。 將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群S1 s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定義適應(yīng)度函數(shù), 取適應(yīng)度函數(shù) f (x)=x2,(3) 計算各代

17、種群中的各個體的適應(yīng)度, 并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個體，即31（11111）出現(xiàn)為止。 ,首先計算種群S1中各個體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的適應(yīng)度f (si), 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361,再計算種群S1中各個體的選擇概率。,由此可求得 P(s1) = P(13) = 0.14 P(s2) = P

18、(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,再計算種群S1中各個體的積累概率,選擇-復(fù)制,設(shè)從區(qū)間0, 1中產(chǎn)生4個隨機(jī)數(shù)如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503,于是，經(jīng)復(fù)制得群體： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19）,被選中兩次,交叉 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。 設(shè)s1與s2配對，s3與s4配對。 s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 分別交換后兩位基因，得新染色體： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,變異 設(shè)變異率pm=0.001。 這樣，群體S1中共有 540.001=0.02 位基因可以變異。 0.02位顯然不足1位，所以本輪遺傳操作不做變異。,于是，得到第二代種群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,第二代種群S2中各染色體的情況,假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中