第六章 演化規(guī)劃

1、第第6章演化規(guī)劃章演化規(guī)劃 武漢大學(xué)計(jì)算機(jī)學(xué)院武漢大學(xué)計(jì)算機(jī)學(xué)院6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l演化規(guī)劃是由演化規(guī)劃是由L.J.FogelL.J.Fogel等在等在2020世紀(jì)世紀(jì)6060年代提出年代提出的。當(dāng)時(shí)演化規(guī)劃的目標(biāo)是通過模擬進(jìn)化來獲的。當(dāng)時(shí)演化規(guī)劃的目標(biāo)是通過模擬進(jìn)化來獲得智能行為。他們將智能視為能夠預(yù)測(cè)其所在得智能行為。他們將智能視為能夠預(yù)測(cè)其所在環(huán)境的狀態(tài)，并按照預(yù)定目標(biāo)作出適當(dāng)響應(yīng)的環(huán)境的狀態(tài)，并按照預(yù)定目標(biāo)作出適當(dāng)響應(yīng)的能力。對(duì)環(huán)境的預(yù)測(cè)能力是智能行為的一個(gè)重能力。對(duì)環(huán)境的預(yù)測(cè)能力是智能行為的一個(gè)重要特征。要特征。6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l

2、FogelFogel將環(huán)境描述為由有限字符集中的符號(hào)所組將環(huán)境描述為由有限字符集中的符號(hào)所組成的序列，而預(yù)測(cè)器則用有限狀態(tài)自動(dòng)機(jī)來表示。成的序列，而預(yù)測(cè)器則用有限狀態(tài)自動(dòng)機(jī)來表示。一個(gè)有限狀態(tài)自動(dòng)機(jī)是一個(gè)五元組一個(gè)有限狀態(tài)自動(dòng)機(jī)是一個(gè)五元組 其中其中S S是狀態(tài)的集合，是狀態(tài)的集合，I I是輸入符號(hào)的集合，是輸入符號(hào)的集合，O O是是輸出符號(hào)的集合，輸出符號(hào)的集合， 是轉(zhuǎn)移函數(shù)，是轉(zhuǎn)移函數(shù)， 是初始狀態(tài)。圖是初始狀態(tài)。圖6.16.1給出了有限狀態(tài)機(jī)的一個(gè)簡(jiǎn)給出了有限狀態(tài)機(jī)的一個(gè)簡(jiǎn)單的例子。單的例子。),(0sOIS OSIS : Ss 06.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)圖圖6.1

3、一個(gè)有限狀態(tài)自動(dòng)機(jī)一個(gè)有限狀態(tài)自動(dòng)機(jī)ACB0/c1/b0/b1/c0/b1/a開始開始6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l在圖在圖6.16.1所示的有限狀態(tài)自動(dòng)機(jī)中，所示的有限狀態(tài)自動(dòng)機(jī)中， 兩個(gè)狀態(tài)之間的一條有向邊兩個(gè)狀態(tài)之間的一條有向邊指示一個(gè)狀態(tài)轉(zhuǎn)移，而狀態(tài)轉(zhuǎn)移函數(shù)指示一個(gè)狀態(tài)轉(zhuǎn)移，而狀態(tài)轉(zhuǎn)移函數(shù) 由邊上形如的標(biāo)記所指明。譬如，從狀態(tài)由邊上形如的標(biāo)記所指明。譬如，從狀態(tài)A A到狀態(tài)到狀態(tài)B B之間的有向邊的標(biāo)記為之間的有向邊的標(biāo)記為 則該標(biāo)記所表示的則該標(biāo)記所表示的狀態(tài)轉(zhuǎn)移為狀態(tài)轉(zhuǎn)移為 即若當(dāng)前狀態(tài)為即若當(dāng)前狀態(tài)為A A且且輸入符號(hào)為輸入符號(hào)為0 0時(shí)，機(jī)器轉(zhuǎn)移到狀態(tài)時(shí)，機(jī)器轉(zhuǎn)

