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