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

1、進(jìn)化戰(zhàn)略和進(jìn)化規(guī)劃德國學(xué)者Schwefel和Rechenburg美國學(xué)者Fogel分別提出進(jìn)化戰(zhàn)略ES和進(jìn)化規(guī)劃EP。這三種方法具有共同的本質(zhì)，分別強(qiáng)調(diào)了自然進(jìn)化中的不同方面：遺傳算法強(qiáng)調(diào)染色體的操作，進(jìn)化戰(zhàn)略強(qiáng)調(diào)了個(gè)體級(jí)的行為變化。而進(jìn)化規(guī)劃那么強(qiáng)調(diào)種群級(jí)上的行為變化。如今學(xué)術(shù)界把遺傳算法GA、進(jìn)化戰(zhàn)略ES和進(jìn)化規(guī)劃EP通稱為進(jìn)化算法EC。8.1 進(jìn)化算法的早期研討進(jìn)化算法來源于20世紀(jì)30年代的經(jīng)過仿真生物進(jìn)化過程進(jìn)展機(jī)器學(xué)習(xí)的研討。早在1932年，Cannon就把自然進(jìn)化想象為一個(gè)學(xué)習(xí)過程。與自然進(jìn)化過程的機(jī)制和結(jié)果略微不同是，Cannon不是經(jīng)過維持一個(gè)特定的種群來進(jìn)展搜索，而是對(duì)單個(gè)

2、個(gè)體反復(fù)進(jìn)展隨機(jī)實(shí)驗(yàn)。到了1950年，Turng認(rèn)識(shí)到，在機(jī)器學(xué)習(xí)和進(jìn)化之間存在著明顯的關(guān)系。1959年，F(xiàn)riedman推測(cè)，利用變異和選擇的仿真可以設(shè)計(jì)“思想機(jī)器，并且指出下棋的程序可以用這種方法設(shè)計(jì)。在1960年，Cambell猜測(cè)：在導(dǎo)致知識(shí)擴(kuò)張的一切過程中，都要涉及“盲目變化選擇幸存的過程。以后，一些學(xué)者逐漸將進(jìn)化實(shí)際用于隨機(jī)工程控制、機(jī)器學(xué)習(xí)和函數(shù)優(yōu)化等領(lǐng)域。8.2 進(jìn)化戰(zhàn)略進(jìn)化戰(zhàn)略Evolutionary Strategies是在1965年由Rechenburg和Schwefel獨(dú)立提出的。早期的進(jìn)化戰(zhàn)略的種群中只包含一個(gè)個(gè)體，并且只運(yùn)用變異操作。在每一代中，變異后的個(gè)體與其父代

3、進(jìn)展比較，并選擇較好的一個(gè)，這種選擇戰(zhàn)略被稱為1+1戰(zhàn)略。進(jìn)化戰(zhàn)略中的個(gè)體用傳統(tǒng)的十進(jìn)制實(shí)型數(shù)表示，即：Xt第t代個(gè)體的數(shù)值，N(0,)服從正態(tài)分布的隨機(jī)數(shù)，其均值為零，規(guī)范差為。8.2 進(jìn)化戰(zhàn)略進(jìn)化戰(zhàn)略的普通算法可以描畫如下：問題為尋覓實(shí)值n維矢量x，使得函數(shù)F(x):RnR取極值。不失普通性，設(shè)此程序?yàn)闃O小化過程。從各維的可行范圍內(nèi)隨機(jī)選取親本xi，i1，p的初始值。初始實(shí)驗(yàn)的分布普通是均勻分布。經(jīng)過對(duì)于x的每個(gè)分量添加零均值和預(yù)先選定的規(guī)范差的高斯隨機(jī)變量，從每個(gè)親本xi產(chǎn)生子代xi。經(jīng)過將誤差F(xi)和F(xi)，i1，p進(jìn)展排序，選擇并決議哪些矢量保管。具有最小誤差的p個(gè)矢量變成下

