資料庫必知詞彙：遺傳算法

遺傳算法（Genetic Algorithm, GA）是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模拟自然進化過程搜尋最優解的方法。遺傳算法是一種基于“适者生存”的高度并行、随機和自适應的優化算法,通過複制、交叉、變異将問題解編碼表示的“染色體”群一代代不斷進化,最終收斂到最适應的群體,進而求得問題的最優解或滿意解。

它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有内在的隐并行性和更好的全局尋優能力；采用機率化的尋優方法，能自動擷取和指導優化的搜尋空間，自适應地調整搜尋方向，不需要确定的規則。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信号處理、自适應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。

遺傳算法也是計算機科學人工智能領域中用于解決最優化的一種搜尋啟發式算法，是進化算法的一種。這種啟發式通常用來生成有用的解決方案來優化和搜尋問題。進化算法最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。遺傳算法在适應度函數選擇不當的情況下有可能收斂于局部最優，而不能達到全局最優。

遺傳算法以一種群體中的所有個體為對象，并利用随機化技術指導對一個被編碼的參數空間進行高效搜尋。其中，選擇、交叉和變異構成了遺傳算法的遺傳操作；參數編碼、初始群體的設定、适應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心内容。

遺傳算法的基本運算過程如下：

(1) 初始化：設定進化代數計數器t=0，設定最大進化代數T，随機生成M個個體作為初始群體P(0)。

(2) 個體評價：計算群體P(t)中各個個體的适應度。

(3) 選擇運算：将選擇算子作用于群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉産生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的适應度評估基礎上的。

(4) 交叉運算：将交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。

(5) 變異運算：将變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。

(6) 終止條件判斷：若t=T,則以進化過程中所得到的具有最大适應度個體作為最優解輸出，終止計算。

資料來源：

【算法】1. 超詳細的遺傳算法(Genetic Algorithm)解析

https://www.jianshu.com/p/ae5157c26af9

1. 人工智能之遺傳算法(GA) http://mp.ofweek.com/ai/a745673720186
2. 陳國良, 王熙法, 莊鎮泉, et al. 遺傳算法及其應用[M]. 人民郵電出版社, 1999.