第八章進(jìn)化策略和進(jìn)化規(guī)劃PPT課件

1、進(jìn)化策略和進(jìn)化規(guī)劃進(jìn)化策略和進(jìn)化規(guī)劃德國(guó)學(xué)者德國(guó)學(xué)者Schwefel和和Rechenburg美國(guó)學(xué)者美國(guó)學(xué)者Fogel分別提分別提出出進(jìn)化策略進(jìn)化策略ES和和進(jìn)化規(guī)劃進(jìn)化規(guī)劃EP。這三種方法具有共同的。這三種方法具有共同的本質(zhì)，分別強(qiáng)調(diào)了自然進(jìn)化中的不同方面：遺傳算法本質(zhì)，分別強(qiáng)調(diào)了自然進(jìn)化中的不同方面：遺傳算法強(qiáng)調(diào)染色體的操作，進(jìn)化策略強(qiáng)調(diào)了個(gè)體級(jí)的行為變強(qiáng)調(diào)染色體的操作，進(jìn)化策略強(qiáng)調(diào)了個(gè)體級(jí)的行為變化。而進(jìn)化規(guī)劃則強(qiáng)調(diào)種群級(jí)上的行為變化?，F(xiàn)在學(xué)化。而進(jìn)化規(guī)劃則強(qiáng)調(diào)種群級(jí)上的行為變化。現(xiàn)在學(xué)術(shù)界把遺傳算法術(shù)界把遺傳算法GA、進(jìn)化策略、進(jìn)化策略ES和進(jìn)化規(guī)劃和進(jìn)化規(guī)劃EP通稱通稱為進(jìn)化算法為進(jìn)

2、化算法EC。8.1 進(jìn)化算法的早期研究進(jìn)化算法的早期研究進(jìn)化算法起源于進(jìn)化算法起源于20世紀(jì)世紀(jì)30年代的通過仿真生物進(jìn)化過程進(jìn)行機(jī)器年代的通過仿真生物進(jìn)化過程進(jìn)行機(jī)器學(xué)習(xí)的研究。早在學(xué)習(xí)的研究。早在1932年，年，Cannon就把自然進(jìn)化想象為一個(gè)學(xué)習(xí)就把自然進(jìn)化想象為一個(gè)學(xué)習(xí)過程。與自然進(jìn)化過程的機(jī)制和結(jié)果稍微不同是，過程。與自然進(jìn)化過程的機(jī)制和結(jié)果稍微不同是，Cannon不是通不是通過維持一個(gè)特定的種群來進(jìn)行搜索，而是對(duì)單個(gè)個(gè)體反復(fù)進(jìn)行隨過維持一個(gè)特定的種群來進(jìn)行搜索，而是對(duì)單個(gè)個(gè)體反復(fù)進(jìn)行隨機(jī)試驗(yàn)。到了機(jī)試驗(yàn)。到了1950年，年，Turng認(rèn)識(shí)到，在機(jī)器學(xué)習(xí)和進(jìn)化之間存認(rèn)識(shí)到，在機(jī)器學(xué)

3、習(xí)和進(jìn)化之間存在著明顯的關(guān)系。在著明顯的關(guān)系。1959年，年，F(xiàn)riedman推測(cè)，利用變異和選擇的仿推測(cè)，利用變異和選擇的仿真可以設(shè)計(jì)真可以設(shè)計(jì)“思想機(jī)器思想機(jī)器”，并且指出下棋的程序可以用這種方法，并且指出下棋的程序可以用這種方法設(shè)計(jì)。在設(shè)計(jì)。在1960年，年，Cambell猜想：在導(dǎo)致知識(shí)擴(kuò)張的所有過程中，猜想：在導(dǎo)致知識(shí)擴(kuò)張的所有過程中，都要涉及都要涉及“盲目盲目變化變化選擇選擇幸存幸存”的過程。此后，一些學(xué)者的過程。此后，一些學(xué)者逐漸將進(jìn)化理論用于隨機(jī)工程控制、機(jī)器學(xué)習(xí)和函數(shù)優(yōu)化等領(lǐng)域。逐漸將進(jìn)化理論用于隨機(jī)工程控制、機(jī)器學(xué)習(xí)和函數(shù)優(yōu)化等領(lǐng)域。8.2 進(jìn)化策略進(jìn)化策略進(jìn)化策略（進(jìn)化策

4、略（Evolutionary Strategies）是在）是在1965年由年由Rechenburg和和Schwefel獨(dú)立提出的。獨(dú)立提出的。早期的進(jìn)化策略的種群中只包含一個(gè)個(gè)體，并且只使用變異操作。早期的進(jìn)化策略的種群中只包含一個(gè)個(gè)體，并且只使用變異操作。在每一代中，變異后的個(gè)體與其父代進(jìn)行比較，并選擇較好的一在每一代中，變異后的個(gè)體與其父代進(jìn)行比較，并選擇較好的一個(gè)，這種選擇策略被稱為（個(gè)，這種選擇策略被稱為（1+1）策略。）策略。進(jìn)化策略中的個(gè)體用傳統(tǒng)的十進(jìn)制實(shí)型數(shù)表示，即：進(jìn)化策略中的個(gè)體用傳統(tǒng)的十進(jìn)制實(shí)型數(shù)表示，即：Xt第第t代個(gè)體的數(shù)值，代個(gè)體的數(shù)值，N(0,)服從正態(tài)分布的隨機(jī)數(shù)

5、，其均值為零，標(biāo)準(zhǔn)差為服從正態(tài)分布的隨機(jī)數(shù)，其均值為零，標(biāo)準(zhǔn)差為。8.2 進(jìn)化策略進(jìn)化策略進(jìn)化策略的一般算法可以描述如下：進(jìn)化策略的一般算法可以描述如下：?jiǎn)栴}為尋找實(shí)值問題為尋找實(shí)值n維矢量維矢量x，使得函數(shù)，使得函數(shù)F(x):RnR取取極值。不失一極值。不失一般性，設(shè)此程序?yàn)闃O小化過程。般性，設(shè)此程序?yàn)闃O小化過程。從各維的可行范圍內(nèi)隨機(jī)選取親本從各維的可行范圍內(nèi)隨機(jī)選取親本xi，i1，p的初始值。初的初始值。初始試驗(yàn)的分布一般是均勻分布。始試驗(yàn)的分布一般是均勻分布。通過對(duì)于通過對(duì)于x的每個(gè)分量增加零均值和預(yù)先選定的標(biāo)準(zhǔn)差的高斯隨的每個(gè)分量增加零均值和預(yù)先選定的標(biāo)準(zhǔn)差的高斯隨機(jī)變量，從每個(gè)親本

