[科普中國]-進化算法

起源發(fā)展

進化計算包括遺傳算法(Genetic Algorithms)、遺傳規(guī)劃（Genetic Programming）、進化策略(Evolution Strategies)和進化規(guī)劃(Evolution Programming)4種典型方法。第一類方法比較成熟，現(xiàn)已廣泛應(yīng)用，進化策略和進化規(guī)劃在科研和實際問題中的應(yīng)用也越來越廣泛。

遺傳算法的主要基因操作是選種、交配和突變，而在進化規(guī)則、進化策略中，進化機制源于選種和突變。就適應(yīng)度的角度來說遺傳算法用于選擇優(yōu)秀的父代(優(yōu)秀的父代產(chǎn)生優(yōu)秀的子代)，而進化規(guī)則和進化策略則用于選擇子代(優(yōu)秀的子代才能存在)。遺傳算法與遺傳規(guī)劃強調(diào)的是父代對子代的遺傳鏈，而進化規(guī)則和進化策略則著重于子代本身的行為特性，即行為鏈。進化規(guī)則和進化策略一般都不采用編碼，省去了運作過程中的編碼—解碼手續(xù)更適用于連續(xù)優(yōu)化問題，但因此也不能進行非數(shù)值優(yōu)化。進化策略可以確定機制產(chǎn)生出用于繁殖的父代，而遺傳算法和進化規(guī)則強調(diào)對個體適應(yīng)度和概率的依賴。

此外，進化規(guī)則把編碼結(jié)構(gòu)抽象為種群之間的相似，而進化策略抽象為個體之間的相似。進化策略和進化規(guī)則已應(yīng)用于連續(xù)函數(shù)優(yōu)化、模式識別、機器學習、神經(jīng)網(wǎng)絡(luò)訓練、系統(tǒng)辨識和智能控制的眾多領(lǐng)域。1

從本世紀40年代起，生物模擬就構(gòu)成了計算科學的一個組成部分，象早期的自動機理論，就是假設(shè)機器是由類似于神經(jīng)元的基本元素組成的，它向人們展示了第一個自復制機模型。這些年來諸如機器能否思維、基于規(guī)則的專家系統(tǒng)是否能勝任人類的工作，以及神經(jīng)網(wǎng)絡(luò)可否使機器具有看和聽的功能等有關(guān)生物類比的問題已成為人工智能關(guān)注的焦點。最近生物計算在機器昆蟲和種群動態(tài)系統(tǒng)模擬上所取得的成功激勵越來越多的人們致力于人工生命領(lǐng)域的研究。當今計算機科學家和分子生物學家已開始攜手進行合作研究，并且類比也得到了更為廣泛的應(yīng)用。

自然界生物體通過自身的演化就能使問題得到完美的解決。這種能力讓最好的計算機程序也相形見拙。計算機科學家為了某個算法可能要耗費數(shù)月甚至幾年的努力，而生物體通過進化和自然選擇這種非定向機制就達到了這個目的。

近三十年的不斷的研究和應(yīng)用已經(jīng)清楚地表明了模擬自然進化的搜索過程可以產(chǎn)生非常魯棒(orbust)的計算機算法，雖然這些模型還只是自然界生物體的粗糙簡化。進化算法就是基于這種思想發(fā)展起來的一類隨機搜索技術(shù)，它們是模擬由個體組成的群體的集體學習過程。其中每個個體表示給定問題搜索空間中的一點。進化算法從任一初始的群體出發(fā)，通過隨機選擇(在某些算法中是確定的)、變異和重組(在某些算法中被完全省去)過程，使群體進化到搜索空間中越來越好的區(qū)域。選擇過程使群體中適應(yīng)性好的個體比適應(yīng)性差的個體有更多的復制機會，重組算子將父輩信息結(jié)合在一起并將他們傳到子代個體，變異在群體中引人了新的變種。

目前研究的進化算法主要有三種典型的算法:遺傳算法、進化規(guī)劃和進化策略。這三種算法是彼此獨立發(fā)展起來的，遺傳算法由美國J.Holand創(chuàng)建，后由K.De Jong，J.Grefenstette，D.Goldberg和L.navis等人進行了改進；進化規(guī)劃最早由美國的L·J·Fogel，A.J.Owens和M.J.walsh提出，最近又由D.B.Fogel進行了完善；進化策略是由德國的I·Reehenberg和H.p.Sehwefel建立的。

