遺傳算法補(bǔ)充課件

1、遺傳算法1 1 基本概念基本概念2 2 基本遺傳算法基本遺傳算法3 3 遺傳算法應(yīng)用舉例遺傳算法應(yīng)用舉例4 4 遺傳算法的特點(diǎn)與優(yōu)勢(shì)遺傳算法的特點(diǎn)與優(yōu)勢(shì)5 5 遺傳算法中的編碼方式討論遺傳算法中的編碼方式討論 1 基本概念 1. 1. 個(gè)體與種群個(gè)體與種群 個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象 （一般就是問(wèn)題的解）的一種稱(chēng)呼，一個(gè)個(gè) 體也就是搜索空間中的一個(gè)點(diǎn)。 種群(population)就是模擬生物種群而由若 干個(gè)體組成的群體, 它一般是整個(gè)搜索空間 的一個(gè)很小的子集。 2. 2. 適應(yīng)度與適應(yīng)度函數(shù)適應(yīng)度與適應(yīng)度函數(shù) 適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的 適應(yīng)程度,而對(duì)問(wèn)題中

2、的個(gè)體對(duì)象所設(shè)計(jì)的 表征其優(yōu)劣的一種測(cè)度。 適應(yīng)度函數(shù)(fitness function)就是問(wèn)題中的 全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。 它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算 法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。 3. 3. 染色體與基因染色體與基因染色體（chromosome）就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱(chēng)為基因（gene）。 例如： 個(gè)體 染色體 9 - 1001 （2，5，6）- 010 101 1104. 4. 遺傳操作遺傳操作亦稱(chēng)遺傳算子(genetic operator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作: 選擇-復(fù)制(selection-

3、reproduction) 交叉(crossover，亦稱(chēng)交換、交配或雜交) 變異(mutation，亦稱(chēng)突變) 選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xiS的選擇概率P(xi)所決定的選中機(jī)會(huì), 分N次從S中隨機(jī)選定N個(gè)染色體, 并進(jìn)行復(fù)制。 NjjiixfxfxP1)()()( 這里的選擇概率P(xi)的計(jì)算公式為交叉 就是互換兩個(gè)染色體某些位上的基因。 s1=01000101, s2=10011011可以看做是原染色體s1和s2的子代染色體。 例如, 設(shè)染色體 s1=01001011, s2=10010101, 交換其后4位基因, 即遺傳算法補(bǔ)充常用的交叉算子v單點(diǎn)

4、交叉 v雙點(diǎn)交叉或多點(diǎn)交叉 v均勻交叉 v算術(shù)交叉 A: 1011 0111 00B: 0001 1100 11雙點(diǎn)交叉A: 1011 1100 00B: 0001 0111 11A: 10110111 00B: 00011100 11單點(diǎn)交叉A: 10110111 11B: 00011100 00 變異變異 就是改變?nèi)旧w某個(gè)(些)位上的基因。 例如, 設(shè)染色體 s=11001101將其第三位上的0變?yōu)?, 即 s=11001101 11101101= s。 s也可以看做是原染色體s的子代染色體。遺傳算法補(bǔ)充常用的變異算子v基本位變異 v均勻變異 v非均勻變異 v高斯變異 A:1010 01

5、010 1基本位變異A: 1010 01010 02 基本遺傳算法 遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止 ?結(jié)束遺傳算法補(bǔ)充 算法中的一些控制參數(shù)：群體規(guī)模popSize，終止進(jìn)化代數(shù)maxGen，交叉概率pc和變異概率pm。 群體規(guī)模popSize：一般建議為20100。終止進(jìn)化代數(shù)maxGen：1001000交叉概率pc：0.40.99變異概率pm：0.0010.1 基本遺傳算法步1 在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T； 步2 隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1, s2, , sN，組成初始種群S=s1

6、, s2, , sN，置代數(shù)計(jì)數(shù)器t=1； 步3 計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f(wàn)() ；步4 若終止條件滿(mǎn)足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。 步5 按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1； 步6 按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2； 步7 按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8 將群體S3作為新一代種群，即用

