演化計算

達爾文的自然選擇學説構成了現代進化論的主體。生物在延續生存的過程中，逐漸適應其生存環境，使得其品質不斷得到改良，這種現象成為演化。生物演化是以集團的形式進行的，這樣的團體稱為羣體，組成羣體的單個生物稱為個體，個體間的差別使得他們對環境的適應程度不同。達爾文的自然選擇學説認為，不同個體間的交配以及其他一些原因，生物的基因可能發生變異形成新的基因，這部分變異將遺傳到下一代。這種變異的概率非常之低，使得種羣得以保持自己的特徵。但是新的基因依據與環境的適應程度決定其繁殖能力，利於環境的基因逐漸增多，從而產生優良物種。

大自然是人類靈感的源泉。我們知道，自然界解決問題的方法是漫長的自適應過程，這個過程稱之為演化過程，除了演化的最終結果，我們也可以運用這一過程本身去解決問題，將生物界所提供的解決問題的方法應用到求解實際問題已被證明是個成功的方法，並由此產生了仿生學。於是，我們可以不明確的描述出問題的全部特徵，只需要根據自然法則產生新的解，決定是更新還是淘汰。

它遵循自然界中生物進化的優勝劣汰原則。演化計算用簡單的編碼表示各種複雜的結構，通過對編碼進行簡單的遺傳操作和優勝劣汰的競爭機制來對問題的解空間進行搜索。演化算法不用明確的瞭解問題的全部特徵，就可以通過體現生物進化機制的演化過程來完成問題的求解。

演化算法在20世紀60年代被提出時並未受到普遍重視，主要原因有三點，一是這些方法當時並不成熟；二是這些方法運行需要較大的計算量，當時計算機速度跟不上要求；三是當時解決類似難題人工智能方法可以得出很好的結果，人們難以過多的關注其他算法。

傳統人工智能解決問題的侷限性在20世紀80年代初被凸顯出來，當時計算機速度已經明顯提高並且普及，制約演化計算的一大瓶頸已經不復存在。演化計算在機器學習，工程優化，過程控制等領域取得極大地成功，這引起了包括數學，物理學在內的各個學科及工程應用領域專家的興趣。

某些學者研究了演化計算的靈現行為(Emergent Behavior)後聲稱,演化計算與混沌理論、分形幾何將成為人們研究非線性現象和複雜系統的新的三大方法,並將與神經網絡一起成為人們研究認知過程的重要工具。

自20世紀80年代中期以來，世界上許多國家都掀起了演化計算的研究熱潮。目前，以演化計算為主題的國際會議在世界各地定期召開，如IEEE。隨着演化計算的廣泛應用，一些雜誌都設置專欄介紹這方面的文章，現在還出版了兩種關於演化計算的影響力較大的新雜誌《Evolutionary Computation》和《IEEE Transactionson Evolutionary Computation》。

演化計算是一種通用的問題求解方法,具有自組織、自適應、自學習性和本質並行性等特點,不受搜索空間限制性條件的約束,也不需要其它輔助信息。因此,演化算法簡單、通用、易操作、能獲得較高的效率,越來越受到人們的青睞。演化計算在大型優化問題求解、機器學習、自適應控制、人工生命、神經網絡、經濟預測等領域取得的成功，引起了包括數學、物理學、化學、生物學、計算機科學、社會科學、經濟學及工程應用等領域科學們的極大興趣。

現在，演化計算的研究內容十分廣泛，例如演化計算的設計與分析、演化計算的理論基礎以及在各個領域中的應用等。隨着演化計算的理論研究的不斷深入和應用領域的不斷擴展，演化計算將會取得很大的成功，必將在當今社會佔據更重要的位置。