4、一代的新親本。進(jìn)展新實(shí)驗(yàn)，選擇具有最小方差的新子代，不斷到獲得充分解，或者直到滿足某個(gè)終止條件8.2 進(jìn)化戰(zhàn)略在這個(gè)模型中，把實(shí)驗(yàn)解的分量看做個(gè)體的行為特性，而不是沿染色體陳列的基因?？梢院虶A一樣，假設(shè)這些表現(xiàn)型特征具有基因根源，但是它們之間的聯(lián)絡(luò)本質(zhì)并沒有被弄清楚，所以我們把著重點(diǎn)放在個(gè)體的行為特性上。假設(shè)不論發(fā)生什么遺傳變換，所呵斥各個(gè)行為的變化均遵照零均值和某個(gè)規(guī)范差的高斯分布。由于基因多效性和多基因性，特定基因的改動(dòng)可以影響許多表現(xiàn)型特征。所以在發(fā)明新子代時(shí)，較為適宜的是同時(shí)改動(dòng)親本一切分量。8.2 進(jìn)化戰(zhàn)略進(jìn)化戰(zhàn)略的最初實(shí)驗(yàn)采用上述算法，主要采用單親本單子代的搜索，即“1+1進(jìn)化戰(zhàn)

5、略(1+1)-ES)，其中單個(gè)子代是由單個(gè)親本產(chǎn)生的，它們都被置于生存競(jìng)爭(zhēng)中，較弱的一個(gè)要被挑選出來消去。當(dāng)把這種算法用于函數(shù)優(yōu)化時(shí)，發(fā)現(xiàn)它有兩個(gè)缺陷：各維取定常的規(guī)范差使得程序收斂到最優(yōu)解的速度很慢；點(diǎn)到點(diǎn)搜索的脆弱本質(zhì)使得程序在部分極值附近容易受停滯的影響雖然此算法闡明可以漸近地收斂到全局最優(yōu)點(diǎn)。8.2 進(jìn)化戰(zhàn)略( + 1)-ES:早期的(1十1)-ES，沒有表達(dá)群體的作用，只是單個(gè)個(gè)體在進(jìn)化，具有明顯的局限性。隨后，Rechenberg又提出(+1)-ES，在這種進(jìn)化戰(zhàn)略中，父代有個(gè)個(gè)體(1)，并且引入重組(Recombination)算子，使父代個(gè)體組合出新的個(gè)體。在執(zhí)行重組時(shí)，從個(gè)父

6、代個(gè)體中用隨機(jī)的方法任選兩個(gè)個(gè)體：8.2 進(jìn)化戰(zhàn)略然后從這兩個(gè)個(gè)體中組合出如下新個(gè)體：式中qi1或2，它以一樣的概率針對(duì)i1，2，n隨機(jī)選取。對(duì)重組產(chǎn)生的新個(gè)體執(zhí)行突變操作，突變方式及的調(diào)整與(1+1)-ES一樣。將突變后的個(gè)體與父代個(gè)個(gè)體相比較，假設(shè)優(yōu)于父代最差個(gè)體，那么替代后者成為下一代個(gè)個(gè)體新成員，否那么，重新執(zhí)行重組和突變產(chǎn)生另一新個(gè)體，8.2 進(jìn)化戰(zhàn)略(+1)-ES和(1+1)-ES具有一樣的戰(zhàn)略：只產(chǎn)生一個(gè)新個(gè)體。(+1)-ES的特點(diǎn)在于： (1) 采用群體，其中包含個(gè)個(gè)體； (2) 增添重組算子，它相當(dāng)于遺傳算法中的交叉算子，從父代承繼信息構(gòu)成新個(gè)體。顯然，(+1)-ES比(1+

7、1)-ES有了明顯的改良，為進(jìn)化戰(zhàn)略這種新的進(jìn)化算法奠定良好的根底。8.2 進(jìn)化戰(zhàn)略在1973年，Rechenburg把該算法的期望收斂速度定義為對(duì)最優(yōu)點(diǎn)的平均間隔與要得到此改善所需求的實(shí)驗(yàn)次數(shù)之比。1981年，Schwefel在進(jìn)化戰(zhàn)略中運(yùn)用多重親本和子代，這是Rechenburg早期任務(wù)運(yùn)用多重親本，但是僅運(yùn)用單個(gè)子代的開展，后來調(diào)查了兩種方法，分別表示為(+)-ES相(，)-ES。在前者中，個(gè)親本制造個(gè)子代，一切解均參與生存競(jìng)爭(zhēng)，選出最好的個(gè)作為下一代的親本。在后者中，只需 個(gè)子代參與生存競(jìng)爭(zhēng)，在每代中個(gè)親本被完全取代。這就是說，對(duì)于每一代，每個(gè)解張成的生命是有限的。添加種群大小，就在固

