遺傳算法補充

遺傳算法補充第一頁，共五十九頁，2022年，8月28日

1基本概念

1.個體與種群

●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

●

種群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。第二頁，共五十九頁，2022年，8月28日

2.適應度與適應度函數(shù)

●

適應度(fitness)就是借鑒生物個體對環(huán)境的適應程度,而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度。

●適應度函數(shù)(fitnessfunction)就是問題中的全體個體與其適應度之間的一個對應關系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。

第三頁，共五十九頁，2022年，8月28日3.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體

9----

1001

（2，5，6）----010101110第四頁，共五十九頁，2022年，8月28日4.遺傳操作亦稱遺傳算子(geneticoperator)，就是關于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

第五頁，共五十九頁，2022年，8月28日

選擇-復制通常做法是：對于一個規(guī)模為N的種群S,按每個染色體xi∈S的選擇概率P(xi)所決定的選中機會,分N次從S中隨機選定N個染色體,并進行復制。

這里的選擇概率P(xi)的計算公式為第六頁，共五十九頁，2022年，8月28日

交叉就是互換兩個染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設染色體s1=01001011,s2=10010101,

交換其后4位基因,即第七頁，共五十九頁，2022年，8月28日常用的交叉算子單點交叉

雙點交叉或多點交叉

均勻交叉

算術交叉

A:1011011100B:0001110011雙點交叉A:1011110000B:0001011111A:1011011100B:0001110011單點交叉A:1011011111B:0001110000第八頁，共五十九頁，2022年，8月28日

變異就是改變?nèi)旧w某個(些)位上的基因。例如,設染色體s=11001101將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。第九頁，共五十九頁，2022年，8月28日常用的變異算子基本位變異

均勻變異

非均勻變異

高斯變異

A:1010010101基本位變異A:1010010100第十頁，共五十九頁，2022年，8月28日2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計算適應度選擇-復制交叉變異生成新一代種群終止?結(jié)束第十一頁，共五十九頁，2022年，8月28日

算法中的一些控制參數(shù)：群體規(guī)模popSize，終止進化代數(shù)maxGen，交叉概率pc和變異概率pm。

群體規(guī)模popSize：一般建議為20～100。終止進化代數(shù)maxGen：100～1000交叉概率pc：0.4~0.99變異概率pm：0.001～0.1第十二頁，共五十九頁，2022年，8月28日

基本遺傳算法

步1

在搜索空間U上定義一個適應度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；

步2

隨機產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；

步3

計算S中每個個體的適應度f()；

步4

若終止條件滿足，則取S中適應度最大的個體作為所求結(jié)果，算法結(jié)束。第十三頁，共五十九頁，2022年，8月28日

步5

按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其染色體復制，共做N次，然后將復制所得的N個染色體組成群體S1；

步6

按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；第十四頁，共五十九頁，2022年，8月28日

步7

按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；

步8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；

第十五頁，共五十九頁，2022年，8月28日3遺傳算法舉例

例4.1

利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY第十六頁，共五十九頁，2022年，8月28日

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。第十七頁，共五十九頁，2022年，8月28日

解：

(1)

設定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設定為4；用5位二進制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應度函數(shù),

取適應度函數(shù)：f(x)=x2

第十八頁，共五十九頁，2022年，8月28日

(3)計算各代種群中的各個體的適應度,并對其染色體進行遺傳操作,直到適應度最高的個體(即31（11111）)出現(xiàn)為止。第十九頁，共五十九頁，2022年，8月28日

首先計算種群S1中各個體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應度f(si)

。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361第二十頁，共五十九頁，2022年，8月28日再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31第二十一頁，共五十九頁，2022年，8月28日

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法第二十二頁，共五十九頁，2022年，8月28日

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為第二十三頁，共五十九頁，2022年，8月28日選擇-復制

設從區(qū)間［0,1］中產(chǎn)生4個隨機數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第二十四頁，共五十九頁，2022年，8月28日于是，經(jīng)復制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）第二十五頁，共五十九頁，2022年，8月28日交叉

設交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

第二十六頁，共五十九頁，2022年，8月28日變異設變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。第二十七頁，共五十九頁，2022年，8月28日

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）第二十八頁，共五十九頁，2022年，8月28日

第二代種群S2中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第二十九頁，共五十九頁，2022年，8月28日

假設這一輪選擇-復制操作中，種群S2中的4個染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會發(fā)生變異。

第三十頁，共五十九頁，2022年，8月28日于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三十一頁，共五十九頁，2022年，8月28日

第三代種群S3中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第三十二頁，共五十九頁，2022年，8月28日

設這一輪的選擇-復制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會發(fā)生變異。第三十三頁，共五十九頁，2022年，8月28日

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

第三十四頁，共五十九頁，2022年，8月28日顯然，在這一代種群中已經(jīng)出現(xiàn)了適應度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

第三十五頁，共五十九頁，2022年，8月28日YYy=x2

8131924

X第一代種群及其適應度y=x2

