1、第4章 基于遺傳算法的隨機(jī)優(yōu)化搜索,4.1 基本概念 4.2 基本遺傳算法 4.3 遺傳算法應(yīng)用舉例 4.4 遺傳算法的特點(diǎn)與優(yōu)勢(shì),4.1 基本概念 1. 個(gè)體與種群 個(gè)體就是模擬生物個(gè)體而對(duì)問題中的對(duì)象 （一般就是問題的解）的一種稱呼，一個(gè)個(gè) 體也就是搜索空間中的一個(gè)點(diǎn)。 種群(population)就是模擬生物種群而由若 干個(gè)體組成的群體, 它一般是整個(gè)搜索空間 的一個(gè)很小的子集。,2. 適應(yīng)度與適應(yīng)度函數(shù) 適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的 適應(yīng)程度,而對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的 表征其優(yōu)劣的一種測(cè)度。 適應(yīng)度函數(shù)(fitness function)就是問題中的 全體個(gè)體與

2、其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。 它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算 法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。,3. 染色體與基因 染色體（chromosome）就是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。 例如： 個(gè)體 染色體 9 - 1001 （2，5，6）- 010 101 110,4. 遺傳操作 亦稱遺傳算子(genetic operator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作: 選擇-復(fù)制(selection-reproduction) 交叉(crossover，亦稱交換、交配或雜交) 變異(mutation，亦稱突變),選擇-復(fù)制通常做法是：對(duì)于

3、一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xiS的選擇概率P(xi)所決定的選中機(jī)會(huì), 分N次從S中隨機(jī)選定N個(gè)染色體, 并進(jìn)行復(fù)制。,交叉 就是互換兩個(gè)染色體某些位上的基因。,s1=01000101, s2=10011011 可以看做是原染色體s1和s2的子代染色體。,例如, 設(shè)染色體 s1=01001011, s2=10010101, 交換其后4位基因, 即,變異 就是改變?nèi)旧w某個(gè)(些)位上的基因。 例如, 設(shè)染色體 s=11001101 將其第三位上的0變?yōu)?, 即 s=11001101 11101101= s。 s也可以看做是原染色體s的子代染色體。,4.2 基本遺傳算法,算法中的一些控制參

4、數(shù)： 種群規(guī)模 最大換代數(shù) 交叉率(crossover rate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.40.99。 變異率(mutation rate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.00010.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, s2, , sN，置代數(shù)計(jì)數(shù)器t=1； 步3 計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f() ； 步4 若終止條件滿足，則取S中

5、適應(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作為新一代種群，即用S3代替S，t = t+1，轉(zhuǎn)步3；,4.3 遺傳算法應(yīng)用舉例,例4.1 利用遺傳算法求解區(qū)間0,31上的二次函

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

7、計(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 (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,再計(jì)算種群S1中各個(gè)體的選擇概率。,選擇概率的計(jì)算公式為,由此可求得 P(s1) = P(13)

8、= 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,賭輪選擇示意, 賭輪選擇法,在算法中賭輪選擇法可用下面的子過程來模擬: 在0, 1區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。 若rq1,則染色體x1被選中。 若qk-1rqk(2kN), 則染色體xk被選中。 其中的qi稱為染色體xi (i=1, 2, , n)的積累概率, 其計(jì)算公式為,選擇-復(fù)制,設(shè)從區(qū)間0, 1中產(chǎn)生4個(gè)隨機(jī)數(shù)如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503,于是，經(jīng)復(fù)制得

9、群體： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19）,交叉 設(shè)交叉率pc=100%，即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）

10、 s3=11011（27）, s4=10000（16）,第二代種群S2中各染色體的情況,假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的 4個(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ā)生變異。,于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=100

11、11（19）,第三代種群S3中各染色體的情況,設(shè)這一輪的選擇-復(fù)制結(jié)果為： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19）,做交叉運(yùn)算，讓s1與s4，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。于是，遺傳操作終止，

12、將染色體“11111”作為最終結(jié)果輸出。 然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。 將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。,Y,例 4.2 用遺傳算法求解TSP。 分析 由于其任一可能解 一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列，都可以事先構(gòu)造出來。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。,（1）定義適應(yīng)度函數(shù) 我們將一個(gè)合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)度，從而適應(yīng)

13、度函數(shù)就是,（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)非法城市序列即無效解。 例如，對(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第二位的C變?yōu)镋，得 s1=（A, E, B,

14、E, D, A） 可以看出，上面得到的s1， s2和s1都是非法的城市序列。,為此，對(duì)TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。 事實(shí)上，人們針對(duì)TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。,4.4 遺傳算法的特點(diǎn)與優(yōu)勢(shì),遺傳算法的主要特點(diǎn) 遺傳算法一般是直接在解空間搜索, 而不像圖搜索那樣一般是在問題空間搜索, 最后才找到解。 遺傳算法的搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集, 而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn), 所

15、以遺傳算法是一種隨機(jī)搜索算法。,遺傳算法總是在尋找優(yōu)解, 而不像圖搜索那樣并非總是要求優(yōu)解, 而一般是設(shè)法盡快找到解, 所以遺傳算法又是一種優(yōu)化搜索算法。 遺傳算法的搜索過程是從空間的一個(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í)。 遺傳算法長于全局搜索, 它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性, 能以很大的概率從離散的、多極值的、 含有噪聲的高維問題中找到全局最優(yōu)解。,遺傳算法的應(yīng)用 遺傳算法在人工智能的眾多領(lǐng)域便得到了廣泛應(yīng)用。例如，機(jī)器學(xué)習(xí)、聚類