6、機(jī)變量，從每個(gè)親本xi產(chǎn)生子代產(chǎn)生子代xi。通過將誤差通過將誤差F(xi)和和F(xi)，i1，p進(jìn)行排序，選擇并決定哪進(jìn)行排序，選擇并決定哪些矢量保留。具有最小誤差的些矢量保留。具有最小誤差的p個(gè)矢量變成下一代的新親本。個(gè)矢量變成下一代的新親本。(1) 進(jìn)行新試驗(yàn)，選擇具有最小方差的新子代，一直到獲得充分解，進(jìn)行新試驗(yàn)，選擇具有最小方差的新子代，一直到獲得充分解，或者直到滿足某個(gè)終止條件或者直到滿足某個(gè)終止條件8.2 進(jìn)化策略進(jìn)化策略在這個(gè)模型中，把試驗(yàn)解的分量看做個(gè)體的行為特性，而在這個(gè)模型中，把試驗(yàn)解的分量看做個(gè)體的行為特性，而不是沿染色體排列的基因?？梢院筒皇茄厝旧w排列的基因?？梢院?/p>

7、GA一樣，假設(shè)這些表現(xiàn)一樣，假設(shè)這些表現(xiàn)型特征具有基因根源，但是它們之間的聯(lián)系實(shí)質(zhì)并沒有被型特征具有基因根源，但是它們之間的聯(lián)系實(shí)質(zhì)并沒有被弄清楚，所以我們把著重點(diǎn)放在個(gè)體的行為特性上。弄清楚，所以我們把著重點(diǎn)放在個(gè)體的行為特性上。假設(shè)不管發(fā)生什么遺傳變換，所造成各個(gè)行為的變化均遵假設(shè)不管發(fā)生什么遺傳變換，所造成各個(gè)行為的變化均遵循零均值和某個(gè)標(biāo)準(zhǔn)差的高斯分布。循零均值和某個(gè)標(biāo)準(zhǔn)差的高斯分布。由于基因多效性和多基因性，特定基因的改變可以影響許由于基因多效性和多基因性，特定基因的改變可以影響許多表現(xiàn)型特征。所以在創(chuàng)造新子代時(shí)，較為合適的是同時(shí)多表現(xiàn)型特征。所以在創(chuàng)造新子代時(shí)，較為合適的是同時(shí)改變

8、親本所有分量。改變親本所有分量。8.2 進(jìn)化策略進(jìn)化策略進(jìn)化策略的最初試驗(yàn)采用上述算法，主要采用單親本進(jìn)化策略的最初試驗(yàn)采用上述算法，主要采用單親本單子代單子代的搜索，即的搜索，即“（1+1）進(jìn)化策略進(jìn)化策略(1+1)-ES)”，其中單個(gè)子，其中單個(gè)子代是由單個(gè)親本產(chǎn)生的，它們都被置于生存競(jìng)爭(zhēng)中，較弱代是由單個(gè)親本產(chǎn)生的，它們都被置于生存競(jìng)爭(zhēng)中，較弱的一個(gè)要被挑選出來消去。的一個(gè)要被挑選出來消去。當(dāng)把這種算法用于函數(shù)優(yōu)化時(shí)，發(fā)現(xiàn)它有兩個(gè)缺點(diǎn)：當(dāng)把這種算法用于函數(shù)優(yōu)化時(shí)，發(fā)現(xiàn)它有兩個(gè)缺點(diǎn)：各維取定常的標(biāo)準(zhǔn)差使得程序收斂到最優(yōu)解的速度很慢；各維取定常的標(biāo)準(zhǔn)差使得程序收斂到最優(yōu)解的速度很慢；(1)

9、點(diǎn)到點(diǎn)搜索的脆弱本質(zhì)使得程序在局部極值附近容易受停點(diǎn)到點(diǎn)搜索的脆弱本質(zhì)使得程序在局部極值附近容易受停滯的影響（雖然此算法表明可以漸近地收斂到全局最優(yōu)滯的影響（雖然此算法表明可以漸近地收斂到全局最優(yōu)點(diǎn)）。點(diǎn)）。8.2 進(jìn)化策略進(jìn)化策略( + 1)-ES:早期的早期的(1十十1)-ES，沒有體現(xiàn)群體的作用，只是單個(gè)個(gè)體在進(jìn)，沒有體現(xiàn)群體的作用，只是單個(gè)個(gè)體在進(jìn)化，具有明顯的局限性。隨后，化，具有明顯的局限性。隨后，Rechenberg又提出又提出(+1)-ES，在這種進(jìn)化策略中，父代有，在這種進(jìn)化策略中，父代有個(gè)個(gè)體個(gè)個(gè)體(1)，并且引入，并且引入重組重組(Recombination)算子，使父代

10、個(gè)體組合出新的個(gè)體。算子，使父代個(gè)體組合出新的個(gè)體。在執(zhí)行重組時(shí)，從在執(zhí)行重組時(shí)，從個(gè)父代個(gè)體中用隨機(jī)的方法任選兩個(gè)個(gè)個(gè)父代個(gè)體中用隨機(jī)的方法任選兩個(gè)個(gè)體：體：8.2 進(jìn)化策略進(jìn)化策略然后從這兩個(gè)個(gè)體中組合出如下新個(gè)體：然后從這兩個(gè)個(gè)體中組合出如下新個(gè)體：式中式中qi1或或2，它以相同的概率針對(duì)，它以相同的概率針對(duì)i1，2，n隨機(jī)選取。隨機(jī)選取。對(duì)重組產(chǎn)生的新個(gè)體執(zhí)行突變操作，突變方式及對(duì)重組產(chǎn)生的新個(gè)體執(zhí)行突變操作，突變方式及的調(diào)整與的調(diào)整與(1+1)-ES相同。相同。將突變后的個(gè)體與父代將突變后的個(gè)體與父代個(gè)個(gè)體相比較，若優(yōu)于父代最差個(gè)體，個(gè)個(gè)體相比較，若優(yōu)于父代最差個(gè)體，則代替后者成為下