12162527

XY第二代種群及其適應度y=x2

9192428

XY第三代種群及其適應度y=x2

16242831

X第四代種群及其適應度第三十六頁，共五十九頁，2022年，8月28日

例4.2

用遺傳算法求解TSP。分析

由于其任一可能解——一個合法的城市序列，即n個城市的一個排列，都可以事先構(gòu)造出來。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。第三十七頁，共五十九頁，2022年，8月28日

（1）定義適應度函數(shù)我們將一個合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個個體。這個序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應個體s的適應度，從而適應度函數(shù)就是第三十八頁，共五十九頁，2022年，8月28日

（2）對個體s=（c1,c2,…,cn,cn+1）進行編碼。但對于這樣的個體如何編碼卻不是一件直截了當?shù)氖虑椤Ｒ驗槿绻幋a不當，就會在實施交叉或變異操作時出現(xiàn)非法城市序列即無效解。例如，對于5個城市的TSP，我們用符號A、B、C、D、E代表相應的城市，用這5個符號的序列表示可能解即染色體。第三十九頁，共五十九頁，2022年，8月28日然后進行遺傳操作。設

s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）實施常規(guī)的交叉或變異操作，如交換后三位，得

s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者將染色體s1第二位的C變?yōu)镋，得

s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，

s2’和s1’’都是非法的城市序列。第四十頁，共五十九頁，2022年，8月28日

為此，對TSP必須設計合適的染色體和相應的遺傳運算。事實上，人們針對TSP提出了許多編碼方法和相應的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。第四十一頁，共五十九頁，2022年，8月28日p1=（1

2

3

|

4

5

6

7

|

8

9）

p2=（4

5

2

|

1

8

7

6

|

9

3）

將按照下面的方式產(chǎ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后，得到

2—1—8—9—3

該序列順次放在o1中：

o1=（2

1

8

|

4

5

6

7

|

9

3）

相似地，我們可以得到另一個后代：

o2=（2

3

4

|

1

8

7

6

|

5

9）

第四十二頁，共五十九頁，2022年，8月28日4遺傳算法的特點與優(yōu)勢

◆遺傳算法的主要特點

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解。

——遺傳算法的搜索隨機地始于搜索空間的一個點集,而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點或終止節(jié)點,所以遺傳算法是一種隨機搜索算法。

第四十三頁，共五十九頁，2022年，8月28日

——遺傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非總是要求優(yōu)解,而一般是設法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法。

——遺傳算法的搜索過程是從空間的一個點集(種群)到另一個點集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個點到另一個點地搜索。因而它實際是一種并行搜索,適合大規(guī)模并行計算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。第四十四頁，共五十九頁，2022年，8月28日

——遺傳算法的適應性強,除需知適應度函數(shù)外,幾乎不需要其他的先驗知識。

——遺傳算法長于全局搜索,它不受搜索空間的限制性假設的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。第四十五頁，共五十九頁，2022年，8月28日◆遺傳算法的應用遺傳算法在人工智能的眾多領域便得到了廣泛應用。例如，機器學習、聚類、控制（如煤氣管道控制）、規(guī)劃（如生產(chǎn)任務規(guī)劃）、設計（如通信網(wǎng)絡設計、布局設計）、調(diào)度（如作業(yè)車間調(diào)度、機器調(diào)度、運輸問題）、配置（機器配置、分配問題）、組合優(yōu)化（如TSP、背包問題）、函數(shù)的最大值以及圖像處理和信號處理等等。第四十六頁，共五十九頁，2022年，8月28日另一方面，人們又將遺傳算法與其他智能算法和技術相結(jié)合，使其問題求解能力得到進一步擴展和提高。例如，將遺傳算法與模糊技術、神經(jīng)網(wǎng)絡相結(jié)合，已取得了不少成果。

第四十七頁，共五十九頁，2022年，8月28日5遺傳算法中的編碼方式討論

遺傳算法的編碼方法有二進制編碼、浮點數(shù)編碼方法、格雷碼、符號編碼方法、多參數(shù)編碼方法等。第四十八頁，共五十九頁，2022年，8月28日(1)二進制編碼是最常用的編碼方法假設某一參數(shù)的取值范圍是[A，B]，A<B。用長度為l的二進制編碼串來表示該參數(shù)，將[A，B]等分成2l-1個子部分，記每一個等分的長度為δ。參數(shù)編碼的對應關系:00000000……00000000=0——→A

00000000……00000001=1——→A+δ……………11111111……11111111=-1——→B第四十九頁，共五十九頁，2022年，8月28日解碼

假設某一個體的編碼是：X：xlxl-1xl-2…x2x1，則上述二進制編碼所對應的解碼公式為：

二進制編碼的最大缺點之一是長度較大,對很多問題用其他編碼方法可能更有利。第五十頁，共五十九頁，2022年，8月28日函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。第五十一頁，共五十九頁，2022年，8月28日

由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222

，所以本例的二進制編碼長度至少需要2