國科大中科院算法講義遺傳算法1210

1、啟發(fā)式算法啟發(fā)式算法三、遺傳算法三、遺傳算法生物進(jìn)化 生命自從在地球上誕生以來，就開始了漫長的生物演化歷程，低級、簡單的生物類型逐漸發(fā)展為高級、復(fù)雜的生物類型。這一過程已經(jīng)由古生物學(xué)、胚胎學(xué)和比較解剖學(xué)等方面的研究工作所證實。生物進(jìn)化的原因自古至今有著各種不同的解釋，其中被人們廣泛接受的是達(dá)爾文的自然選擇學(xué)說。 復(fù)雜高級簡單低級生物進(jìn)化, 1825年至1828年在愛丁大學(xué)學(xué)醫(yī)，后進(jìn)入劍橋大學(xué)學(xué)習(xí)神學(xué)。1831年從劍橋大學(xué)畢業(yè)后，以博物學(xué)家的身份乘海軍勘探船“貝格爾號（Beagle）”作歷時5年（18311836）的環(huán)球旅行，觀察和搜集了動物、植物和地質(zhì)等方面的大量材料，經(jīng)過歸納整理和綜合分析，

2、形成了生物進(jìn)化的概念。 1859年出版物種起源（On the Origin of Species），全面提出以自然選擇（Theory of Natural Selection）為基礎(chǔ)的進(jìn)化學(xué)說。該書出版震動當(dāng)時的學(xué)術(shù)界，成為生物學(xué)史上的一個轉(zhuǎn)折點。自然選擇的進(jìn)化學(xué)說對各種唯心的神造論、目的論和物種不變論提出根本性的挑戰(zhàn)。使當(dāng)時生物學(xué)各領(lǐng)域已經(jīng)形成的概念和觀念發(fā)生根本性的改變。 達(dá)爾文（Charles Robert Darwin，18091882）英國博物學(xué)家，進(jìn)化論的奠基人。1809年2月12日，出生于英國醫(yī)生家庭。物競天擇，適者生存 自然選擇學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭。生存

3、斗爭包括種內(nèi)斗爭、種間斗爭以及生物與無機環(huán)境之間的斗爭三個方面。在生存斗爭中，具有有利變異(mutation)的個體容易存活下來，并且有更多的機會將有利變異傳給后代，具有不利變異的個體容易被淘汰，產(chǎn)生后代的機會也少得多。因此，凡是在生存斗爭中獲勝的個體都是對環(huán)境適應(yīng)性比較強的。達(dá)爾文把這種在生存斗爭中適者生存、不適者淘汰的過程叫做自然選擇。達(dá)爾文的自然選擇學(xué)說表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。遺傳算法（Genetic Algorithm） 遺傳算法借鑒生物界自然選擇原理和自然遺傳機制而形成的一種迭代式自適應(yīng)概率性全局優(yōu)化搜索算法。 模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵好的結(jié)構(gòu) 模

4、擬孟德爾遺傳變異理論在迭代過程中保持已有結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu) 70年代初期由美國Michigan大學(xué)的Holland教授發(fā)展起來的。 以1975年Holland的專著Adaptation in natural and Artificial systems出版為標(biāo)志。遺傳算法 基本思想：從一組解的初值開始進(jìn)行搜索，這組解稱為一個種群，種群由一定數(shù)量、通過基因編碼的個體組成，其中每一個個體稱為染色體。不同個體通過染色體的復(fù)制、交叉和變異又生成新的個體，依照適者生存的規(guī)則，個體也在一代一代進(jìn)化，通過若干代的進(jìn)化最終得出條件最優(yōu)的個體。遺傳算法（GA） 個體（Individual）就是模擬生物個體

5、而對問題中的候選解的一種稱呼，一個個體也就是搜索空間中的一個點。 種群（ population ）：是模擬生物種群而由若干個體組成的群體, 它一般是整個搜索空間的一個很小的子集。種群中含有的個體的數(shù)量叫做種群的規(guī)模(population size)。人工智能范疇 符號智能的特點是以知識為基礎(chǔ)，偏重于邏輯推理 計算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計算。 遺傳算法演化計算計算智能考慮如下優(yōu)化問題：這里f是X上的一個正值函數(shù)，即對任意xX，f(x)0。X是問題的解空間，即問題的所有可能解全體。它可以是一個有限集合(如組合優(yōu)化問題)，也可以是實空間Rn的一個子集(如連續(xù)優(yōu)化問題)等。對以上問題，我們通