4、移到狀態(tài)B B且輸出符號(hào)且輸出符號(hào)b b。初始狀態(tài)為初始狀態(tài)為A A。,CBAS ,1 , 0 I,cbaO OSIS : ),()0 ,(bBA ,/0 b6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l一個(gè)簡(jiǎn)單的預(yù)測(cè)任務(wù)是：給定一個(gè)序列一個(gè)簡(jiǎn)單的預(yù)測(cè)任務(wù)是：給定一個(gè)序列 在觀察到前在觀察到前n n個(gè)符號(hào)個(gè)符號(hào) 的基礎(chǔ)的基礎(chǔ)上，預(yù)測(cè)第上，預(yù)測(cè)第 個(gè)符號(hào)。個(gè)符號(hào)。l演化規(guī)劃就是通過模擬生物進(jìn)化的方式演化出能演化規(guī)劃就是通過模擬生物進(jìn)化的方式演化出能夠執(zhí)行預(yù)測(cè)任務(wù)的有限狀態(tài)自動(dòng)機(jī)夠執(zhí)行預(yù)測(cè)任務(wù)的有限狀態(tài)自動(dòng)機(jī). .l當(dāng)輸入序列為當(dāng)輸入序列為 時(shí)，有限狀態(tài)時(shí)，有限狀態(tài)自動(dòng)機(jī)產(chǎn)生一個(gè)輸出序列自動(dòng)機(jī)產(chǎn)生

5、一個(gè)輸出序列 其中其中 是對(duì)是對(duì) 的預(yù)測(cè)。的預(yù)測(cè)。,21aa), 2 , 1(,21 naaan1 n), 2 , 1(,21 naaan,21nbbb)1, 2 , 1( nibi1 ia6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l一個(gè)執(zhí)行這種預(yù)測(cè)任務(wù)的自動(dòng)機(jī)如圖一個(gè)執(zhí)行這種預(yù)測(cè)任務(wù)的自動(dòng)機(jī)如圖6.26.2所示。所示。l當(dāng)輸入序列為當(dāng)輸入序列為011101011101時(shí)，所產(chǎn)生的輸出序列為時(shí)，所產(chǎn)生的輸出序列為110111110111。這時(shí)，當(dāng)。這時(shí)，當(dāng)n=1，2，5時(shí)，機(jī)器作出了準(zhǔn)時(shí)，機(jī)器作出了準(zhǔn)確的預(yù)測(cè)，預(yù)測(cè)準(zhǔn)確率為確的預(yù)測(cè)，預(yù)測(cè)準(zhǔn)確率為60%。 圖圖6.2 作為預(yù)測(cè)器的有限狀態(tài)自動(dòng)機(jī)

6、作為預(yù)測(cè)器的有限狀態(tài)自動(dòng)機(jī)ACB0/01/10/11/00/11/1開始開始6.1 演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu)l用演化規(guī)劃求解上述問題的方法是：保持一個(gè)用演化規(guī)劃求解上述問題的方法是：保持一個(gè)具有具有 個(gè)有限狀態(tài)自動(dòng)機(jī)的種群，對(duì)種群中的個(gè)有限狀態(tài)自動(dòng)機(jī)的種群，對(duì)種群中的每個(gè)自動(dòng)機(jī)進(jìn)行變異得到每個(gè)自動(dòng)機(jī)進(jìn)行變異得到 個(gè)后代。變異通常個(gè)后代。變異通常有改變輸出符號(hào)、改變狀態(tài)轉(zhuǎn)移、添加一個(gè)狀有改變輸出符號(hào)、改變狀態(tài)轉(zhuǎn)移、添加一個(gè)狀態(tài)、刪除一個(gè)狀態(tài)和改變初始狀態(tài)五種方式。態(tài)、刪除一個(gè)狀態(tài)和改變初始狀態(tài)五種方式。然后根據(jù)對(duì)有限狀態(tài)自動(dòng)機(jī)的某種適應(yīng)值度量，然后根據(jù)對(duì)有限狀態(tài)自動(dòng)機(jī)的某種適應(yīng)值度量

