進(jìn)化計(jì)算課件

第十一章進(jìn)化計(jì)算

史忠植

中科院計(jì)算所

內(nèi)容

11.1概述

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

11.3達(dá)爾文進(jìn)化算法

11.4分類(lèi)器系統(tǒng)

11.5桶鏈算法

11.6遺傳算法

11.7并行遺傳算法

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

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

11.10進(jìn)化策略

11.11進(jìn)化程序設(shè)計(jì)

11.1概述

遺傳算法思想來(lái)源于生物進(jìn)化過(guò)程,它

是基于進(jìn)化過(guò)程中的信息遺傳機(jī)制和優(yōu)勝

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

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

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

發(fā)展歷史

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

■60年代開(kāi)始

■70年代熱門(mén)

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

特點(diǎn)

特點(diǎn)：

■通用

■魯棒

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

遺傳算法能解決的問(wèn)題：

■優(yōu)化

■NP完全

■NP難

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

遺傳算法與自然進(jìn)化的比較

自然界遺傳算法

染色體字符串

基因字符，特征

等位基因(allele)特征值

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

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

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

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

新達(dá)爾文進(jìn)化理論的主要論點(diǎn)

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

2）隨機(jī)過(guò)程在進(jìn)化中起重大作用，遺傳變異大

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

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

變；

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

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

果.

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

基因的變化；

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

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

進(jìn)化的主要過(guò)程

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

???

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

進(jìn)化系統(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達(dá)爾文進(jìn)化算法

1）建立原始種體。

2）通過(guò)突變建立子孫。

s'l=%

x\=x+s；Z]

???

s）=sg丸

3）選擇:

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

l<z<2

4）返回到步驟（1）。

11.4分類(lèi)器系統(tǒng)

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

消息來(lái)自

輸入接口

支付

來(lái)自?xún)?nèi)部監(jiān)控器的消息

（目標(biāo)）

規(guī)則與消息

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

約定：條件的長(zhǎng)度是固定的，用二進(jìn)制數(shù)表示。

定義：

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

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

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

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

分類(lèi)器系統(tǒng)使用兩個(gè)學(xué)習(xí)機(jī)制，

?桶鏈(bucketbrigade)算法?；趯?duì)系統(tǒng)的貢

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

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

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

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

分類(lèi)器

(a)全部消息進(jìn)行條件測(cè)試

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

分類(lèi)器基本算法

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

2）將消息表中的全部消息與全部分類(lèi)器所有

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

3）滿(mǎn)足分類(lèi)器條件部分的每組匹配，將其動(dòng)作

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

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

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

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

6）返回到步驟（1）。

簡(jiǎn)單的視覺(jué)分類(lèi)器系統(tǒng)

視覺(jué)向量

1...1011

消息

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

r1,如果移動(dòng)對(duì)象

Lo,其它

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

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

L如果對(duì)象在中心的右邊

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

〃=其它

"ZLL/1,如其它果對(duì)象很大

,J1,如果對(duì)象是狹長(zhǎng)的

""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)算法基于對(duì)系統(tǒng)的貢獻(xiàn),

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

規(guī)則同時(shí)要求被激活時(shí)的競(jìng)爭(zhēng)問(wèn)題。

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

一##00：0001

0111一01##：0000

一00#0：1100

主要問(wèn)題

引入信用值后的兩個(gè)問(wèn)題：

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

決競(jìng)爭(zhēng)問(wèn)題

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

如何分配信用

_________桶鏈算法

為解決上述兩個(gè)問(wèn)題，引入拍賣(mài)行和票據(jù)交易所:

■當(dāng)有多個(gè)分類(lèi)器獲得匹配時(shí)，每個(gè)分類(lèi)器要出

一個(gè)與其強(qiáng)度成正比的叫價(jià)B

■叫價(jià)高的分類(lèi)器被激活并允許發(fā)送消息，同時(shí)

通過(guò)票據(jù)交易所將其叫價(jià)B提供給激活改分類(lèi)

器的分類(lèi)器。

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

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

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

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

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

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

生新的消費(fèi)者鏈

舉例

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

索引號(hào)分類(lèi)器強(qiáng)度

101##：0000200

200#0：1000200

311##：1000200

4##00：0001200

第一步

分類(lèi)器強(qiáng)度消息匹配叫價(jià)

01##：0000200E20

00#0：1000200

11##：1000200

##00：0001200

第二步

分類(lèi)器強(qiáng)度消息匹配叫價(jià)

01##：00001800000

00#0：1000200120

11##:1000200

##00：0001200120

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

第三步

分類(lèi)器強(qiáng)度消息匹配叫價(jià)

01##：0000220

00#0：10001801100

11##:1000200220

##00：00011800001218

第四步

分類(lèi)器強(qiáng)度消息匹配叫價(jià)

01##：0000220

00#0：1000218

11##:10001801000

##00：0001162316

第五步

分類(lèi)器強(qiáng)度消息匹配叫價(jià)強(qiáng)度

01##：0000220220

00#0：1000218218

11##：1000196196

##00：00011460001206

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

投標(biāo)改變分類(lèi)器的強(qiáng)度

在時(shí)間t對(duì)分類(lèi)器C的支持

對(duì)在t-1作在時(shí)間t滿(mǎn)足C

