遺傳算法
      目錄·遺傳算法定義
      ·遺傳算法特點
      ·遺傳算法的應用
      ·遺傳算法的現狀
      ·遺傳算法的一般算法
      ·遺傳算法實例



      遺傳算法定義

      遺傳算法（Genetic 
      Algorithm）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它是有美國Michigan大學J.Holland教授于1975年首先提出來的，并出版了頗有影響的專著《Adaptation 
      in Natural and Artificial 
      Systems》，GA這個名稱才逐漸為人所知，J.Hilland教授所提出的GA通常為簡單遺傳算法（SGA）。
      遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小挑選（selection）個體，并借助于自然遺傳學的遺傳算子（genetic 
      operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

      遺傳算法特點
      遺傳算法是一類可用于復雜系統優化的具有魯棒性的搜索算法，與傳統的優化算法相比，主要有以下特點：
      1、 
      遺傳算法以決策變量的編碼作為運算對象。傳統的優化算法往往直接決策變量的實際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便的應用遺傳操作算子。
      2、 遺傳算法直接以適應度作為搜索信息，無需導數等其它輔助信息。
      3、 遺傳算法使用多個點的搜索信息，具有隱含并行性。
      4、 遺傳算法使用概率搜索技術，而非確定性規則。



      遺傳算法的應用
      由于遺傳算法的整體搜索策略和優化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳算法提供了一種求解復雜系統問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于許多科學，下面我們將介紹遺傳算法的一些主要應用領域：
      1、 函數優化。
      函數優化是遺傳算法的經典應用領域，也是遺傳算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對于一些非線性、多模型、多目標的函數優化問題，用其它優化方法較難求解，而遺傳算法可以方便的得到較好的結果。
      2、 組合優化
      隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于組合優化中的NP問題非常有效。例如遺傳算法已經在求解旅行商問題、 
      背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。
      此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。


      遺傳算法的現狀
      進入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），該算子在根據兩個母體以及一個額外的個體產生新個體，事實上他的交叉結果與對三個個體用選舉交叉產生的結果一致。同時，文獻還將三者交叉算子與點交叉、均勻交叉做了比較，結果表明，三這交叉算子比其余兩個有更好的性能。
      國內也有不少的專家和學者對遺傳算法的交叉算子進行改進。2002年，戴曉明等應用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經典遺傳算法的收斂到局部最優值問題
      2004年，趙宏立等針對簡單遺傳算法在較大規模組合優化問題上搜索效率不高的現象，提出了一種用基因塊編碼的并行遺傳算法（Building-block 
      Coded Parallel 
      GA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。
      2005年，江雷等針對并行遺傳算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優解方向進化。


      遺傳算法的一般算法
      遺傳算法是基于生物學的，理解或編程都不太難。下面是遺傳算法的一般算法：