7、，從個(gè)從個(gè) 父體和父體和 個(gè)后代中選取個(gè)后代中選取 個(gè)個(gè)體作為下個(gè)個(gè)體作為下一代種群。一代種群。 6.1演化規(guī)劃的基本結(jié)構(gòu)演化規(guī)劃的基本結(jié)構(gòu) endsolution;best the return while end ; 1 );(,),( )(elect survivor_s ) 1( for; end );)(evaluate( );(mutate()( do to 1for do condition) nterminatio(not while );(evaluate( );(,),(),()(initialize ; 0 begin mingry_ProgramEvolutiona p

8、rocedure121 tttototPtPtotatoitPtatatatPtiii 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l表示表示 (1)(1)標(biāo)準(zhǔn)演化規(guī)劃標(biāo)準(zhǔn)演化規(guī)劃 (2)(2)元演化規(guī)劃元演化規(guī)劃 (3)(3)旋轉(zhuǎn)演化規(guī)劃旋轉(zhuǎn)演化規(guī)劃 ),(21nxxxx ),(),(2121nnxxxx ),(),(212121mnnxxxx 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l其中其中 表示表示 與與 之間的相關(guān)之間的相關(guān)系數(shù)，系數(shù)， 表示表示 與與 之間的相關(guān)系數(shù)，之間的相關(guān)系數(shù)， 表示表示 與與 之間的相關(guān)系數(shù)。之間的相關(guān)系數(shù)。l若若 表示變量表示變量 與與 之間的相關(guān)系數(shù)

9、，則之間的相關(guān)系數(shù)，則 與與 之間的協(xié)方差由下式確定：之間的協(xié)方差由下式確定：. 2/ )1( nnm1 1x2x2 1x3xm nx1 nxk ixjxixjx,jiijkc 1 , 1 k 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l由協(xié)方差由協(xié)方差 可以構(gòu)可以構(gòu)成協(xié)方差矩陣成協(xié)方差矩陣C，而，而 其中其中 lC用于產(chǎn)生服從用于產(chǎn)生服從n n維正態(tài)分布的隨機(jī)向量維正態(tài)分布的隨機(jī)向量 ), 1; 1, 2 , 1(nijnicij nnnnnccccccC 2122211121)(jiccjiij ), 0(CN6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l變異變異 (1) 標(biāo)準(zhǔn)演化規(guī)劃標(biāo)

10、準(zhǔn)演化規(guī)劃 這時(shí)個(gè)體的表示為這時(shí)個(gè)體的表示為 變異操作為：變異操作為： 其中其中 為個(gè)體為個(gè)體x x的適應(yīng)值，的適應(yīng)值， 為為待定的參數(shù)。通常取待定的參數(shù)。通常取 ).,(21nxxxx iiiiiiixFNxx )()1 , 0()(xF), 2 , 1(,niii , 1 i . 0 i 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l(2) 元演化規(guī)劃元演化規(guī)劃 這時(shí)個(gè)體的表示為這時(shí)個(gè)體的表示為 變異操作為：變異操作為： 其中其中 為常系數(shù)為常系數(shù). . ),(),(11nnxxx )1 , 0()1 , 0(iiiiiiiiNNxx 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l(3)

11、旋轉(zhuǎn)演化規(guī)劃旋轉(zhuǎn)演化規(guī)劃 這時(shí)個(gè)體的表示為這時(shí)個(gè)體的表示為 變異操作為：變異操作為： 其中其中 為常系數(shù)。為常系數(shù)。 ),(),(111mnnxxx )1 , 0()1 , 0(), 0(jjjjiiiiNNCNxx ,6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l目前已經(jīng)提出多種變異算子。這些變異算子的目前已經(jīng)提出多種變異算子。這些變異算子的區(qū)別主要在于：區(qū)別主要在于： (1) (1) 修改變異步長(zhǎng)公式的不同；修改變異步長(zhǎng)公式的不同； (2) (2) 在公式中使用方差而不是標(biāo)準(zhǔn)差；在公式中使用方差而不是標(biāo)準(zhǔn)差； (3) (3) 和和x x被變異的次序不同。被變異的次序不同。l譬如，對(duì)元演化規(guī)

12、劃，有人提出下面的變異公譬如，對(duì)元演化規(guī)劃，有人提出下面的變異公式：式： )1 , 0()1 , 0(1(iiiiiiNxxN 2 . 0 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)l父體選擇父體選擇 演化規(guī)劃中的父體選擇非常簡(jiǎn)單。在演化規(guī)劃演化規(guī)劃中的父體選擇非常簡(jiǎn)單。在演化規(guī)劃中，種群中的每個(gè)個(gè)體經(jīng)過變異恰好產(chǎn)生一個(gè)后中，種群中的每個(gè)個(gè)體經(jīng)過變異恰好產(chǎn)生一個(gè)后代。種群中的每個(gè)個(gè)體都是一個(gè)父體，無需進(jìn)行代。種群中的每個(gè)個(gè)體都是一個(gè)父體，無需進(jìn)行專門選擇。專門選擇。l存活選擇存活選擇 存活選擇從存活選擇從 個(gè)父體和個(gè)父體和 個(gè)后代中選取個(gè)后代中選取 個(gè)作個(gè)作為下一代種群為下一代種群。 l通常

13、演化規(guī)劃采用隨機(jī)型競(jìng)爭(zhēng)選擇。在這種方法通常演化規(guī)劃采用隨機(jī)型競(jìng)爭(zhēng)選擇。在這種方法中，對(duì)每個(gè)個(gè)體中，對(duì)每個(gè)個(gè)體 其中其中 為為 個(gè)個(gè)后代的集合，從后代的集合，從 中隨機(jī)地選取中隨機(jī)地選取q q個(gè)個(gè)個(gè)個(gè)體。然后將個(gè)體體。然后將個(gè)體a a的適應(yīng)值分別與這的適應(yīng)值分別與這q q個(gè)個(gè)體的適個(gè)個(gè)體的適應(yīng)值進(jìn)行比較，并記錄個(gè)體應(yīng)值進(jìn)行比較，并記錄個(gè)體a a的適應(yīng)值優(yōu)于或等的適應(yīng)值優(yōu)于或等于所比較個(gè)體適應(yīng)值的次數(shù)，該次數(shù)稱為個(gè)體于所比較個(gè)體適應(yīng)值的次數(shù)，該次數(shù)稱為個(gè)體a a的得分。最后，將的得分。最后，將 中的個(gè)個(gè)體按照它中的個(gè)個(gè)體按照它們的得分按降序排序，并選擇前們的得分按降序排序，并選擇前 個(gè)個(gè)體作為個(gè)個(gè)

14、體作為 ),()(tPtPa )(tP )()(tPtP )()(tPtP 6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù)6.2 演化規(guī)劃的實(shí)現(xiàn)技術(shù)演化規(guī)劃的實(shí)現(xiàn)技術(shù) 下一代種群下一代種群. .lq- -競(jìng)爭(zhēng)選擇是一種隨機(jī)選擇。總的來說，優(yōu)良競(jìng)爭(zhēng)選擇是一種隨機(jī)選擇?？偟膩碚f，優(yōu)良個(gè)體進(jìn)入下一代種群的機(jī)會(huì)較大，但較差個(gè)體個(gè)體進(jìn)入下一代種群的機(jī)會(huì)較大，但較差個(gè)體也有進(jìn)入下一代種群的機(jī)會(huì)。隨著也有進(jìn)入下一代種群的機(jī)會(huì)。隨著q q值的增加，值的增加，較差個(gè)體進(jìn)入下一代種群的機(jī)會(huì)減小。當(dāng)較差個(gè)體進(jìn)入下一代種群的機(jī)會(huì)減小。當(dāng)q q增加增加到其最大值到其最大值 時(shí)，競(jìng)爭(zhēng)選擇演變?yōu)檠莼呗詴r(shí)，競(jìng)爭(zhēng)選擇演變?yōu)檠莼?/p>

15、策略中的中的 確定性確定性 選擇。選擇。 2)( 6.3 應(yīng)用實(shí)例應(yīng)用實(shí)例l作為演化規(guī)劃的一個(gè)應(yīng)用實(shí)例，我們還是考慮作為演化規(guī)劃的一個(gè)應(yīng)用實(shí)例，我們還是考慮下面的下面的AckleyAckley函數(shù)的優(yōu)化問題：函數(shù)的優(yōu)化問題：l用元演化規(guī)劃求解該問題，其設(shè)計(jì)如下：用元演化規(guī)劃求解該問題，其設(shè)計(jì)如下： (1)(1)表示：個(gè)體的表示為如下形式表示：個(gè)體的表示為如下形式71282. 2;30, 2 , 1 ,3030 20)2cos(301exp3012 . 0exp20),(min30130123021 eixexxxxxfiiiii ),(30213021 xxx6.3 應(yīng)用實(shí)例應(yīng)用實(shí)例 (2)

16、適應(yīng)函數(shù)：適應(yīng)函數(shù)取為目標(biāo)函數(shù)。適應(yīng)函數(shù)：適應(yīng)函數(shù)取為目標(biāo)函數(shù)。 (3) 參數(shù)設(shè)置：參數(shù)設(shè)置： (4) 終止準(zhǔn)則：當(dāng)進(jìn)行終止準(zhǔn)則：當(dāng)進(jìn)行200000200000次函數(shù)值計(jì)算或發(fā)現(xiàn)次函數(shù)值計(jì)算或發(fā)現(xiàn)最優(yōu)解后終止算法。最優(yōu)解后終止算法。 (5) 種群初始化：初始種群中每個(gè)個(gè)體的變量部分種群初始化：初始種群中每個(gè)個(gè)體的變量部分隨機(jī)地產(chǎn)生，每個(gè)變量均勻地分布在區(qū)間隨機(jī)地產(chǎn)生，每個(gè)變量均勻地分布在區(qū)間 內(nèi)。每個(gè)個(gè)體的變異步長(zhǎng)都相同，設(shè)為內(nèi)。每個(gè)個(gè)體的變異步長(zhǎng)都相同，設(shè)為 運(yùn)行上述算法運(yùn)行上述算法1010次，每次找到的最好解都位于全次，每次找到的最好解都位于全局最優(yōu)峰上。最好解的平均函數(shù)值為局最優(yōu)峰上。最

17、好解的平均函數(shù)值為,200 ,10 q6 30 ,30 . 3 .1039. 12 演化計(jì)算課程論文題目演化計(jì)算課程論文題目( (下列題目選擇之一下列題目選擇之一) ) 1 用遺傳算法用遺傳算法求解下列約束優(yōu)化問題：求解下列約束優(yōu)化問題： 其中其中 )()2sin()2(sin),(max213121321xxxxxxxf 0)4(1012221221 xxxx100 ,10021 xx演化計(jì)算課程論文題目演化計(jì)算課程論文題目( (下列題目選擇之一下列題目選擇之一) )2 用遺傳算法求解下列優(yōu)化問題用遺傳算法求解下列優(yōu)化問題(n=2,4,6,8,10,20) 并研究問題的維數(shù)對(duì)算法性能的影響并研究問題的維數(shù)對(duì)算法性能的影響。71828. 2;, 2 , 1 ,3030 20)2cos(1exp12 . 0exp20),.,(min1121