7、S3代替S，t = t+1，轉(zhuǎn)步3； 3 遺傳算法舉例 例例4.1 利用遺傳算法求解區(qū)間0,31上的二次函數(shù)y=x2的最大值。y=x2 31 XY 分析 原問(wèn)題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點(diǎn)a的問(wèn)題。那么，0, 31 中的點(diǎn)x就是個(gè)體, 函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0, 31就是一個(gè)(解)空間 。這樣, 只要能給出個(gè)體x的適當(dāng)染色體編碼, 該問(wèn)題就可以用遺傳算法來(lái)解決。解：(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。 將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1: s1= 13 (01101), s2= 24 (11000) s

8、3= 8 (01000), s4= 19 (10011) (2) 定義適應(yīng)度函數(shù), 取適應(yīng)度函數(shù)：f (x)=x2 (3) 計(jì)算各代種群中的各個(gè)體的適應(yīng)度, 并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。 首先計(jì)算種群S1中各個(gè)體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的適應(yīng)度f(wàn) (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19)

9、= 192 = 361再計(jì)算種群S1中各個(gè)體的選擇概率。NjjiixfxfxP1)()()(選擇概率的計(jì)算公式為 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31 賭輪選擇示意s40.31s20.49s10.14s30.06 賭輪選擇法在算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬: 在0, 1區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。 若rq1,則染色體x1被選中。 若qk-1rqk(2kN), 則染色體xk被選中。 其中的qi稱(chēng)為染色體xi (i=1, 2, , n)的積累概率

10、積累概率, 其計(jì)算公式為 ijjixPq1)(選擇-復(fù)制 設(shè)從區(qū)間0, 1中產(chǎn)生4個(gè)隨機(jī)數(shù)如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色體 適應(yīng)度選擇概率積累概率選中次數(shù)s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 1于是，經(jīng)復(fù)制得群體：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 交叉 設(shè)交叉率pc=10

11、0%，即S1中的全體染色體都參加交叉運(yùn)算。 設(shè)s1與s2配對(duì)，s3與s4配對(duì)。分別交換后兩位基因，得新染色體： 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中各染色體的情況中各染色體的情況 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的

12、選中次數(shù)s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1 假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中個(gè)染色體都被選中，則得到群體： s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（16） 做交叉運(yùn)算，讓s1與s2，s3與s4 分別交換后三位基因，得 s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19） 這一輪仍然不會(huì)發(fā)

13、生變異。 于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 第三代種群第三代種群S3中各染色體的情況中各染色體的情況 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的選中次數(shù)s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1 設(shè)這一輪的選擇-復(fù)制結(jié)果為： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19） 做交叉運(yùn)算，讓s1與s4

14、，s2與s3 分別交換后兩位基因，得 s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第四代種群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。 將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。 YYy=x2 8 13

15、19 24 X第一代種群及其適應(yīng)度y=x2 12 16 25 27 XY第二代種群及其適應(yīng)度y=x2 9 19 24 28 XY第三代種群及其適應(yīng)度y=x2 16 24 28 31 X第四代種群及其適應(yīng)度例 4.2 用遺傳算法求解TSP。 分析 由于其任一可能解 一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列，都可以事先構(gòu)造出來(lái)。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。（1）定義適應(yīng)度函數(shù) 我們將一個(gè)合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)

16、度，從而適應(yīng)度函數(shù)就是 niiiccdsf11),(1)(（2）對(duì)個(gè)體s=（c1, c2, , cn, cn+1）進(jìn)行編碼。但對(duì)于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑椤Ｒ驗(yàn)槿绻幋a不當(dāng)，就會(huì)在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無(wú)效解。 例如，對(duì)于5個(gè)城市的TSP，我們用符號(hào)A、B、C、D、E代表相應(yīng)的城市，用這5個(gè)符號(hào)的序列表示可能解即染色體。然后進(jìn)行遺傳操作。設(shè) s1=（A, C, B, E, D, A），s2=（A, E, D, C, B, A）實(shí)施常規(guī)的交叉或變異操作，如交換后三位，得 s1=（A,C,B,C,B,A）， s2=（A,E,D,E,D,A）或者將染色體s1第二位的

17、C變?yōu)镋，得 s1=（A, E, B, E, D, A） 可以看出，上面得到的s1， s2和s1都是非法的城市序列。 為此，對(duì)TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。 事實(shí)上，人們針對(duì)TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。 遺傳算法補(bǔ)充 p1=（1 2 3 | 4 5 6 7 | 8 9） p2=（4 5 2 | 1 8 7

18、 6 | 9 3） 將按照下面的方式產(chǎn)生后代。首先，切割點(diǎn)之間的片段被拷貝到后代里： o1=（x x x | 4 5 6 7 | x x） o2=（x x x | 1 8 7 6 | x x） 為了得到o1，我們只需要移走p2中已在o1中的城市4、5、6和7后，得到 21893 該序列順次放在o1中： o1=（2 1 8 | 4 5 6 7 | 9 3） 相似地，我們可以得到另一個(gè)后代： o2=（2 3 4 | 1 8 7 6 | 5 9） 4 遺傳算法的特點(diǎn)與優(yōu)勢(shì) 遺傳算法的主要特點(diǎn) 遺傳算法一般是直接在解空間搜索, 而不像圖搜索那樣一般是在問(wèn)題空間搜索, 最后才找到解。 遺傳算法的搜索隨機(jī)