11、一代則代替后者成為下一代個(gè)個(gè)體新成員，否則，重新執(zhí)行重個(gè)個(gè)體新成員，否則，重新執(zhí)行重組和突變產(chǎn)生另一新個(gè)體，組和突變產(chǎn)生另一新個(gè)體，8.2 進(jìn)化策略進(jìn)化策略(+1)-ES和和(1+1)-ES具有相同的策略：只產(chǎn)生一個(gè)新個(gè)體。具有相同的策略：只產(chǎn)生一個(gè)新個(gè)體。(+1)-ES的特點(diǎn)在于：的特點(diǎn)在于： (1) 采用群體，其中包含采用群體，其中包含個(gè)個(gè)體；個(gè)個(gè)體； (2) 增添重組算子，它相當(dāng)于遺傳算法中的交叉算子，從父增添重組算子，它相當(dāng)于遺傳算法中的交叉算子，從父代繼承信息構(gòu)成新個(gè)體。代繼承信息構(gòu)成新個(gè)體。顯然，顯然，(+1)-ES比比(1+1)-ES有了明顯的改進(jìn)，為進(jìn)化策略這種有了明顯的改進(jìn)，

12、為進(jìn)化策略這種新的進(jìn)化算法奠定良好的基礎(chǔ)。新的進(jìn)化算法奠定良好的基礎(chǔ)。8.2 進(jìn)化策略進(jìn)化策略在在1973年，年，Rechenburg把該算法的期望收斂速度定義為對(duì)把該算法的期望收斂速度定義為對(duì)最優(yōu)點(diǎn)的平均距離與要得到此改善所需要的試驗(yàn)次數(shù)之比。最優(yōu)點(diǎn)的平均距離與要得到此改善所需要的試驗(yàn)次數(shù)之比。1981年，年，Schwefel在進(jìn)化策略中使用多重親本和子代，這是在進(jìn)化策略中使用多重親本和子代，這是Rechenburg早期工作（使用多重親本，但是僅使用單個(gè)子早期工作（使用多重親本，但是僅使用單個(gè)子代）的發(fā)展，后來考察了兩種方法，分別表示為代）的發(fā)展，后來考察了兩種方法，分別表示為(+)-ES相

13、相(，)-ES。在前者中，。在前者中，個(gè)親本制造個(gè)親本制造個(gè)子代，所有解均個(gè)子代，所有解均參加生存競(jìng)爭(zhēng)，選出最好的參加生存競(jìng)爭(zhēng)，選出最好的個(gè)作為下一代的親本。在后者個(gè)作為下一代的親本。在后者中，只有中，只有（ ）個(gè)子代參加生存競(jìng)爭(zhēng)，在每代中）個(gè)子代參加生存競(jìng)爭(zhēng)，在每代中個(gè)親個(gè)親本被完全取代。這就是說，對(duì)于每一代，每個(gè)解張成的生本被完全取代。這就是說，對(duì)于每一代，每個(gè)解張成的生命是有限的。增加種群大小，就在固定數(shù)目的世代中增加命是有限的。增加種群大小，就在固定數(shù)目的世代中增加了優(yōu)化速率。了優(yōu)化速率。8.2 進(jìn)化策略進(jìn)化策略Rechenburg引入了如下想法，在每個(gè)新樣本的特征分布中附加了引入了如

14、下想法，在每個(gè)新樣本的特征分布中附加了一個(gè)自適應(yīng)參數(shù)。在這個(gè)方法中，每個(gè)解矢量不僅包括了一個(gè)自適應(yīng)參數(shù)。在這個(gè)方法中，每個(gè)解矢量不僅包括了n維試維試驗(yàn)矢量驗(yàn)矢量x，而且還包括了擾動(dòng)矢量，而且還包括了擾動(dòng)矢量，后者給出如何變異，后者給出如何變異x以及它以及它本身如何變異的指令。例如，設(shè)本身如何變異的指令。例如，設(shè)x為當(dāng)前矢量，為當(dāng)前矢量， 為對(duì)應(yīng)于為對(duì)應(yīng)于x每個(gè)每個(gè)維的方差矢量，于是新的解矢量維的方差矢量，于是新的解矢量x， 可以這樣產(chǎn)生：可以這樣產(chǎn)生：N(0,1)表示單個(gè)標(biāo)準(zhǔn)高所隨機(jī)變量，表示單個(gè)標(biāo)準(zhǔn)高所隨機(jī)變量， Ni(0,1)表示第表示第i個(gè)獨(dú)立相同的個(gè)獨(dú)立相同的標(biāo)準(zhǔn)高斯分布，標(biāo)準(zhǔn)高斯分布

15、，和和是影響總體和個(gè)體步長(zhǎng)的算子集參數(shù)。以這是影響總體和個(gè)體步長(zhǎng)的算子集參數(shù)。以這種方式，進(jìn)化策略可以在線地適應(yīng)誤差曲面的寬度，并且更恰當(dāng)種方式，進(jìn)化策略可以在線地適應(yīng)誤差曲面的寬度，并且更恰當(dāng)?shù)胤峙鋵?shí)驗(yàn)次數(shù)。地分配實(shí)驗(yàn)次數(shù)。進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)問題的表達(dá)：?jiǎn)栴}的表達(dá)：為了與突變操作相適應(yīng)，進(jìn)化策略有兩種表達(dá)方式。為了與突變操作相適應(yīng)，進(jìn)化策略有兩種表達(dá)方式。(1) 二元表達(dá)方式二元表達(dá)方式。這種表達(dá)方式中個(gè)體由目標(biāo)變量。這種表達(dá)方式中個(gè)體由目標(biāo)變量X和標(biāo)準(zhǔn)差和標(biāo)準(zhǔn)差兩部?jī)刹糠纸M成，每部分又可以有分組成，每部分又可以有n個(gè)分量，即：個(gè)分量，即：X和和的關(guān)系為的關(guān)系為:為全局系數(shù)

16、，常取為全局系數(shù)，常取1。進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)(2) 三元表達(dá)方式三元表達(dá)方式。為了改善進(jìn)化策略的收斂速度，。為了改善進(jìn)化策略的收斂速度，Schwefel在二元在二元表達(dá)的基礎(chǔ)上引入第三個(gè)因子表達(dá)的基礎(chǔ)上引入第三個(gè)因子坐標(biāo)旋轉(zhuǎn)角度坐標(biāo)旋轉(zhuǎn)角度。個(gè)體的描述。個(gè)體的描述擴(kuò)展為擴(kuò)展為(X, , )，即：，即：三者的關(guān)系為：三者的關(guān)系為：i父代個(gè)體父代個(gè)體i分量與分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；分量間坐標(biāo)的旋轉(zhuǎn)角度；j子代新個(gè)體子代新個(gè)體i分量與分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；分量間坐標(biāo)的旋轉(zhuǎn)角度；系數(shù)，常取系數(shù)，常取0.0873；zi取決于取決于及及的正態(tài)分布隨機(jī)數(shù)。的正態(tài)分布隨機(jī)數(shù)。進(jìn)

