進化演算法

A. 進化演算法的簡介

進化演算法包括遺傳演算法、遺傳規劃、進化規劃和進化策略等等。進化演算法的基本框架還是簡單遺傳演算法所描述的框架，但在進化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化，進化演算法的大致框圖可描述如右圖所示：
同遺傳演算法一樣，進化演算法的收斂性也有一些結果，文獻證明了在保存最優個體時通用的進化計算是收斂的，但進化演算法的很多結果是從遺傳演算法推過去的。
遺傳演算法對交叉操作要看重一些，認為變異操作是演算法的輔助操作；而進化規劃和進化策略認為在一般意義上說交叉並不優於變異，甚至可以不要交叉操作。

B. 各種進化演算法有什麼異同

（差異進化演算法DE）是一種用於優化問題的啟發式演算法。本質上說，它是一種基於實數編碼的具有保優思想的貪婪遺傳演算法[1] 。同遺傳演算法一樣，差異進化演算法包含變異和交叉操作，但同時相較於遺傳演算法的選擇操作，差異進化演算法採用一對一的淘汰機制來更新種群。由於差異進化演算法在連續域優化問題的優勢已獲得廣泛應用，並引發進化演算法研究領域的熱潮。 差異進化演算法由Storn 以及Price [2]提出，演算法的原理採用對個體進行方向擾動，以達到對個體的函數值進行下降的目的，同其他進化演算法一樣，差異進化演算法不利用函數的梯度信息，因此對函數的可導性甚至連續性沒有要求，適用性很強。

C. 什麼是進化計算它包括哪些內容它們的出發點是什麼

1、准確的說應該叫進化演算法或演化演算法。是一個「演算法簇」，盡管它有很多的變化，有不同的遺傳基因表達方式，不同的交叉和變異運算元，特殊運算元的引用，以及不同的再生和選擇方法。與傳統的基於微積分的方法和窮舉法等優化演算法相比，進化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優化方法，具有自組織、自適應、自學習的特性，能夠不受問題性質的限制，有效地處理傳統優化演算法難以解決的復雜問題。

2、進化演算法內容包括遺傳演算法(Genetic Algorithms)、遺傳規劃（Genetic Programming）、進化策略(Evolution Strategies)和進化規劃(Evolution Programming)等等。進化演算法的基本框架還是簡單遺傳演算法所描述的框架，但在進化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化。

3、它們產生的出發點（或者說靈感）都來自於大自然的生物進化。

D. 進化演算法的特點