19、地始于搜索空間的一個(gè)點(diǎn)集, 而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn), 所以遺傳算法是一種隨機(jī)搜索算法。 遺傳算法總是在尋找優(yōu)解, 而不像圖搜索那樣并非總是要求優(yōu)解, 而一般是設(shè)法盡快找到解, 所以遺傳算法又是一種優(yōu)化搜索算法。 遺傳算法的搜索過(guò)程是從空間的一個(gè)點(diǎn)集(種群)到另一個(gè)點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。 因而它實(shí)際是一種并行搜索, 適合大規(guī)模并行計(jì)算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。遺傳算法的適應(yīng)性強(qiáng), 除需知適應(yīng)度函數(shù)外, 幾乎不需要其他的先驗(yàn)知識(shí)。 遺傳算法長(zhǎng)于全局搜索, 它不受搜索空間的限制性假設(shè)的約束,不要

20、求連續(xù)性, 能以很大的概率從離散的、多極值的、 含有噪聲的高維問(wèn)題中找到全局最優(yōu)解。 遺傳算法的應(yīng)用v遺傳算法在人工智能的眾多領(lǐng)域便得到了廣泛應(yīng)用。例如，機(jī)器學(xué)習(xí)、聚類(lèi)、控制（如煤氣管道控制）、規(guī)劃（如生產(chǎn)任務(wù)規(guī)劃）、設(shè)計(jì)（如通信網(wǎng)絡(luò)設(shè)計(jì)、布局設(shè)計(jì)）、調(diào)度（如作業(yè)車(chē)間調(diào)度、機(jī)器調(diào)度、運(yùn)輸問(wèn)題）、配置（機(jī)器配置、分配問(wèn)題）、組合優(yōu)化（如TSP、背包問(wèn)題）、函數(shù)的最大值以及圖像處理和信號(hào)處理等等。v另一方面，人們又將遺傳算法與其他智能算法和技術(shù)相結(jié)合，使其問(wèn)題求解能力得到進(jìn)一步擴(kuò)展和提高。例如，將遺傳算法與模糊技術(shù)、神經(jīng)網(wǎng)絡(luò)相結(jié)合，已取得了不少成果。 遺傳算法補(bǔ)充5 遺傳算法中的編碼方式討論 v遺

21、傳算法的編碼方法有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼方法、格雷碼、符號(hào)編碼方法、多參數(shù)編碼方法等。遺傳算法補(bǔ)充(1) 二進(jìn)制編碼v是最常用的編碼方法v假設(shè)某一參數(shù)的取值范圍是A，B，AB。用長(zhǎng)度為l的二進(jìn)制編碼串來(lái)表示該參數(shù)，將A，B等分成2l-1個(gè)子部分，記每一個(gè)等分的長(zhǎng)度為。v參數(shù)編碼的對(duì)應(yīng)關(guān)系:00000000 00000000=0 A 00000000 00000001=1 A+ 11111111 11111111= -1 Bl2遺傳算法補(bǔ)充v解碼 假設(shè)某一個(gè)體的編碼是： X：xlxl-1xl-2x2x1， 則上述二進(jìn)制編碼所對(duì)應(yīng)的解碼公式為： 二進(jìn)制編碼的最大缺點(diǎn)之一是長(zhǎng)度較大, 對(duì)很多問(wèn)題用其

22、他編碼方法可能更有利。11212iliilxABAx遺傳算法補(bǔ)充函數(shù)優(yōu)化示例 v求下列一元函數(shù)的最大值：v 0 . 2)10sin()(xxxf遺傳算法補(bǔ)充v 由于區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因?yàn)?21 3106 222 ，所以本例的二進(jìn)制編碼長(zhǎng)度至少需要22位，本例的編碼過(guò)程實(shí)質(zhì)上是將區(qū)間-1，2內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20b0）。遺傳算法補(bǔ)充1.二進(jìn)制編碼方法：二進(jìn)制編碼方法：它由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集。它有以下一些優(yōu)點(diǎn)：編碼、解碼操作簡(jiǎn)單易行交叉、變異等遺傳操作便于實(shí)現(xiàn)符合最小字符集編碼原則利用模式定理對(duì)算法進(jìn)行理論分析。二進(jìn)制編碼的缺點(diǎn)是：對(duì)于一些連續(xù)函數(shù)的優(yōu)化問(wèn)題，由于其隨機(jī)性使得其局部搜索能力較差，如對(duì)于一些高精度的問(wèn)題（如上例），當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會(huì)遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)定。而格雷碼能有效地防止這類(lèi)現(xiàn)象遺傳算法補(bǔ)充2.格雷碼方法：格雷碼方法：格雷碼方法是這樣的一種編碼方法，其連續(xù)兩個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間僅僅只有一個(gè)碼位是不同的。遺傳算法補(bǔ)充v假設(shè)有一個(gè)二進(jìn)制編碼B=bmbm-1b2b1，其對(duì)應(yīng)的格雷碼為G=gmgm-1g2g1v由二進(jìn)制編碼轉(zhuǎn)格