8、定數(shù)目的世代中添加了優(yōu)化速率。8.2 進(jìn)化戰(zhàn)略Rechenburg引入了如下想法，在每個(gè)新樣本的特征分布中附加了一個(gè)自順應(yīng)參數(shù)。在這個(gè)方法中，每個(gè)解矢量不僅包括了n維實(shí)驗(yàn)矢量x，而且還包括了擾動(dòng)矢量，后者給出如何變異x以及它本身如何變異的指令。例如，設(shè)x為當(dāng)前矢量， 為對(duì)應(yīng)于x每個(gè)維的方差矢量，于是新的解矢量x， 可以這樣產(chǎn)生：N(0,1)表示單個(gè)規(guī)范高所隨機(jī)變量， Ni(0,1)表示第i個(gè)獨(dú)立一樣的規(guī)范高斯分布，和是影響總體和個(gè)體步長的算子集參數(shù)。以這種方式，進(jìn)化戰(zhàn)略可以在線地順應(yīng)誤差曲面的寬度，并且更恰當(dāng)?shù)胤峙鋵?shí)驗(yàn)次數(shù)。進(jìn)化戰(zhàn)略的根本技術(shù)問題的表達(dá)：為了與突變操作相順應(yīng)，進(jìn)化戰(zhàn)略有兩種表達(dá)

9、方式。(1) 二元表達(dá)方式。這種表達(dá)方式中個(gè)體由目的變量X和規(guī)范差兩部分組成，每部分又可以有n個(gè)分量，即：X和的關(guān)系為:為全局系數(shù)，常取1。進(jìn)化戰(zhàn)略的根本技術(shù)(2) 三元表達(dá)方式。為了改善進(jìn)化戰(zhàn)略的收斂速度，Schwefel在二元表達(dá)的根底上引入第三個(gè)因子坐標(biāo)旋轉(zhuǎn)角度。個(gè)體的描畫擴(kuò)展為(X, , )，即：三者的關(guān)系為：i父代個(gè)體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；j子代新個(gè)體i分量與j分量間坐標(biāo)的旋轉(zhuǎn)角度；系數(shù)，常取0.0873；zi取決于及的正態(tài)分布隨機(jī)數(shù)。進(jìn)化戰(zhàn)略的根本技術(shù)旋轉(zhuǎn)角度i外表上是分量i與j間坐標(biāo)的旋轉(zhuǎn)角度，本質(zhì)上它是分量i與分量j之間協(xié)方差的表達(dá)。重組進(jìn)化戰(zhàn)略中的重組(Recomb

10、ination)算子相當(dāng)于遺傳算法的交叉，它們都是以兩個(gè)父代個(gè)體為根底進(jìn)展信息交換。進(jìn)化戰(zhàn)略中，重組方式主要有三種：(1)離散重組。先隨機(jī)選擇兩個(gè)父代個(gè)體進(jìn)化戰(zhàn)略的根本技術(shù)然后將其分量進(jìn)展隨機(jī)交換，構(gòu)成子代新個(gè)體的各個(gè)分量，從而得出如下新個(gè)體：(2) 中值重組。這種重組方式也是先隨機(jī)選擇兩個(gè)父代個(gè)體，然后將父代個(gè)體各分量的平均值作為子代新個(gè)體的分量，構(gòu)成的新個(gè)體為：這時(shí)，新個(gè)體的各個(gè)分量兼容兩個(gè)父代個(gè)體信息，而在離散重組中那么只含有某一個(gè)父代個(gè)體的因子。進(jìn)化戰(zhàn)略的根本技術(shù)(3)混雜(Panmictic)重組。這種重組方式的特點(diǎn)在于父代個(gè)體的選擇上?；祀s重組時(shí)先隨機(jī)選擇一個(gè)固定的父代個(gè)體，然后針