6、常用兩類方法來求解之，一類是解析法，通過一定的手段直接計算出問題的解，另一類是迭代法，給出問題的一個初始猜測，然后從此初始點出發(fā)，逐步迭代，直至達(dá)到停機條件。遺傳算法也是一種迭代法，但它有別于傳統(tǒng)的迭代法。| )(maxXxxf設(shè)計一個遺傳算法要涉及到以下步驟：確定編碼方案確定適應(yīng)值函數(shù)選擇策略的確定遺傳算子的設(shè)計確定算法的終止準(zhǔn)則(1) 控制參數(shù)的選取例12sin)( )(max10 xxexxfxf，編碼方案變量是演化算法的表現(xiàn)型形式。編碼是將優(yōu)化問題解空間中可行解（個體），即設(shè)計變量映射到GA中的基因型數(shù)據(jù)結(jié)構(gòu)。我們這里采用二進(jìn)制編碼，將某個變量值代表的個體表示為一個0,1二進(jìn)制串。串長

7、取決于求解的精度。如果確定求解精度到3位小數(shù)，由于區(qū)間長度為1，編碼的二進(jìn)制串長至少需要10位。 二進(jìn)制串轉(zhuǎn)化為十進(jìn)制：如： s= x=561 x=0.548 與表示區(qū)間端點0和1。)2(900123456789xbbbbbbbbbbbiii12110 xx 基因型：1000110001 表現(xiàn)型：0.548 編碼解碼個體（染色體）基因隨機生成初始種群：S1=, x1 = 0.890S2= , x2 = 0.320S3=, x3 = 0.200S4=, x4 = 0.738S5=, x5 = 0.607S6=, x6 = 0.461S7=, x7 = 0.950S8=, x8 = 0.036構(gòu)造

8、適應(yīng)值函數(shù)直接將目標(biāo)函數(shù)作為適應(yīng)值函數(shù): f(x) =sinx+2e-x -1有了適應(yīng)值函數(shù)，可以對初始種群進(jìn)行評估。 S1(0)= ,f(x1)= 0.598 S2 (0) = , f(x2)=0.767 S3 (0) = , f(x3)=0.836 S4 (0) = , f(x4)=0.629 S5 (0) = , f(x5)=0.660 S6 (0) = , f(x6)=0.706 S7 (0) = , f(x7)=0.578 S8 (0) = , f(x8)=0.965選擇策略基于適應(yīng)值比例的選擇：繁殖池(breeding pool)選擇首先按下式計算其相對適應(yīng)值：其中fi是群體中第i

9、個個體的適應(yīng)值，N是群體的規(guī)模。每個個體的繁殖量為：Ni=round(reli N)其中round(x) 表示與x距離最小的整數(shù)。將每個個體復(fù)制Ni個生成一個臨時群體，即繁殖池。Niiiiffrel1輪盤賭選擇方法 輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個體i 的適應(yīng)度為 Fi，則個體i 被選中遺傳到下一代群體的概率為： niiiiFFP1/ ABCDErel2=0.134, N2=1rel3=0.146, N3=1rel4=0.110, N4=1rel5=0.115, N5=1rel6=0.123, N6=1rel7=0

10、.101, N7=1rel8=0.168, N8=1繁殖池：s1(0), s2 (0), s3 (0), s4 (0), s5 (0), s6 (0), s7 (0) , s8 (0)1)8( ,104. 0 ,739. 5)(1111181)0(relroundNffrelsfNiiii 遺傳算子的設(shè)計a. 雜交單點雜交：雜交概率pc =0.75，6個個體參加雜交s2(0)和s6 (0), s1(0)和s5(0), s3(0)和s4(0)s2(0) = s2=, f(s2)=0.644s6(0) = s6=, f(s6)=0.712s1(0) = s1=, f(s1)=0.580s5(0)

11、= s5=, f(s5)=0.687s3(0) = s3=, f(s3)=0.834s4(0) = s4=, f(s4)=0.629b. 變異變異概率pm=0.02，10*8*0.02=1.6，隨機選取2個基因位進(jìn)行變異s6(0)= s6= f(s6)=0.704s3(0) = s3= f(s2)=0.880新群體：所有子代和父代中最好的8個個體404. 6)(81)1(iisf704. 0)( 0111011100706. 0)( 0111011000712. 0)( 0111000111767. 0)( 0101000111834. 0)( 0011001111 836. 0)( 0011

12、001101880. 0)( 00100011010.965=)( 0000100101= )1(8)1(8)1(7)1(7)1(6)1(6)1(5)1(5)1(4)1(4)1(3)1(3)1(2)1(2)1(1)1(1sfssfssfssfssfssfssfssfs，(5) 確定算法的終止準(zhǔn)則a. 遺傳運算的終止進(jìn)化代數(shù)T，一般取為100500b. 最好個體在若干代內(nèi)無改變(6) 控制參數(shù)的選取a. 種群規(guī)模N，一般取為20100b.雜交概率pc，一般取為0.40.9c. 變異概率pm, 一般取為0.0010.1SGA的形式化描述 GA(P(0), N, l, s, g, p, f, t)

13、初始種群：P(0)(a1(0), a2(0),aN(0) IN 位串空間：I=0,1l ， l表示二進(jìn)制串的長度 種群規(guī)模：N 選擇策略：s: ININ 遺傳算子g：通常包括繁殖算子Or: II、雜交算子Oc: II II和變異算子Om: II 遺傳算子的操作概率p：包括繁殖概率pr、雜交概率pc和變異概率pm； f: IR+是適應(yīng)函數(shù)； t:IN 0, 1是終止準(zhǔn)則。SGA的流程圖產(chǎn)生初始群體產(chǎn)生初始群體是否滿足停止準(zhǔn)則是否滿足停止準(zhǔn)則是是輸出結(jié)果并結(jié)束輸出結(jié)果并結(jié)束計算個體適應(yīng)度值計算個體適應(yīng)度值比例選擇運算比例選擇運算單點交叉運算單點交叉運算基本位變異運算基本位變異運算否否產(chǎn)生新一代群體

14、產(chǎn)生新一代群體SGA的理論基礎(chǔ)（1） 模式模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即 0 或者 1，如101*1。 模式 H 中確定位置的個數(shù)稱為模式 H 的階，記作O(H)。例如O(10*1)=3 。 模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式 H 的定義距，記作(H)。例如(10*1)=4 。 SGA的理論基礎(chǔ)（2） 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的

15、性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 SGA的理論基礎(chǔ)（3） 模式定理模式定理（Schema Theorem）（）（ Holland 1975，自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性 ）：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性，從理論上保證了遺傳算法是一個可以尋求最優(yōu)可行解的優(yōu)化過程，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)，被認(rèn)為是遺傳算法的基本定理。 SGA的理論基礎(chǔ)（4） 設(shè)X=IN=(0,1l)N 為SGA群體狀態(tài)的空間， 是任一模式， 表示SGA在

16、第t 代時的群體，f：I R1 為適應(yīng)函數(shù) 模式H的平均適應(yīng)值： P(t)的平均適應(yīng)值：llVH, 1 , 0XtxtxtxtPN)(,),(),()(21)()(| )(|1),(tPHxxftPHtHf)(/ )()(tPxNxftfSGA的理論基礎(chǔ)（5） 設(shè)SGA的雜交概率和變異概率分別為pc 和pm，模式H 的定義長度為 、階為 ，第t+1代群體P(t+1)含有H 中元素個數(shù)的期望值記為 則： )(H)(Ho|) 1(|tPHE)(1)(1 )(),(| )(|) 1(|mcpHolHptftHftPHtPHESGA的理論基礎(chǔ)（6） 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)

