進化策略進化規(guī)劃

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

2、個體反復進行隨機試驗。到了1950年，Turng認識到，在機器學習和進化之間存在著明顯的關(guān)系。1959年，F(xiàn)riedman推測，利用變異和選擇的仿真可以設計“思想機器”，并且指出下棋的程序可以用這種方法設計。在1960年，Cambell猜想：在導致知識擴張的所有過程中，都要涉及“盲目變化選擇幸存”的過程。此后，一些學者逐漸將進化理論用于隨機工程控制、機器學習和函數(shù)優(yōu)化等領(lǐng)域。28.2 進化策略進化策略（Evolutionary Strategies）是在1965年由Rechenburg和Schwefel獨立提出的。早期的進化策略的種群中只包含一個個體，并且只使用變異操作。在每一代中，變異后的個

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

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

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

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

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

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

9、的表達：為了與突變操作相適應，進化策略有兩種表達方式。(1) 二元表達方式。這種表達方式中個體由目標變量X和標準差兩部分組成，每部分又可以有n個分量，即：X和的關(guān)系為:為全局系數(shù)，常取1。12進化策略的基本技術(shù)(2) 三元表達方式。為了改善進化策略的收斂速度，Schwefel在二元表達的基礎(chǔ)上引入第三個因子坐標旋轉(zhuǎn)角度。個體的描述擴展為(X, , )，即：三者的關(guān)系為：i父代個體i分量與j分量間坐標的旋轉(zhuǎn)角度；j子代新個體i分量與j分量間坐標的旋轉(zhuǎn)角度；系數(shù)，常取0.0873；zi取決于及的正態(tài)分布隨機數(shù)。13進化策略的基本技術(shù)旋轉(zhuǎn)角度i表面上是分量i與j間坐標的旋轉(zhuǎn)角度，實質(zhì)上它是分量i與分

10、量j之間協(xié)方差的體現(xiàn)。重組進化策略中的重組(Recombination)算子相當于遺傳算法的交叉，它們都是以兩個父代個體為基礎(chǔ)進行信息交換。進化策略中，重組方式主要有三種：(1)離散重組。先隨機選擇兩個父代個體14進化策略的基本技術(shù)然后將其分量進行隨機交換，構(gòu)成子代新個體的各個分量，從而得出如下新個體：(2) 中值重組。這種重組方式也是先隨機選擇兩個父代個體，然后將父代個體各分量的平均值作為子代新個體的分量，構(gòu)成的新個體為：這時，新個體的各個分量兼容兩個父代個體信息，而在離散重組中則只含有某一個父代個體的因子。15進化策略的基本技術(shù)(3)混雜(Panmictic)重組。這種重組方式的特點在于父

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

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

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

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

15、添加一個隨機數(shù)，添加值的大小與個體的適應度有關(guān)：適應度大的個體添加值也大，反之亦然。根據(jù)這種表達方式，進化規(guī)劃首先產(chǎn)生個初始個體，這也就是突變。接著從個舊個體及個新個體(2 個個體)中根據(jù)適應度挑選出個個體組成新群體。如此反復迭代，直至得到滿意結(jié)果。應該指出，進化規(guī)劃沒有重組或交換這類算子，它的進化主要依賴突變。在標準進化規(guī)劃中這種突變十分簡單，它只需參照個體適應度添加一個隨機數(shù)。很明顯，標準進化規(guī)劃在進化過程中的自適應調(diào)整功能主要依靠適應度f(X)來實現(xiàn)。228.3 進化規(guī)劃Standard EP流程：生成初始群體；While Not-End Do突變；計算個體適應度；選擇；組成新群體End

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

17、:(1)執(zhí)行順序不同。進化規(guī)劃中首先計算新個體的目標變量xi ，計算中沿用舊個體的標準差i ；其次才計算新個體的標準差i ，新的標準差留待下次進化時才用。與之相反，進化策略是先調(diào)整標準差，然后再用新的標準差去更改個體的目標變量X。(2)計算式的不同。進化規(guī)劃的計算式比進化策略的計算式簡單。258.3 進化規(guī)劃旋轉(zhuǎn)進化規(guī)劃旋轉(zhuǎn)進化規(guī)劃(Rmeta EP)進一步擴展進化規(guī)劃，在表達個體時添加第三個因子協(xié)方差，用三元組表示個體，即(X, , )，具體計算如下：X舊個體的目標變量，其內(nèi)含n個分量；X新個體的目標變量，其內(nèi)含n個分量；N(0,C)遵從正態(tài)分布的隨機數(shù)，其數(shù)學期望為0、其標準差與協(xié)方差有關(guān)

18、；j相關(guān)系數(shù)，26進化規(guī)劃的基本技術(shù)表達方法采用十進制的實型數(shù)表達問題。X=(x1, x2, , xi, , xn)由X和組成的二元組(X, )是進化規(guī)劃最常用的表達形式。有人建議將進化規(guī)劃再增加一個控制因子 ，構(gòu)成三元表達式(X, , )，其中 =(1, 2, , j, , n)j是相關(guān)系數(shù)的單下標表達, 它表示xi和xj 之間的協(xié)方差:27進化規(guī)劃的基本技術(shù)產(chǎn)生初始群體進化規(guī)劃中產(chǎn)生初始群體的方法類似于進化策略中隨機選擇個個體作為進化計算的出發(fā)點。計算適應度進化規(guī)劃采用十進制實數(shù)表達問題，計算適應度比較簡單直觀。突變突變是進化規(guī)劃產(chǎn)生新群體的唯一方法，它不采用重組或交換算子。28進化規(guī)劃的

19、基本技術(shù)選擇在進化規(guī)劃中，新群體的個體數(shù)目等于舊群體的個體數(shù)目，選擇便是在2 個個體中選擇個個體組成新群體。進化規(guī)劃的選擇采用隨機型的q競爭選擇法。在這種選擇方法中，為了確定某一個體 i 的優(yōu)劣，我們從新、舊群體的2 個個體中任選q個個體組成測試群體。然后將個體 i 的適應度與q個個體的適應度進行比較，記錄個體 i 優(yōu)于或等于q內(nèi)各個體的次數(shù)，得到個體 i 的得分Wi，即29進化規(guī)劃的基本技術(shù)上述得分測試分別對2個個體進行，每次鍘試時重新選擇q個個體組成新的測試群體。最后，按個體的得分選擇分值高的個個體組成下一代新群體。q競爭選擇法是一種隨機選擇，總體上講，優(yōu)良個體入選的可能性較大。但是由于測

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

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

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

23、2, , fn中，函數(shù)fi可以是運算符、函數(shù)、說明等，具體有：(1) 算術(shù)運算符，如+, -, *, /等。其中除號為防止計算機溢出，規(guī)定不允許用零作分母，稱保護性除法(Protected Division)，用標記。一旦遇到分母為零時，最簡單的處理方法是令其商為1、或是重新選擇算術(shù)運算符。35遺傳規(guī)劃的基本技術(shù)(2)超越函數(shù)，如sin, cos, tan, log, exp等。其中l(wèi)og要防止處理小于或等于零的數(shù)值，稱保護性對數(shù)，記為Rlog其處理方法類似于。(3)布爾運算符，如AND、OR或NOT等。(4)條件表達式，如If-then-else, Switch-Case等。(5)循環(huán)表達式如Do-until, while-do, For-do等。(6)控