群體搜索策略和群體中個體之間的信息交換是進化算法的兩大特點。它們的優(yōu)越性主要表現(xiàn)在:首先，進化算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)是不連續(xù)的，非規(guī)則的或有噪聲的情況下，它們也能以很大的概率找到全局最優(yōu)解；其次，由于它們固有的并行性，進化算法非常適合于巨量并行機；再者，進化算法采用自然進化機制來表現(xiàn)復雜的現(xiàn)象，能夠快速可靠地解決非常困難的問題；此外，由于它們?nèi)菀捉槿说揭延械哪Ｐ椭胁⑶揖哂锌蓴U展性，以及易于同別的技術(shù)混和等因素，進化算法目前已經(jīng)在最優(yōu)化、機器學習和并行處理等領(lǐng)域得到了越來越廣泛的應(yīng)用。1993年德國Dortmound大學的等人在一份研究t報告中搜集了篇有關(guān)進化算法的應(yīng)用的科技文獻。2

簡介進化算法包括遺傳算法、遺傳規(guī)劃、進化規(guī)劃和進化策略等等。進化算法的基本框架還是簡單遺傳算法所描述的框架，但在進化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化，進化算法的大致框圖可描述如右圖所示：

同遺傳算法一樣，進化算法的收斂性也有一些結(jié)果，文獻證明了在保存最優(yōu)個體時通用的進化計算是收斂的，但進化算法的很多結(jié)果是從遺傳算法推過去的。

遺傳算法對交叉操作要看重一些，認為變異操作是算法的輔助操作；而進化規(guī)劃和進化策略認為在一般意義上說交叉并不優(yōu)于變異，甚至可以不要交叉操作。

進化計算是基于自然選擇和自然遺傳等生物進化機制的一種搜索算法。與普通的搜索方法一樣，進化計算也是一種迭代算法，不同的是進化計算在最優(yōu)解的搜索過程中，一般是從原問題的一組解出發(fā)改進到另一組較好的解，再從這組改進的解出發(fā)進一步改進。而且在進化問題中，要求當原問題的優(yōu)化模型建立后，還必須對原問題的解進行編碼。進化計算在搜索過程中利用結(jié)構(gòu)化和隨機性的信息，使最滿足目標的決策獲得最大的生存可能，是一種概率型的算法。

一般來說，進化計算的求解包括以下幾個步驟：給定一組初始解；評價當前這組解的性能；從當前這組解中選擇一定數(shù)量的解作為迭代后的解的基礎(chǔ)；再對其進行操作，得到迭代后的解；若這些解滿足要求則停止，否則將這些迭代得到的解作為當前解重新操作。

以遺傳算法為例，其工作步驟可概括為：

（1） 對工作對象——字符串用二進制的0/1或其它進制字符編碼。

（2） 根據(jù)字符串的長度L，隨即產(chǎn)生L個字符組成初始個體。

（3） 計算適應(yīng)度。適應(yīng)度是衡量個體優(yōu)劣的標志，通常是所研究問題的目標函數(shù)。

（4） 通過復制，將優(yōu)良個體插入下一代新群體中，體現(xiàn)“優(yōu)勝劣汰”的原則。

（5） 交換字符，產(chǎn)生新個體。交換點的位置是隨機決定的

（6） 對某個字符進行補運算，將字符1變?yōu)?，或?qū)?變?yōu)?，這是產(chǎn)生新個體的另一種方法，突變字符的位置也是隨機決定的。

（7） 遺傳算法是一個反復迭代的過程，每次迭代期間，要執(zhí)行適應(yīng)度計算、復制、交換、突變等操作，直至滿足終止條件。

將其用形式化語言表達，則為：假設(shè)α∈I記為個體，I記為個體空間。適應(yīng)度函數(shù)記為Φ：I→R。在第t代，群體P(t)={a1(t),a2(t)，…，an(t)}經(jīng)過復制r(reproduction)、交換c(crossover)及突變m(mutation)轉(zhuǎn)換成下一代群體。這里r、c、m均指宏算子，把舊群體變換為新群體。L：I→{True, Flase}記為終止準則。利用上述符號，遺傳算法可描述為：