11、對(duì)子代個(gè)體每個(gè)分量再從父代群體中隨機(jī)選擇第二個(gè)父代個(gè)體。也就是說，第二個(gè)父代個(gè)體是經(jīng)常變化的。至于父代兩個(gè)個(gè)體的組合方式，既可以采用離散方式，也可以來用中值方式，甚至可以把中值重組中的1/2改為0,1之間的任一權(quán)值。研討闡明，進(jìn)化戰(zhàn)略采用重組后，明顯添加算法的收斂速度。Schwefel建議，對(duì)于目的變量X宜用離散重組，對(duì)于戰(zhàn)略因子及宜用中值重組或混雜中值重組。進(jìn)化戰(zhàn)略的根本技術(shù)選擇：進(jìn)化戰(zhàn)略的選擇有兩種：一為(+)選擇，另一為(, )選擇。(+)選擇是從個(gè)父代個(gè)體及個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)選出個(gè)個(gè)體組成下一代新群體。(, )選擇是從個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)桃選個(gè)個(gè)體(要求)組成下一代群體，

12、每個(gè)個(gè)體只存活一代，隨即被新個(gè)體頂替。粗略地看，似乎(+)選擇最好，它可以保證最優(yōu)個(gè)體存活，使群體的進(jìn)化過程呈單調(diào)上升趨勢(shì)。但是，深化分析后發(fā)現(xiàn)(+)選擇具有下述缺陷：進(jìn)化戰(zhàn)略的根本技術(shù)(1) (+)選擇保管舊個(gè)體，它有時(shí)會(huì)是過時(shí)的可行解，妨礙算法向最優(yōu)方向開展。(，)選擇全部舍棄舊個(gè)體，使算法一直重新的根底上全方位進(jìn)化。(2) (+)選擇保管舊個(gè)體，有時(shí)是部分最優(yōu)解，從而誤導(dǎo)進(jìn)化戰(zhàn)略收斂于次優(yōu)解而不是最優(yōu)解。(，)選擇舍棄舊的優(yōu)良個(gè)體，容易進(jìn)化至全局員優(yōu)解。(3) (+)選擇在保管舊個(gè)體的同時(shí)，也將進(jìn)化參數(shù)保管下來，不利于進(jìn)化戰(zhàn)略中的自順應(yīng)調(diào)整機(jī)制。(，)選擇那么恰恰相反，可促進(jìn)這種自順應(yīng)調(diào)

13、整。 實(shí)際也證明，(, )-ES優(yōu)于(+)-ES，前者已成為當(dāng)前進(jìn)化戰(zhàn)略的主流。進(jìn)化戰(zhàn)略的根本技術(shù)在(+)-ES中，為了控制群體的多樣性和選擇的力度，比值/是一個(gè)重要參數(shù)，它對(duì)算法的收斂速度有很大影響。一方面， 不能太小，否那么群體太單調(diào)(例如1的極端情況)；另一方面， 也不能太大，否那么計(jì)算任務(wù)量過大。通常， 取15或更多一些。 數(shù)值的大小，類似于的作用，也要適當(dāng)。某些研討闡明比值/宜取1/7左右。也就是說，假設(shè)=15，那么宜取100。8.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃(Evolutionary Programming)由Fogel在20世紀(jì)60年代所提出。Fogel將仿真進(jìn)化方法用于由相互競(jìng)爭(zhēng)的算法

