簡介

遺傳算法 ( GA ) 指的是啟發(fā)性算法 ( EA )，主要應(yīng)用于其分析解法十分困難或甚至不可能的問題，它在大多數(shù)具有現(xiàn)實(shí)意義的情形中給出問題的可接受解決方案，但決策的正確性沒有經(jīng)過數(shù)學(xué)證明。

此類（NP 類）問題的一個(gè)經(jīng)典例子是“旅行商問題”（最著名的組合優(yōu)化問題之一）。該問題的主要挑戰(zhàn)在于找出最有利的路線，通過給定的城市至少一次后回到出發(fā)城市。但不會影響把它們用于囿于形式化的任務(wù)。

EA 被廣泛用于解決具有高度計(jì)算復(fù)雜性的問題，而不是一一嘗試所有選項(xiàng)，這將耗費(fèi)大量的時(shí)間。它們被應(yīng)用于人工智能領(lǐng)域（如模式識別）、殺毒軟件、工程、電腦游戲和其他領(lǐng)域。

值得一提的是，赫茲量化交易 在其軟件產(chǎn)品中使用了 GA。我們都知道策略測試程序，也知道使用內(nèi)置的策略優(yōu)化程序可以節(jié)省大量的時(shí)間和精力，正如在其中使用直接枚舉優(yōu)化 GA 的應(yīng)用是可能的。此外，MetaTrader 5 測試程序允許赫茲量化使用用戶優(yōu)化標(biāo)準(zhǔn)?？赡茏x者會有興趣閱讀一些有關(guān) GA 的文章，并對相比 直接枚舉 EA 可提供哪些優(yōu)勢感興趣。

1. 歷史一瞥

就在一年前，我亟需一個(gè)優(yōu)化算法用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)。在快速地了解各種算法后，我選擇了 GA。然而在搜索現(xiàn)成實(shí)施后，我發(fā)現(xiàn)對公眾開放的算法要么就具有功能限制（如可優(yōu)化的參數(shù)的數(shù)量），要么就是“可自己發(fā)揮的空間”太小。

我需要的是具有普適性的靈活工具，不僅可用于訓(xùn)練所有類型的神經(jīng)網(wǎng)絡(luò)，亦可用于任何優(yōu)化問題的一般性求解。在對陌生的“遺傳資料”長期研究后，我仍然無法理解它們是如何工作的。造成這種情況的原因可能是復(fù)雜的代碼風(fēng)格，或是我缺乏編程經(jīng)驗(yàn)，或兩者皆有之。

困難主要來自于將基因編碼為二進(jìn)制代碼以及以這種形式使用它們。無論哪種方式，都需要從頭開始編寫遺傳算法，將重點(diǎn)放在可量測性和未來易于修改上。

我不想進(jìn)行二進(jìn)制轉(zhuǎn)換，并決定直接使用基因，即，以實(shí)數(shù)的形式通過基因組來表示染色體。這就是我使用實(shí)數(shù)表示染色體的遺傳算法的代碼問世的過程。后來我才知道，這并不是什么新的發(fā)現(xiàn)，類似的遺傳算法（稱為實(shí)數(shù)編碼 GA）自從它們首次被發(fā)布出來已超過 15 年。

我把我探索 GA 功能的實(shí)施和原理的構(gòu)想留待讀者評定，因?yàn)檫@是基于它在實(shí)際問題中使用的個(gè)人經(jīng)驗(yàn)。

2. GA 說明

GA 蘊(yùn)含的原理借鑒于大自然本身。它們是遺傳和變異的原理。遺傳是生物將它們的生物特性和進(jìn)化特征傳遞給后代的能力。由于這種能力，所有生物才能將它們的物種特性留給它們的后代。

生物的基因變異保證了種群的遺傳多樣性，并且變異是隨機(jī)的，因?yàn)榇笞匀粺o法提前得知哪些特征在未來是最合適的（氣候變遷、食物的增加/減少、競爭物種的出現(xiàn)等）。變異使生物出現(xiàn)新的性狀，從而能夠在新的、變化的棲息條件下生存和留下后代。