17、化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)旋轉(zhuǎn)角度旋轉(zhuǎn)角度i表面上是分量表面上是分量i與與j間坐標(biāo)的旋轉(zhuǎn)角度，實(shí)質(zhì)上它是間坐標(biāo)的旋轉(zhuǎn)角度，實(shí)質(zhì)上它是分量分量i與分量與分量j之間協(xié)方差的體現(xiàn)。之間協(xié)方差的體現(xiàn)。重組重組進(jìn)化策略中的重組進(jìn)化策略中的重組(Recombination)算子相當(dāng)于遺傳算法的交算子相當(dāng)于遺傳算法的交叉，它們都是以兩個(gè)父代個(gè)體為基礎(chǔ)進(jìn)行信息交換。進(jìn)化叉，它們都是以兩個(gè)父代個(gè)體為基礎(chǔ)進(jìn)行信息交換。進(jìn)化策略中，重組方式主要有三種：策略中，重組方式主要有三種：(1)離散重組離散重組。先隨機(jī)選擇兩個(gè)父代個(gè)體。先隨機(jī)選擇兩個(gè)父代個(gè)體進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)然后將其分量進(jìn)行隨機(jī)交換

18、，構(gòu)成子代新個(gè)體的各個(gè)分量，從而得然后將其分量進(jìn)行隨機(jī)交換，構(gòu)成子代新個(gè)體的各個(gè)分量，從而得出如下新個(gè)體：出如下新個(gè)體：(2) 中值重組中值重組。這種重組方式也是先隨機(jī)選擇兩個(gè)父代個(gè)體，然后將。這種重組方式也是先隨機(jī)選擇兩個(gè)父代個(gè)體，然后將父代個(gè)體各分量的平均值作為子代新個(gè)體的分量，構(gòu)成的新個(gè)體父代個(gè)體各分量的平均值作為子代新個(gè)體的分量，構(gòu)成的新個(gè)體為：為：這時(shí)，新個(gè)體的各個(gè)分量兼容兩個(gè)父代個(gè)體信息，而在離散重組中這時(shí)，新個(gè)體的各個(gè)分量兼容兩個(gè)父代個(gè)體信息，而在離散重組中則只含有某一個(gè)父代個(gè)體的因子。則只含有某一個(gè)父代個(gè)體的因子。進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)(3)混雜混雜(Panmic

19、tic)重組重組。這種重組方式的特點(diǎn)在于父代個(gè)體。這種重組方式的特點(diǎn)在于父代個(gè)體的選擇上?；祀s重組時(shí)先隨機(jī)選擇一個(gè)固定的父代個(gè)體，的選擇上。混雜重組時(shí)先隨機(jī)選擇一個(gè)固定的父代個(gè)體，然后針對(duì)子代個(gè)體每個(gè)分量再?gòu)母复后w中隨機(jī)選擇第二然后針對(duì)子代個(gè)體每個(gè)分量再?gòu)母复后w中隨機(jī)選擇第二個(gè)父代個(gè)體。也就是說，第二個(gè)父代個(gè)體是經(jīng)常變化的。個(gè)父代個(gè)體。也就是說，第二個(gè)父代個(gè)體是經(jīng)常變化的。至于父代兩個(gè)個(gè)體的組合方式，既可以采用離散方式，也至于父代兩個(gè)個(gè)體的組合方式，既可以采用離散方式，也可以來用中值方式，甚至可以把中值重組中的可以來用中值方式，甚至可以把中值重組中的1/2改為改為0,1之間的任一權(quán)值。之間

20、的任一權(quán)值。研究表明，進(jìn)化策略采用重組后，明顯增加算法的收斂速度。研究表明，進(jìn)化策略采用重組后，明顯增加算法的收斂速度。Schwefel建議，對(duì)于目標(biāo)變量建議，對(duì)于目標(biāo)變量X宜用離散重組，對(duì)于策略因子宜用離散重組，對(duì)于策略因子及及宜用中值重組或混雜中值重組。宜用中值重組或混雜中值重組。進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)選擇：選擇：進(jìn)化策略的選擇有兩種：一為進(jìn)化策略的選擇有兩種：一為(+)選擇，另一為選擇，另一為(, )選擇。選擇。(+)選擇是從選擇是從個(gè)父代個(gè)體及個(gè)父代個(gè)體及個(gè)子代新個(gè)體中確定性地?fù)駛€(gè)子代新個(gè)體中確定性地?fù)駜?yōu)選出優(yōu)選出個(gè)個(gè)體組成下一代新群體。個(gè)個(gè)體組成下一代新群體。(, )選

21、擇是從選擇是從個(gè)子代個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)桃選新個(gè)體中確定性地?fù)駜?yōu)桃選個(gè)個(gè)體個(gè)個(gè)體(要求要求)組成下一代組成下一代群體，每個(gè)個(gè)體只存活一代，隨即被新個(gè)體頂替。粗略地群體，每個(gè)個(gè)體只存活一代，隨即被新個(gè)體頂替。粗略地看，似乎看，似乎(+)選擇最好，它可以保證選擇最好，它可以保證最優(yōu)最優(yōu)個(gè)體存活個(gè)體存活，使群使群體的進(jìn)化過程呈單調(diào)體的進(jìn)化過程呈單調(diào)上上升趨勢(shì)。但是，深入分析后發(fā)現(xiàn)升趨勢(shì)。但是，深入分析后發(fā)現(xiàn)(+)選擇具有下述缺點(diǎn)：選擇具有下述缺點(diǎn)：進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)(1) (+)選擇保留舊個(gè)體，它有時(shí)會(huì)是過時(shí)的可行解，妨礙算法向最選擇保留舊個(gè)體，它有時(shí)會(huì)是過時(shí)的可行解，妨礙算

