遺傳算法的應(yīng)用

1、遺傳算法（Genetic Algorithm）Natural Computing,1、算法起源2、基本術(shù)語和遺傳算子3、模式定理4、遺傳算法的應(yīng)用,算法起源,遺傳算法（簡稱GA）的基本思想起源于生物體的遺傳進(jìn)化。生物的進(jìn)化是發(fā)生在作為生物體結(jié)構(gòu)編碼的染色體上，染色體主要是由DNA和蛋白質(zhì)組成，其中DNA又是最主要的遺傳物質(zhì)，它儲(chǔ)存著遺傳信息，可以準(zhǔn)確地復(fù)制，也能夠發(fā)生突變，并可通過控制蛋白質(zhì)的合成而控制生物的性狀。生物的遺傳特

2、性，使生物界的物種能夠保持相對(duì)的穩(wěn)定；生物的變異特性，使生物個(gè)體產(chǎn)生新的性狀，以至于形成了新的物種，推動(dòng)了生物的進(jìn)化和發(fā)展。遺傳算法正是模擬這一過程，通過向自然學(xué)習(xí)來求解問題。,算法起源,1975年，美國Michigan大學(xué)的Holland教授出版了系統(tǒng)論述遺傳算法的第一本專著，標(biāo)志著遺傳算法的誕生。80年代，遺傳算法得到了廣泛應(yīng)用與研究。1989年，D.J.Goldberg出版了他的著作，對(duì)遺傳算法作了系統(tǒng)的闡述，確立了現(xiàn)代遺傳

3、算法的基礎(chǔ)。,基本遺傳算法是一種概率搜索算法，利用編碼技術(shù)作用于稱為染色體（chromosome）的二進(jìn)制數(shù)串，模擬由這些串組成的群體的進(jìn)化過程。類似于自然進(jìn)化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。遺傳算法通過有組織的然而是隨機(jī)的信息交換來重新結(jié)合那些適應(yīng)性好的串。雖是一類隨機(jī)算法，但又不是簡單的隨機(jī)走動(dòng)，它可以有效利用已有的信息來搜尋那些有希望改善解質(zhì)量的串。與自然界相似，遺傳算法對(duì)求解問題本身一無所知，

4、它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。,基本術(shù)語和遺傳算子,定義1 將待解決問題的解變量用某種編碼技術(shù)編制成特定形式的數(shù)字串，稱這個(gè)數(shù)字串為染色體（chromosome）；數(shù)字串的每位數(shù)字碼稱為基因（gene）（基本GA中，采用二進(jìn)制編碼串），串的長度即為染色體的長度定義2 由一定數(shù)目的同等長度染色體組成的集合稱為一個(gè)種群（population

5、）；相應(yīng)的染色體稱為種群的一個(gè)個(gè)體（individual）定義3 根據(jù)擬定的函數(shù)對(duì)個(gè)體性質(zhì)評(píng)價(jià)的一種度量，稱為個(gè)體的適應(yīng)值或適應(yīng)度（fitness）,基本術(shù)語和遺傳算子,定義 4 對(duì)兩個(gè)個(gè)體進(jìn)行部分基因互換，產(chǎn)生兩個(gè)新個(gè)體的操作，稱為交叉或雜交運(yùn)算（crossover）定義 5 對(duì)個(gè)體的某些基因進(jìn)行改變，產(chǎn)生新個(gè)體的操作，稱作變異運(yùn)算（mutation）定義 6 從當(dāng)前種群中選出優(yōu)良的個(gè)體，使之有機(jī)會(huì)作為父代繁殖下一代

