演化演算法

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

同遺傳演算法一樣，差異進化演算法包含變異和交叉操作，但同時相較於遺傳演算法的選擇操作，差異進化演算法採用一對一的淘汰機制來更新種群。由於差異進化演算法在連續域優化問題的優勢已獲得廣泛應用，並引發進化演算法研究領域的熱潮。

進化演算法

或稱「演化演算法」 (evolutionary algorithms) 是一個「演算法簇」，盡管它有很多的變化，有不同的遺傳基因表達方式，不同的交叉和變異運算元，特殊運算元的引用，以及不同的再生和選擇方法，但它們產生的靈感都來自於大自然的生物進化。

與傳統的基於微積分的方法和窮舉法等優化演算法相比，進化計算是一種成熟的具有高魯棒性和廣泛適用性的全局優化方法，具有自組織、自適應、自學習的特性，能夠不受問題性質的限制，有效地處理傳統優化演算法難以解決的復雜問題。

⑵ 進化演算法的基本步驟

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

⑶ 進化演算法的差分演算法

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

⑷ 演化計算的分支

自計算機出現以來,生物模擬便成為計算機科學領域的一個組成部分。其目的之一是試圖建立一種人工的模擬環境,在這個環境中使用計算機進行模擬,以便能夠更好地了解人類自己以及人類的生存空間;另一個目的則是從研究生物系統出發,探索產生基本認知行為的微觀機理,然後設計具有生物智能的機器或模擬系統,來解決復雜問題。如,神經網路、細胞自動機和演化計算都是從不同角度對生物系統進行模擬而發展起來的研究方向。演化計算最初具有三大分支:遺傳演算法(GeneticAlgorithm，GA)、演化規劃(EvolutionaryProgramming、EP)和演化策略(EvolutionStrategy，ES)。上世紀90年代初,在遺傳演算法的基礎上又形成了一個新的分支:遺傳程序設計(GeneticProgramming，GP)。雖然這幾個分支在演算法實現上有一些細微差別,但是它們都有一個共同的特點,即都是藉助生物演化的思想及原理來解決實際問題的。
(1）遺傳演算法
上世紀50年代末人們嘗試把計算機科學與進化論結合起來，但由於缺乏一種通用的編碼方案，人們只能依賴變異而非交配來產生新的基因結構，加上當時只有少數計算機可以滿足運算速度的要求，故而收效甚微。到60年代中期,美國Michigan大學的JohnHolland在A.S.Fraser和H.J.Bremermann等人工作的基礎上提出了位串編碼技術。這種編碼技術不但適於變異操作。而已同樣適於交配(即雜交)操作。並且強調將交配作為主要的遺傳操作。遺傳演算法的通用編碼技術和簡單有效的遺傳操作意義重大，並為其廣泛、成功的應用奠定了堅實的基礎。Holland遺傳演算法被稱為簡單遺傳演算法(SGA)。其操作對象是一群二進制串(稱為染色體、個體)。在解決實際問題中，每個染色體都對應問題的一個可行解。從初始種群出發，使用雜交和變異來產生下一代種群。如此一代代進行演化。直到達到設定好的終止條件。需要指出的是：目前的遺傳演算法已不再僅僅局限於二進制編碼。
(2) 演化策略
上世紀60年代初，柏林工業大學的學生I.Rechenberg和H.P.Schwefel在進行風洞實驗時，由於用傳統的方法難以對設計中描述物體形狀的參數進行優化。因而利用生物遺傳和變異的思想來改變參數值，並獲得了較好的效果。隨後，他們對這種方法進行了深入的研究和探索。形成了演化計算的另一個重要分支——演化策略。
(3)演化規劃
演化規劃的方法最初是由L.J.Fogel等提出在上世紀60年代。他們在研究人工智慧的時候發現，智能行為就是具有感應其所處環境的狀態、並按給定目標自動做出適當響應的能力。在研究中，他們將模擬環境描述成由有限字元集中的符號組成的序列。於是問題就被轉化為，如何根據當前觀察到的符號序列做出響應，以獲得最大收益。這里，收益主要由環境中將要出現的下一個符號及預先定義好的效益目標來確定。他們將此方法應用到數據診斷、模式識別和分類及控制系統的設計等問題中，取得了較好的結果。
(4)遺傳程序設計
自計算機出現以來，計算機科學的一個方向性目標就是讓計算機自主進行程序設計，即只要告訴計算機要解決的問題，而不需要告訴它具體如何去做。遺傳程序設計便是在該領域的一種嘗試。它採用演化演算法中遺傳演算法的基本思想，但使用一種更為靈活的表示方式——使用分層結構來表示解空間。這些分層結構有葉節點和中間節點，葉結點是所需解決問題的原始變數，中間結點則是組合這些原始變數的函數。這樣，每個分層結構對應問題的一個可行解。遺傳程序設計就是使用一些遺傳操作動態地改變這些結構，以獲得解決該問題的可行的計算機程序。遺傳程序設計的思想是Stanford大學的J.R.Koza在上世紀90年代初提出的。

⑸ 什麼是演化演算法

演化演算法是解決組合優化問題的高效搜索演算法.該文在現有求解TSP問題的演化演算法的基礎上,通過引入映射運算元、優化運算元以及增加一些控制策略,提出了一種高效的演化搜索演算法.實驗表明,該演算法是有效的,通過對CHN144以及國際通用的TSPLIB中不同城市規模的數據進行測試表明,其中實例CHN144得到的最短路徑為30353.860997,優於吳斌等運用分段演算法得到的最短路徑30354.3,亦優於朱文興等人的結果,實例st70和kroB150得到的最短路徑分別與運用分段演算法得到的最短路徑值相同,實例pr136得到的最短路徑值為96770.924122,優於TSPLIB中提供的最短路徑96772,對於其它實例也均能快速地得到和TSPLIB中提供的最優路徑相同或更優的路徑,該演算法不僅很容易收斂到問題的最優解,而且求解速度極快.

⑹ 演化演算法能解決什麼問題大家多說幾種題目，有20分獎勵！！

. 研究如何利用計算技術研究生物現象
2. 研究如何利用生物技術研究計算問題

⑺ 如何證明演化演算法得到的解是近似最優解

1,用你的演化演算法作一個benchmark，如果達到近似最優解，說明你的演化演算法比較好。
2，演算法沒有缺點時，進行足夠的時間計算，可以作為近似最優解。
3，鬆弛約束後，根據差可以基本判斷是否最優解

⑻ Evolutionary Algorithms，Genetic Algorithm 進化演算法和遺傳演算法二者有啥區別

Evolutionary Algorithms：進化演算法；
Genetic Algorithm：遺傳演算法；
進化演算法包括遺傳演算法、進化程序設計、進化規劃和進化策略。
基於對生物進化機制的模仿，共產生進化演算法的四種典型模型：
①遺傳演算法 Genetic Algorithm,GA
②進化規劃 Evolutionary Programming,EP
③遺傳規劃 Genetic Programming,GP
④進化策略 Evolution Strategy, ES
雖然這些概念的內涵有一定的差別，它們有各自不同的側重點，各自有不同的生物進化背景，各自強調了生物進化過程中的不同特性，但本質上都基於進化思想的，都能產生魯棒性較強的計算機演算法，適應面較廣，因此又稱它們為進化演算法或進化計算。

⑼ 高分尋達人分別介紹下遺傳演算法和演化演算法，以及之間的聯系和區別

根據閱讀的資料，大概有以下判斷：
遺傳演算法是演化演算法中的一種。

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。

遺傳演算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源於生物遺傳學和適者生存的自然規律，是具有「生存＋檢測」的迭代過程的搜索演算法。遺傳演算法以一種群體中的所有個體為對象，並利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳演算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳演算法的核心內容。 作為一種新的全局優化搜索演算法，遺傳演算法以其簡單通用、魯棒性強、適於並行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，並逐漸成為重要的智能演算法之一。

遺傳演算法是基於生物學的，理解或編程都不太難。下面是遺傳演算法的一般演算法：
創建一個隨機的初始狀態

初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智慧系統的情況不一樣，在那裡問題的初始狀態已經給定了。

評估適應度

對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。不要把這些「解」與問題的「答案」混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。

繁殖(包括子代突變)

帶有較高適應度值的那些染色體更可能產生後代(後代產生後也將發生突變)。後代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為「雜交」。

下一代

如果新的一代包含一個解，能產生一個充分接近或等於期望答案的輸出，那麼問題就已經解決了。如果情況並非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。

並行計算

非常容易將遺傳演算法用到並行計算和群集環境中。一種方法是直接把每個節點當成一個並行的種群看待。然後有機體根據不同的繁殖方法從一個節點遷移到另一個節點。另一種方法是「農場主/勞工」體系結構，指定一個節點為「農場主」節點，負責選擇有機體和分派適應度的值，另外的節點作為「勞工」節點，負責重新組合、變異和適應度函數的評估。
http://ke..com/view/45853.html

演化演算法：
這部分的研究主要是提供具有演化特徵的演算法，已知的遺傳演算法是其中之一。許多新的演算法正在研究中。由於遺傳演算法的整體搜索策略和優化計算時不依賴於梯度信息，所以它的應用非常廣泛，尤其適合於處理傳統搜索方法難以解決的高度復雜的非線性問題。人工生命研究的重要內容就是進化現象，遺傳演算法是研究進化現象的重要方法之一
我國學者接觸這個領域較晚，目前尚未形成聲勢和有規模的研究隊伍。1997年夏天，在中科院基礎局、國家科委基礎司及中國國際經濟及技術交流中心的支持下，由中科院系統科學所和自動化研究所舉辦了第一次人工生命及進化機器人研討會[20]。與會者約60人。除去邀請了五位國際知名學者的學術報告之外，國內也有數名學者介紹了相關的研究成果。主要在數字生命、復雜巨系統方面進行了一些研究。據目前了解到的情況，國內尚有一些人在研究演化演算法，在人工智慧的一本書上有一段介紹人工生命。但對人工社會、人工生態環境及進化機器人等尚無人問津。
http://blog.ustc.e.cn/chujx/archives/000925.html