進化策略

進化策略的思想與進化規劃的思想有很多相似之處，但它是在歐洲獨立於遺傳算法和進化規劃而發展起來的。1963年，德國柏林技術大學的兩名學生I．Rechenberg和H．P．Schwefel，利用流體工程研究所的風洞做實驗，以便確定氣流中物體的最優外形。由於當時存在的一些優化策略(如簡單的梯度策略)不適於解決這類問題，Rechenberg提出按照自然突變相自然選擇的生物進化思想，對物體的外形參數進行隨機變化並嘗試其效果，進化策略的思想便由此誕生。

當時，人們對這種隨機策略無法接受，但他們仍堅持實驗。1970年，Rechenberg完成了有關進化策略研究的博士論文並獲得博士學位，現為仿生學與進化工程教授。1974年，Schwefel把有關進化策略研究的成果做了歸納整理，他現為計算機科學與系統分析教授。

1990年，在歐洲召開了第一屆“基於自然思想的並行問題求解”(PPSN，Parallel ProblemSolving Nature)國際會議。此後，該會每兩年舉行一次，成為在歐洲召開的有關進化計算的主要國際會議。 ^[1] 

最簡單形式的進化策略可描述如下：

(1)問題被定義為尋求與函數的極值相關聯的實數n維矢量x，F(x)：

—R。

(2)從每個可能的範圍內隨機選擇父矢量的初始羣體，初始試探的分佈具有典型的一致性。

(3)父矢量Xi(i=1，…，P)通過加入一個零均方差的高斯隨機變量以及預先選擇X的標準偏差來產生子代矢量Xi‘。

(4)通過對誤差F(Xi‘)(i=1，…，P)排序以選擇和決定保持哪些矢量。哪些擁有最小誤差的P矢量成為下一代的新的父代。

(5)產生新的試驗數據以及選擇最小誤差矢量的過程將繼續到找到符合條件的答案或者所有的計算已經全部完成為止。 ^[2] 

1．(1+1)一ES

原始的進化策略被稱為(1+1)-進化策略，簡稱(1+1)一ES，原因在於只考慮單個個體的進化，每次迭代由1個父代個體進化到1個子代個體，並且進化操作只有隨機突變1種方式，即利用隨機變量修正舊個體。突變方式與進化規劃是相似的。

在每次迭代中，對舊個體進行突變得到新個體後，計算新個體的適應度。如果新個體的適應度優於舊個體的適應度，則用新個體代替舊個體，否則不做替換。

2．(μ+1)——ES

(1+1)一ES沒有體現羣體的作用，具有明顯的侷限性。隨後提出的(μ+1)——ES對其進行了改進，不是在單個個體上進化，而是在μ個個體上進化，但每次進化所獲得的新個體數仍然為1。同時增加了重組算子，用於從兩個個體中組合出新個體。

在重組所獲得的新個體上再執行突變操作。最後將突變後的個體與μ個父代個體中的最差個體進行比較，如果優於該最差個體，則取代它；否則重新執行重組和突變產生另一個新個體。

3．(μ+λ)一ES與(μ，λ)一ES

(μ+λ)一ES與(μ，λ)一ES都在μ個父代個體上執行重組和變異，產生λ個新個體。二者區別僅在於子代羣體的選擇上。其中(μ+λ)一ES從μ個父代個體和A個新個體的並集中再選擇λ個子代個體；(μ，λ)一ES只在λ個新個體中再選擇μ個子代個體，這裏要求λ>μ。 ^[3] 

進化策略有以下獨特之處。

(1)進化策略中的自然選擇是按照確定方式進行的，有別於遺傳算法和進化規劃中的隨機選擇方式。

(2)進化策略中提供了重組算子，但進化策略中的重組不同於遺傳算法中的交換。即它不是將個體的某一部分互換，而是使個體中的每一位發生結合，新個體中的每一位都包含有兩個舊個體中的相應信息。 ^[3]