22、法向最優(yōu)方向發(fā)展。優(yōu)方向發(fā)展。(，)選擇全部舍棄舊個(gè)體，使算法始終從新的基選擇全部舍棄舊個(gè)體，使算法始終從新的基礎(chǔ)上全方位進(jìn)化。礎(chǔ)上全方位進(jìn)化。(2) (+)選擇保留舊個(gè)體，有時(shí)是局部最優(yōu)解，從而誤導(dǎo)進(jìn)化策略收選擇保留舊個(gè)體，有時(shí)是局部最優(yōu)解，從而誤導(dǎo)進(jìn)化策略收斂于次優(yōu)解而不是最優(yōu)解。斂于次優(yōu)解而不是最優(yōu)解。(，)選擇舍棄舊的優(yōu)良個(gè)體，容易選擇舍棄舊的優(yōu)良個(gè)體，容易進(jìn)化至全局員優(yōu)解。進(jìn)化至全局員優(yōu)解。(3) (+)選擇在保留舊個(gè)體的同時(shí)，也將進(jìn)化參數(shù)選擇在保留舊個(gè)體的同時(shí)，也將進(jìn)化參數(shù)保留下來，不利保留下來，不利于進(jìn)化策略中的自適應(yīng)調(diào)整機(jī)制。于進(jìn)化策略中的自適應(yīng)調(diào)整機(jī)制。(，)選擇則恰恰相反，

23、可促選擇則恰恰相反，可促進(jìn)這種自適應(yīng)調(diào)整。進(jìn)這種自適應(yīng)調(diào)整。 實(shí)踐也證明，實(shí)踐也證明，(, )-ES優(yōu)于優(yōu)于(+)-ES，前者已成為當(dāng)前進(jìn)化策略，前者已成為當(dāng)前進(jìn)化策略的主流。的主流。進(jìn)化策略的基本技術(shù)進(jìn)化策略的基本技術(shù)在在(+)-ES中，為了控制群體的多樣性和選擇的力度，比值中，為了控制群體的多樣性和選擇的力度，比值/是一個(gè)重要參數(shù)，它對(duì)算法的收斂速度有很大影響。一是一個(gè)重要參數(shù)，它對(duì)算法的收斂速度有很大影響。一方面，方面， 不能太小，否則群體太單調(diào)不能太小，否則群體太單調(diào)(例如例如1的極端情況的極端情況)；另一方面，另一方面， 也不能太大，否則計(jì)算工作量過大。通常，也不能太大，否則計(jì)算工作

24、量過大。通常， 取取15或更多一些?；蚋嘁恍?數(shù)值的大小，類似于數(shù)值的大小，類似于的作用，也要適的作用，也要適當(dāng)。某些研究表明比值當(dāng)。某些研究表明比值/宜取宜取1/7左右。也就是說，若左右。也就是說，若=15，則，則宜取宜取100。8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃進(jìn)化規(guī)劃進(jìn)化規(guī)劃(Evolutionary Programming)由由Fogel在在20世紀(jì)世紀(jì)60年年代所提出。代所提出。Fogel將仿真進(jìn)化方法用于由相互競(jìng)爭(zhēng)的算法所將仿真進(jìn)化方法用于由相互競(jìng)爭(zhēng)的算法所構(gòu)成的種群，在一系列研究中探索了進(jìn)化規(guī)劃的可能性，構(gòu)成的種群，在一系列研究中探索了進(jìn)化規(guī)劃的可能性，目的是發(fā)展人工智能。目的是發(fā)展人

25、工智能。Fogel認(rèn)為，智能行為需要有如下的認(rèn)為，智能行為需要有如下的復(fù)合能力：復(fù)合能力： (1)預(yù)報(bào)它的環(huán)境；預(yù)報(bào)它的環(huán)境； (2)把預(yù)報(bào)變成對(duì)于給定目標(biāo)的適當(dāng)響應(yīng)。把預(yù)報(bào)變成對(duì)于給定目標(biāo)的適當(dāng)響應(yīng)。8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃標(biāo)準(zhǔn)進(jìn)化規(guī)劃標(biāo)準(zhǔn)進(jìn)化規(guī)劃進(jìn)化規(guī)劃用傳統(tǒng)的十進(jìn)制實(shí)數(shù)表達(dá)問題。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃進(jìn)化規(guī)劃用傳統(tǒng)的十進(jìn)制實(shí)數(shù)表達(dá)問題。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃（Standard EP）中，個(gè)體的表達(dá)形式為：）中，個(gè)體的表達(dá)形式為：式中：式中：xi舊個(gè)體目標(biāo)變量舊個(gè)體目標(biāo)變量X的第的第i個(gè)分量，個(gè)分量， xi新個(gè)體目標(biāo)變量新個(gè)體目標(biāo)變量X的第的第i個(gè)分量，個(gè)分量， f(X)舊個(gè)體舊個(gè)體X的適應(yīng)度；的適應(yīng)度；

26、 N(0, 1)針對(duì)第針對(duì)第i分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。) 1 , 0()(iiiNXfxx8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃上式表明，新個(gè)體是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，添加值上式表明，新個(gè)體是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，添加值的大小與個(gè)體的適應(yīng)度有關(guān)：適應(yīng)度大的個(gè)體添加值也大，反之的大小與個(gè)體的適應(yīng)度有關(guān)：適應(yīng)度大的個(gè)體添加值也大，反之亦然。亦然。根據(jù)這種表達(dá)方式，進(jìn)化規(guī)劃首先產(chǎn)生根據(jù)這種表達(dá)方式，進(jìn)化規(guī)劃首先產(chǎn)生個(gè)初始個(gè)體，這也就是個(gè)初始個(gè)體，這也就是突變。接著從突變。接著從個(gè)舊個(gè)體及個(gè)舊個(gè)體及個(gè)新個(gè)體個(gè)新個(gè)體(2 個(gè)個(gè)體個(gè)個(gè)體)中根據(jù)適應(yīng)

27、度挑中根據(jù)適應(yīng)度挑選出選出個(gè)個(gè)體組成新群體。如此反復(fù)迭代，直至得到滿意結(jié)果。個(gè)個(gè)體組成新群體。如此反復(fù)迭代，直至得到滿意結(jié)果。應(yīng)該指出，進(jìn)化規(guī)劃沒有重組或交換這類算子，它的進(jìn)化主要依應(yīng)該指出，進(jìn)化規(guī)劃沒有重組或交換這類算子，它的進(jìn)化主要依賴突變。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃中這種突變十分簡(jiǎn)單，它只需參照個(gè)體賴突變。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃中這種突變十分簡(jiǎn)單，它只需參照個(gè)體適應(yīng)度添加一個(gè)隨機(jī)數(shù)。很明顯，標(biāo)準(zhǔn)進(jìn)化規(guī)劃在進(jìn)化過程中的適應(yīng)度添加一個(gè)隨機(jī)數(shù)。很明顯，標(biāo)準(zhǔn)進(jìn)化規(guī)劃在進(jìn)化過程中的自適應(yīng)調(diào)整功能主要依靠適應(yīng)度自適應(yīng)調(diào)整功能主要依靠適應(yīng)度f(X)來實(shí)現(xiàn)。來實(shí)現(xiàn)。8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃Standard EP流程：流程：

28、生成初始群體；生成初始群體；While Not-End Do突變；突變；計(jì)算個(gè)體適應(yīng)度；計(jì)算個(gè)體適應(yīng)度；選擇；選擇；組成新群體組成新群體1. End While8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃元進(jìn)化規(guī)劃元進(jìn)化規(guī)劃為了增加進(jìn)化規(guī)劃在進(jìn)化過程中的自適應(yīng)調(diào)整功能，人們?cè)谕蛔冎袨榱嗽黾舆M(jìn)化規(guī)劃在進(jìn)化過程中的自適應(yīng)調(diào)整功能，人們?cè)谕蛔冎刑砑臃讲畹母拍?。類似于進(jìn)化策略，在進(jìn)化規(guī)劃中個(gè)體的表達(dá)采添加方差的概念。類似于進(jìn)化策略，在進(jìn)化規(guī)劃中個(gè)體的表達(dá)采用下述方式：用下述方式：式中：式中：i舊個(gè)體第舊個(gè)體第 i 分量的標(biāo)準(zhǔn)差；分量的標(biāo)準(zhǔn)差； i新個(gè)體第新個(gè)體第 i 分量的標(biāo)準(zhǔn)差；分量的標(biāo)準(zhǔn)差； N(0, 1)針對(duì)第針對(duì)

