演化計算是模擬自然界中的生物的演化過程產生的一種群體導向的隨機搜尋技術和方法。
基本介紹
- 中文名：演化計算
- 由來：自然界中的生物的演化過程
- 特點：本質並行性、智慧型型
- 重要性：研究內容十分廣泛
由來,發展現狀,分支,特點,研究領域,相關信息,
由來
達爾文的自然選擇學說構成了現代進化論的主體。生物在延續生存的過程中，逐漸適應其生存環境，使得其品質不斷得到改良，這種現象成為演化。生物演化是以集團的形式進行的，這樣的團體稱為群體，組成群體的單個生物稱為個體，個體間的差別使得他們對環境的適應程度不同。達爾文的自然選擇學說認為，不同個體間的交配以及其他一些原因，生物的基因可能發生變異形成新的基因，這部分變異將遺傳到下一代。這種變異的機率非常之低，使得種群得以保持自己的特徵。但是新的基因依據與環境的適應程度決定其繁殖能力，利於環境的基因逐漸增多，從而產生優良物種。
大自然是人類靈感的源泉。我們知道，自然界解決問題的方法是漫長的自適應過程，這個過程稱之為演化過程，除了演化的最終結果，我們也可以運用這一過程本身去解決問題，將生物界所提供的解決問題的方法套用到求解實際問題已被證明是個成功的方法，並由此產生了仿生學。於是，我們可以不明確的描述出問題的全部特徵，只需要根據自然法則產生新的解，決定是更新還是淘汰。
它遵循自然界中生物進化的優勝劣汰原則。演化計算用簡單的編碼表示各種複雜的結構，通過對編碼進行簡單的遺傳操作和優勝劣汰的競爭機制來對問題的解空間進行搜尋。演化算法不用明確的了解問題的全部特徵，就可以通過體現生物進化機制的演化過程來完成問題的求解。
發展現狀
演化算法在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)自組織、自適應和自學習性(智慧型性)
演化計算在求解問題時,在編碼方案、適應值函式及遺傳運算元確定後,將利用演化過程中獲得的信息進行自行組織搜尋，即演化算法的自組織性。演化計算基於自然的選擇策略:適者生存、不適應者淘汰,適應值大的個體比適值小的個體具有較高的生存機率。根據自然法則，適應值大的個體具有更加適應環境的基因結構,適值大的個體通過雜交等遺傳操作,就可能產生比上一代更適應環境的後代。這就是演化算法的自組織、自適應特徵。
此外，算法本身也可以採用動態自適應技術，在進化過程中自動調整算法控制參數和編碼精度，比如使用模糊自適應法。
自然選擇不需要事先明確描述問題的全部特點, 只需要根據自然法則產生新的解，決定是更新還是淘汰。我們可以利用演化計算的這個特點解決那些結構尚無人能理解的複雜問題。
(2)本質並行性
演化計算的本質並行性表現在內在並行性和內含並行性兩個方面。演化計算的內在並行性(inherent parallelism),即演化算法本身非常適合大規模並行。最簡單的並行方式是讓幾百甚至更多台計算機各自進行獨立種群的演化計算,運行過程中不進行任何通信或者有少量通訊,等到運算結束時比較,選取最佳個體。由於這種並行處理方式對並行系統結構沒有什麼限制和要求,演化計算適合在目前所有的並行機上進行並行處理,而且對並行效率沒有影響很小。演化計算的內含並行性(implicitparallelism)。因為演化計算採用種群的方式組織搜尋,所以算法可同時搜尋解空間內的多個區域,並互相交流信息。
研究領域
演化計算主要的經過長時間的發展，主要出現了以下幾個研究領域：
(1)演化計算的理論研究；
(2)新的計算模型；
(3)演化最佳化；
(4)演化人工神經網路；
(5)並行和分散式演化計算；
(6)演化機器學習；
(7)演化計算套用系統；
(8)演化硬體；
(9)演化軟體；
(10)演化計算內涵的擴充
相關信息
EA_demo，英國格拉斯哥大學1997年出版，至今仍廣泛使用，採用大學包括英國利物浦（Liverpool）大學、蘇塞克斯（Sussex）大學、北安普頓（Northampton）大學，德國烏爾姆（Ulm）大學，瑞士日內瓦（Geneva）大學，西班牙格瑞那達（Granada）大學，葡萄牙新里斯本（Nova de Lisboa）大學，美國加州大學戴維斯分校（UC Davies），加拿大卡爾加里（Calgary）大學，澳大利亞墨爾本皇家理工大學（RMIT），新加坡國立大學，台灣國立清華大學，上海交通大學，巴西PUCRS大學等。
EA_demo允許用戶直接在網頁上一代一代地手動運行，以看遺傳/進化算法是怎樣一步一步操作的，亦可在背景中批次運行，以觀察算法的收斂和染色體是否跳出局部最優。用戶可以改變終止代數，群體規模，交配率，變異率和選擇機制。也有其它自學課件收錄於AI中心網站和歐洲軟計算中心網站。
