遺傳算法（Genetic Algorithm，GA）

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

基因型 (Genotype)

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

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

種群 (Population)

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

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

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

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

選擇 (Selection)

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

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

交叉 (Crossover)

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

突變 (Mutation)

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

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

遺傳算法理論

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

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

圖式定理 (schema theorem)

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

對于每個(gè)圖式，具有以下兩個(gè)度量：

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

下表提供了四位二進(jìn)制圖式及其度量的幾個(gè)示例：

遺傳算法的組成要素

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

精英主義 (elitism)

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

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

Elitism 策略有時(shí)會(huì)對算法的性能產(chǎn)生重大的積極影響，因?yàn)樗苊饬酥匦掳l(fā)現(xiàn)遺傳過程中丟失的良好解決方案所需的潛在時(shí)間浪費(fèi)。