29、第i分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。) 1 , 0() 1 , 0(iiiiiiiiNNxx8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃從上式可以看出，新個(gè)體也是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，從上式可以看出，新個(gè)體也是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，該添加量取決于個(gè)體的方差，而方差在每次進(jìn)化中又有自適應(yīng)調(diào)該添加量取決于個(gè)體的方差，而方差在每次進(jìn)化中又有自適應(yīng)調(diào)整。這種進(jìn)化方式已成為進(jìn)化規(guī)劃的主要手段，因此在進(jìn)化規(guī)劃整。這種進(jìn)化方式已成為進(jìn)化規(guī)劃的主要手段，因此在進(jìn)化規(guī)劃前冠以前冠以“元元”這個(gè)術(shù)語以表示它為基本方法。這個(gè)術(shù)語以表示它為基本方法。元進(jìn)化規(guī)劃元進(jìn)化規(guī)劃(M

30、eta EP)的突變盡管類似于進(jìn)化策略，但是它們有下述的突變盡管類似于進(jìn)化策略，但是它們有下述差別差別:(1)執(zhí)行順序不同。進(jìn)化規(guī)劃中首先計(jì)算新個(gè)體的目標(biāo)變量執(zhí)行順序不同。進(jìn)化規(guī)劃中首先計(jì)算新個(gè)體的目標(biāo)變量xi ，計(jì)算，計(jì)算中沿用舊個(gè)體的標(biāo)準(zhǔn)差中沿用舊個(gè)體的標(biāo)準(zhǔn)差i ；其次才計(jì)算新個(gè)體的標(biāo)準(zhǔn)差；其次才計(jì)算新個(gè)體的標(biāo)準(zhǔn)差i ，新的，新的標(biāo)準(zhǔn)差留待下次進(jìn)化時(shí)才用。與之相反，進(jìn)化策略是先調(diào)整標(biāo)準(zhǔn)標(biāo)準(zhǔn)差留待下次進(jìn)化時(shí)才用。與之相反，進(jìn)化策略是先調(diào)整標(biāo)準(zhǔn)差差，然后再用新的標(biāo)準(zhǔn)差然后再用新的標(biāo)準(zhǔn)差去更改個(gè)體的目標(biāo)變量去更改個(gè)體的目標(biāo)變量X。(2)計(jì)算式的不同。進(jìn)化規(guī)劃的計(jì)算式比進(jìn)化策略的計(jì)算式簡(jiǎn)單。計(jì)算式

31、的不同。進(jìn)化規(guī)劃的計(jì)算式比進(jìn)化策略的計(jì)算式簡(jiǎn)單。8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃旋轉(zhuǎn)進(jìn)化規(guī)劃旋轉(zhuǎn)進(jìn)化規(guī)劃旋轉(zhuǎn)進(jìn)化規(guī)劃旋轉(zhuǎn)進(jìn)化規(guī)劃(Rmeta EP)進(jìn)一步擴(kuò)展進(jìn)化規(guī)劃，在表達(dá)個(gè)體時(shí)添加第三個(gè)進(jìn)一步擴(kuò)展進(jìn)化規(guī)劃，在表達(dá)個(gè)體時(shí)添加第三個(gè)因子因子協(xié)方差，用三元組表示個(gè)體，即協(xié)方差，用三元組表示個(gè)體，即(X, , )，具體計(jì)算如下：，具體計(jì)算如下：X舊個(gè)體的目標(biāo)變量，其內(nèi)含舊個(gè)體的目標(biāo)變量，其內(nèi)含n個(gè)分量；個(gè)分量；X新個(gè)體的目標(biāo)變量，其內(nèi)含新個(gè)體的目標(biāo)變量，其內(nèi)含n個(gè)分量；個(gè)分量；N(0,C)遵從正態(tài)分布的隨機(jī)數(shù)，其數(shù)學(xué)期望為遵從正態(tài)分布的隨機(jī)數(shù)，其數(shù)學(xué)期望為0、其標(biāo)準(zhǔn)差與協(xié)方差有、其標(biāo)準(zhǔn)差與協(xié)方差有關(guān)；關(guān)；

32、j相關(guān)系數(shù)，相關(guān)系數(shù)，) 1 , 0() 1 , 0(), 0(jjjjiiiiNNCNXXjiijjc進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)表達(dá)方法表達(dá)方法采用十進(jìn)制的實(shí)型數(shù)表達(dá)問題。采用十進(jìn)制的實(shí)型數(shù)表達(dá)問題。X=(x1, x2, , xi, , xn)由由X和和組成的二元組組成的二元組(X, )是進(jìn)化規(guī)劃最常用的表達(dá)形式。有是進(jìn)化規(guī)劃最常用的表達(dá)形式。有人建議將進(jìn)化規(guī)劃再增加一個(gè)控制因子人建議將進(jìn)化規(guī)劃再增加一個(gè)控制因子 ，構(gòu)成三元表達(dá)式，構(gòu)成三元表達(dá)式(X, , )，其中，其中 =(1, 2, , j, , n)j是相關(guān)系數(shù)的單下標(biāo)表達(dá)是相關(guān)系數(shù)的單下標(biāo)表達(dá), 它表示它表示xi和和xj

