遺傳算法（Genetic Algorithm，GA）

是模擬生物在自然環(huán)境中的遺傳和進化的過程而形成的自適應(yīng)全局優(yōu)化搜索算法。它借用了生物遺傳學(xué)的觀點，通過自然選擇、遺傳和變異等作用機制，實現(xiàn)各個個體適應(yīng)性的提高。

基因型 (Genotype)

在自然界中，通過基因型表征繁殖，繁殖和突變，基因型是組成染色體的一組基因的集合。

在遺傳算法中，每個個體都由代表基因集合的染色體構(gòu)成。例如，一條染色體可以表示為二進制串，其中每個位代表一個基因：

種群 (Population)

遺傳算法保持大量的個體 (individuals) —— 針對當(dāng)前問題的候選解集合。由于每個個體都由染色體表示，因此這些種族的個體 (individuals) 可以看作是染色體集合：

適應(yīng)度函數(shù) (Fitness function)

在算法的每次迭代中，使用適應(yīng)度函數(shù)(也稱為目標(biāo)函數(shù))對個體進行評估。目標(biāo)函數(shù)是用于優(yōu)化的函數(shù)或試圖解決的問題。

適應(yīng)度得分更高的個體代表了更好的解，其更有可能被選擇繁殖并且其性狀會在下一代中得到表現(xiàn)。隨著遺傳算法的進行，解的質(zhì)量會提高，適應(yīng)度會增加，一旦找到具有令人滿意的適應(yīng)度值的解，終止遺傳算法。

選擇 (Selection)

在計算出種群中每個個體的適應(yīng)度后，使用選擇過程來確定種群中的哪個個體將用于繁殖并產(chǎn)生下一代，具有較高值的個體更有可能被選中，并將其遺傳物質(zhì)傳遞給下一代。

仍然有機會選擇低適應(yīng)度值的個體，但概率較低。這樣，就不會完全摒棄其遺傳物質(zhì)。

交叉 (Crossover)

為了創(chuàng)建一對新個體，通常將從當(dāng)前代中選擇的雙親樣本的部分染色體互換(交叉)，以創(chuàng)建代表后代的兩個新染色體。此操作稱為交叉或重組：

突變 (Mutation)

突變操作的目的是定期隨機更新種群，將新模式引入染色體，并鼓勵在解空間的未知區(qū)域中進行搜索。

突變可能表現(xiàn)為基因的隨機變化。變異是通過隨機改變一個或多個染色體值來實現(xiàn)的。例如，翻轉(zhuǎn)二進制串中的一位：

遺傳算法理論

構(gòu)造遺傳算法的理論假設(shè)——針對當(dāng)前問題的最佳解是由多個要素組成的，當(dāng)更多此類要素組合在一起時，將更接近于問題的最優(yōu)解。

種群中的個體包含一些最優(yōu)解所需的要素，重復(fù)選擇和交叉過程將個體將這些要素傳達給下一代，同時可能將它們與其他最優(yōu)解的基本要素結(jié)合起來。這將產(chǎn)生遺傳壓力，從而引導(dǎo)種群中越來越多的個體包含構(gòu)成最佳解決方案的要素

圖式定理 (schema theorem)

如果一組染色體用長度為 4 的二進制串表示，則圖式 1*01 表示所有這些染色體，其中最左邊的位置為1，最右邊的兩個位置為01，從左邊數(shù)的第二個位置為 1 或 0，其中 * 表示通配符。

對于每個圖式，具有以下兩個度量：

階 (Order)：固定數(shù)字的數(shù)量
定義長度 (Defining length)：最遠的兩個固定數(shù)字之間的距離

下表提供了四位二進制圖式及其度量的幾個示例：

遺傳算法的組成要素

遺傳算法的核心是循環(huán)——依次應(yīng)用選擇，交叉和突變的遺傳算子，然后對個體進行重新評估——一直持續(xù)到滿足停止條件為止

精英主義 (elitism)

盡管遺傳算法群體的平均適應(yīng)度通常隨著世代的增加而增加，但在任何時候都有可能失去當(dāng)代的最佳個體。這是由于選擇、交叉和變異運算符在創(chuàng)建下一代的過程中改變了個體。在許多情況下，丟失是暫時的，因為這些個體(或更好的個體)將在下一代中重新引入種群。

但是，如果要保證最優(yōu)秀的個體總是能進入下一代，則可以選用精英主義策略。這意味著，在我們使用通過選擇、交叉和突變創(chuàng)建的后代填充種群之前，將前 n 個個體( n 是預(yù)定義參數(shù))復(fù)制到下一代。復(fù)制后的的精英個體仍然有資格參加選擇過程，因此仍可以用作新個體的親本。

Elitism 策略有時會對算法的性能產(chǎn)生重大的積極影響，因為它避免了重新發(fā)現(xiàn)遺傳過程中丟失的良好解決方案所需的潛在時間浪費。