t=0initialize P(0):={ a1(0),a2(0)，…，an(0)};while(l(P(t))≠True) doevaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};reproduction: P′(t):=r(P(t));crossover: P″(t):=c(P′(t));mutation: P(t+1):= m(P″(t));t=t+1;end框架進化算法是以達爾文的進化論思想為基礎(chǔ)，通過模擬生物進化過程與機制的求解問題的自組織、自適應(yīng)的人工智能技術(shù)。生物進化是通過繁殖、變異、競爭和選擇實現(xiàn)的；而進化算法則主要通過選擇、重組和變異這三種操作實現(xiàn)優(yōu)化問題的求解。如下3

1、t=02、初始化群體p(0)3、評估初始化群體p(0)4、while終止條件不滿足do5、 重組操作：p(t)=r(p(t))6、 變異操作：p(t)=m(p(t))7、 評估操作：p(t)8、 選擇操作：p(t+1)=s(p(t)UQ)9、 t=t+110、end其中r、m、s分別表示重組算子、變異算子、選擇算子。圖1：進化算法基本框架

特點進化計算是一種具有魯棒性的方法，能適應(yīng)不同的環(huán)境不同的問題，而且在大多數(shù)情況下都能得到比較滿意的有效解。他對問題的整個參數(shù)空間給出一種編碼方案，而不是直接對問題的具體參數(shù)進行處理，不是從某個單一的初始點開始搜索，而是從一組初始點搜索。搜索中用到的是目標函數(shù)值的信息，可以不必用到目標函數(shù)的導數(shù)信息或與具體問題有關(guān)的特殊知識。因而進化算法具有廣泛的應(yīng)用性，高度的非線性，易修改性和可并行性。

此外，算法本身也可以采用動態(tài)自適應(yīng)技術(shù)，在進化過程中自動調(diào)整算法控制參數(shù)和編碼精度，比如使用模糊自適應(yīng)法。

進化策略進化策略(ES)是在1965年由Rechenberg和Schwefel獨立提出的。

進化策略的一般算法

(1) 問題為尋找實值n維矢量x，使得函數(shù)F(x): R→R取極值。不失一般性，設(shè)此程序為極小化過程。

(2) 從各維的可行范圍內(nèi)隨機選取親本xi，i = 1, … , p的始值。初始試驗的分布一般是均勻分布。

(3) 通過對于x的每個分量增加零均值和預先選定的標準差的高斯隨機變量，從每個親本xi產(chǎn)生子代xi’。

(4) 通過將適應(yīng)度F(xi)和F(xi’)，i=1，…，P進行排序，選擇并決定那些矢量保留。具有最小適應(yīng)度的P個矢量變成下一代的新親本。

進行新試驗，選擇具有最小方差的新子代，一直到獲得充分解，或者直到滿足某個終止條件。

在這個模型中，把試驗解的分量看做個體的行為特性，而不是沿染色體排列的基因。假設(shè)不管發(fā)生什么遺傳變換，所造成各個個體行為的變化均遵循零均值和某個標準差的高斯分布。

由于基因多效性和多基因性，特定基因的改變可以影響許多表現(xiàn)型特征。所以在創(chuàng)造新子系時，較為合適的是同時改變親本所有分量。

(1+1)****—ES：

早期的進化策略的種群中只包含一個個體，并且只使用變異操作。在每一代中，變異后的個體與其父代進行比較，并選擇較好的一個，這種選擇策略被稱為(1+1)策略。

(1+1)—ES的缺點：

(1) 各維取定常的標推差使得程序收斂到最優(yōu)解的速度很慢；

(2) 點到點搜索的脆弱本質(zhì)使得程序在局部極值附近容易受停滯的影響(雖然此算法表明可以漸近地收斂到全局最優(yōu)點)。

**(μ+λ)****—**ES：μ個親本制造λ個子代，所有解均參加生存競爭，選出最好的μ個作為下一代的親本。

**(μ，λ)****—**ES：只有λ個子代參加生存競爭，在每代中μ個親本被完全取代。

1**．個體的表示法:**

每個解矢量不僅包括了n維試驗矢量x，而且還包括了擾動矢量σ，后者給出如何變異x以及它本身如何變異的指令。

2**．變異：**

設(shè)x為當前矢量。σ為對應(yīng)于x每個維的方差矢量，于是新的解矢量x’，σ’可以這樣產(chǎn)生：

3**．交叉：**

4**．選擇**

在進化策略中，選擇是按完全確定的方式進行。(μ,λ)—ES是從λ個子代個體集中選擇μ(1