《常用演算法之智慧計算 (四) 》：遺傳演算法
遺傳演算法(Genetic Algorithms) ， 也有人把它叫作 進化演算法(Evolutionary Algorithms) ，是基於 ofollow,noindex" target="_blank">生物進化的“物競天擇，適者生存”理論 發展起來的一種應用廣泛且高效隨機搜尋與優化並舉的智慧演算法，其主要特點是群體 搜尋策略 和群體中 個體 之間的 資訊交換 ，不依賴於問題的梯度資訊。遺傳演算法最初被研究的出發點不是為專門解決最優化問題而設計的，它與 進化策略 、進化規劃共同構成了 遺傳演算法 的主要 框架 ，都是為當時 人工智慧 的發展服務的。迄今為止，遺傳演算法是智慧計算中最廣為人知的一種演算法。
遺傳演算法就是模擬自然界進化論的基本思想，可以很好地用於優化問題，若把它看作對自然過程高度理想化的模擬，更能顯出它本身的優雅與應用的重要。該演算法以一個群體中的所有個體為物件，並利用隨機化技術指導對一個被編碼的引數空間進行高效搜尋。其中，選擇、雜交和變異構成了遺傳演算法的遺傳操作；引數編碼、初始群體的設定、適應度函式的設計、遺傳操作設計、控制引數設定五要素組成了遺傳演算法的核心內容。作為一種新的全域性優化搜尋演算法，遺傳演算法以其簡單通用、健壯性強、適於並行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，並逐漸成為重要的智慧演算法之一。
近幾年來，遺傳演算法主要在複雜優化 問題求解 和 工業工程 領域 應用等方面，取得了一些令人信服的結果，所以引起更 多人 的關注。
要想進一步的瞭解遺傳演算法，當然要先了解遺傳、進化及其有關的一些概念和知識，下面就對其進行一些簡單介紹。作為遺傳演算法生物背景的介紹，瞭解下面的一些概念及內容也就夠了。
個體：組成種群的單個生物；
種群：生物進化以群體的形式進行，這樣的一個群體稱為種群；
基因：DNA長鏈結構中佔有一定位置的基本遺傳單位，也叫遺傳因子；
基因DNA、RNA片段(摘自網際網路)
染色體：是生物細胞中含有的一種微小的絲狀物，是遺傳物質的主要載體，由多個遺傳基因組成；
遺傳：新個體會遺傳父母雙方各自一部分的基因，承現出親子之間以及 子代 個體之間性狀相似性，表明性狀可以從親代傳遞給子代；
變異：親代和子代之間、子代和子代的不同個體之間總會存在一些差異，這種現象稱為變異；變異是隨機發生的，變異的選擇和積累是生命多樣性的根源；
進化：生物在其延續生命的過程中，逐漸適應其生存環境使得其品質不斷得到改良，這種生命現象稱為進化；生物的進化是以種群的形式進行的；
生存競爭，適者生存：生物的繁殖過程，會發生基因交叉、基因突變，適應度低的個體會被逐步淘汰，而適應度高的個體會越來越多；這樣經過多代的自然選擇後，儲存下來的都是適應度很高的個體，其中很可能包含史上產生的適應度最高的那些個體。
遺傳演算法是解決搜尋問題的一種通用演算法，各種各樣、型別不同的問題都可以使用。 遺傳演算法 的共同特徵有： ① 首先組成一組候選解； ② 依據某些適應性條件測算這些候選解的適應度； ③ 根據適應度保留某些優良候選解，放棄其中欠佳的部分候選解； ④ 對保留的候選解進行某些操作，生成新的候選解。在遺傳演算法中，上述幾個特徵以一種特殊的方式組合 在一起 ，如基於 染色體 群的並行搜尋，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳演算法與其它搜尋演算法 區別 開來。
除上述共同特徵外，遺傳演算法還具有以下幾方面的特點：
(1) 遺傳演算法從問題解的串集中開始搜尋，而不是從單個解開始，這是遺傳演算法與 傳統 優化演算法的最大區別。傳統優化演算法是從單個初始值迭代求最優解，容易誤入區域性最優解。遺傳演算法從串集開始搜尋，覆蓋面大，利於全域性擇優。
(2) 許多傳統搜尋演算法都是 單點 搜尋演算法，容易陷入區域性的最優解。遺傳演算法同時處理群體中的多個個體，即對搜尋 空間 中的多個解進行評估，減少了陷入區域性最優解的風險，同時演算法本身易於實現並行化。
(3) 遺傳演算法 基本上 不用搜索空間的知識或其它 輔助資訊 ，而僅用 適應度函式 值來評估個體，在此基礎上進行遺傳操作。適應度函式不僅不受連續、可微等的約束，而且其定義域可以任意設定。這一特點使得遺傳演算法的 應用範圍 得到很大擴充套件。
(4) 遺傳演算法不是採用 確定性規則 ，而是採用概率的變遷規則來指導它的搜尋方向。
(5) 具有 自組織 、自適應和自學習等特性。遺傳演算法利用進化過程獲得的資訊自行組織搜尋時，硬度大的個體具有較高的生存概率，並獲得更適應環境的 基因結構 。
遺傳演算法以一個群體中的所有個體為物件，利用隨機化技術對編碼引數空間進行高效搜尋，把選擇、雜交和變異等遺傳現象構成遺傳操作。作為一種全域性優化搜尋演算法，遺傳演算法不考慮函式本身是否連續、是否可微等性質，以其簡單通用、健壯性強和高效、實用、隱含並行性、容易找到“全域性最優解”等顯著特點，在許多領域得到成功應用，成為一種重要的智慧演算法。
上面的描述是簡單的遺傳演算法模型，可由此給出下面的遺傳演算法流程圖，再加延伸，可以在這一基本型上進行改進和發展，形成諸多不同類別的遺傳演算法，使其在 科學 和工程領域得到更廣泛的應用。
遺傳演算法流程圖
上面遺傳演算法流程圖中有六個重要的環節：
（1）編碼和初始群體的生成：遺傳演算法在進行搜尋之前先將解空間的解資料表示成遺傳空間的基因型串結構資料，這些串結構資料的不同組合便構成了不同的點。然後隨機產生N個初始串結構資料，每個串結構資料稱為一個個體， N個體構成了一個群體。遺傳演算法以這N個串結構資料作為初始點開始迭代。當然，初始群體應該選取適當，如果選取的過小則雜交優勢不明顯，演算法效能很差，群體選取太大則計算量會過大。
（2）檢查演算法收斂準則是否滿足，控制演算法是否結束，也可以採用判斷與最優解的適配度或者選定一個迭代次數來結束計算。
（3）適應度評估選擇和檢測：適應性函式表明個體或解的優劣性，在程式的開始也應該評價適應性，以便和以後的做比較。不同的問題，適應性函式的定義方式也不同。根據適應性的好壞，進行選擇。選擇的目的是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳演算法通過選擇過程體現這一思想，進行選擇的原則是適應性強的個體為下一代貢獻一個或多個後代的概率大。選擇實現了達爾文的適者生存原則。
（4） 選擇 :將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的 適應度 評估基礎上的。
（5）雜交：按照雜交概率進行雜交。雜交操作是遺傳演算法中最主要的遺傳操作。通過雜交操作可以得到新一代個體，新個體組合了其父輩個體的特性。雜交體現了資訊交換的思想。
可以選定一個點對染色體串進行互換，插入，逆序等雜交，也可以隨機選取幾個點雜交。雜交概率如果太大，種群更新快，但是高適應性的個體很容易被淹沒，概率小了搜尋會停滯。
（6）變異：按照變異概率進行變異。變異首先在群體中隨機選擇一個個體，對於選中的個體以一定的概率隨機地改變串結構資料中某個串的值。同生物界一樣，遺傳演算法中變異發生的概率很低，但為新個體的產生提供了機會。
變異可以防止有效基因的缺損造成的進化停滯。比較低的變異概率就已經可以讓基因不斷變更，太大了會陷入隨機搜尋。不難想象一下，生物界每一代都和上一代差距很大，會出現是怎樣一種可怕的情形。
就像自然界的變異適和任何物種一樣，對變數進行了編碼的遺傳演算法沒有考慮函式本身是否可導，是否連續等性質，所以適用性很強；並且，它開始就對一個種群進行操作，隱含了並行性，也容易找到“全域性最優解”。
由上面遺傳演算法流程圖不難看出，遺傳演算法提供了一種求解複雜系統優化問題的通用框架，計算時不依賴於梯度資訊或其它輔助知識，而只需要影響搜尋方向的目標函式和相應的適應度函式，不依賴於問題的具體領域，對問題的種類有很強的穩健性，可廣泛應用於很多學科。下面是遺傳演算法的一些主要應用領域。
（1）函式優化：函式優化是遺傳演算法的經典應用領域，也是對遺傳演算法進行效能評價的常用算例，特別是對於一些非線性、多模型、多目標的函式優化問題，用其他優化方法較難求解，而遺傳演算法卻可以方便地得到較好的結果；（2）組合優化：隨著問題規模的增大，組合優化問題的搜尋空間也急劇擴大，實踐證明，遺傳演算法已經在求解旅行商問題、揹包問題、裝箱問題、佈局優化、圖形劃分問題等各種具有NP難度的問題中得到成功的應用；（3）生產排程問題：車間排程問題是一個典型的NP問題,從最初的傳統車間排程問題到柔性作業車間排程問題，遺傳演算法都有優異的結果顯示，在很多算例中都得到了最優解或近優解；（4）自動控制；（5） 機器人學；（6） 影象處理；（7）人工生命；（8）遺傳程式設計；（9）機器學習；（10）資料探勘等。
隨著應用領域的擴充套件，遺傳演算法的研究出現了幾個引人注目的新動向：（1）基於遺傳演算法機器學習，這一新的研究課題把遺傳演算法從歷來離散的搜尋空間的優化搜尋演算法擴充套件到具有獨特的規則生成功能的機器學習演算法。這一新的學習機制對於解決人工智慧中知識獲取和知識優化精煉的瓶頸難題帶來了希望。（2）遺傳演算法正日益和神經網路、模糊推理以及混沌理論等其它智慧計算方法相互滲透和結合，這對開拓21世紀中新的智慧計算技術將具有重要的意義。（3） 並行處理 的遺傳演算法的研究十分活躍。這一研究不僅對遺傳演算法本身的發展，而且對於新一代智慧 計算機體系結構 的研究都是十分重要的。（4）遺傳演算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用 計算機模擬 自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究物件，而遺傳演算法在這方面將會發揮一定的作用，（5）遺傳演算法和進化規劃以及 進化策略 等進化 計算理論 日益結合。它們幾乎是和遺傳演算法同時獨立發展起來的，同遺傳演算法一樣，它們也是模擬自然界生物進化機制的 智慧算 法，即同遺傳演算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。
進入二十一世紀，遺傳演算法迎來了興盛發展時期，無論是數學理論研究、計算機硬體研發還是應用研究都成了十分熱門的課題，尤其是遺傳演算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳演算法進行優化和規則學習的能力也顯著提高。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳演算法增添了新的活力。遺傳演算法的應用研究已從初期的組合優化求解擴充套件到了許多更新、更工程化的應用方面，同樣也會取得更多新的突破，使得遺傳演算法的研究更上一層樓。