自計算機出現以來,生物模擬便成為計算機科學領域的一個組成部分。其目的之一是試圖建立一種人工的模擬環境,在這個環境中使用計算機進行仿真,以便能夠更好地瞭解人類自己以及人類的生存空間;另一個目的則是從研究生物系統出發,探索產生基本認知行為的微觀機理,然後設計具有生物智能的機器或模擬系統,來解決複雜問題。如,神經網絡、細胞自動機和演化計算都是從不同角度對生物系統進行模擬而發展起來的研究方向。演化計算最初具有三大分支:遺傳算法(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年代初提出的。

演化計算最主要的特點體現在以下兩個方面:

(1)自組織、自適應和自學習性(智能性)

演化計算在求解問題時,在編碼方案、適應值函數及遺傳算子確定後,將利用演化過程中獲得的信息進行自行組織搜索，即演化算法的自組織性。演化計算基於自然的選擇策略:適者生存、不適應者淘汰,適應值大的個體比適值小的個體具有較高的生存概率。根據自然法則，適應值大的個體具有更加適應環境的基因結構,適值大的個體通過雜交等遺傳操作,就可能產生比上一代更適應環境的後代。這就是演化算法的自組織、自適應特徵。

此外，算法本身也可以採用動態自適應技術，在進化過程中自動調整算法控制參數和編碼精度，比如使用模糊自適應法 ^[1]  。

自然選擇不需要事先明確描述問題的全部特點, 只需要根據自然法則產生新的解，決定是更新還是淘汰。我們可以利用演化計算的這個特點解決那些結構尚無人能理解的複雜問題。

(2)本質並行性

演化計算的本質並行性表現在內在並行性和內含並行性兩個方面。演化計算的內在並行性(inherent parallelism),即演化算法本身非常適合大規模並行。最簡單的並行方式是讓幾百甚至更多台計算機各自進行獨立種羣的演化計算,運行過程中不進行任何通信或者有少量通訊,等到運算結束時比較,選取最佳個體。由於這種並行處理方式對並行系統結構沒有什麼限制和要求,演化計算適合在目前所有的並行機上進行並行處理,而且對並行效率沒有影響很小。演化計算的內含並行性(implicitparallelism)。因為演化計算採用種羣的方式組織搜索,所以算法可同時搜索解空間內的多個區域,並互相交流信息。

演化計算主要的經過長時間的發展，主要出現了以下幾個研究領域：

(1)演化計算的理論研究；

(2)新的計算模型；

(3)演化優化；

(4)演化人工神經網絡；

(5)並行和分佈式演化計算；

(6)演化機器學習；

(7)演化計算應用系統；

(8)演化硬件；

(9)演化軟件；

(10)演化計算內涵的擴充

EA_demo，英國格拉斯哥大學1997年出版 ^[2]  ，至今仍廣泛使用，採用大學包括英國利物浦（Liverpool）大學、蘇塞克斯（Sussex）大學、北安普頓（Northampton）大學，德國烏爾姆（Ulm）大學，瑞士日內瓦（Geneva）大學，西班牙格林納達（Granada）大學，葡萄牙新里斯本（Nova de Lisboa）大學，美國加州大學戴維斯分校（UC Davies），加拿大卡爾加里（Calgary）大學，澳大利亞墨爾本皇家理工大學（RMIT），新加坡國立大學，台灣清華大學，上海交通大學，巴西PUCRS大學等。

EA_demo允許用户直接在網頁上一代一代地手動運行，以看遺傳/進化算法是怎樣一步一步操作的，亦可在背景中批次運行，以觀察算法的收斂和染色體是否跳出局部最優。用户可以改變終止代數，羣體規模，交配率，變異率和選擇機制。但隨着web技術發展和手機瀏覽器的發展，2015-2017年多數瀏覽器客户端已經不支持java插件。不過對於學習者來説，幸運的是，2019年IE瀏覽器仍支持java插件，故對於EA_demo可以通過網站提示，快速體驗該應用。另，其上級頁面有很多自學資料，對於初學者來説，可以從中得到很大的收益。