進(jìn)化策略進(jìn)化規(guī)劃

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

2、個(gè)體反復(fù)進(jìn)行隨機(jī)試驗(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猜想：在導(dǎo)致知識(shí)擴(kuò)張的所有過(guò)程中，都要涉及“盲目變化選擇幸存”的過(guò)程。此后，一些學(xué)者逐漸將進(jìn)化理論用于隨機(jī)工程控制、機(jī)器學(xué)習(xí)和函數(shù)優(yōu)化等領(lǐng)域。28.2 進(jìn)化策略進(jìn)化策略（Evolutionary Strategies）是在1965年由Rechenburg和Schwefel獨(dú)立提出的。早期的進(jìn)化策略的種群中只包含一個(gè)個(gè)體，并且只使用變異操作。在每一代中，變異后的個(gè)

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

4、的p個(gè)矢量變成下一代的新親本。進(jìn)行新試驗(yàn)，選擇具有最小方差的新子代，一直到獲得充分解，或者直到滿足某個(gè)終止條件48.2 進(jìn)化策略在這個(gè)模型中，把試驗(yàn)解的分量看做個(gè)體的行為特性，而不是沿染色體排列的基因?？梢院虶A一樣，假設(shè)這些表現(xiàn)型特征具有基因根源，但是它們之間的聯(lián)系實(shí)質(zhì)并沒(méi)有被弄清楚，所以我們把著重點(diǎn)放在個(gè)體的行為特性上。假設(shè)不管發(fā)生什么遺傳變換，所造成各個(gè)行為的變化均遵循零均值和某個(gè)標(biāo)準(zhǔn)差的高斯分布。由于基因多效性和多基因性，特定基因的改變可以影響許多表現(xiàn)型特征。所以在創(chuàng)造新子代時(shí)，較為合適的是同時(shí)改變親本所有分量。58.2 進(jìn)化策略進(jìn)化策略的最初試驗(yàn)采用上述算法，主要采用單親本單子代的搜

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

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

7、。顯然，(+1)-ES比(1+1)-ES有了明顯的改進(jìn)，為進(jìn)化策略這種新的進(jìn)化算法奠定良好的基礎(chǔ)。98.2 進(jìn)化策略在1973年，Rechenburg把該算法的期望收斂速度定義為對(duì)最優(yōu)點(diǎn)的平均距離與要得到此改善所需要的試驗(yàn)次數(shù)之比。1981年，Schwefel在進(jìn)化策略中使用多重親本和子代，這是Rechenburg早期工作（使用多重親本，但是僅使用單個(gè)子代）的發(fā)展，后來(lái)考察了兩種方法，分別表示為(+)-ES和(，)-ES。在前者中，個(gè)親本制造個(gè)子代，所有解均參加生存競(jìng)爭(zhēng)，選出最好的個(gè)作為下一代的親本。在后者中，只有（ ）個(gè)子代參加生存競(jìng)爭(zhēng)，在每代中個(gè)親本被完全取代。這就是說(shuō)，對(duì)于每一代，每個(gè)解

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

9、的表達(dá)：為了與突變操作相適應(yīng)，進(jìn)化策略有兩種表達(dá)方式。(1) 二元表達(dá)方式。這種表達(dá)方式中個(gè)體由目標(biāo)變量X和標(biāo)準(zhǔn)差兩部分組成，每部分又可以有n個(gè)分量，即：X和的關(guān)系為:為全局系數(shù)，常取1。12進(jìn)化策略的基本技術(shù)(2) 三元表達(dá)方式。為了改善進(jìn)化策略的收斂速度，Schwefel在二元表達(dá)的基礎(chǔ)上引入第三個(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ù)。13進(jìn)化策略的基本技術(shù)旋轉(zhuǎn)角度i表面上是分量i與j間坐標(biāo)的旋轉(zhuǎn)角度，實(shí)質(zhì)上它是分量i與分

10、量j之間協(xié)方差的體現(xiàn)。重組進(jìn)化策略中的重組(Recombination)算子相當(dāng)于遺傳算法的交叉，它們都是以兩個(gè)父代個(gè)體為基礎(chǔ)進(jìn)行信息交換。進(jìn)化策略中，重組方式主要有三種：(1)離散重組。先隨機(jī)選擇兩個(gè)父代個(gè)體14進(jì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è)體的因子。15進(jìn)化策略的基本技術(shù)(3)混雜(Panmictic)重組。這種重組方式的特點(diǎn)在于父

11、代個(gè)體的選擇上?；祀s重組時(shí)先隨機(jī)選擇一個(gè)固定的父代個(gè)體，然后針對(duì)子代個(gè)體每個(gè)分量再?gòu)母复后w中隨機(jī)選擇第二個(gè)父代個(gè)體。也就是說(shuō)，第二個(gè)父代個(gè)體是經(jīng)常變化的。至于父代兩個(gè)個(gè)體的組合方式，既可以采用離散方式，也可以來(lái)用中值方式，甚至可以把中值重組中的1/2改為0,1之間的任一權(quán)值。研究表明，進(jìn)化策略采用重組后，明顯增加算法的收斂速度。Schwefel建議，對(duì)于目標(biāo)變量X宜用離散重組，對(duì)于策略因子及宜用中值重組或混雜中值重組。16進(jìn)化策略的基本技術(shù)選擇：進(jìn)化策略的選擇有兩種：一為(+)選擇，另一為(, )選擇。(+)選擇是從個(gè)父代個(gè)體及個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)選出個(gè)個(gè)體組成下一代新群體。(, )選

