進化計算

經過幾億年的發展，在我們的地球上，簡單的細胞逐步演化形成了繽紛多彩的大自然。生物的進化過程，在很長一段時間裡，並不為我們人類所知。從拉馬克的進化學說到達爾文的進化論，再到孟德爾的遺傳學，人類對生命進化現象的研究進入了史無前例的偉大時期。其中，達爾文的進化論是一部對人類影響深遠偉大學說，根據此學說，地球生物在繁殖過程中可能會產生變異，從而形成新物種。由於資源有限，不同的物種之間產生競爭，適者生存，不適者淘汰。自然界中的生物，正是根據這種優勝劣汰的原則，不斷地進化。

運用達爾文理論解決問題的思想起源於20世紀50年代。

20世紀60年代，這一想法在三個地方分別被發展起來。美國的Lawrence J. Fogel提出了進化編程（Evolutionary programming），而來自美國Michigan 大學的John Henry Holland則借鑒了達爾文的生物進化論和孟德爾的遺傳定律的基本思想，並將其進行提取、簡化與抽象提出了遺傳演演算法（Genetic algorithms）。在德國，Ingo Rechenberg 和Hans-Paul Schwefel提出了進化策略（Evolution strategies）。

這些理論大約獨自發展了15年。在80年代之前，並沒有引起人們太大的關注，因為它本身還不夠成熟，而且受到了當時計算機容量小、運算速度慢的限制，並沒有發展出實際的應用成果。

到了20世紀90年代初，遺傳編程（Genetic programming）這一分支也被提出，進化計算作為一個學科開始正式出現。四個分支交流頻繁，取長補短，並融合出了新的進化演演算法，促進了進化計算的巨大發展。

Nils Aall Barricelli在20世紀六十年代開始進行用進化演演算法和人工生命模擬進化的工作。Alex Fraser發表的一系列關於模擬人工選擇的論文大大發展了這一工作。Ingo Rechenberg在上世紀 60 年代和 70 年代初用進化策略來解決複雜的工程問題的工作使人工進化成為廣泛認可的優化方法。特別是John Holland的作品讓遺傳演演算法變得流行起來。隨著學術研究興趣的增長，計算機能力的急劇增加使包括自動演化的計算機程序等實際的應用程序成為現實。比起人類設計的軟體，進化演演算法可以更有效地解決多維的問題，優化系統的設計。

進化演演算法正是借用以上生物進化的規律，通過繁殖、競爭、再繁殖、再競爭，實現優勝劣汰，一步步逼近複雜工程技術問題的最優解。進化計算的主要分支有：遺傳演演算法GA，遺傳編程GP、進化策略ES、進化編程EP。

在進化演演算法中，從一組隨機生成的出事個體出發，仿效生物的遺傳方式，主要採用複製、交換、突變這三種一串操作，衍生出下一代的個體。再根據適應度的大小進行個體的優勝劣汰，提高新一代群體的質量，在經過反覆多次迭代，逐步逼近最優解。從數學角度講，進化演演算法實質上是一種搜索尋優的方法。

進化演演算法是一種基於自然選擇和遺傳變異等生物進化機制的全局性概率搜索演演算法，運用了迭代的方法。

它從選定的初始解出發，通過不斷迭代逐步改進當前解，直至最後搜索到最適合問題的解。在進化計算中，用迭代計算過程模擬生物體的進化機制，從一組解（群體）出發，採用類似於自然選擇和有性繁殖的方式，在繼承原有優良基因的基礎上，生成具有更好性能指標的下一代解的群體：

種群（population）：進化計算在求解問題時是從多個解開始的

代數（generation）：種群進化的代數，即迭代的次數

群體的規模（popsize）：一般地，元素的個數在整個進化過程中是不變的

當前解：新解的父解（parent，或稱為父親、父體等）

後代解（offspring，或稱為兒子、後代等）：產生的新解

編碼：計劃計算常常還需要對問題的解進行編碼，即通過變換將映射到另一空間（稱為基因空間）。通常採用字元串（如位串或向量等）的形式

一個長度為的二進位串稱為一個染色體（個體）。染色體的每一位稱為基因（gene），基因的取值稱為等位基因（allele），基因所在染色體中的位置稱為基因位（1ocus）。

進化計算的搜索策略不是盲目搜索，也不是窮舉搜索，而是以目標函數為指導的搜索方式。進化演演算法一般採用天然的并行結構，且藉助交叉和變異產生新個體，不斷產生新個體，擴大搜索範圍，因此它不易於陷入局部最優點，並能以較大的概率找到全局最優點。

進化計算有著極為廣泛的應用，在模式識別、圖象處理、人工智慧、經濟管理、機械工程、電氣工程、通訊、生物學等眾多領域都獲得了較為成功的應用。如利用進化演演算法研究小生境理論和生物物種的形成，通信網路的優化設計，超大規模集成電路的布線，飛機外形的設計，人類行為規範進化過程的模擬。

現在，進化計算的發展非常迅速，得到了學術界的廣泛認可。

如何對進化計算進行優化以及運用進化計算解決實際問題是當前研究的熱點。並且一些新的演演算法也被提出，如約束優化進化演演算法，群記憶性演演算法（PMA），思維進化計算，互動式進化計算。