進化計算是一種具有魯棒性的方法，能適應不同的環境不同的問題，而且在大多數情況下都能得到比較滿意的有效解。他對問題的整個參數空間給出一種編碼方案，而不是直接對問題的具體參數進行處理，不是從某個單一的初始點開始搜索，而是從一組初始點搜索。搜索中用到的是目標函數值的信息，可以不必用到目標函數的導數信息或與具體問題有關的特殊知識。因而進化演算法具有廣泛的應用性，高度的非線性，易修改性和可並行性。
此外，演算法本身也可以採用動態自適應技術，在進化過程中自動調整演算法控制參數和編碼精度，比如使用模糊自適應法 。 進化策略(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是選擇演算法的參數。

E. 進化演算法的起源發展

進化計算包括遺傳演算法(Genetic Algorithms)、遺傳規劃（Genetic Programming）、進化策略(Evolution Strategies)和進化規劃(Evolution Programming)4種典型方法。第一類方法比較成熟，現已廣泛應用，進化策略和進化規劃在科研和實際問題中的應用也越來越廣泛。
遺傳演算法的主要基因操作是選種、交配和突變，而在進化規則、進化策略中，進化機制源於選種和突變。就適應度的角度來說遺傳演算法用於選擇優秀的父代(優秀的父代產生優秀的子代)，而進化規則和進化策略則用於選擇子代(優秀的子代才能存在)。
遺傳演算法與遺傳規劃強調的是父代對子代的遺傳鏈，而進化規則和進化策略則著重於子代本身的行為特性，即行為鏈。
進化規則和進化策略一般都不採用編碼，省去了運作過程中的編碼—解碼手續更適用於連續優化問題，但因此也不能進行非數值優化。進化策略可以確定機制產生出用於繁殖的父代，而遺傳演算法和進化規則強調對個體適應度和概率的依賴。
此外，進化規則把編碼結構抽象為種群之間的相似，而進化策略抽象為個體之間的相似。進化策略和進化規則已應用於連續函數優化、模式識別、機器學習、神經網路訓練、系統辨識和智能控制的眾多領域

F. 進化演算法的差分演算法

差分進化演算法(Differential Evolution, DE)是一種新興的進化計算技術，或稱為差分演化演算法、微分進化演算法、微分演化演算法、差異演化演算法。它是由Storn等人於1995年提出的，最初的設想是用於解決切比雪夫多項式問題，後來發現DE也是解決復雜優化問題的有效技術。DE與人工生命，特別是進化演算法有著極為特殊的聯系。
差分進化演算法是基於群體智能理論的優化演算法，通過群體內個體間的合作與競爭產生的群體智能指導優化搜索。但相比於進化演算法，DE保留了基於種群的全局搜索策略，採用實數編碼基於差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復雜性。同時，DE特有的記憶能力使其可以動態跟蹤當前的搜索情況，以調整其搜索策略，具有較強的全局收斂能力和魯棒性，且不需要藉助問題的特徵信息，適於求解一些利用常規的數學規劃方法所無法求解的復雜環境中的優化問題。
差分進化演算法是一種基於群體進化的演算法，具有記憶個體最優解和種群內信息共享的特點，即通過種群內個體間的合作與競爭來實現對優化問題的求解，其本質是一種基於實數編碼的具有保優思想的貪婪遺傳演算法。
DE是一種用於優化問題的啟發式演算法。本質上說，它是一種基於實數編碼的具有保優思想的貪婪遺傳演算法 。同遺傳演算法一樣，DE包含變異和交叉操作，但同時相較於遺傳演算法的選擇操作，DE採用一對一的淘汰機制來更新種群。由於DE在連續域優化問題的優勢已獲得廣泛應用，並引發進化演算法研究領域的熱潮。
DE由Storn 以及Price提出，演算法的原理採用對個體進行方向擾動，以達到對個體的函數值進行下降的目的，同其他進化演算法一樣，DE不利用目標函數的梯度信息，因此對目標的可導性甚至連續性沒有要求，適用性很強。同時，演算法與粒子群優化有相通之處 ，但因為DE在一定程度上考慮了多變數間的相關性，因此相較於粒子群優化在變數耦合問題上有很大的優勢。演算法的實現參考實現代碼部分。

G. 進化演算法的框架

進化演算法是以達爾文的進化論思想為基礎，通過模擬生物進化過程與機制的求解問題的自組織、自適應的人工智慧技術。生物進化是通過繁殖、變異、競爭和選擇實現的；而進化演算法則主要通過選擇、重組和變異這三種操作實現優化問題的求解。如圖1： 1、t=0
2、初始化群體p(0)
3、評估初始化群體p(0)
4、while終止條件不滿足do
5、 重組操作：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+1
10、end 圖1：進化演算法基本框架
其中r、m、s分別表示重組運算元、變異運算元、選擇運算元。

H. 多目標差分進化演算法

差分進化演算法(Differential Evolution, DE)是一種基於群體差異的啟發式隨機搜索演算法，該演算法是由R.Storn和K.Price為求解Chebyshev多項式而提出的。是一種用於最佳化問題的後設啟發式演算法。本質上說，它是一種基於實數編碼的具有保優思想的貪婪遺傳演算法。

將問題的求解表示成"染色體"的適者生存過程，通過"染色體"群的一代代不斷進化，包括復制、交叉和變異等操作，最終收斂到"最適應環境"的個體，從而求得問題的最優解或滿意解。

差分進化演算法類似遺傳演算法，包含變異，交叉操作，淘汰機制，而差分進化演算法與遺傳演算法不同之處，在於變異的部分是隨選兩個解成員變數的差異，經過伸縮後加入當前解成員的變數上，因此差分進化演算法無須使用概率分布產生下一代解成員。最優化方法分為傳統優化方法和啟發式優化方法兩大類。傳統的優化方法大多數都是利用目標函數的導數求解；而啟發式優化方法以仿生演算法為主，通過啟發式搜索策略實現求解優化。啟發式搜索演算法不要求目標函數連續、可微等信息，具有較好的全局尋優能力，成為最優化領域的研究熱點。

在人工智慧領域中，演化演算法是演化計算的一個分支。它是一種基於群體的元啟發式優化演算法，具有自適應、自搜索、自組織和隱並行性等特點。近年來，很多學者將演化演算法應用到優化領域中，取得了很大的成功，並已引起了人們的廣泛關注。越來越多的研究者加入到演化優化的研究之中，並對演化演算法作了許多改進，使其更適合各種優化問題。目前，演化演算法已廣泛應用於求解無約束函數優化、約束函數優化、組合優化、多目標優化等多種優化問題中。

I. 請問遺傳演算法和進化演算法是什麼關系

對主角的形態進行拆分，用數值表示問題解的最小構成單位即表示基因本身，基因串即表示一個個體。以字元串的形態存儲耳朵顏色，形狀，眼睛顏色形狀，皮膚顏色，花紋以及尾巴顏色，形狀的相關數據，通過多點交叉，然後產生新的子代個體，接下來進行圖像組合，調整每一個部件的相對位置，組合成完整的個體。適應度由玩家交互的次數決定，玩家對自己最喜愛的寵物的關心最多，然後依次遞減，適應度最高的個體有大幾率繁衍下一代且攜帶優秀基因（玩家喜愛度更高），實現進化。

J. 進化演算法的基本步驟

進化計算是基於自然選擇和自然遺傳等生物進化機制的一種搜索演算法。與普通的搜索方法一樣，進化計算也是一種迭代演算法，不同的是進化計算在最優解的搜索過程中，一般是從原問題的一組解出發改進到另一組較好的解，再從這組改進的解出發進一步改進。而且在進化問題中，要求當原問題的優化模型建立後，還必須對原問題的解進行編碼。進化計算在搜索過程中利用結構化和隨機性的信息，使最滿足目標的決策獲得最大的生存可能，是一種概率型的演算法。
一般來說，進化計算的求解包括以下幾個步驟：給定一組初始解；評價當前這組解的性能；從當前這組解中選擇一定數量的解作為迭代後的解的基礎；再對其進行操作，得到迭代後的解；若這些解滿足要求則停止，否則將這些迭代得到的解作為當前解重新操作。
以遺傳演算法為例，其工作步驟可概括為：
（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