17、度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 遺傳算法的收斂性(1) 種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收

18、斂于全局最優(yōu)解。遺傳算法的收斂性(2) 交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。 變異操作是對種群模式的擾動，有利于增加種群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。遺傳算法的本質(zhì) 遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，

19、最終得到問題的最優(yōu)解。 遺傳算法的特點 （1）群體搜索，易于并行化處理； （2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。遺傳算法的改進(jìn) 遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。 遺傳算法的改進(jìn)途徑（1）對編碼方式的改進(jìn) （2）對遺傳算子 的改進(jìn)（3）對控制參數(shù)的改進(jìn) （4）對執(zhí)行策略的改進(jìn) 編碼方式 在設(shè)計遺傳算法時，編碼表示與遺傳算子尤其是雜交算子是同步考慮的，如果編碼處理不當(dāng)，在遺傳空間中因雜交而生成的個體映射到問題空間時

20、，有可能成為無用解，我們稱形成無用解的染色體為致死因子。同時，即使逆映射到問題空間的是有用解，但也可能是和雙親完全無緣的解。編碼要避免在問題空間中形成這些不適當(dāng)?shù)膫€體。評估編碼策略常采用以下3個規(guī)范： 1. 完備性(completeness)：問題空間中的所有點(候選解)都能作為演化空間中的點(染色體)表現(xiàn)； 2. 健全性(soundness)：演化空間中的染色體能對應(yīng)所有問題空間中的候選解； 3.非冗余性(nonredundancy)：染色體和候選解一一對應(yīng)。 二進(jìn)制編碼（Binary Encoding）將原問題的解空間映射到位串空間0,1l上，然后在位串空間上進(jìn)行演化操作。結(jié)果再通過解碼過