14、所構(gòu)成的種群，在一系列研討中探求了進(jìn)化規(guī)劃的能夠性，目的是開展人工智能。Fogel以為，智能行為需求有如下的復(fù)合才干： (1)預(yù)告它的環(huán)境； (2)把預(yù)告變成對(duì)于給定目的的適當(dāng)呼應(yīng)。8.3 進(jìn)化規(guī)劃規(guī)范進(jìn)化規(guī)劃進(jìn)化規(guī)劃用傳統(tǒng)的十進(jìn)制實(shí)數(shù)表達(dá)問題。在規(guī)范進(jìn)化規(guī)劃Standard EP中，個(gè)體的表達(dá)方式為：式中：xi舊個(gè)體目的變量X的第i個(gè)分量， xi新個(gè)體目的變量X的第i個(gè)分量， f(X)舊個(gè)體X的順應(yīng)度； N(0, 1)針對(duì)第i分量發(fā)生的隨機(jī)數(shù)，它服從規(guī)范正態(tài)分布。8.3 進(jìn)化規(guī)劃上式闡明，新個(gè)體是在舊個(gè)體的根底上添加一個(gè)隨機(jī)數(shù)，添加值的大小與個(gè)體的順應(yīng)度有關(guān)：順應(yīng)度大的個(gè)體添加值也大，反之亦

15、然。根據(jù)這種表達(dá)方式，進(jìn)化規(guī)劃首先產(chǎn)生個(gè)初始個(gè)體，這也就是突變。接著從個(gè)舊個(gè)體及個(gè)新個(gè)體(2 個(gè)個(gè)體)中根據(jù)順應(yīng)度挑選出個(gè)個(gè)體組成新群體。如此反復(fù)迭代，直至得到稱心結(jié)果。應(yīng)該指出，進(jìn)化規(guī)劃沒有重組或交換這類算子，它的進(jìn)化主要依賴突變。在規(guī)范進(jìn)化規(guī)劃中這種突變非常簡單，它只需參照個(gè)體順應(yīng)度添加一個(gè)隨機(jī)數(shù)。很明顯，規(guī)范進(jìn)化規(guī)劃在進(jìn)化過程中的自順應(yīng)調(diào)整功能主要依托順應(yīng)度f(X)來實(shí)現(xiàn)。8.3 進(jìn)化規(guī)劃Standard EP流程：生成初始群體；While Not-End Do突變；計(jì)算個(gè)體順應(yīng)度；選擇；組成新群體End While8.3 進(jìn)化規(guī)劃元進(jìn)化規(guī)劃為了添加進(jìn)化規(guī)劃在進(jìn)化過程中的自順應(yīng)調(diào)整功能，

16、人們?cè)谕蛔冎刑砑臃讲畹母拍?。類似于進(jìn)化戰(zhàn)略，在進(jìn)化規(guī)劃中個(gè)體的表達(dá)采用下述方式：式中：i舊個(gè)體第 i 分量的規(guī)范差； i新個(gè)體第 i 分量的規(guī)范差； N(0, 1)針對(duì)第i分量發(fā)生的隨機(jī)數(shù)，它服從規(guī)范正態(tài)分布。8.3 進(jìn)化規(guī)劃從上式可以看出，新個(gè)體也是在舊個(gè)體的根底上添加一個(gè)隨機(jī)數(shù)，該添加量取決于個(gè)體的方差，而方差在每次進(jìn)化中又有自順應(yīng)調(diào)整。這種進(jìn)化方式已成為進(jìn)化規(guī)劃的主要手段，因此在進(jìn)化規(guī)劃前冠以“元這個(gè)術(shù)語以表示它為根本方法。元進(jìn)化規(guī)劃(Meta EP)的突變雖然類似于進(jìn)化戰(zhàn)略，但是它們有下述差別:(1)執(zhí)行順序不同。進(jìn)化規(guī)劃中首先計(jì)算新個(gè)體的目的變量xi ，計(jì)算中沿用舊個(gè)體的規(guī)范差i ；