12、擇是從個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)桃選個(gè)個(gè)體(要求)組成下一代群體，每個(gè)個(gè)體只存活一代，隨即被新個(gè)體頂替。粗略地看，似乎(+)選擇最好，它可以保證最優(yōu)個(gè)體存活，使群體的進(jìn)化過(guò)程呈單調(diào)上升趨勢(shì)。但是，深入分析后發(fā)現(xiàn)(+)選擇具有下述缺點(diǎn)：17進(jìn)化策略的基本技術(shù)(1) (+)選擇保留舊個(gè)體，它有時(shí)會(huì)是過(guò)時(shí)的可行解，妨礙算法向最優(yōu)方向發(fā)展。(，)選擇全部舍棄舊個(gè)體，使算法始終從新的基礎(chǔ)上全方位進(jìn)化。(2) (+)選擇保留舊個(gè)體，有時(shí)是局部最優(yōu)解，從而誤導(dǎo)進(jìn)化策略收斂于次優(yōu)解而不是最優(yōu)解。(，)選擇舍棄舊的優(yōu)良個(gè)體，容易進(jìn)化至全局員優(yōu)解。(3) (+)選擇在保留舊個(gè)體的同時(shí)，也將進(jìn)化參數(shù)保留下來(lái)，不利于

13、進(jìn)化策略中的自適應(yīng)調(diào)整機(jī)制。(，)選擇則恰恰相反，可促進(jìn)這種自適應(yīng)調(diào)整。 實(shí)踐也證明，(, )-ES優(yōu)于(+)-ES，前者已成為當(dāng)前進(jìn)化策略的主流。18進(jìn)化策略的基本技術(shù)在(+)-ES中，為了控制群體的多樣性和選擇的力度，比值/是一個(gè)重要參數(shù)，它對(duì)算法的收斂速度有很大影響。一方面， 不能太小，否則群體太單調(diào)(例如1的極端情況)；另一方面， 也不能太大，否則計(jì)算工作量過(guò)大。通常， 取15或更多一些。 數(shù)值的大小，類似于的作用，也要適當(dāng)。某些研究表明比值/宜取1/7左右。也就是說(shuō)，若=15，則宜取100。198.3 進(jìn)化規(guī)劃進(jìn)化規(guī)劃(Evolutionary Programming)由Fogel在

14、20世紀(jì)60年代所提出。Fogel將仿真進(jìn)化方法用于由相互競(jìng)爭(zhēng)的算法所構(gòu)成的種群，在一系列研究中探索了進(jìn)化規(guī)劃的可能性，目的是發(fā)展人工智能。Fogel認(rèn)為，智能行為需要有如下的復(fù)合能力： (1)預(yù)報(bào)它的環(huán)境； (2)把預(yù)報(bào)變成對(duì)于給定目標(biāo)的適當(dāng)響應(yīng)。208.3 進(jìn)化規(guī)劃標(biāo)準(zhǔn)進(jìn)化規(guī)劃進(jìn)化規(guī)劃用傳統(tǒng)的十進(jìn)制實(shí)數(shù)表達(dá)問(wèn)題。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃（Standard EP）中，個(gè)體的表達(dá)形式為：式中：xi舊個(gè)體目標(biāo)變量X的第i個(gè)分量， xi新個(gè)體目標(biāo)變量X的第i個(gè)分量， f(X)舊個(gè)體X的適應(yīng)度； N(0, 1)針對(duì)第i分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。218.3 進(jìn)化規(guī)劃上式表明，新個(gè)體是在舊個(gè)體的基礎(chǔ)上

