遺傳演算法與機器學習

『壹』 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(1)遺傳演算法與機器學習擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。

『貳』 遺傳演算法的現狀

進入90年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高，同時產業應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。遺傳演算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。
隨著應用領域的擴展，遺傳演算法的研究出現了幾個引人注目的新動向：一是基於遺傳演算法的機器學習，這一新的研究課題把遺傳演算法從歷來離散的搜索空間的優化搜索演算法擴展到具有獨特的規則生成功能的嶄新的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是並行處理的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智能計算機體系結構的研究都是十分重要的。四是遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳演算法在這方面將會發揮一定的作用，五是遺傳演算法和進化規劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳演算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。
1991年D.Whitey在他的論文中提出了基於領域交叉的交叉運算元（Adjacency based crossover），這個運算元是特別針對用序號表示基因的個體的交叉，並將其應用到了TSP問題中，通過實驗對其進行了驗證。D.H.Ackley等提出了隨機迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）採用了一種復雜的概率選舉機制，此機制中由m個「投票者」來共同決定新個體的值（m表示群體的大小）。實驗結果表明，SIGH與單點交叉、均勻交叉的神經遺傳演算法相比，所測試的六個函數中有四個表現出更好的性能，而且總體來講，SIGH比現存的許多演算法在求解速度方面更有競爭力。H.Bersini和G.Seront將遺傳演算法與單一方法（simplex method）結合起來，形成了一種叫單一操作的多親交叉運算元（simplex crossover），該運算元在根據兩個母體以及一個額外的個體產生新個體，事實上他的交叉結果與對三個個體用選舉交叉產生的結果一致。同時，文獻還將三者交叉運算元與點交叉、均勻交叉做了比較，結果表明，三者交叉運算元比其餘兩個有更好的性能。
1992年，英國格拉斯哥大學的李耘（Yun Li）指導博士生將基於二進制基因的遺傳演算法擴展到七進制、十進制、整數、浮點等的基因，以便將遺傳演算法更有效地應用於模糊參量，系統結構等的直接優化，於1997年開發了可能是世界上最受歡迎的、也是最早之一的遺傳/進化演算法的網上程序 EA_demo，以幫助新手在線互動式了解進化計算的編碼和工作原理 ，並在格拉斯哥召開第二屆IEE/IEEE遺傳演算法應用國際會議，於2000年組織了由遺傳編程(Genetic Programming)發明人斯坦福的 John Koza 等參加的 EvoNet 研討會，探索融合GA與GP結構尋優，超越固定結構和數值優化的局限性。
國內也有不少的專家和學者對遺傳演算法的交叉運算元進行改進。2002年，戴曉明等應用多種群遺傳並行進化的思想，對不同種群基於不同的遺傳策略，如變異概率，不同的變異運算元等來搜索變數空間，並利用種群間遷移運算元來進行遺傳信息交流，以解決經典遺傳演算法的收斂到局部最優值問題
2004年，趙宏立等針對簡單遺傳演算法在較大規模組合優化問題上搜索效率不高的現象，提出了一種用基因塊編碼的並行遺傳演算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度並行遺傳演算法為基本框架，在染色體群體中識別出可能的基因塊，然後用基因塊作為新的基因單位對染色體重新編碼，產生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
2005年，江雷等針對並行遺傳演算法求解TSP問題，探討了使用彈性策略來維持群體的多樣性，使得演算法跨過局部收斂的障礙，向全局最優解方向進化。

『叄』 為什麼遺傳演算法能被廣泛的應用到各個領域

遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。一、遺傳演算法的特點 1．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，復蓋面大，利於全局擇優。 2．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。 3．遺傳演算法有極強的容錯能力遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳演算法有很高的容錯能力。 4．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。 5．遺傳演算法具有隱含的並行性

『肆』 遺傳演算法的特點

遺傳演算法具有十分頑強的魯棒性^{［56，53］}，這是因為比起普通的優化搜索方法，它採用了許多獨特的方法和技術，歸納起來，主要有以下幾個方面。

遺傳演算法的處理對象不是參數本身，而是對參數集進行了編碼的個體。此編碼操作，使得遺傳演算法可直接對結構對象進行操作。所謂結構對象泛指集合、序列、矩陣、樹、圖、鏈和表等各種一維或二維甚至三維結構形式的對象。這一特點，使得遺傳演算法具有廣泛的應用領域。比如：

①通過對連接矩陣的操作，遺傳演算法可用來對神經網路或自動機的結構或參數加以優化；②通過對集合的操作，遺傳演算法可實現對規則集合或知識庫的精煉而達到高質量的機器學習目的；③通過對樹結構的操作用遺傳演算法可得到用於分類的最佳決策樹；④通過對任務序列的操作，遺傳演算法可用於任務規劃，而通過對操作序列的處理遺傳演算法可自動構造順序控制系統。

如前所述許多傳統搜索方法都是單點搜索演算法，即通過一些變動規則，問題的解從搜索空間中的當前解（點）移到另一解（點）。這種點對點的搜索方法，對於多峰分布的搜索空間常常會陷於局部的某個單峰的優解。相反，遺傳演算法是採用同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進行評估，更形象地說，遺傳演算法是並行地爬多個峰。這一特點使遺傳演算法具有較好的全局搜索性能，減少了陷於局部優解的風險，同時這使遺傳演算法本身也十分易於並行化。

在標準的遺傳演算法中，基本上不用搜索空間的知識或其他輔助信息，無需導數或其他輔助信息，而僅用適應度函數值來評估個體，並在此基礎上進行遺傳操作。需要著重提出的是，遺傳演算法的適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。對適應度函數的惟一要求是，對於輸入可計算出加以比較的正的輸出。遺傳演算法的這一特點使它的應用范圍大大擴展。

圖7-1 基本遺傳演算法的框圖

遺傳演算法不是採用確定性規則，而是採用概率的變遷規則來指導它的搜索方向。在以後的章節中我們將會看到，遺傳演算法採用概率僅僅是作為一種工具來引導其搜索過程朝著搜索空間的更優化的解區域移動。因此雖然看起來它是一種盲目搜索方法，但實際上有明確的搜索方向。

遺傳演算法利用簡單的編碼技術和繁殖機制來表現復雜的現象，從而解決非常困難的問題。特別是由於它不受搜索空間的限制性假設的約束，不必要求諸如連續性、導數存在和單峰等假設，它能從離散的、多極值的、含有噪音的高維問題中以很大的概率找到全局最優解；其次，由於它固有的並行性，遺傳演算法非常適用於大規模並行計算。遺傳演算法目前已經在優化、機器學習和並行處理等領域得到了越來越廣泛的應用。