進化計算課件

第十一章進化計算

史忠植

中科院計算所

內(nèi)容

11.1概述

11.2進化系統(tǒng)理論的形式模型

11.3達爾文進化算法

11.4分類器系統(tǒng)

11.5桶鏈算法

11.6遺傳算法

11.7并行遺傳算法

11.8分類器系統(tǒng)Boole

11.9規(guī)則發(fā)現(xiàn)系統(tǒng)

11.10進化策略

11.11進化程序設(shè)計

11.1概述

遺傳算法思想來源于生物進化過程,它

是基于進化過程中的信息遺傳機制和優(yōu)勝

劣汰的自然選擇原則的搜索算法（以字符串

表示狀態(tài)空間）。遺傳算法用概率搜索過程

在該狀態(tài)空間中搜索，產(chǎn)生新的樣本。

發(fā)展歷史

遺傳算法的發(fā)展歷史：

■60年代開始

■70年代熱門

■國內(nèi)90年代有了研究

特點

特點：

■通用

■魯棒

■次優(yōu)解、滿意解

遺傳算法能解決的問題：

■優(yōu)化

■NP完全

■NP難

■高度復(fù)雜的非線性問題

遺傳算法與自然進化的比較

自然界遺傳算法

染色體字符串

基因字符，特征

等位基因(allele)特征值

染色體位亶(locus)字符串位置

基因型(genotype)結(jié)構(gòu)

表型(phenotype)參數(shù)集，譯碼結(jié)構(gòu)

面向執(zhí)行的學(xué)習(xí)系統(tǒng)

新達爾文進化理論的主要論點

1）個體是基本的選擇目標(biāo)；

2）隨機過程在進化中起重大作用，遺傳變異大

部分是偶然現(xiàn)象；

3）基因型變異大部分是重組的產(chǎn)物，特別是突

變；

4）逐;斬進化可能與表型不連續(xù)有關(guān)；

5）不是所有表型變化都是自然選擇的必然結(jié)

果.

6）進山是在適應(yīng)中變化的，形式多樣,不僅是

基因的變化；

7）選擇是概率型的，而不是決定型的。

11.2進化系統(tǒng)理論的形式模型

進化的主要過程

遺傳操作符后生環(huán)境選擇環(huán)境

???

-g-----------""P------

進化系統(tǒng)理論的形式模型

基因型空間：GS={g=(%,...,%),%w/J

表型空間：PS={p=(p],…，pm),PjGlR)

后生環(huán)境：EP={EPX，…，EPk}

變換函數(shù)：/：GS乂EPfPS

p=f(g,EP)

質(zhì)量函數(shù)：q(p,ES/)fIR+

11.3達爾文進化算法

1）建立原始種體。

2）通過突變建立子孫。

s'l=%

x\=x+s；Z]

???

s）=sg丸

3）選擇:

Q(x)=max{0(x')}

l<z<2

4）返回到步驟（1）。

11.4分類器系統(tǒng)

分類器系統(tǒng)的一般結(jié)構(gòu)

消息來自

輸入接口

支付

來自內(nèi)部監(jiān)控器的消息

（目標(biāo)）

規(guī)則與消息

產(chǎn)生式規(guī)則：IF〈條件>THENv動作〉

約定：條件的長度是固定的，用二進制數(shù)表示。

定義：

<message>::=<mk>,mz.e{0,1},z=1,...,k

<condition>::=<s^s2,...,sk>,邑G{0,1,#},Z=1,...,左,#為通酉己符

<classifier>::=<condition>/<message>

學(xué)習(xí)機制

分類器系統(tǒng)使用兩個學(xué)習(xí)機制，

?桶鏈(bucketbrigade)算法?；趯ο到y(tǒng)的貢

獻,對現(xiàn)有規(guī)則分配一個信用值。

?規(guī)則發(fā)現(xiàn)算法。這包括遺傳算法，該算法可

產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識庫。

分類器系統(tǒng)的基本結(jié)構(gòu)

分類器

(a)全部消息進行條件測試

(b)選中分類器產(chǎn)生新消息

分類器基本算法

1）將輸入接口全部消息放入消息表。

2）將消息表中的全部消息與全部分類器所有

條件比較,記錄所有匹配。

3）滿足分類器條件部分的每組匹配，將其動作

部分所規(guī)定的消息送到新的消息表。

4）用新的消息表取代消息表中的全部消息。

5）將消息表中的消息翻譯成輸出接口的要求,

產(chǎn)生系統(tǒng)當(dāng)前的輸出。

6）返回到步驟（1）。

簡單的視覺分類器系統(tǒng)

視覺向量

1...1011

消息

性質(zhì)檢測器規(guī)定的值

r1,如果移動對象

Lo,其它

(0,0),如果對象在視野的中間

(d2,d3)=<(1,0),如果對象在中心的左邊

L如果對象在中心的右邊

,r1,如果系統(tǒng)是對象的近鄰

〃=其它

"ZLL/1,如其它果對象很大

,J1,如果對象是狹長的

""io,其它

規(guī)則表示

規(guī)則：

IF如果有“捕食(prey)"(small,moving,nonstripedobject),

處于視野中間(centered),非鄰近(nonadjacent),

THEN迅速移向?qū)ο?ALIGN),(FAST).

可以表示為：

00#########000001/0100000000000000,ALIGN,FAST.

網(wǎng)絡(luò)圖

d{八=。d6=0I］。=0a。=1

網(wǎng)絡(luò)圖的規(guī)則表示

MOVING和ALERT之間的箭頭：

00#############1/01001###########

SMALL,NOTSTRIPEDandALERTS

TARGET的箭頭：

00########00####,01001###########/

10001###########

11.5桶鏈算法

桶鏈(bucketbrigade)算法基于對系統(tǒng)的貢獻,

對現(xiàn)有規(guī)則分配一個信用值。主要解決多條

規(guī)則同時要求被激活時的競爭問題。

例如：下面的情況下應(yīng)該選擇哪條規(guī)則。

一##00：0001

0111一01##：0000

一00#0：1100

主要問題

引入信用值后的兩個問題：

■當(dāng)多條規(guī)則同時要求被激活時，如何解

決競爭問題

■對一規(guī)則被激活產(chǎn)生過作用的那些規(guī)則

如何分配信用

_________桶鏈算法

為解決上述兩個問題，引入拍賣行和票據(jù)交易所:

■當(dāng)有多個分類器獲得匹配時，每個分類器要出

一個與其強度成正比的叫價B

■叫價高的分類器被激活并允許發(fā)送消息，同時

通過票據(jù)交易所將其叫價B提供給激活改分類

器的分類器。

■如此繼續(xù)下去，一條規(guī)則可通過消費者獲利

（增加了強度），通過規(guī)則的不斷激活形成一

條消費者鏈，直至最終消費者（達到目標(biāo)）直

接從環(huán)境中得到補償。

■若鏈中一條規(guī)則導(dǎo)致錯誤結(jié)論，則序列上改規(guī)

則的強度將減弱，并且沿著序列回溯，從而產(chǎn)

生新的消費者鏈

舉例

環(huán)境0111,強度為0,叫價系數(shù)為0」。

索引號分類器強度

101##：0000200

200#0：1000200

311##：1000200

4##00：0001200

第一步

分類器強度消息匹配叫價

01##：0000200E20

00#0：1000200

11##：1000200

##00：0001200

第二步

分類器強度消息匹配叫價

01##：00001800000

00#0：1000200120

11##:1000200

##00：0001200120

兩條規(guī)則同時激活

第三步

分類器強度消息匹配叫價

01##：0000220

00#0：10001801100

11##:1000200220

##00：00011800001218

第四步

分類器強度消息匹配叫價

01##：0000220

00#0：1000218

11##:10001801000

##00：0001162316

第五步

分類器強度消息匹配叫價強度

01##：0000220220

00#0：1000218218

11##：1000196196

##00：00011460001206

規(guī)則4達到目標(biāo)獲得補償60。

投標(biāo)改變分類器的強度

在時間t對分類器C的支持

對在t-1作在時間t滿足C

用的分類送去消息的分

器投標(biāo)類器

分類器中的遺傳算法

遺傳算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知

識庫。

可僅在三種情況下應(yīng)用GA：

1）引入一個參數(shù)T（時間間隔），用于控制何

時使用GA。

2）特殊情況時（如消息的條件都不能匹配）

使用GA。

3）系統(tǒng)的性能太差。

算法步驟

l)t=o,隨機生成集合Bt,|Bt|=M(大小)；

2)計算Bt中全體分類器的平均強度Vt,對每

個分類器賦予一個標(biāo)準(zhǔn)強度St(Cj)/Vt；

3)給Bt中的每個分類器Cj賦予一個與其標(biāo)準(zhǔn)

強度成正比的概率，并根據(jù)Bt中的概率分

布，從Bt中選取n個分類器，n?M；

4)對每個分類器應(yīng)用交叉算子，生成2n個分

類器；

5)將Bt中的2n個強度最低的分類器用新生成

的2n個取代；

6)t=t+l,轉(zhuǎn)(2)。

算法說明

1）算法中SO（Cj）是預(yù)知的；

2）實現(xiàn)時考慮結(jié)束條件；

3）該算法是經(jīng)典GA的變種，其中沒有變異

算子；

4）新分類器的強度是由舊分類器的強度決

定的。

1L6遺傳算法

■遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式，每個字符串結(jié)構(gòu)

被稱為個體。

■然后對一組字符串結(jié)構(gòu)（被稱為一個群體）進行循環(huán)操作。

每次循環(huán)被稱作一代，包括一個保存字符串中較優(yōu)結(jié)構(gòu)的過

程和一個有結(jié)構(gòu)的、隨機的字符串間的信息交換過程。

■類似于自然進化，遺傳算法通過作用于染色體上的基因?qū)?/p>

找好的染色體來求解問題。

■與自然界相似，遺傳算法對求解問題的本身一無所知，它

所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基

于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁

殖機會。

■在遺傳算法中，位字符串扮演染色體的作用，單個位扮演

了基因的作用，隨機產(chǎn)生一個體字符串的初始群體，每個

個體給予一個數(shù)值評價，稱為適應(yīng)度，取消低適應(yīng)度的個

體，選擇高適應(yīng)度的個體參加操作。

■常用的遺傳算子有復(fù)制、雜交、變異和反轉(zhuǎn)。

遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同

1）遺傳算法不是直接作用在參變量集上,而是

利用參變量集的某種編碼；

2）遺傳算法不是從單個點,而是在群體中從一

個點開始搜索；

3）遺傳算法利用適應(yīng)值信息,無需導(dǎo)數(shù)或其它

輔助信息；

4）遺傳算法利用概率轉(zhuǎn)移規(guī)則,而非確定性規(guī)

則。

遺傳算法的準(zhǔn)備工作

1）確定表示方案；

2）確定適應(yīng)值的度量；

3）確定控制該算法的參數(shù)和變量；

4）確定怎樣指定結(jié)果及程序運行結(jié)束的標(biāo)準(zhǔn)。

基本的遺傳算法

1.隨機產(chǎn)生一個由固定長度字符串組成的初始群體；

2.對于字符串群體，迭代地執(zhí)行下述步驟，直到選種標(biāo)準(zhǔn)被

滿足為止：

1）計算群體中的每個個體字符串的適應(yīng)值；

2）應(yīng)用下述三種操作（至少前兩種）來產(chǎn)生新的群體：

?復(fù)制:把現(xiàn)有的個體字符串復(fù)制到新的群體中。

■雜交:通過遺傳重組隨機選擇兩個現(xiàn)有的子字符串,

產(chǎn)生新的字符串。

?變異:將現(xiàn)有字符串中某一位的字符隨機變異。

3.把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算

法運行的結(jié)果。這一結(jié)果可以是問題的解（或近似解）。

基本遺傳算法的流程圖

（轉(zhuǎn)下頁）

（接上頁）

表示模式

所謂模式就是一個相同的構(gòu)形,它描述的是一

個串的子集,這個集合中的串之間在某些位上相同。

模式的復(fù)制生長方程：

f(H)

M(H+1)=M(H

f

這表明,一個特定的模式按照其平均適應(yīng)值與

群體的平均適應(yīng)值之間的比率生長。

雜交操作

■雜交操作是個有結(jié)構(gòu)、隨機的字符串間信息交

換過程。

■簡單的雜交操作分為三步

?從當(dāng)前群體B(t)中選擇兩個結(jié)構(gòu)：

CI—S]S2???S〃Q=SS2???i

?隨機選擇一個整數(shù)X€{1,2,...,Z-1)

?交換a和中位置x左邊的元素，產(chǎn)生兩個新

的結(jié)構(gòu):“"“.s'/,s；..s[Sx+i.?.S/

具有強度的遺傳算法

1.在t=0時隨機產(chǎn)生M字符串的群體B(t)。計算群體B(t)中字

符串的平均強度v(t),給群體B(t)中的每個字符串賦以規(guī)范

值S(Cj,t)/v(t)o

2.對群體B(t)中的每個字符串賦與一個概率值,其值與規(guī)范值

成正比。然后,使用概率分布，從B(t)中選擇n對字符串，

n?M,并且將它們復(fù)制。

3.對每對復(fù)制字符串進行雜交操作，形成2n個新的字符串。

4.用步驟(3)中生成的2n個新的字符串取代群體B(t)中2n個強

度最低的字符串。

5.時間t變?yōu)閠+1,返回步驟(1)。

[Suuds^o][J9AOSSOJQ][SuijdsjjoON][SJUOJUJ]

f

■Jggueqoqju!jo，idQ'3”D

變異操作

簡單的變異操作過程如下：

■每個位置的字符變量都有一個變異概率，各位置互

相獨立。通過隨機過程選擇發(fā)生變異的位置：

ac],23???13ci

■產(chǎn)生一個新結(jié)構(gòu)優(yōu)=邑...-1$；%+1…%2-/；與2+1…S/'其

