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