遺傳演算法實例 f(x,y)=x^2+y^2求極大值ppt 最新協作平台活動 衛道中學程式設計 遺傳演算法實例 f(x,y)=x

遺傳算法 (GA) 的肇始

“ 活的有機體是解決問題的專家。它們所表現

出來的各種才能足以使最好的計算機程序自慚

形穢。這種現象尤其令計算機科學家們感到痛

楚。計算機科學家們為了某種算法可能花費數

月乃至數年的腦力勞動，而有機體則能通過進

化和自然選擇這樣一種顯然並非定向進行的機

制獲得這種能力。” ---

John Holland

遺傳算法的思想

• Darwin 的進化論

---- “ 自然選擇、適者生存”

特定環境的考驗

• 種群中個體的 _選擇

• _{種群中的交叉 繁殖}

• 種群中個體的 _變異

上述操作反復執行，個體逐漸優化

遺傳算法的手工模擬計算示例

遺傳算法的手工模擬計算示例

為更好地理解遺傳算法的運算過程，下面用手工計算來簡單地模擬遺傳算法的各 個主要執行步驟。

例：求下述二元函數的最大值： max f(x₁,x₂)=x₁²+x₂²

s.t. x₁  {1,2,3,4,5,6,7} x₂  {1,2,3,4,5,6,7}

(1) (1) 個體編碼個體編碼

遺傳算法的運算對象是表示個體的符號串，所以必須把變量 x₁, x₂ ^{編碼為一種} 符號串。本題中，用無符號二進制整數來表示。

因 x1^{, x}2 為 0 ~ 7 之間的整數，所以分別用 3 位無符號二進制整數來表示，將它 們連接在一起所組成的 6 位無符號二進制數就形成了個體的基因型，表示一個可 行解。

^{例如，基因型 X} ＝ 101110 所對應的表現型是： x ＝ [ 5 ， 6 ] 。 個體的表現型 x 和基因型 X 之間可通過編碼和解碼程序相互轉換。

(2) (2) 初始群體的產生初始群體的產生

遺傳算法是對群體進行的進化操作，需要給其淮備一些表示起始搜索點的初始 群體數據。

本例中，群體規模的大小取為 4 ，即群體由 4 個個體組成，每個個體可通過隨機 方法產生。

如： 011101 ， 101011 ， 011100 ， 111001 (3) (3) 適應度汁算適應度汁算

遺傳算法中以個體適應度的大小來評定各個個體的優劣程度，從而決定其遺傳 機會的大小。

本例中，目標函數總取非負值，並且是以求函數最大值為優化目標，故可直接 利用目標函數值作為個體的適應度。

(4) (4) 選擇運算選擇運算

選擇運算 ( 或稱為複製運算 ) 把當前群體中適應度較高的個體按某種規則或模型 遺傳到下一代群體中。一般要求適應度較高的個體將有更多的機會遺傳到下一 代

群體中。

本例中，我們採用與適應度成正比的概率來確定各個個體複製到下一代群體中 的數量。其具體操作過程是：

• 先計算出群體中所有個體的適應度的總和 f_i ( i=1.2,…,M );

• 其次計算出每個個體的相對適應度的大小 f_i^/f_i ，它即為每個個體被遺 傳

到下一代群體中的概率，

• 每個概率值組成一個區域，全部概率值之和為 1 ；

• 最後再產生一個 0 到 1 之間的隨機數，依據該隨機數出現在上述哪一個概 率區

域內來確定各個個體被選中的次數。

0 1

24% ^24% 17% ^35%

1^# 2^# 3^# 4^#

個體編號 初始群體 p(0) ^{適值 占總數的百分比}

總和 1 2 3 4

011101 101011 011100 111001

34 34 25 50

0.24 0.24 0.17 0.35

143 ¹

選擇次數 選擇結果 1

1 0 2

011101 111001 101011 111001

x₁x₂ 3 5 5 3 3 4 7 1

(5)

(5) 交叉運算交叉運算

交叉運算是遺傳算法中產生新個體的主要操作過程，它以某一概率相互交換某 兩個個體之間的部分染色體。

本例採用單點交叉的方法，其具體操作過程是： • 先對群體進行隨機配對；

• 其次隨機設置交叉點位置；

• 最後再相互交換配對染色體之間的部分基因。

選擇結果

01 1101 11 1001 1010 11 1110 01

配對情況 ^{交叉點位置}

個體編號 1 2 3 4

1-2 3-4

1-2_{： 2} 3-4： 4

交叉結果

011001 111101 101001 111011

可以看出，其中新產生的個體“ 111101” 、“ 111011” 的適應度較原來兩個個 體

的適應度都要高。

(6)