33、之間的協(xié)方差之間的協(xié)方差:jiijjc進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)產(chǎn)生初始群體產(chǎn)生初始群體進(jìn)化規(guī)劃中產(chǎn)生初始群體的方法類似于進(jìn)化策略中隨機(jī)選擇進(jìn)化規(guī)劃中產(chǎn)生初始群體的方法類似于進(jìn)化策略中隨機(jī)選擇個(gè)個(gè)體作為進(jìn)化計(jì)算的出發(fā)點(diǎn)。個(gè)個(gè)體作為進(jìn)化計(jì)算的出發(fā)點(diǎn)。計(jì)算適應(yīng)度計(jì)算適應(yīng)度進(jìn)化規(guī)劃采用十進(jìn)制實(shí)數(shù)表達(dá)問題，計(jì)算適應(yīng)度比較簡(jiǎn)單直觀。進(jìn)化規(guī)劃采用十進(jìn)制實(shí)數(shù)表達(dá)問題，計(jì)算適應(yīng)度比較簡(jiǎn)單直觀。突變突變突變是進(jìn)化規(guī)劃產(chǎn)生新群體的唯一方法，它不采用重組或交換突變是進(jìn)化規(guī)劃產(chǎn)生新群體的唯一方法，它不采用重組或交換算子。算子。進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)選擇選擇在進(jìn)化規(guī)劃中，新群體的個(gè)體數(shù)目在進(jìn)化規(guī)

34、劃中，新群體的個(gè)體數(shù)目等于舊群體的個(gè)體數(shù)目等于舊群體的個(gè)體數(shù)目，選擇便是在選擇便是在2 個(gè)個(gè)體中選擇個(gè)個(gè)體中選擇個(gè)個(gè)體組成新群體。個(gè)個(gè)體組成新群體。進(jìn)化規(guī)劃的選擇采用隨機(jī)型的進(jìn)化規(guī)劃的選擇采用隨機(jī)型的q競(jìng)爭(zhēng)選擇法。在這種選擇方競(jìng)爭(zhēng)選擇法。在這種選擇方法中，為了確定某一個(gè)體法中，為了確定某一個(gè)體 i 的優(yōu)劣，我們從新、舊群體的的優(yōu)劣，我們從新、舊群體的2 個(gè)個(gè)體中任選個(gè)個(gè)體中任選q個(gè)個(gè)體組成測(cè)試群體。然后將個(gè)體個(gè)個(gè)體組成測(cè)試群體。然后將個(gè)體 i 的適的適應(yīng)度與應(yīng)度與q個(gè)個(gè)體的適應(yīng)度進(jìn)行比較，記錄個(gè)體個(gè)個(gè)體的適應(yīng)度進(jìn)行比較，記錄個(gè)體 i 優(yōu)于或等于優(yōu)于或等于q內(nèi)各個(gè)體的次數(shù)，得到個(gè)體內(nèi)各個(gè)體的次數(shù)

35、，得到個(gè)體 i 的得分的得分Wi，即，即qjjiiffifW101其他優(yōu)于或等于進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)上述得分測(cè)試分別對(duì)上述得分測(cè)試分別對(duì)2個(gè)個(gè)體進(jìn)行，每次鍘試時(shí)重新選擇個(gè)個(gè)體進(jìn)行，每次鍘試時(shí)重新選擇q個(gè)個(gè)體組個(gè)個(gè)體組成新的測(cè)試群體。最后，按個(gè)體的得分選擇分值高的成新的測(cè)試群體。最后，按個(gè)體的得分選擇分值高的個(gè)個(gè)體組個(gè)個(gè)體組成下一代新群體。成下一代新群體。q競(jìng)爭(zhēng)選擇法是一種隨機(jī)選擇，總體上講，優(yōu)良個(gè)體入選的可能性競(jìng)爭(zhēng)選擇法是一種隨機(jī)選擇，總體上講，優(yōu)良個(gè)體入選的可能性較大。但是由于測(cè)試群體較大。但是由于測(cè)試群體q每次都是隨機(jī)選擇的，當(dāng)每次都是隨機(jī)選擇的，當(dāng)q個(gè)個(gè)體都不個(gè)個(gè)體都不甚

36、好時(shí)，有可能使較差的個(gè)體因得分高而入選。這正是隨機(jī)選擇甚好時(shí)，有可能使較差的個(gè)體因得分高而入選。這正是隨機(jī)選擇的本意。的本意。q競(jìng)爭(zhēng)選擇法中競(jìng)爭(zhēng)選擇法中q的大小是一個(gè)重要參數(shù)。若的大小是一個(gè)重要參數(shù)。若q很大，極端地設(shè)很大，極端地設(shè)q2，則選擇變?yōu)榇_定性選擇。反之，若，則選擇變?yōu)榇_定性選擇。反之，若q很小，則選擇的隨機(jī)性很小，則選擇的隨機(jī)性太大，不能保證優(yōu)良個(gè)體入選。通常太大，不能保證優(yōu)良個(gè)體入選。通常q在在10以上，可取以上，可取0.9。進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)終止終止進(jìn)化規(guī)劃的終止準(zhǔn)則與進(jìn)化策略相同，即根據(jù)進(jìn)化規(guī)劃的終止準(zhǔn)則與進(jìn)化策略相同，即根據(jù)最大進(jìn)化代次最大進(jìn)化代次、最優(yōu)個(gè)

