進化驅動演算法

① 進化演算法的特點

進化計算是一種具有魯棒性的方法，能適應不同的環境不同的問題，而且在大多數情況下都能得到比較滿意的有效解。他對問題的整個參數空間給出一種編碼方案，而不是直接對問題的具體參數進行處理，不是從某個單一的初始點開始搜索，而是從一組初始點搜索。搜索中用到的是目標函數值的信息，可以不必用到目標函數的導數信息或與具體問題有關的特殊知識。因而進化演算法具有廣泛的應用性，高度的非線性，易修改性和可並行性。
此外，演算法本身也可以採用動態自適應技術，在進化過程中自動調整演算法控制參數和編碼精度，比如使用模糊自適應法 。 進化策略(ES)是在1965年由Rechenberg和Schwefel獨立提出的。
進化策略的一般演算法
(1) 問題為尋找實值n維矢量x，使得函數F(x): R→R取極值。不失一般性，設此程序為極小化過程。
(2) 從各維的可行范圍內隨機選取親本xi，i = 1, … , p的始值。初始試驗的分布一般是均勻分布。
(3) 通過對於x的每個分量增加零均值和預先選定的標准差的高斯隨機變數，從每個親本xi產生子代xi』。
(4) 通過將適應度F(xi)和F(xi』)，i=1，…，P進行排序，選擇並決定那些矢量保留。具有最小適應度的P個矢量變成下一代的新親本。
進行新試驗，選擇具有最小方差的新子代，一直到獲得充分解，或者直到滿足某個終止條件。
在這個模型中，把試驗解的分量看做個體的行為特性，而不是沿染色體排列的基因。假設不管發生什麼遺傳變換，所造成各個個體行為的變化均遵循零均值和某個標准差的高斯分布。
由於基因多效性和多基因性，特定基因的改變可以影響許多表現型特徵。所以在創造新子系時，較為合適的是同時改變親本所有分量。
(1+1)—ES：
早期的進化策略的種群中只包含一個個體，並且只使用變異操作。在每一代中，變異後的個體與其父代進行比較，並選擇較好的一個，這種選擇策略被稱為(1+1)策略。
(1+1)—ES的缺點：
(1) 各維取定常的標推差使得程序收斂到最優解的速度很慢；
(2) 點到點搜索的脆弱本質使得程序在局部極值附近容易受停滯的影響(雖然此演算法表明可以漸近地收斂到全局最優點)。
(μ+λ)—ES：μ個親本製造λ個子代，所有解均參加生存競爭，選出最好的μ個作為下一代的親本。
(μ，λ)—ES：只有λ個子代參加生存競爭，在每代中μ個親本被完全取代。
1．個體的表示法:
每個解矢量不僅包括了n維試驗矢量x，而且還包括了擾動矢量σ，後者給出如何變異x以及它本身如何變異的指令。
2．變異：
設x為當前矢量。σ為對應於x每個維的方差矢量，於是新的解矢量x』，σ』可以這樣產生：
3．交叉：
4．選擇
在進化策略中，選擇是按完全確定的方式進行。(μ,λ)—ES是從λ個子代個體集中選擇μ(1<μ<λA=個最好的個體；(μ+λ)—ES是從父代和子代個體的並集中選擇μ個最好的個體。雖然(μ+λ)—ES保留最優的個體能保證性能單調提高，但這種策略不能處理變化的環境，因此，目前選用最多的還是(μ,λ)—ES。 進化規劃(EP)由Fogel在20世紀60年代提出。
1．表示法和適應值度量
進化規劃假設—個有界子空間 ，其中ui<vi。搜索區域被擴展到I=R，即個體為目標變數向量，a=x∈I，進化規劃把目標函數值通過比例變換到正值，同時加入某個隨機改變θ來得到適應值 ，其中δ是比例函數。
2．變異
可簡化為：
3．選擇
在P個父代個體每個經過一次變異產生P個子代後，進化規劃利用一種隨機q競爭選擇方法從父代和子代的集合中選擇P個個體，其中q>1是選擇演算法的參數。

② 人工智慧之進化演算法

進化計算的三大分支包括：遺傳演算法(Genetic Algorithm ，簡稱GA)、進化規劃(Evolu-tionary Programming，簡稱EP)和進化策略(Evolution Strategies ，簡稱ES)。這三個分支在演算法實現方面具有一些細微的差別，但它們具有一個共同的特點，即都是藉助生物進化的思想和原理來解決實際問題。

遺傳演算法是一類通過模擬生物界自然選擇和自然遺傳機制的隨機化搜索演算法，由美國Holand J教授於1975年首次提出。它是利用某種編碼技術作用於稱為染色體的二進制數串，其基本思想是模擬由這些串組成的種群的進化過程，通過有組織的、然而是隨機的信息交換來重新組合那些適應性好的串。遺傳演算法對求解問題的本身一無所知，它所需要的僅是對演算法所產生的每個染色體進行評價，並根據適應性來選擇染色體，使適應性好的染色體比適應性差的染色體有更多的繁殖機會。遺傳演算法尤其適用於處理傳統搜索方法難於解決的復雜的非線性問題，可廣泛用於組合優化、機器學習、自適應控制、規劃設計和人工生命等領域，是21世紀有關智能計算中的關鍵技術之一。

1964年，由德國柏林工業大學的RechenbergI等人提出。在求解流體動力學柔性彎曲管的形狀優化問題時，用傳統的方法很難在優化設計中描述物體形狀的參數，然而利用生物變異的思想來隨機地改變參數值並獲得了較好效果。隨後，他們便對這種方法進行了深入的研究和發展，形成了進化計算的另一個分支——進化策略。

進化策略與遺傳演算法的不同之處在於：進化策略直接在解空間上進行操作，強調進化過程中從父體到後代行為的自適應性和多樣性，強調進化過程中搜索步長的自適應性調節;而遺傳演算法是將原問題的解空間映射到位串空間之中，然後再施行遺傳操作，它強調個體基因結構的變化對其適應度的影響。

進化策略主要用於求解數值優化問題。

進化規劃的方法最初是由美國人Fogel LJ等人在20世紀60年代提出的。他們在人工智慧的研究中發現，智能行為要具有能預測其所處環境的狀態，並按照給定的目標做出適當的響應的能力。在研究中，他們將模擬環境描述成是由有限字元集中符號組成的序列。

進化演算法與傳統的演算法具有很多不同之處，但其最主要的特點體現在下述兩個方面：

進化計算的智能性包括自組織、自適應和自學習性等。應用進化計算求解問題時，在確定了編碼方案、適應值函數及遺傳運算元以後，演算法將根據「適者生存、不適應者淘汰"的策略，利用進化過程中獲得的信息自行組織搜索，從而不斷地向最佳解方向逼近。自然選擇消除了傳統演算法設計過程中的-一個最大障礙：即需要事先描述問題的全部特點，並說明針對問題的不同特點演算法應採取的措施。於是，利用進化計算的方法可以解決那些結構尚無人能理解的復雜問題。

進化計算的本質並行性表現在兩個方面：

一是進化計算是內在並行的，即進化計算本身非常適合大規模並行。

二是進化計算的內含並行性，由於進化計算採用種群的方式組織搜索，從而它可以同時搜索解空間內的多個區域，並相互交流信息，這種搜索方式使得進化計算能以較少的計算獲得較大的收益。

③ 進化演算法的基本步驟

進化計算是基於自然選擇和自然遺傳等生物進化機制的一種搜索演算法。與普通的搜索方法一樣，進化計算也是一種迭代演算法，不同的是進化計算在最優解的搜索過程中，一般是從原問題的一組解出發改進到另一組較好的解，再從這組改進的解出發進一步改進。而且在進化問題中，要求當原問題的優化模型建立後，還必須對原問題的解進行編碼。進化計算在搜索過程中利用結構化和隨機性的信息，使最滿足目標的決策獲得最大的生存可能，是一種概率型的演算法。
一般來說，進化計算的求解包括以下幾個步驟：給定一組初始解；評價當前這組解的性能；從當前這組解中選擇一定數量的解作為迭代後的解的基礎；再對其進行操作，得到迭代後的解；若這些解滿足要求則停止，否則將這些迭代得到的解作為當前解重新操作。
以遺傳演算法為例，其工作步驟可概括為：
（1） 對工作對象——字元串用二進制的0/1或其它進制字元編碼 。
（2） 根據字元串的長度L，隨即產生L個字元組成初始個體。
（3） 計算適應度。適應度是衡量個體優劣的標志，通常是所研究問題的目標函數。
（4） 通過復制，將優良個體插入下一代新群體中，體現「優勝劣汰」的原則。
（5） 交換字元，產生新個體。交換點的位置是隨機決定的
（6） 對某個字元進行補運算，將字元1變為0，或將0變為1，這是產生新個體的另一種方法，突變字元的位置也是隨機決定的。
（7） 遺傳演算法是一個反復迭代的過程，每次迭代期間，要執行適應度計算、復制、交換、突變等操作，直至滿足終止條件。
將其用形式化語言表達，則為：假設α∈I記為個體，I記為個體空間。適應度函數記為Φ：I→R。在第t代，群體P(t)={a1(t),a2(t)，…，an(t)}經過復制r(reproction)、交換c(crossover)及突變m(mutation)轉換成下一代群體。這里r、c、m均指宏運算元，把舊群體變換為新群體。L：I→{True, Flase}記為終止准則。利用上述符號，遺傳演算法可描述為：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end