15、添加一個(gè)隨機(jī)數(shù)，添加值的大小與個(gè)體的適應(yīng)度有關(guān)：適應(yīng)度大的個(gè)體添加值也大，反之亦然。根據(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ī)劃沒(méi)有重組或交換這類算子，它的進(jìn)化主要依賴突變。在標(biāo)準(zhǔn)進(jìn)化規(guī)劃中這種突變十分簡(jiǎn)單，它只需參照個(gè)體適應(yīng)度添加一個(gè)隨機(jī)數(shù)。很明顯，標(biāo)準(zhǔn)進(jìn)化規(guī)劃在進(jìn)化過(guò)程中的自適應(yīng)調(diào)整功能主要依靠適應(yīng)度f(wàn)(X)來(lái)實(shí)現(xiàn)。228.3 進(jìn)化規(guī)劃Standard EP流程：生成初始群體；While Not-End Do突變；計(jì)算個(gè)體適應(yīng)度；選擇；組成新群體End

16、 While238.3 進(jìn)化規(guī)劃元進(jìn)化規(guī)劃為了增加進(jìn)化規(guī)劃在進(jìn)化過(guò)程中的自適應(yīng)調(diào)整功能，人們?cè)谕蛔冎刑砑臃讲畹母拍睢ｎ愃朴谶M(jìn)化策略，在進(jìn)化規(guī)劃中個(gè)體的表達(dá)采用下述方式：式中：i舊個(gè)體第 i 分量的標(biāo)準(zhǔn)差； i新個(gè)體第 i 分量的標(biāo)準(zhǔn)差； N(0, 1)針對(duì)第i分量發(fā)生的隨機(jī)數(shù)，它服從標(biāo)準(zhǔn)正態(tài)分布。248.3 進(jìn)化規(guī)劃從上式可以看出，新個(gè)體也是在舊個(gè)體的基礎(chǔ)上添加一個(gè)隨機(jī)數(shù)，該添加量取決于個(gè)體的方差，而方差在每次進(jìn)化中又有自適應(yīng)調(diào)整。這種進(jìn)化方式已成為進(jìn)化規(guī)劃的主要手段，因此在進(jìn)化規(guī)劃前冠以“元”這個(gè)術(shù)語(yǔ)以表示它為基本方法。元進(jìn)化規(guī)劃(Meta EP)的突變盡管類似于進(jìn)化策略，但是它們有下述差別

17、:(1)執(zhí)行順序不同。進(jìn)化規(guī)劃中首先計(jì)算新個(gè)體的目標(biāo)變量xi ，計(jì)算中沿用舊個(gè)體的標(biāo)準(zhǔn)差i ；其次才計(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)差去更改個(gè)體的目標(biāo)變量X。(2)計(jì)算式的不同。進(jìn)化規(guī)劃的計(jì)算式比進(jìn)化策略的計(jì)算式簡(jiǎn)單。258.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, , )，具體計(jì)算如下：X舊個(gè)體的目標(biāo)變量，其內(nèi)含n個(gè)分量；X新個(gè)體的目標(biāo)變量，其內(nèi)含n個(gè)分量；N(0,C)遵從正態(tài)分布的隨機(jī)數(shù)，其數(shù)學(xué)期望為0、其標(biāo)準(zhǔn)差與協(xié)方差有關(guān)

18、；j相關(guān)系數(shù)，26進(jìn)化規(guī)劃的基本技術(shù)表達(dá)方法采用十進(jìn)制的實(shí)型數(shù)表達(dá)問(wèn)題。X=(x1, x2, , xi, , 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é)方差:27進(jìn)化規(guī)劃的基本技術(shù)產(chǎn)生初始群體進(jìn)化規(guī)劃中產(chǎn)生初始群體的方法類似于進(jìn)化策略中隨機(jī)選擇個(gè)個(gè)體作為進(jìn)化計(jì)算的出發(fā)點(diǎn)。計(jì)算適應(yīng)度進(jìn)化規(guī)劃采用十進(jìn)制實(shí)數(shù)表達(dá)問(wèn)題，計(jì)算適應(yīng)度比較簡(jiǎn)單直觀。突變突變是進(jìn)化規(guī)劃產(chǎn)生新群體的唯一方法，它不采用重組或交換算子。28進(jìn)化規(guī)劃的

