遺傳演算法的基本概念
遺傳演算法的基本概念
遺傳演算法(genetic algorithm, GA)是模擬自然界生物進化機制的一種演算法，遵循適者生存、優勝劣汰的法則。
遺傳演算法的作用對象是種群(Population)，種群中的每個個體是問題的一個解，叫做染色體(Chromosome)。染色體按照一定的編碼（比如二進位編碼）來表示一個解。染色體中的元素叫做基因(Gene)。遺傳演算法對種群施加選擇(Selection)、交叉(Crossover)和變異(Mutation)等操作，使個體和種群的適應度(Fitness)不斷改進，從而達到趨向最優的目的。
遺傳演算法過程圖如下圖。
常見的編碼策略有二進位編碼、格雷編碼、實數編碼、符號編碼等。編碼通常需遵循三個原則：完備性、健全性和非冗餘性。
選擇運算元的任務就是從父代中選出一部分個體遺傳到下一代。選擇操作建立在種群個體的適應度評估基礎上，常見的選擇方法有輪盤賭演算法、適應度比例方法、隨機遍歷抽樣法和局部選擇法。
交叉運算元的作用是生物遺傳基因的重組。常用的交叉方法有實值重組和二進位交叉。
變異運算元的任務是對群體中的染色體的某些基因做變動。變異操作的主要目的有兩個：一是使遺傳演算法具有局部的隨機搜索能力，這種情況下變異概率應該取較小值；二是使遺傳演算法維持群體多樣性，以避免早熟的現象，這種情況下變異概率應該取較大值。
遺傳演算法的特點是：
- 從串級開始搜索，對空間中多個解進行評估，覆蓋面大，利於尋找全局最優。
- 基本上不用搜索空間的知識和其他輔助信息，僅用適應度值評估個體，適應度函數不受連續可微的約束，定義域可以任意設定。
- 採用概率的變遷確定搜索方向。 具有自組織、自適應和自學習性。
推薦閱讀：