中是從對應(yīng)位置項的字符變量的值域中隨機選

擇的二個取值。歐，…，鼠可以同樣得到。

x2xk

反轉(zhuǎn)操作

簡單反轉(zhuǎn)操作的步驟如下：

1）從當(dāng)前群體中隨機選擇一個結(jié)構(gòu)

a—s島…s’

JL6

2）從中隨機選擇兩個數(shù)『和『，并定義

i=min{i',j'},>max{i',j'};

3）顛倒a中位置i、j之間的部分,產(chǎn)生新的結(jié)構(gòu)

^1^2…*3—13-2…邑+13…S/

遺傳算法舉例

問題：求Maxf(x)=x2,xe[0,31]

(1)編碼：xeooooo?inn

此時取均長為5,每個染色體｛?！梗?

(2)初始群體生成：群體大小視情況而定，此處設(shè)

置為4,隨機產(chǎn)生四個個體：

編碼：01101,11000,01000,10011

解碼：1324819

適應(yīng)度：16957664361

(3)適應(yīng)度評價：fitness(x)=x2

（4）選擇：選擇概率々=/./"9=1170

個體：01101,11000,01000,10011

適應(yīng)度：16957664361

選擇概率：0.140.490.060.31

選擇結(jié)果：01101,11000,11000,10011

（5）交叉操作：發(fā)生交叉的概率較大￡=0.8,0.9…

哪兩個個體配對交叉是隨機的0

交叉點位置的選取是隨機的（單點交叉）

onokoiiooii^ooonon

noob"nooiIO^OIIfloooo

(6)變異:發(fā)生變異的概率很小P=0.0001

m

(7)新群體的產(chǎn)生：

保留上一代最優(yōu)個體，一般為10%左右，至少1個

用新個體取代舊個體，隨機取代或擇優(yōu)取代。

11000,11011,11001,10011

(8)重復(fù)上述操作：

說明：GA的終止條件一般人為設(shè)置；

GA只能求次優(yōu)解或滿意解。

分析：按第二代新群體進行遺傳操作，若無變異，永

遠(yuǎn)也找不到最優(yōu)解—擇優(yōu)取代有問題。

若隨機的將個體01101選入新群體中，有可能

找到最優(yōu)解。

11.7并行遺傳算法

基于離散門德爾模型的遺傳算法由六部分組成:

1）對給定問題求解的染色體表示；

2）求解的原始物種；

3）起環(huán)境作用的品質(zhì)函數(shù)；

4）可以生成子孫的個體的選擇過程；

5）一種遺傳操縱子，如變異、重組；

6）控制算法本身的參數(shù)。

并行遺傳算法

并行遺傳算法：

1）給定具有不同開始表型的N個個體;

2）每個個體計算局部最大；

3）選擇—在“近鄰”中選擇配對；

4）用重組和突變創(chuàng)建子孫；

5）返回步驟2。

11.8分類器系統(tǒng)Boole

Wilson于1987年開發(fā)了一個布爾問題的

分類器系統(tǒng)Boole(Wilson1987)。一個布爾

函數(shù)變量L是從長度為L的字符串到｛0,1｝的

映射。學(xué)習(xí)函數(shù)意味獲得對任何輸入字符串

能給出正確輸出0或1的能力。

分類器強度調(diào)整算法

1）將與所選動作相同的分類器形成子集［M］,稱作動

作集［A］。將不在［M］中的其它分類器放在集合

NOT［A］中。

2）在［A］中的全部分類器強度減少一個分?jǐn)?shù)e。

3）如果系統(tǒng)決策正確，則將贏利量R分配給［A］的強

度；

4）如果系統(tǒng)決策錯誤，則將贏利量R，（其中0SRKR）分

配給［A］的強度，從［A］的強度減少一個分?jǐn)?shù)p。至

少R和p中的一個為0。

5）從NOT［A］中的強度減去一個分?jǐn)?shù)仁

Boole的遺傳算法

i）根據(jù)［P］中分類器的強度，通過概率選擇第一個分類器G。

2）根據(jù)概率乙與步驟⑴相同，選擇分類器g，并對C1和g

進行雜交；從結(jié)果中選擇一個作為子孫，另一個被拋棄。

3）如果步驟（2）未完成，則復(fù)制G形成子孫。

4）對子孫應(yīng)用變異操作，以概率〃改變每個分類的等位基因。

5）如果通過雜交生成子孫，每個父母的強度減少三分之一，

子孫的初始強度等于父母減少的總和；否則減少G的一半，

而子孫的初始強度等于減少的量。

6）將子孫加到［P］中。

7）根據(jù)［P］中分類器強度的概率分布，刪除最小的一個分類器。

11.9規(guī)則發(fā)現(xiàn)系統(tǒng)