(6) 變異運算變異運算

變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進 行改變，它也是產生新個體的一種操作方法。

本例中，我們採用基本位變異的方法來進行變異運算，其具體操作過程是：

• 首先確定出各個個體的基因變異位置，下表所示為隨機產生的變異點位置

，

其中的數字表示變異點設置在該基因座處；

• 然後依照某一概率將變異點的原有基因值取反。

對群體 P(t) 進行一輪選擇、交叉、變異運算之後可得到新一代的群體 p(t+1) 。

個體編號 1 2 3 4

交叉結果

011001 111101 101001 111011

變異結果 變異點

4 5 2 6

011101 111111 111001 111010

子代群體 p(1)

011101 111111 111001 111010

從上表中可以看出，群體經過一代進化之後，其適應度的最大值、平均值都得 到了明顯的改進。事實上，這裏已經找到了最佳個體“ 111111” 。

[[ _注意注意 ]_]

需要說明的是，表中有些欄的數據是隨機產生的。這裏為了更好地說明問題， 我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實際運算過程中 有可能需要一定的循環次數才能達到這個最優結果。

個體編號 子群體 p(1) ^{適值 占總數的百分比}

總和 1 2 3 4

011101 111111 111001 111010

34 98 50 53

0.14 0.42 0.21 0.23

235 1

x₁x₂ 3 5 7 7 7 1 7 2

個體編號 初始群體 p(0) 適值 f_i(x₁,x₂)

占總數的百分比 f_i/f

1 2 3 4

011101 101011 011100 111001

34 34 25 50

0.24 0.24 0.17 0.35

x₁x₂

3 5 5 3 3 4 7 1

f_i=143 f_max=50 f=35.75

選擇結果

011101 111001 101011 111001

配對情況 交叉點位置

1-2 3-4

1-2： 2 3-4_{： 4}

交叉結果

011001 111101 101001 111011

選擇次數 1

1 0 2

變異點 變異結果 4

5 2 6

011101 111111 111001 111010

子代群體 p(1) _適值

f_i(x₁,x₂)

占總數的百分比 f_i/f

011101 111111 111001 111010

34 98 50 53

0.14 0.42 0.21 0.23

x₁x₂

3 5 7 7 7 1 7 2

f_i=253 f_max=98 f=58.75

遺傳算法的一個實例

• _{求解方程：}

將方程求解問題轉化為生存問題：

解一定在 [0,10] 之間，將區間 [0,10] 劃分成

若干個小區間，設想每個小區間為一個生

物個體，使下列表達式最小的個體有

最好的生存能力，該個體即為解。

10 _{ e} x _ 100

x ^{(  x 0 )}

|

100

| x ¹⁰  e ^x 

遺傳算法的一個實例

• 如何找到這個最優個體？

可通過 Darwin 的進化論由初始個體經過

代代演化，逐漸進化出來。

• 如何將生物進化的操作轉化為計算機可

以執行的操作？

通過編碼表徵生物個體，則生物之間的演

化轉化為編碼的變化。

步驟一：初始化

• 個體編碼： ( 假定要求小數點後兩位 )

將 [0,10] 劃分為 1024 個小區間

個體 1 0000000000

個體 2 0000000001

個體 3 0000000010

……

個體 1024 1111111111

• 種群初始化：

隨機生成 m _{個 10 位二進制串}

1024

2

¹⁰

^

0 ₁₀

• 定義適應度函數：

• 選擇（適應度較大的個體）

步驟二：選擇

|

100

1 |

10 _{ }

 _x

e

f x _{為何取倒數？}

0.1

0.3

0.2

0.4 ^{0.1 0.1}

0.3 0.4 0.2 0.6 0.4 1.0

A B D C

隨機產生

[0,1] _之間

的數 RN

，選擇個體

RN

個體 ^{A B C D}

1 . 0

0 RN  0.1 RN 0.4 0.4  RN 0.6 0.6  RN 1

• 選中的優勢個體進行交叉

--- 由父個體生成子個體

步驟三：交叉

相同的兩個父個體生成相同的兩個子個體

• _變異操作

在個體中隨機選擇一位，改變該位的值

步驟四：變異

交叉和變異操作均以一定概率進行

• 反復執行步驟二、三、四並記錄最優個體

（適應度最大的個體）

• 程序結束時，最優個體即為所求解

• 程序結束的判定

根據循環次數

根據最大適應度

根據種群中相同個體數與總個體數的比值

步驟五

遺傳算法各步驟的評價

• _選擇 --- _優勝劣汰

選擇操作為種群提供了演進的方向

• _交叉 --- _優優組合

交叉操作的作用在於彙集散佈於不同

個體間的局部優勢模式