19、基本技術(shù)選擇在進(jìn)化規(guī)劃中，新群體的個(gè)體數(shù)目等于舊群體的個(gè)體數(shù)目，選擇便是在2 個(gè)個(gè)體中選擇個(gè)個(gè)體組成新群體。進(jìn)化規(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，即29進(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è)

20、試群體q每次都是隨機(jī)選擇的，當(dāng)q個(gè)個(gè)體都不甚好時(shí)，有可能使較差的個(gè)體因得分高而入選。這正是隨機(jī)選擇的本意。q競(jìng)爭(zhēng)選擇法中q的大小是一個(gè)重要參數(shù)。若q很大，極端地設(shè)q2，則選擇變?yōu)榇_定性選擇。反之，若q很小，則選擇的隨機(jī)性太大，不能保證優(yōu)良個(gè)體入選。通常q在10以上，可取0.9。30進(jìn)化規(guī)劃的基本技術(shù)終止進(jìn)化規(guī)劃的終止準(zhǔn)則與進(jìn)化策略相同，即根據(jù)最大進(jìn)化代次、最優(yōu)個(gè)體與期望值的偏差、適應(yīng)度的變化趨勢(shì)以及最優(yōu)適應(yīng)度與最差適應(yīng)度之差等四個(gè)判據(jù)。31進(jìn)化規(guī)劃的基本技術(shù)進(jìn)化規(guī)劃的算法算法流程：(1)確定問(wèn)題的表達(dá)方式。(2)隨機(jī)產(chǎn)生初始群體，并計(jì)算其適應(yīng)度。(3)用下述操作產(chǎn)生新群體：1) 突變。對(duì)舊個(gè)體

21、添加隨機(jī)量，產(chǎn)生新個(gè)體2) 計(jì)算新個(gè)體適應(yīng)度；3) 選擇。挑選優(yōu)良個(gè)體組成新群體。(4)反復(fù)執(zhí)行(3)，直至滿足終止條件，選擇最佳個(gè)體作為進(jìn)化規(guī)劃的最優(yōu)解。32遺傳規(guī)劃遺傳算法的局限性：(1)不能描述層次化的問(wèn)題。(2)不能描述計(jì)算機(jī)程序。(3)缺乏動(dòng)態(tài)可變性。1992年、美國(guó)John R. Koza正式提出遺傳規(guī)劃(Genetic Programming)，用層次化的結(jié)構(gòu)性語(yǔ)言表達(dá)問(wèn)題。遺傳規(guī)劃的最大特點(diǎn)，是采用層次化的結(jié)構(gòu)表達(dá)問(wèn)題，它類似于計(jì)算機(jī)程序分行或分段地描述問(wèn)題。這種廣義的計(jì)算機(jī)程序能夠根據(jù)環(huán)境狀態(tài)自動(dòng)改變程序的結(jié)構(gòu)及大小。33遺傳規(guī)劃的工作步驟可歸納如下：(1)確定個(gè)體的表達(dá)方式

22、，包括函數(shù)集F及終止符集T。(2)隨機(jī)產(chǎn)生初始群體。(3)計(jì)算各個(gè)體的適應(yīng)度。(4)根據(jù)遺傳參數(shù)，用下述操作產(chǎn)生新個(gè)體：1)復(fù)制。將已有的優(yōu)良個(gè)體復(fù)制，加入新群體中，并相應(yīng)刪除劣質(zhì)個(gè)體2)交換。將選出的兩個(gè)個(gè)體進(jìn)行交換，所產(chǎn)生的兩個(gè)新個(gè)體插入新群體中。3)突變。隨機(jī)改變個(gè)體某一部分，將新個(gè)體插入新群體中。(5)反復(fù)執(zhí)行(3)及(4)直至取得滿意結(jié)果。34遺傳規(guī)劃的基本技術(shù)問(wèn)題的表達(dá)遺傳規(guī)劃是用層次結(jié)構(gòu)可變的形式表達(dá)問(wèn)題，在表達(dá)中主要用函數(shù)和終止符兩類組分。簡(jiǎn)單地說(shuō)，終止符表示問(wèn)題的值，函數(shù)表示對(duì)值的處理。綜合在一起，遺傳規(guī)劃的個(gè)體表示對(duì)各種值(終止符)的處理過(guò)程(函數(shù))。 在函數(shù)集Ff1, f

23、2, , fn中，函數(shù)fi可以是運(yùn)算符、函數(shù)、說(shuō)明等，具體有：(1) 算術(shù)運(yùn)算符，如+, -, *, /等。其中除號(hào)為防止計(jì)算機(jī)溢出，規(guī)定不允許用零作分母，稱保護(hù)性除法(Protected Division)，用標(biāo)記。一旦遇到分母為零時(shí)，最簡(jiǎn)單的處理方法是令其商為1、或是重新選擇算術(shù)運(yùn)算符。35遺傳規(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)控