17、其次才計(jì)算新個(gè)體的規(guī)范差i ，新的規(guī)范差留待下次進(jìn)化時(shí)才用。與之相反，進(jìn)化戰(zhàn)略是先調(diào)整規(guī)范差，然后再用新的規(guī)范差去更改個(gè)體的目的變量X。(2)計(jì)算式的不同。進(jìn)化規(guī)劃的計(jì)算式比進(jìn)化戰(zhàn)略的計(jì)算式簡單。8.3 進(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è)因子協(xié)方差，用三元組表示個(gè)體，即(X, , )，詳細(xì)計(jì)算如下：X舊個(gè)體的目的變量，其內(nèi)含n個(gè)分量；X新個(gè)體的目的變量，其內(nèi)含n個(gè)分量；N(0,C)服從正態(tài)分布的隨機(jī)數(shù)，其數(shù)學(xué)期望為0、其規(guī)范差與協(xié)方差有關(guān)；j相關(guān)系數(shù)，進(jìn)化規(guī)劃的根本技術(shù)表達(dá)方法采用十進(jìn)制的實(shí)型數(shù)表達(dá)問題。X=(x1, x2, , xi

18、, , xn)由X和組成的二元組(X, )是進(jìn)化規(guī)劃最常用的表達(dá)方式。有人建議將進(jìn)化規(guī)劃再添加一個(gè)控制因子 ，構(gòu)成三元表達(dá)式(X, , )，其中 =(1, 2, , j, , n)j是相關(guān)系數(shù)的單下標(biāo)表達(dá), 它表示xi和xj 之間的協(xié)方差:進(jìn)化規(guī)劃的根本技術(shù)產(chǎn)生初始群體進(jìn)化規(guī)劃中產(chǎn)生初始群體的方法類似于進(jìn)化戰(zhàn)略中隨機(jī)選擇個(gè)個(gè)體作為進(jìn)化計(jì)算的出發(fā)點(diǎn)。計(jì)算順應(yīng)度進(jìn)化規(guī)劃采用十進(jìn)制實(shí)數(shù)表達(dá)問題，計(jì)算順應(yīng)度比較簡單直觀。突變突變是進(jìn)化規(guī)劃產(chǎn)生新群體的獨(dú)一方法，它不采用重組或交換算子。進(jìn)化規(guī)劃的根本技術(shù)選擇在進(jìn)化規(guī)劃中，新群體的個(gè)體數(shù)目等于舊群體的個(gè)體數(shù)目，選擇便是在2 個(gè)個(gè)體中選擇個(gè)個(gè)體組成新群體。進(jìn)

19、化規(guī)劃的選擇采用隨機(jī)型的q競(jìng)爭(zhēng)選擇法。在這種選擇方法中，為了確定某一個(gè)體 i 的優(yōu)劣，我們重新、舊群體的2 個(gè)個(gè)體中任選q個(gè)個(gè)體組成測(cè)試群體。然后將個(gè)體 i 的順應(yīng)度與q個(gè)個(gè)體的順應(yīng)度進(jìn)展比較，記錄個(gè)體 i 優(yōu)于或等于q內(nèi)各個(gè)體的次數(shù)，得到個(gè)體 i 的得分Wi，即進(jìn)化規(guī)劃的根本技術(shù)上述得分測(cè)試分別對(duì)2個(gè)個(gè)體進(jìn)展，每次鍘試時(shí)重新選擇q個(gè)個(gè)體組成新的測(cè)試群體。最后，按個(gè)體的得分選擇分值高的個(gè)個(gè)體組成下一代新群體。q競(jìng)爭(zhēng)選擇法是一種隨機(jī)選擇，總體上講，優(yōu)良個(gè)體入選的能夠性較大。但是由于測(cè)試群體q每次都是隨機(jī)選擇的，當(dāng)q個(gè)個(gè)體都不甚好時(shí)，有能夠使較差的個(gè)體因得分高而入選。這正是隨機(jī)選擇的本意。q競(jìng)爭(zhēng)選

