遺傳算法可以做什麼？遺傳算法是元啟發式算法之一。它有與達爾文理論（1859 年發表）的自然演化相似的機制。如果你問我什麼是元啟發式算法，我們最好談談啟發式算法的區別。
啟發式和元啟發式都是優化的主要子領域，它們都是用迭代方法尋找一組解的過程。啟發式算法是一種局部搜索方法，它只能處理特定的問題，不能用於廣義問題。而元啟發式是一個全局搜索解決方案，該方法可以用於一般性問題，但是遺傳算法在許多問題中還是被視為黑盒。
那麼，遺傳算法能做什麼呢?和其他優化算法一樣，它會根據目標函數、約束條件和初始解給我們一組解。
遺傳算法是如何工作的?遺傳算法有5個主要任務，直到找到最終的解決方案。它們如下。定以我們的問題我們將使用以下等式作為遺傳算法的示例。它有 5 個變量和約束，其中 X1、X2、X3、X4 和 X5 是非負整數且小於 10（0、1、2、4、5、6、7、8、9）。使用遺傳算法，我們將嘗試找到 X1、X2、X3、X4 和 X5 的最優解。
將上面的方程轉化為目標函數。遺傳算法將嘗試最小化以下函數以獲得 X1、X2、X3、X4 和 X5 的解決方案。
由於目標函數中有 5 個變量，因此染色體將由 5 個基因組成，如下所示。
初始化在初始化時，確定每一代的染色體數。在這種情況下，染色體的數量是 5。因此，每個染色體有 5 個基因，在整個種群中總共有 25 個基因。使用 0 到 9 之間的隨機數生成基因。
在算法中：一條染色體由幾個基因組成。一組染色體稱為種群
適應度函數計算它也被稱為評估。在這一步中，評估先前初始化中的染色體。對於上面示例，使用以下的計算方式。
將 X1、X2、X3、X4 和 X5 代入目標函數，得到 53。
適應度函數是 1 除以誤差，其中誤差為 (1 + f(x))。
選擇輪盤賭法是遺傳算法中的一種隨機選擇方法。這就像賭場裡的輪盤賭。它有一個固定點，並且輪子旋轉直到輪子上的一個區域到達固定點的前面。
在遺傳算法的背景下，具有較高適應度值的染色體將更有可能在輪盤賭中被選中。
總計 = 𝟎.𝟏𝟑𝟕𝟖總計 = 0.0185 + 0.0400 + 0.0178 + 0.0181 + 0.0434
然後，計算每個染色體的概率。下圖是第一條染色體概率的樣本計算（P1 =0.1342）。
計算累積概率後，要使用輪盤進行選擇，需要生成5個隨機數Uniform(0,1)，這些隨機數決定了從選擇中剔除哪條染色體。
下圖就是挑選和消除染色體的方法。首先，根據累積概率排列染色體，所選擇的染色體由隨機數決定如下:
交叉在生物學中，交叉是指生殖的一個術語。兩條染色體被隨機選擇並通過數學運算進行匹配。在本例中使用單點交叉。
下圖包含使用Uniform(0,1)生成的隨機數。選擇用於交叉的染色體數量是由交叉率(Pc)控制的，其中最小值為0，最大值為1。例如確定Pc = 0.25，這意味着隨機數目小於0.25的染色體將成為交叉中的親本。
隨機數對染色體。例如，R1對1號染色體，R2對2號染色體，以此類推
交叉的染色體是染色體1，染色體3和染色體5。這三條染色體的結合如下所示。
為了確定交叉線的位置，需要生成一個1到n之間的隨機數，其中n是染色體- 1的長度。我們生成了1到4。
染色體1和染色體3之間的交叉(稱為CO1)如下所示。
1號染色體和5號染色體之間的交叉(稱為CO2)如下所示。
突變1號染色體和2號染色體來自新的2號染色體和4號染色體。他們沒有被選中進行交叉。而染色體3、4和5來自前代的交叉。
下圖就是與「染色體選擇後使用交叉的結果」進行的對比。
突變是我們賦予任何基因新的價值的過程。在本例中使用隨機突變，突變基因的數量由突變率決定(𝑃𝑚)。首先，計算一個種群中的基因數量。
#genes = 5 x 6#genes = 30
#genesmutation=30x0.1#genes mutation = 3
所以需要生成從1到30的隨機數。隨機數的結果是7、19和23。它們是突變基因的位置。接下來，對於每一個被選中的基因，生成一個從0到9的隨機數來替換舊的值。
評估
使用生成的新一代重複這個過程，就可以以獲得X1、X2、X3、X4和X5的最佳解。經過幾代後，得到的最佳染色體如下。
這個目標函數是有不同解的，所以我們這裡只給出一個。如果需要添加限制條件，可以修改目標函數。
代碼下面的Jupyter Notebook是上面我們過程的代碼實現：https://gist.github.com/audhiaprilliant/f507d629a5322ca7f1ceaea027df0f6f
[1] M. Fronita, R. Gernowo, V. Gunawan. 2017. Comparison of Genetic Algorithm and Hill Climbing for Shortest Path Optimization Mapping. The 2nd International Conference on Energy, Environment and Information System (ICENIS 2017). August 15th — 16th 2017. Semarang (ID). pp: 1–5.[2] N. Arfandi, Faizah. 2013. Implementation of genetic algorithm for student placement process of community development program in Universitas Gadjah Mada. Journal of Computer Science and Information. 6(2): 70–75.[3] T. Suratno, N. Rarasati, Z. Gusmanely. 2019. Optimization of genetic algorithm for implementation designing and modelling in academic scheduling. Eksakta: Berkala Ilmiah Bidang MIPA. 20(1): 17–24.轉自：DeepHub IMBA
留言列表
留言列表