1.1.2 進化策略

1964年，德國柏林工業大學的H. P. Schwefel[15]和I. Rechenberg[16]在研究流體動力學問題時，如彎管形狀優化試驗，按照自然突變和自然選擇的生物進化思想提出了一種適合于實數變量的優化算法——進化策略（ES）。該算法優化能力主要依靠變異算子對物體的外形參數進行隨機變化并嘗試其效果，后來受GA的啟迪，也引入了輔助的雜交算子。

ES的個體表示為Pi(x,σ)，i=1，2，…，n。其中，x=(x1,x2,…,xm)為群體中的一個候選實數解；σ=(σ1,σ2,…,σm)為候選解x變異時的正實數參數，稱為“策略參數”；m為優化變量的個數，即優化空間的維數；n為群體規模。Schwefel引入了一種高斯變異算子，如果父代某個個體表示為Pk(x,σ)，1≤k≤n，由該個體變異后的子代個體表示為，其中，，。具體變異過程如下：

式中，α～N(0,1)，βj～N(0,1)，，τ是群體變異步長，τ′是個體變異步長。

從變異式（1-1）和式（1-2）可以看出，ES的變異主要是σ帶有隨機性的調整，τ和τ′是對調整起關鍵作用的兩個參數，一般

這兩個參數是固定不變的，因而實質上，新的候選解是以原來候選解加上一個服從高斯分布的隨機變量變異產生的。

在ES中，目標參數和策略參數都需要編碼到染色體中。目標參數是指直接涉及適應值計算的參數。策略參數即應用于進化算法中的控制參數，例如種群規模、突變步長、突變頻率、交叉位置、交叉頻率等。一般而言，策略參數的選取對進化算法的性能有著直接的影響。因此，人們希望策略參數和目標參數在進化的過程中可以同時得到優化，這就是“自適應”的由來。

ES可簡單描述如下：

（1）確定問題：尋找n維實值向量x，使函數f(x)取極值。

（2）初始化種群：在各維的可行范圍內，一般依據均勻分布隨機選擇父向量xi(i=1，2，…，n)作為初始群體。

（3）進化：對父向量的每個分量增加一個均值為0和預先選擇標準差的高斯隨機變量來產生子代向量。

（4）選擇：對排序，選擇和決定保留哪些向量作為下一代的父代。

（5）終止：重復進化和選擇，直到找到符合條件的答案。

ES的實現形式有如下3種。

1. (1+1)-ES

原始的ES被稱為(1+1)-ES，原因在于只考慮單個個體的進化，沒有體現群體的作用，具有明顯的局限性。每次迭代由1個父代個體進化到1個子代個體，并且進化操作只有隨機突變一種方式，即利用隨機變量修正舊個體。突變方式與進化規劃是相似的。

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

當把這種算法用于函數優化時，有兩個缺點：各維取固定常數的標準差導致程序收斂到最優解的速度很慢，點到點搜索的脆弱本質使得程序在局部極值附近容易受停滯的影響。

2. (μ+1)-ES

隨后提出的(μ+1)-ES進行了改進，不是在單個個體上進化，而是在μ個個體上進化，但每次進化所獲得的新個體數仍然為1。同時增加了重組算子，用于從兩個個體中組合出新個體。

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

盡管(μ+1)-ES沒有得到廣泛應用，但這是第一個基于種群的ES，常用于多處理機下的異步并行計算，并引入了交叉算子，把變異步長以內的參數（策略參數）形式作為個體基因的部分參與進化。

3. (μ+λ)-ES與(μ, λ)-ES

(μ+λ)-ES與(μ, λ)-ES都在μ個父代個體上執行重組和變異，產生λ個新個體。二者區別僅在于子代群體的選擇上，其中，(μ+λ)-ES從μ個父代個體和λ個新個體的并集中再選擇μ個子代個體；(μ，λ)-ES只在λ(>μ)個新個體中選擇μ個子代個體。