20、擇法中q的大小是一個(gè)重要參數(shù)。假設(shè)q很大，極端地設(shè)q2，那么選擇變?yōu)榇_定性選擇。反之，假設(shè)q很小，那么選擇的隨機(jī)性太大，不能保證優(yōu)良個(gè)體入選。通常q在10以上，可取0.9。進(jìn)化規(guī)劃的根本技術(shù)終止進(jìn)化規(guī)劃的終止準(zhǔn)那么與進(jìn)化戰(zhàn)略一樣，即根據(jù)最大進(jìn)化代次、最優(yōu)個(gè)體與期望值的偏向、順應(yīng)度的變化趨勢(shì)以及最優(yōu)順應(yīng)度與最差順應(yīng)度之差等四個(gè)判據(jù)。進(jìn)化規(guī)劃的根本技術(shù)進(jìn)化規(guī)劃的算法算法流程：(1)確定問題的表達(dá)方式。(2)隨機(jī)產(chǎn)生初始群體，并計(jì)算其順應(yīng)度。(3)用下述操作產(chǎn)生新群體：1) 突變。對(duì)舊個(gè)體添加隨機(jī)量，產(chǎn)生新個(gè)體2) 計(jì)算新個(gè)體順應(yīng)度；3) 選擇。挑選優(yōu)良個(gè)體組成新群體。(4)反復(fù)執(zhí)行(3)，直至滿足

21、終止條件，選擇最正確個(gè)體作為進(jìn)化規(guī)劃的最優(yōu)解。遺傳規(guī)劃遺傳算法的局限性：(1)不能描畫層次化的問題。(2)不能描畫計(jì)算機(jī)程序。(3)缺乏動(dòng)態(tài)可變性。1992年、美國John R. Koza正式提出遺傳規(guī)劃(Genetic Programming)，用層次化的構(gòu)造性言語表達(dá)問題。遺傳規(guī)劃的最大特點(diǎn)，是采用層次化的構(gòu)造表達(dá)問題，它類似于計(jì)算機(jī)程序分行或分段地描畫問題。這種廣義的計(jì)算機(jī)程序可以根據(jù)環(huán)境形狀自動(dòng)改動(dòng)程序的構(gòu)造及大小。遺傳規(guī)劃的任務(wù)步驟可歸納如下：(1)確定個(gè)體的表達(dá)方式，包括函數(shù)集F及終止符集T。(2)隨機(jī)產(chǎn)生初始群體。(3)計(jì)算各個(gè)體的順應(yīng)度。(4)根據(jù)遺傳參數(shù)，用下述操作產(chǎn)生新個(gè)體

22、：1)復(fù)制。將已有的優(yōu)良個(gè)體復(fù)制，參與新群體中，并相應(yīng)刪除劣質(zhì)個(gè)體2)交換。將選出的兩個(gè)個(gè)體進(jìn)展交換，所產(chǎn)生的兩個(gè)新個(gè)體插入新群體中。3)突變。隨機(jī)改動(dòng)個(gè)體某一部分，將新個(gè)體插入新群體中。(5)反復(fù)執(zhí)行(3)及(4)直至獲得稱心結(jié)果。遺傳規(guī)劃的根本技術(shù)問題的表達(dá)遺傳規(guī)劃是用層次構(gòu)造可變的方式表達(dá)問題，在表達(dá)中主要用函數(shù)和終止符兩類組分。簡單地說，終止符表示問題的值，函數(shù)表示對(duì)值的處置。綜合在一同，遺傳規(guī)劃的個(gè)體表示對(duì)各種值(終止符)的處置過程(函數(shù))。 在函數(shù)集Ff1, f2, , fn中，函數(shù)fi可以是運(yùn)算符、函數(shù)、闡明等，詳細(xì)有：(1) 算術(shù)運(yùn)算符，如+, -, *, /等。其中除號(hào)為防止計(jì)算機(jī)溢出，規(guī)定不允許用零作分母，稱維護(hù)性除法(Protected Division)，用標(biāo)志。一旦遇到分母為零時(shí)，最簡單的處置方法是令其商為1、或是重新選擇算術(shù)運(yùn)算符。遺傳規(guī)劃的根本技術(shù)(2)超越函數(shù)，如sin, cos, tan, log, exp等。其中l(wèi)og要防止處置小于或等于零的數(shù)值，稱維護(hù)性對(duì)數(shù)，記為Rlog其處置方法類似于。(3)布爾運(yùn)算符，如AND、OR或NOT等。(4)條件表達(dá)式，如If-then-else, Switch-Case等。(5)循環(huán)表達(dá)式如Do-until, while-do, For-do等。(6