遺傳算法可以做什么？
遺傳算法是元啟發(fā)式算法之一。它有與達爾文理論（1859 年發(fā)表）的自然演化相似的機制。如果你問(wèn)我什么是元啟發(fā)式算法，我們最好談?wù)剢l(fā)式算法的區別。啟發(fā)式和元啟發(fā)式都是優(yōu)化的主要子領(lǐng)域，它們都是用迭代方法尋找一組解的過(guò)程。啟發(fā)式算法是一種局部搜索方法，它只能處理特定的問(wèn)題，不能用于廣義問(wèn)題。而元啟發(fā)式是一個(gè)全局搜索解決方案，該方法可以用于一般性問(wèn)題，但是遺傳算法在許多問(wèn)題中還是被視為黑盒。那么，遺傳算法能做什么呢?和其他優(yōu)化算法一樣，它會(huì )根據目標函數、約束條件和初始解給我們一組解。遺傳算法是如何工作的?
遺傳算法有5個(gè)主要任務(wù)，直到找到最終的解決方案。它們如下。
定以我們的問(wèn)題
我們將使用以下等式作為遺傳算法的示例。它有 5 個(gè)變量和約束，其中 X1、X2、X3、X4 和 X5 是非負整數且小于 10（0、1、2、4、5、6、7、8、9）。使用遺傳算法，我們將嘗試找到 X1、X2、X3、X4 和 X5 的最優(yōu)解。將上面的方程轉化為目標函數。遺傳算法將嘗試最小化以下函數以獲得 X1、X2、X3、X4 和 X5 的解決方案。
由于目標函數中有 5 個(gè)變量，因此染色體將由 5 個(gè)基因組成，如下所示。
初始化
在初始化時(shí)，確定每一代的染色體數。在這種情況下，染色體的數量是 5。因此，每個(gè)染色體有 5 個(gè)基因，在整個(gè)種群中總共有 25 個(gè)基因。使用 0 到 9 之間的隨機數生成基因。在算法中：一條染色體由幾個(gè)基因組成。一組染色體稱(chēng)為種群
適應度函數計算
它也被稱(chēng)為評估。在這一步中，評估先前初始化中的染色體。對于上面示例，使用以下的計算方式。將 X1、X2、X3、X4 和 X5 代入目標函數，得到 53。
適應度函數是 1 除以誤差，其中誤差為 (1 + f(x))。
選擇
輪盤(pán)賭法是遺傳算法中的一種隨機選擇方法。這就像賭場(chǎng)里的輪盤(pán)賭。它有一個(gè)固定點(diǎn)，并且輪子旋轉直到輪子上的一個(gè)區域到達固定點(diǎn)的前面。在遺傳算法的背景下，具有較高適應度值的染色體將更有可能在輪盤(pán)賭中被選中。
總計 = ??.????????總計 = 0.0185 + 0.0400 + 0.0178 + 0.0181 + 0.0434
然后，計算每個(gè)染色體的概率。下圖是第一條染色體概率的樣本計算（P1 = 0.1342）。計算概率后，對于輪盤(pán)賭方法，需要計算其累積概率。
計算累積概率后，要使用輪盤(pán)進(jìn)行選擇，需要生成5個(gè)隨機數Uniform(0,1)，這些隨機數決定了從選擇中剔除哪條染色體。
產(chǎn)生5個(gè)數字因為我們有5條染色體
下圖就是挑選和消除染色體的方法。首先，根據累積概率排列染色體，所選擇的染色體由隨機數決定如下:
交叉
在生物學(xué)中，交叉是指生殖的一個(gè)術(shù)語(yǔ)。兩條染色體被隨機選擇并通過(guò)數學(xué)運算進(jìn)行匹配。在本例中使用單點(diǎn)交叉。單點(diǎn)交叉意味著(zhù)兩個(gè)親本的基因被一個(gè)交叉線(xiàn)交換
下圖包含使用Uniform(0,1)生成的隨機數。選擇用于交叉的染色體數量是由交叉率(Pc)控制的，其中最小值為0，最大值為1。例如確定Pc = 0.25，這意味著(zhù)隨機數目小于0.25的染色體將成為交叉中的親本。隨機數對染色體。例如，R1對1號染色體，R2對2號染色體，以此類(lèi)推
交叉的染色體是染色體1，染色體3和染色體5。這三條染色體的結合如下所示。
為了確定交叉線(xiàn)的位置，需要生成一個(gè)1到n之間的隨機數，其中n是染色體- 1的長(cháng)度。我們生成了1到4。
染色體1和染色體3之間的交叉(稱(chēng)為CO1)如下所示。
1號染色體和5號染色體之間的交叉(稱(chēng)為CO2)如下所示。
3號染色體和5號染色體(稱(chēng)為CO3)
突變
1號染色體和2號染色體來(lái)自新的2號染色體和4號染色體。他們沒(méi)有被選中進(jìn)行交叉。而染色體3、4和5來(lái)自前代的交叉。下圖就是與“染色體選擇后使用交叉的結果”進(jìn)行的對比。突變是我們賦予任何基因新的價(jià)值的過(guò)程。在本例中使用隨機突變，突變基因的數量由突變率決定(????)。首先，計算一個(gè)種群中的基因數量。
接下來(lái)，發(fā)生突變的基因數量如下。#genes = 5 x 6#genes = 30
#genes mutation = 30 x 0.1#genes mutation = 3
所以需要生成從1到30的隨機數。隨機數的結果是7、19和23。它們是突變基因的位置。接下來(lái)，對于每一個(gè)被選中的基因，生成一個(gè)從0到9的隨機數來(lái)替換舊的值。
評估
使用生成的新一代重復這個(gè)過(guò)程，就可以以獲得X1、X2、X3、X4和X5的最佳解。經(jīng)過(guò)幾代后，得到的最佳染色體如下。
這個(gè)目標函數是有不同解的，所以我們這里只給出一個(gè)。如果需要添加限制條件，可以修改目標函數。
代碼
下面的Jupyter Notebook是上面我們過(guò)程的代碼實(shí)現：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.
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