37、體與期望值的偏差最優(yōu)個(gè)體與期望值的偏差、適應(yīng)度的變化趨勢(shì)適應(yīng)度的變化趨勢(shì)以及以及最優(yōu)適最優(yōu)適應(yīng)度與最差適應(yīng)度之差應(yīng)度與最差適應(yīng)度之差等四個(gè)判據(jù)。等四個(gè)判據(jù)。進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的算法算法流程：進(jìn)化規(guī)劃的算法算法流程：(1)確定問題的表達(dá)方式。確定問題的表達(dá)方式。(2)隨機(jī)產(chǎn)生初始群體，并計(jì)算其適應(yīng)度。隨機(jī)產(chǎn)生初始群體，并計(jì)算其適應(yīng)度。(3)用下述操作產(chǎn)生新群體：用下述操作產(chǎn)生新群體：1) 突變。對(duì)舊個(gè)體添加隨機(jī)量，產(chǎn)生新個(gè)體突變。對(duì)舊個(gè)體添加隨機(jī)量，產(chǎn)生新個(gè)體2) 計(jì)算新個(gè)體適應(yīng)度；計(jì)算新個(gè)體適應(yīng)度；3) 選擇。挑選優(yōu)良個(gè)體組成新群體。選擇。挑選優(yōu)良個(gè)體組成新群體。(4

38、)反復(fù)執(zhí)行反復(fù)執(zhí)行(3)，直至滿足終止條件，選擇最佳個(gè)體作為進(jìn)化規(guī)劃的，直至滿足終止條件，選擇最佳個(gè)體作為進(jìn)化規(guī)劃的最優(yōu)解。最優(yōu)解。遺傳規(guī)劃遺傳規(guī)劃遺傳算法的局限性：遺傳算法的局限性：(1)不能描述層次化的問題。不能描述層次化的問題。(2)不能描述計(jì)算機(jī)程序。不能描述計(jì)算機(jī)程序。(3)缺乏動(dòng)態(tài)可變性。缺乏動(dòng)態(tài)可變性。1992年、美國(guó)年、美國(guó)John R. Koza正式提出遺傳規(guī)劃正式提出遺傳規(guī)劃(Genetic Programming)，用層次化的結(jié)構(gòu)性語言表達(dá)問題。用層次化的結(jié)構(gòu)性語言表達(dá)問題。遺傳規(guī)劃的最大特點(diǎn)，是采用層次化的結(jié)構(gòu)表達(dá)問題，它類似于計(jì)算遺傳規(guī)劃的最大特點(diǎn)，是采用層次化的結(jié)構(gòu)

39、表達(dá)問題，它類似于計(jì)算機(jī)程序分行或分段地描述問題。這種廣義的計(jì)算機(jī)程序能夠根據(jù)環(huán)機(jī)程序分行或分段地描述問題。這種廣義的計(jì)算機(jī)程序能夠根據(jù)環(huán)境狀態(tài)自動(dòng)改變程序的結(jié)構(gòu)及大小。境狀態(tài)自動(dòng)改變程序的結(jié)構(gòu)及大小。遺傳規(guī)劃的工作步驟可歸納如下：遺傳規(guī)劃的工作步驟可歸納如下：(1)確定個(gè)體的表達(dá)方式，包括函數(shù)集確定個(gè)體的表達(dá)方式，包括函數(shù)集F及終止符集及終止符集T。(2)隨機(jī)產(chǎn)生初始群體。隨機(jī)產(chǎn)生初始群體。(3)計(jì)算各個(gè)體的適應(yīng)度。計(jì)算各個(gè)體的適應(yīng)度。(4)根據(jù)遺傳參數(shù)，用下述操作產(chǎn)生新個(gè)體：根據(jù)遺傳參數(shù)，用下述操作產(chǎn)生新個(gè)體：1)復(fù)制。將已有的優(yōu)良個(gè)體復(fù)制，加入新群體中，并相應(yīng)刪除劣復(fù)制。將已有的優(yōu)良個(gè)體

40、復(fù)制，加入新群體中，并相應(yīng)刪除劣質(zhì)個(gè)體質(zhì)個(gè)體2)交換。將選出的兩個(gè)個(gè)體進(jìn)行交換，所產(chǎn)生的兩個(gè)新個(gè)體插入交換。將選出的兩個(gè)個(gè)體進(jìn)行交換，所產(chǎn)生的兩個(gè)新個(gè)體插入新群體中。新群體中。3)突變。隨機(jī)改變個(gè)體某一部分，將新個(gè)體插入新群體中。突變。隨機(jī)改變個(gè)體某一部分，將新個(gè)體插入新群體中。(5)反復(fù)執(zhí)行反復(fù)執(zhí)行(3)及及(4)直至取得滿意結(jié)果。直至取得滿意結(jié)果。遺傳規(guī)劃的基本技術(shù)遺傳規(guī)劃的基本技術(shù)問題的表達(dá)問題的表達(dá)遺傳規(guī)劃是用層次結(jié)構(gòu)可變的形式表達(dá)問題，在表達(dá)中主要用函數(shù)遺傳規(guī)劃是用層次結(jié)構(gòu)可變的形式表達(dá)問題，在表達(dá)中主要用函數(shù)和終止符兩類組分。簡(jiǎn)單地說，終止符表示問題的值，函數(shù)表示和終止符兩類組分。

41、簡(jiǎn)單地說，終止符表示問題的值，函數(shù)表示對(duì)值的處理。綜合在一起，遺傳規(guī)劃的個(gè)體表示對(duì)各種值對(duì)值的處理。綜合在一起，遺傳規(guī)劃的個(gè)體表示對(duì)各種值(終止符終止符)的處理過程的處理過程(函數(shù)函數(shù))。 在函數(shù)集在函數(shù)集Ff1, f2, , fn中，函數(shù)中，函數(shù)fi可以是運(yùn)算符、函數(shù)、說明等，可以是運(yùn)算符、函數(shù)、說明等，具體有：具體有：(1) 算術(shù)運(yùn)算符算術(shù)運(yùn)算符，如，如+, -, *, /等。其中除號(hào)為防止計(jì)算機(jī)溢出，規(guī)定不等。其中除號(hào)為防止計(jì)算機(jī)溢出，規(guī)定不允許用零作分母，稱保護(hù)性除法允許用零作分母，稱保護(hù)性除法(Protected Division)，用標(biāo)記。，用標(biāo)記。一旦遇到分母為零時(shí)，最簡(jiǎn)單的處理方法是令其商為一旦遇到分母為零時(shí)，最簡(jiǎn)單的處理方法是令其商為1、或是重、或是重新選擇算術(shù)運(yùn)算符。新選擇算術(shù)運(yùn)算符。遺傳規(guī)劃的基本技術(shù)遺傳規(guī)劃的基本技術(shù)(2)超越函數(shù)，如超越函數(shù)，如sin, cos, tan, log, exp等。其中等。其中l(wèi)og要防止處理小于或要防止處理小于或等于零的數(shù)值，稱保護(hù)性對(duì)數(shù)，記為等于零的數(shù)值，稱保護(hù)性對(duì)數(shù)，記為Rlog其處理方法類似于。其處理方法類似于。(3)布爾運(yùn)