• _變異 --- ^{尋找新模式}

變異操作是種群向外擴展的觸角 ( 隨機 )

好的變異將保留，壞的淘汰

遺傳算法的總體評價

• _優點

解決問題的方法具有普適性

全局收斂性（依概率收斂）

能解決的問題範圍很廣

• _不足

求得的解為近似的數值解

對於經典數學可以解決的問題，效率較低

遺傳算法的適應度函數

求函數的全局極小值

取 的初始區間，例如： [-10,10]

將此區間分為 1024 個小區間，然後編碼

若求全局極大值 ( 且為正 ) ，可直接取函數值

為其適應度值，據此作概率選擇；

若求全局極小值 ( 且為正 ) ，可取函數值的倒

數為其適應度值，據此作概率選擇。

若不全為負，可統一加上一個正數，使為正。

)

4 (

)) 1

(

10

sin(

))

80

sin(sin(

))

sin(

70

sin(

)

60

sin(

))

50

exp(sin( x  e

^y

 x  y  x  y  x

²

 y

²

y

x,

TSP 問題的遺傳算法求解

• 步驟一：個體編碼及種群初始化

• 步驟二：適應度選擇

• 步驟三：交叉操作

• 步驟四：變異操作

• 步驟五：重複二、三、四步，直至結束

令城市 ( 點 ) 數目為 N

• _個體編碼

取長度為 N 的數字串，串中數字互不重複，取值

範圍為 [1,N] 之間的整數。則每一個數字串代

表一個個體，個體中數字出現的位置表徵路徑

中城市出現的順序。

• _初始種群

令種群中有 M 個個體，可隨機產生 M 個數字

串構成初始種群。例如：

將數字串 1234…N 上的數字進行隨機的交換

步驟一：初始化

• 適應度的計算

步驟二：適應度選擇

1

2

3

4

5

l

1

l

2

l

3

l

4

l

5







_N

i

i j

l

f

1

1

對於個體 ，適應度為： ^j

被選中作為父個體的概率：







_M

j

j j j

f

p f

1

 ^p

^j

^{ 1 選擇 M 次}

重新生成種群

• TSP 中交叉算子的特點

要保證生成的解為有效解

從一個父個體中隨機選取一段子串 A ，在另一個父個體

中將 A 中出現的數字去掉形成串 B _{， AB 為一個子串}

步驟三：交叉操作

此外還有多種交叉算子

• 常用的變異操作：

隨機選取兩個相鄰位置的數字，交換其順序。

51243(5) 51234(5)

步驟四：變異操作

1

2

3

4

5

1

2

3

4

交換 3, 5

4

此外還有多種變異算子

• 反復執行步驟二、三、四

• _結束判定

循環執行 G 次 ( 例如 G=500) 後

當最優個體的總路徑長度小於預期時

步驟五：

中國各省會城市的運行結果

1

2

3

4

5

缺陷：相同父個體生成不同的子個體

以下是相同個體：

12345(1) 54321(5) _反射操作

12345(1) 34512(3) 旋轉操作

交叉算子的進一步研究

用群論描述

所有路徑的集合形成一個二面體群 A

等價解構成一個正規子群 B

A 中陪集的數目為 2N

12345(1) 32154(3) ^{相同父個體交叉}

34215(3) 15234(1) 不同子個體，且和父個體不同

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

1.

_{產生初始種群}

2.

_{計算適應度}

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

0001100000 0101111001 0000000101 1001110100 1010101010

1110010110 1001011011 1100000001 1001110100 0001010011

（ 8 ） （ 5 ） （ 2 ） （ 10 ） （ 7 ）

（ 12 ） （ 5 ） （ 19 ） （ 10 ） （ 14 ）

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

3.

_選擇

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

個體 染色體 適應度 選擇概率 累積概率

1 0001100000 8

2 0101111001 5

3 0000000101 2

4 1001110100 10

5 1010101010 7

6 1110010110 12

7 1001011011 5

8 1100000001 19 9 1001110100 10 10 0001010011 14

8

8 ＋ 5 ＋ 2 ＋ 10 ＋ 7 ＋ 12 ＋ 5 ＋ 19 ＋ 10

＋ 14

0.086957

5

8 ＋ 5 ＋ 2 ＋ 10 ＋ 7 ＋ 12 ＋ 5 ＋ 19 ＋ 10

＋ 14

0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

3.

_選擇

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

個體 染色體 適應度 選擇概率 累積概率

1 0001100000 8

2 0101111001 5

3 0000000101 2

4 1001110100 10

5 1010101010 7

6 1110010110 12

7 1001011011 5

8 1100000001 19 9 1001110100 10 10 0001010011 14

0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174

0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

3.

_選擇

在 0 ～ 1 之間產生一個

隨機數：

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

個體 染色體 適應度 選擇概率 累積概率

1 0001100000 8

2 0101111001 5

3 0000000101 2

4 1001110100 10

5 1010101010 7

6 1110010110 12

7 1001011011 5

8 1100000001 19 9 1001110100 10 10 0001010011 14

0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174

0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000 0.070221

0.545929 0.784567 0.446930 0.507893 0.291198 0.716340 0.270901 0.371435 0.854641

淘汰！淘汰！

0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

4.

_交叉

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011

0001

1110100000

010110 111

1000010110

1011011 110000 100111

0100 0001

1001110100 1100000001

1010101 0001010010

011

4.1

4.1 ^{遺傳算法簡介} 遺傳算法簡介

智能優化計算

智能優化計算

• _簡單實例

5.

_變異

4.1.4 4 .1.4 ^{遺傳算法的基本操作} 遺傳算法的基本操作

0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001

1110100000

010110 111

1000010110

1011011 110000 100101

0100 0001

1001110100 1100000001

1010101 0001010010

011 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001

1110100000

010110 111

1000010110

1011011 110000 100111

0100 0001

1001110100 1100000001

1010101 0001010010

011

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 問題的提出

^{一元函數求最大值：}

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

]

2

,

1

[

0

.

2

)

10

sin(

)

( x ^ x ^ x ^ x ^{ }

f 

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 問題的提出

用微分法求取 f(x) 的最大值：

解有無窮多個：

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

x

x

x

x

x

x

f

































10

)

10

tan(

0

)

10

cos(

10

)

10

sin(

)

(

'

即

的实数递减序列。

一接近于

是

， 及

0

)

,

2

,

1

,

2

,

1

(

,

2

,

1

20 ,

1

2

0

,

2

,

1

20 ,

1

2

0

















 



 











 







 

 i i

i i

x

x

i i

x

i

i i

i

i







4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 問題的提出

當 i 為奇數時 x

i

對應局部極大值點， i _為偶數時

x

_i

對應局部極小值。 x

19

即為區間 [-1,2] 內的最大

值點：

此時，函數最大值 f(x

₁₉

) 比 f(1.85)=3.85 稍大。

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

19 19

19

^{1 . 85}

20

37     

x 

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• _編碼

表現型： x

基因型：二進制編碼（串長取決於求解精度）

串長與精度之間的關係：

若要求求解精度到 6 位小數，區間長度為 2-(-1) ＝ 3

，即需將區間分為 3/0.000001=3×10

⁶

_等份。

所以編碼的二進制串長應為 22 位。

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

4194304

2

3000000

2

2097152 

²¹

 

²²



4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 產生初始種群

^{產生的方式：隨機}

產生的結果：長度為 22 的二進制串

產生的數量：種群的大小（規模），如 30 _{， 50 ，…}

1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000

……

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 計算適應度

不同的問題有不同的適應度計算方法

本例：直接用目標函數作為適應度函數

① 將某個體轉化為 [-1,2] 區間的實數：

s=<1000101110110101000111>→x=0.637197

② 計算 x 的函數值（適應度）：

f(x)=xsin(10πx)+2.0=2.586345

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• 計算適應度

二進制與十進制之間的轉換 ：

第一步，將一個二進制串（ b

₂₁

b

₂₀

…b

₀

）轉化為 10

進制數：

第二步， x’ 對應的區間 [-1,2] 內的實數：

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

'

)

2

(

)

(

²¹ ₁₀

0 2

0 20

21

^{b b b x}

b

i

i

i

^{ }

 _





1

2

)

1

(

' 2

0

.

1

₂₂





 





 x

x

(0000000000000000000000)→-1 (1111111111111111111111)→2

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• _遺傳操作

^{選擇：輪盤賭選擇法；}

交叉：單點交叉；

變異：小概率變異

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• _模擬結果

^{設置的參數} ：

種群大小 50 ；交叉概率 0.75 ；變異概率 0.05

；最大代數 200 。

^{得到的最佳個體} ：

s

_max

=<1111001100111011111100>;

x

_max

=1.8506;

f(x

_max

)=3.8503;

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

4.2

4.2 ^{基本遺傳算法} 基本遺傳算法

智能優化計算

智能優化計算

• _模擬結果

進化的過程 ：

4.2.1 4 .2.1 ^{簡單函數優化的實例} 簡單函數優化的實例

世代數 自變量 適應度

1 1.4495 3.4494

9 1.8395 3.7412

17 1.8512 3.8499

30 1.8505 3.8503

50 1.8506 3.8503

80 1.8506 3.8503

120 1.8506 3.8503 200 1.8506 3.8503