21、程還原成其表現(xiàn)型以進(jìn)行適應(yīng)值的評估。很多數(shù)值與非數(shù)值問題都可以用二進(jìn)制編碼以應(yīng)用演化算法。二進(jìn)制編碼有如下優(yōu)點：二進(jìn)制編碼類似于生物染色體的組成，算法易于用生物遺傳理論來解釋并使得演化操作如雜交、變異很容易實現(xiàn)；采用二進(jìn)制編碼時，算法處理的模式數(shù)最多；1.這種編碼方式便于模式定理進(jìn)行分析，因為模式定理就是以二值編碼為基礎(chǔ)的。 二進(jìn)制編碼在求解連續(xù)數(shù)值優(yōu)化問題時的缺點：相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，這種缺陷將降低演化算子的搜索效率，二進(jìn)制編碼的這一缺點有時稱為Hamming懸崖（Hamming Cliffs）；二進(jìn)制編碼時，所需解的精度確定后，串長也就確定了，當(dāng)需要改變精

22、度時，很難在算法執(zhí)行過程中進(jìn)行調(diào)整，從而使算法缺乏微調(diào)的功能；當(dāng)應(yīng)用于高維、高精度數(shù)值問題時，產(chǎn)生的二進(jìn)制位串很長，搜索空間非常大，從而使算法的搜索效率很低。 格雷編碼（Gray Encoding）格雷編碼也稱為反射二進(jìn)制編碼，其目的是克服二進(jìn)制編碼的Hamming懸崖的缺點。格雷編碼使得兩個相鄰的整數(shù)的編碼只差一個二進(jìn)制位。二進(jìn)制串與格雷串的轉(zhuǎn)換關(guān)系如下： 設(shè)二進(jìn)制串 對應(yīng)的格雷串為 ，則它們之間有如下的變換關(guān)系： 其中 表示模2加法運算。 ，kkkkk11,11如果如果n,21n,21格雷編碼（Gray Encoding） Binary Code Gray Code 00000000100

23、1010011011010100110101111110101111100引入了另一種形式的cliff!實數(shù)編碼 為了克服二進(jìn)制編碼的缺點，對于問題的變量是實向量的情形，可以直接采用實進(jìn)制進(jìn)行編碼。這樣，便可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力。 “在人工遺傳和演化搜索方案中，實型編碼或浮點基因的使用已經(jīng)有很長的歷史了，盡管是有爭議的，但它們在以后的使用趨勢仍在上升。這種上升的使用趨勢多少有些使熟知基本遺傳算法(GA)理論的研究者感到驚訝，因為簡單的分析似乎建議通過使用低基數(shù)性的字母表可以增強模式的處理，而來自于實算的結(jié)論似乎直接反駁了這種觀點，實型編碼在許多實際問題里工作得較好?！保?Goldberg ） 對實數(shù)編碼的情形，從理論上講，二進(jìn)制編碼下的各種遺傳操作同樣可以使用，因為在機器中實數(shù)也是采用二