6、的操作，稱作選擇運(yùn)算（selection），或復(fù)制運(yùn)算（reproduction）,基本遺傳算子：以二進(jìn)制編碼為例,單點(diǎn)交叉: (隨機(jī)投點(diǎn)）X = 1 0 0 1 1 0 1 0 0; X’ = 0 1 0 1 1 0 1 0 0; Y = 0 1 0 1 1 1 0 1 1； Y’ = 1 0 0 1 1 1 0 1 1 ；兩點(diǎn)交叉：X = 1 0 0 1 1

7、0 1 0 0; X’ = 0 1 0 1 1 0 0 1 1 ; Y = 0 1 0 1 1 1 0 1 1； Y’ = 1 0 0 1 1 1 1 0 0 ； 或者 X” = 1 0 0 1 1 1 1 0 0;

8、 Y” = 0 1 0 1 1 0 0 1 1；,,,,,,,,,,,,基本遺傳算子：以二進(jìn)制編碼為例,單點(diǎn)變異: (隨機(jī)投點(diǎn)）X = 1 0 0 1 1 0 1 0 0; X’ = 1 0 1 1 1 0 1 0 0; Y = 0 1 0 1 1 1 0 1 1； Y’ = 1 1 0 1 1

9、 1 0 1 1 ；多點(diǎn)變異：X = 1 0 0 1 1 0 1 0 0; X’ = 1 1 0 1 0 0 1 0 1 ; Y = 0 1 0 1 1 1 0 1 1； Y’ = 1 0 0 1 1 1 1 1 1 ；,,,,,基本遺傳算子：以二進(jìn)制編碼為例,個(gè)體選擇復(fù)制: (賭輪原則）設(shè)種群規(guī)模為4,,,,,X4,X3,X2,X1,,,Roulette Whe

10、el Selection,標(biāo)準(zhǔn)遺傳算法（SGA） 考慮全局優(yōu)化問題（P） max{f(x)：x∈DRn→R1}遺傳算法基于以下兩條基本策略求解問題（P）：（a）對(duì)于給定的目標(biāo)函數(shù) f ，它使用 f 的任一適應(yīng)值函數(shù)（換言之，一個(gè)值域非負(fù)、與 f 有相同極點(diǎn)的函數(shù)）；（b）它不直接作用于實(shí)向量x，而是作用于x的某種編碼（最常見的為定長二進(jìn)制數(shù)串編碼）。所以，對(duì)于取定 f 的任一適應(yīng)值函數(shù)F

11、和固定長度為L的二進(jìn)制數(shù)串編碼，遺傳算法實(shí)質(zhì)上是通過求解組合優(yōu)化問題 （P’） max{F(x)：x∈S}來求解問題（P）的，這里S={0，1}L為D的編碼空間（即D中所有實(shí)變量的長度為L的二進(jìn)制數(shù)串編碼全體）。,Step 1 初始化：1.1 指定種群規(guī)模N，雜交概率Pc ，變異概率Pm及終止進(jìn)化準(zhǔn)則；1.2 隨機(jī)生成初始種群X(0)=(X1 (0) ，X2 (0) ，…，XN (0))∈S

12、N， 置k =0。Step 2 種群進(jìn)化：2.1 （選擇）依據(jù)Xi(k)的適應(yīng)值，隨機(jī)、獨(dú)立、重復(fù)地從X(k)中選取N個(gè)個(gè)體為母體；2.2 （交叉）依概率Pc獨(dú)立地對(duì)所選N個(gè)母體執(zhí)行雜交，以產(chǎn)生新的N個(gè)中間個(gè)體；2.3 （變異）依概率Pm獨(dú)立地對(duì)交叉生成的N個(gè)中間個(gè)體執(zhí)行變異，從而生成新一代種群X(k +1)=(X1 (k +1) ，X2 (k +1) ，…，XN (k +1)),Step 3 終止檢驗(yàn)：如果X（k+1）

13、已滿足預(yù)設(shè)的進(jìn)化終止原則，則停止；否則，置k = k +1，轉(zhuǎn)Step2。常見的終止條件有：1、 ,其中δ為給定的常數(shù)，與具體問題的求解精度有關(guān)；2、整個(gè)群體僅由某個(gè)個(gè)體生成；3、進(jìn)化次數(shù)超過預(yù)定的值。,,常見的選擇機(jī)制,1. 賭輪選擇（roulette wheel selection）；2.最佳保留（elitist model）；3．期望值模型（expected value model）選

14、擇機(jī)制; 在該模型選擇機(jī)制中，先按期望值Q的整數(shù)部分安排個(gè)體被選中的次數(shù)，而對(duì)期望值Q的小數(shù)部分可按下述幾種方式進(jìn)行處理：（1）   確定方式; （2）   賭輪方式; （3）  貝努利試驗(yàn)（Bernoulli Trials）方式,遺傳算法的改進(jìn)——精英策略,采用精英策略(優(yōu)、劣解同時(shí)保留)的遺傳算法是保持當(dāng)前一個(gè)最好解和最差解；最好解(the fittest)

15、不參與交叉和變異操作；最差解不參加交叉操作，但參加變異操作；,Step 1初始化：隨機(jī)產(chǎn)生一個(gè)規(guī)模為N的初始種群，其中每個(gè)個(gè)體為二進(jìn)制位串的形式。Step 2 計(jì)算適應(yīng)值并按序排列：計(jì)算種群中每個(gè)個(gè)體的適應(yīng)值，并把個(gè)體按適應(yīng)值從小到大排列。Step 3 選擇：把適應(yīng)值最大、最小的個(gè)體按1:1選擇，另外的N-2個(gè)個(gè)體根據(jù)每個(gè)個(gè)體的相對(duì)適應(yīng)值，計(jì)算每個(gè)個(gè)體被選擇的概率，進(jìn)行選擇操作。Step 4 交叉：從上述選擇后的種群中，除了最優(yōu)

16、、最差兩個(gè)個(gè)體外，隨機(jī)選擇兩個(gè)染色體，按一定的交叉概率Pc進(jìn)行基因變換，交換的位置隨機(jī)選取。Step 5 變異：從種群中，除了最優(yōu)、最差兩個(gè)個(gè)體外，隨機(jī)選擇一個(gè)染色體，按一定的變異概率Pm進(jìn)行基因變異；對(duì)最差的個(gè)體按增大后的變異概率 kPm (k取10-20)進(jìn)行基因變異。Step 6 若達(dá)到預(yù)設(shè)的進(jìn)化代數(shù)，則算法停止，否則，轉(zhuǎn)Step 2.,模式定理,定義： 基于三值字符集 {0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字

17、符串集的字符串稱作模式。模式是二值符號(hào)串的一種擴(kuò)展，其中基因的取值可為0，1或*。符號(hào)“*”稱作“無關(guān)符”，表示一種隨意的情況，也就是說基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是長為6位的二值符號(hào)串的模式。,包含個(gè)體與隱含模式,如果一個(gè)個(gè)體X符合模式H，就稱X屬于H，或H包含X。如：H=10*0**; 包含：101011,100001,…,給定一個(gè)個(gè)體X, 如果X屬于模式H，也稱H

18、為X隱含的模式。如：X=101011,它隱含的模式有H1=1*****, H2=*01**1, H3=10**11,…,,定義： 模式H中確定位置的個(gè)數(shù)稱作該模式的模式階，記作O(H)。比如模式011*0*的階是4，而模式0*****為1。顯然一個(gè)模式的階數(shù)越高，其包含的樣本數(shù)就越少，因而確定性也就越高。定義： 模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱作該模式的定義距，記作δ(H)。比如模式011*1*的定義距是4

19、，而模式0*****的定義距為0。,模式階和定義距描述了模式的基本性質(zhì)。下面討論模式在遺傳操作下的變化。令A(yù)(t) 表示第 t 代中串的群體，以Aj(j=1,2,···, n)表示一代中第j個(gè)個(gè)體串。1、選擇操作對(duì)模式的作用假設(shè)在t代，群體A(t)中模式H所包含的個(gè)體數(shù)為m(H，t)。在選擇運(yùn)算中，一個(gè)串是根據(jù)其適應(yīng)度進(jìn)行復(fù)制的。即以概率Pi=fi /(∑fj）進(jìn)行選擇的，其中fi 是個(gè)體Ai(t)適應(yīng)

20、度。則模式H在第t+1代中包含的個(gè)體數(shù)為（從概率角度）,,其中，f(H), f(t) 分別是模式H（在A(t)中）和群體A(t)的適應(yīng)度平均值。,可見，模式的增長（減少）依賴于模式的平均適應(yīng)度與群體平均適應(yīng)度之比：那些平均適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中增長；而那些平均適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少?，F(xiàn)在，假定模式H的平均適應(yīng)度一直高于群體平均適應(yīng)度(設(shè)至少為1+c倍）， c為正的常數(shù)，則有,,即，在選擇算子

21、作用下，平均適應(yīng)度高于群體平均適應(yīng)度的模式將呈指數(shù)級(jí)增長；而低于群體平均適應(yīng)度的模式將呈指數(shù)級(jí)減少。,2．模式在交叉算子作用下的變化考慮一個(gè)長度為6的串以及隱含其中的兩個(gè)模式： A = 0 1 0 1 1 0 H1 = * 1 * * * 0 H2 = * * * 1 1 * 假定A被選中進(jìn)行交叉，不妨設(shè)交叉點(diǎn)為3，即

22、 A = 0 1 0 1 1 0 H1 = * 1 * * * 0 H2 = * * * 1 1 *,,模式在交叉算子作用下的變化 A = 0 1 0 1 1 0 B= 1 0 1 0 0 1 A’ = 1 0 1 1 1 0 B’= 0 1 0 0 0 1

23、 H1 = * 1 * * * 0 H2 = * * * 1 1 *顯然，H1被破壞，而H2依然存在,,,模式H1的定義距為4，那么交叉點(diǎn)在l －1=5個(gè)位置上隨機(jī)產(chǎn)生時(shí)， H1遭到破壞的概率是 Pd=δ(H1 ) / ( l－1 ) = 4 / 5，換句話說，其生存概率為1/5；模式H2的定義距是1，則H2遭破壞的概率是

24、 Pd=δ(H2 ) /( l－1 ) = 1 / 5，即生存概率是4/5。一般地講，當(dāng)交叉點(diǎn)落在定義距之外時(shí)，模式H才能生存。在簡單交叉（單點(diǎn)交叉）下的H的生存概率 Ps=1－δ( H ) / ( l－1 ),由于交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率為如果與A進(jìn)行交叉的串在位置2，6上有一位與A相同，則H1將被保留。因此，以上公式只是生存概率的一個(gè)下界，即有：這個(gè)公式描述了模

25、式在交叉算子作用下的生存概率。如果考慮模式H在選擇和交叉算子的共同作用下的變化。則有,,,,3．模式在變異算子作用下的變化 考慮變異操作。串的某一位置發(fā)生改變的概率為Pm，故該位置不變的概率為1－Pm，而模式H在變異運(yùn)算作用下若要不受破壞，則其中所有的確定位置必須保持不變。因此模式H保持不變的概率為其中O( H )為模式H的階數(shù)。當(dāng)Pm<<1時(shí)，模式H在變異算子作用下的生存概率為,綜合三種算子對(duì)模式H的影響，有如下的生

26、存概率估計(jì)：,模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將得以(指數(shù)級(jí))增長。 結(jié)論：在一定前提下，遺傳算法以概率為1收斂到全局最優(yōu)解！,遺傳算法的應(yīng)用,染色體編碼：視具體問題而定，可以整數(shù)序列串，也可以實(shí)數(shù)序列。適應(yīng)值函數(shù)的定義，如何評(píng)估？交叉算子的本質(zhì)：保持父代基因段或信息；變異算子的本質(zhì)：新解的實(shí)質(zhì)多樣性；如何定義這2個(gè)演化算子，使之保持解的可行性？（特

27、別是約束情況下？）參數(shù)設(shè)定問題。,2024/3/1,智能技術(shù)課程－－葉東毅,SAT問題（無約束）,F(x) ：布爾變量 x = (x1,…, xn)的合取范式.問題：找到x = (x1,…, xn)的一個(gè)真值指派，使得 F(x) = TRUE ( or 1) .例如： F(x) =（ x1 ?x3 ） ? （ x2 ?x5 ? ?x6 ） ? （ ? x4 ?x5 ）取 x = (1, 0, 0, 0, 0, 1 )， 則

28、 F(x) = 0；取 x = (1, 0, 0, 0, 0, 0 )， 則 F(x) = 1；求得一個(gè)解！,2024/3/1,智能技術(shù)課程－－葉東毅,編碼和適應(yīng)值函數(shù),二進(jìn)制編碼：直接用原問題的變量編碼；適應(yīng)值：直接采用問題的目標(biāo)函數(shù)F(x)? 要么F(x)=1，找到解；要么F(x)=0，此時(shí)，如何區(qū)別不同個(gè)體的質(zhì)量呢？如何引導(dǎo)選擇過程呢？適應(yīng)值函數(shù)的合理確定問題?。?F(x) = f1(x) ? f2(x) ?… ? f

29、p(x) ; fi(x)為析取項(xiàng);適應(yīng)值函數(shù)：Q(x) = ? Boolean(fi(x) )；0? Q(x) ? p如果 Q(x) = p, 則 x 為一個(gè)解；可以有其他（可能更好）的方式定義適應(yīng)值函數(shù)。,2024/3/1,智能技術(shù)課程－－葉東毅,對(duì)稱全通路TSP問題（含約束）,城市編號(hào)（頂點(diǎn)）序列為染色體（整數(shù)編碼）： X = 1 2 3…n 的某一個(gè)排列，這樣最自然！如何定義交叉、變異呢？ 簡

30、單交換或變異導(dǎo)致不可行的解： 12435 + 23154 = 12154+23435 適應(yīng)值函數(shù)：距離總和。,采用二進(jìn)制編碼？按照邊，但是需要判斷頂點(diǎn)集合的重疊性。同時(shí)，邊數(shù)遠(yuǎn)遠(yuǎn)多于頂點(diǎn)數(shù)。另外，面臨演化算子的設(shè)計(jì)問題。不合適！,X = 1 2 3 4 5 6 7 8 9; Y = 3 2 4 6 9 5 7 8 1,,,,,,,X’ = 1 2 3 4 5 6 7 9 8 Y’= 3 2 4

31、6 9 1 7 5 8,1、基于次序的交叉：在父代隨機(jī)選取一組位置，強(qiáng)加到另一個(gè)上,2、基于位置的交叉：,X = 1 2 3 4 5 6 7 8 9; Y = 3 2 4 6 9 5 7 8 1,,,,,,,X’ = 3 1 2 4 9 5 6 8 7 ；Y’= 1 3 2 4 5 6 9 8 7,X = 1 2 3 4 5 6 7 8 9; 4：7，5：9，6：8Y = 3 2 4 7 9 8 6 5 1,X’ =

32、 1 2 3 7 9 8 4 6 5 Y’= 3 2 7 4 5 6 8 9 1,3、部分映射交叉：在父代隨機(jī)選取一組位置，段內(nèi)元對(duì)應(yīng)對(duì)交換,,,,,變異算子：1、隨機(jī)選2個(gè)元素，將第二元置于第一元之前；X = 1 2 3 4 5 6 7 8 9， X’ = 1 2 4 5 3 6 7 8 9,,2、隨機(jī)選2個(gè)元素，交換位置；X = 1 2 3 4 5 6 7 8 9，

33、 X’ = 1 2 6 4 5 3 7 8 9,,2024/3/1,智能技術(shù)課程－－葉東毅,圖著色問題（混合算法） ---貪心+遺傳,給定每個(gè)頂點(diǎn)具有加權(quán)的圖和 n 種顏色,圖著色問題：從n 種顏色的集合中選擇一種顏色到任一個(gè)頂點(diǎn)上，但要滿足任何一條邊關(guān)聯(lián)的一對(duì)頂點(diǎn)不具有相同的顏色。未著色的頂點(diǎn)為無色的。著色頂點(diǎn)的加權(quán)總和為著色方案的分?jǐn)?shù)。求具有最高分?jǐn)?shù)的著色方案。這是NP-完全問題。,2024/3/1,智能技

34、術(shù)課程－－葉東毅,貪心策略,按照加權(quán)大小順序?qū)旤c(diǎn)排序；按照該順序取每個(gè)頂點(diǎn)，并為其指定它能夠具有的第一個(gè)合法顏色。該算法速度快，有時(shí)可以獲得最優(yōu)解。,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-36,2-8,3-14,4-13,1-12,6-10,5-9,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-36,2-8,3-14,4-13,1-12,6-10,

35、5-9,n =1, Score =36; Best solution! Greedy idea wins!,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-15,2-8,3-14,4-13,1-12,6-10,5-9,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-15,2-8,3-14,4-13,1-12,6-10,5-9,n =1, Score =15; Not

36、 best!Greedy idea fails!,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-15,2-8,3-14,4-13,1-12,6-10,5-9,n =1, Score =35; Best!,2024/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-15,2-8,3-14,4-13,1-12,6-10,5-9,n =2, Score =66; Best!,20

37、24/3/1,智能技術(shù)課程－－葉東毅,,,,,,,,,,,,,,,,,,,,7-15,2-8,3-14,4-13,1-12,6-10,5-9,n =3, Score =81; Best! Again, greedy idea wins!,2024/3/1,智能技術(shù)課程－－葉東毅,混合遺傳算法,編碼：有序頂點(diǎn)序列（整數(shù)串）適應(yīng)值函數(shù)：依照貪心策略，對(duì)給定的頂點(diǎn)序列進(jìn)行著色，求出相應(yīng)的分?jǐn)?shù)作為適應(yīng)值；應(yīng)用遺傳算法進(jìn)行演化，每得到新的一代