用的分類(lèi)送去消息的分

器投標(biāo)類(lèi)器

分類(lèi)器中的遺傳算法

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

識(shí)庫(kù)。

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

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

時(shí)使用GA。

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

使用GA。

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

算法步驟

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

2)計(jì)算Bt中全體分類(lèi)器的平均強(qiáng)度Vt,對(duì)每

個(gè)分類(lèi)器賦予一個(gè)標(biāo)準(zhǔn)強(qiáng)度St(Cj)/Vt；

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

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

布，從Bt中選取n個(gè)分類(lèi)器，n?M；

4)對(duì)每個(gè)分類(lèi)器應(yīng)用交叉算子，生成2n個(gè)分

類(lèi)器；

5)將Bt中的2n個(gè)強(qiáng)度最低的分類(lèi)器用新生成

的2n個(gè)取代；

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

算法說(shuō)明

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

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

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

算子；

4）新分類(lèi)器的強(qiáng)度是由舊分類(lèi)器的強(qiáng)度決

定的。

1L6遺傳算法

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

被稱(chēng)為個(gè)體。

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

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

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

■類(lèi)似于自然進(jìn)化，遺傳算法通過(guò)作用于染色體上的基因?qū)?/p>

找好的染色體來(lái)求解問(wèn)題。

■與自然界相似，遺傳算法對(duì)求解問(wèn)題的本身一無(wú)所知，它

所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基

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

殖機(jī)會(huì)。

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

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

個(gè)體給予一個(gè)數(shù)值評(píng)價(jià)，稱(chēng)為適應(yīng)度，取消低適應(yīng)度的個(gè)

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

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

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

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

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

2）遺傳算法不是從單個(gè)點(diǎn),而是在群體中從一

個(gè)點(diǎn)開(kāi)始搜索；

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

輔助信息；

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

則。

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

1）確定表示方案；

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

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

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

基本的遺傳算法

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

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

滿(mǎn)足為止：

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

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

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

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

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

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

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

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

基本遺傳算法的流程圖

（轉(zhuǎn)下頁(yè)）

（接上頁(yè)）

表示模式

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

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

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

f(H)

M(H+1)=M(H

f

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

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

雜交操作

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

換過(guò)程。

■簡(jiǎn)單的雜交操作分為三步

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

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

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

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

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

具有強(qiáng)度的遺傳算法

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

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

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

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

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

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

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

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

度最低的字符串。

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

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

f

■Jggueqoqju!jo，idQ'3”D

變異操作

簡(jiǎn)單的變異操作過(guò)程如下：

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

相獨(dú)立。通過(guò)隨機(jī)過(guò)程選擇發(fā)生變異的位置：

ac],23???13ci

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

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

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

x2xk

反轉(zhuǎn)操作

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

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

a—s島…s’

JL6

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

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

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

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

遺傳算法舉例

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

(1)編碼：xeooooo?inn

此時(shí)取均長(zhǎng)為5,每個(gè)染色體｛?！梗?

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

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

編碼：01101,11000,01000,10011

解碼：1324819

適應(yīng)度：16957664361

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

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

個(gè)體：01101,11000,01000,10011

適應(yīng)度：16957664361

選擇概率：0.140.490.060.31

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

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

哪兩個(gè)個(gè)體配對(duì)交叉是隨機(jī)的0

交叉點(diǎn)位置的選取是隨機(jī)的（單點(diǎn)交叉）

onokoiiooii^ooonon

noob"nooiIO^OIIfloooo

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

m

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

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

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

11000,11011,11001,10011

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

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

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

分析：按第二代新群體進(jìn)行遺傳操作，若無(wú)變異，永

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

若隨機(jī)的將個(gè)體01101選入新群體中，有可能

找到最優(yōu)解。

11.7并行遺傳算法

基于離散門(mén)德?tīng)柲Ｐ偷倪z傳算法由六部分組成:

1）對(duì)給定問(wèn)題求解的染色體表示；

2）求解的原始物種；

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

4）可以生成子孫的個(gè)體的選擇過(guò)程；

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

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

并行遺傳算法

并行遺傳算法：

1）給定具有不同開(kāi)始表型的N個(gè)個(gè)體;

2）每個(gè)個(gè)體計(jì)算局部最大；

3）選擇—在“近鄰”中選擇配對(duì)；

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

5）返回步驟2。

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

Wilson于1987年開(kāi)發(fā)了一個(gè)布爾問(wèn)題的

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

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

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

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

分類(lèi)器強(qiáng)度調(diào)整算法

1）將與所選動(dòng)作相同的分類(lèi)器形成子集［M］,稱(chēng)作動(dòng)

作集［A］。將不在［M］中的其它分類(lèi)器放在集合

NOT［A］中。

2）在［A］中的全部分類(lèi)器強(qiáng)度減少一個(gè)分?jǐn)?shù)e。

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

度；

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

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

少R和p中的一個(gè)為0。

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

Boole的遺傳算法

i）根據(jù)［P］中分類(lèi)器的強(qiáng)度，通過(guò)概率選擇第一個(gè)分類(lèi)器G。

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

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

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

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

5）如果通過(guò)雜交生成子孫，每個(gè)父母的強(qiáng)度減少三分之一，

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

而子孫的初始強(qiáng)度等于減少的量。

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

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

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