在生物學(xué)中，由于突變引起的變異稱為突變，而通過交配實(shí)現(xiàn)基因的進(jìn)一步交叉組合所引起的變異稱為組合。GA 中有這兩種變異類型的實(shí)施。此外，還有突變的實(shí)施，模仿于突變的自然機(jī)制（DNA 的核苷酸序列發(fā)生變化）- 自然（自發(fā)）和人工（誘變）。

按照算法的準(zhǔn)則，信息傳遞的最簡單的單位是基因 - 遺傳的結(jié)構(gòu)和功能單位，控制特定的性狀和屬性的發(fā)展。我們將函數(shù)的一個(gè)變量稱之為基因?；蛲ㄟ^實(shí)數(shù)來表示。基因組 - 所研究函數(shù)的變量是染色體的表征特征。

我們同意以列的形式表示染色體。則函數(shù) f (x) = x ^ 2 的染色體將如下圖所示：

圖 1. 函數(shù) f (x) = x ^ 2 的染色體

其中，第 0 個(gè)索引 - 函數(shù) f (x) 的值，稱為個(gè)體的適應(yīng)度（我們將該函數(shù)稱之為適應(yīng)度函數(shù) - FF ，將函數(shù)的值稱之為 - VFF ）。染色體可方便地存儲于一維數(shù)組中。即，double Chromosome [] 數(shù)組。

所有進(jìn)化同代的樣本組成一個(gè)種群。此外，種群將隨意地分為兩個(gè)相等的群體 - 上代群體和后代群體。執(zhí)行上代物種（從整個(gè)種群中選出）的交叉以及 GA 的其他算子后，我們將得到一個(gè)新的后代群體，其規(guī)模為種群規(guī)模的一半，并將取代種群中的后代群體。

在搜索函數(shù) f (x) = x ^ 2 最小值的期間全體個(gè)體種群可能如下圖所示：

圖 2. 全體個(gè)體種群

種群通過 VFF 存儲。在這里，染色體的第 0 個(gè)索引被具有最小 VFF 的樣本占據(jù)。新的后代完全取代后代群體中的個(gè)體，而上代群體保持不變。然而，上代群體不是始終保持完整的，因?yàn)橹貜?fù)的樣本將被銷毀，然后新的后代將填充上代群體中的空缺，剩余的則填充至后代群體中。

換言之，種群規(guī)模保持恒定的情況是很罕見的，因年代而變，這幾乎和大自然是一樣的。例如，在繁殖前后種群可能如下圖所示：

圖 3. 繁殖前種群

編輯切換為居中

圖 4. 繁殖后種群

描述的通過后代“半”實(shí)現(xiàn)種群的機(jī)制以及銷毀重復(fù)的染色體和禁止個(gè)體與自身雜交都只有一個(gè)目的 - 那就是避免“瓶頸效應(yīng)”（生物學(xué)中的一個(gè)術(shù)語，意思是多種不同因素造成的臨界減少所引起的種群基因庫的縮減可導(dǎo)致物種的完全滅絕。GA 面臨著不再出現(xiàn)唯一染色體、在某個(gè)局部最優(yōu)解“卡住”的情形）。

3. UGAlib 函數(shù)的說明

算法 GA：

1. 創(chuàng)建一個(gè)原型種群?；蛟诮o定范圍內(nèi)隨機(jī)生成。

2. 確定每個(gè)個(gè)體的適應(yīng)度，或換言之，VFF 的計(jì)算。

3. 刪除重復(fù)的染色體，準(zhǔn)備繁殖種群。

4. 隔離和保留參考染色體（具有最優(yōu)的 VFF）。

5. UGA 算子（選擇、交配、突變）。對于每次交配和突變，選擇新的父母。準(zhǔn)備種群的下一代。

6. 將最優(yōu)后代的基因與參考染色體的基因進(jìn)行比對。如果最優(yōu)后代的染色體優(yōu)于參考染色體，則替換參考染色體。

針對指定數(shù)量的一代，從步驟 5 開始重復(fù)執(zhí)行此過程，直到?jīng)]有優(yōu)于參考染色體的染色體出現(xiàn)。