一點(diǎn)前奏
（寫(xiě)在前面，公式無(wú)法正常顯示噢，使用TeX的公式。）
第一次聽(tīng)說(shuō)遺傳算法是在高三晚上放學(xué)回家的路上，同行的小伙伴問(wèn)我：你知道遺傳算法么？我自然沒(méi)聽(tīng)說(shuō)過(guò)，于是追問(wèn)細(xì)節(jié)。
“聽(tīng)說(shuō)遺傳算法能夠自我迭代，讓他本身系統(tǒng)內(nèi)的東西進(jìn)行優(yōu)勝劣汰的自然選擇，把好的保留下來(lái)，次一點(diǎn)的東西就排除掉。是不是特別像人工智能的那種感覺(jué)？”
這么高端的么？那時(shí)候我就對(duì)這個(gè)算法產(chǎn)生了一點(diǎn)興趣，畢竟一個(gè)算法是如何做到自我判斷什么是好什么是壞。
因?yàn)槿绱耍谖医佑|到編程以后，我終于有能力去深入研究一下遺傳算法了。最后覺(jué)得，其實(shí)這個(gè)算法也沒(méi)有當(dāng)初想得那么玄乎。
當(dāng)初年輕不懂事時(shí)，對(duì)未知的事物有著天然的好奇，自然會(huì)把遺傳算法想的無(wú)限大，甚至認(rèn)為可以自我淘汰不好的代碼，學(xué)習(xí)優(yōu)秀的代碼等。
其實(shí)現(xiàn)在再看過(guò)來(lái)，遺傳算法的本質(zhì)始終沒(méi)變，依舊是優(yōu)勝劣汰，選出最優(yōu)秀的個(gè)體。只不過(guò)它的作用被我規(guī)劃成了“求一個(gè)系統(tǒng)/模型的最優(yōu)解”。
遺傳算法簡(jiǎn)介
顧名思義，學(xué)過(guò)高中生物的都應(yīng)該可以理解“遺傳”是什么，染色體變異、染色體交叉等術(shù)語(yǔ)應(yīng)該也能夠大概知道是什么意思。其實(shí)遺傳算法主要就是模擬這一個(gè)過(guò)程。
不過(guò)我也不是專業(yè)搞生物的，高中的知識(shí)細(xì)節(jié)部分我早都忘光了，因此拋開(kāi)其他的，接下來(lái)我用我的理解來(lái)定義一下遺傳算法的過(guò)程。
遺傳算法四個(gè)基礎(chǔ)概念
遺傳算法中，一個(gè)基本單位為“個(gè)體”，一個(gè)種群（系統(tǒng)）中擁有好多個(gè)體。每個(gè)個(gè)體攜帶兩個(gè)內(nèi)容：染色體與適應(yīng)度。
為了形象起見(jiàn)，我們可以把一個(gè)個(gè)體比喻成一頭羊，一堆羊聚集在一起就成了一個(gè)種群。每一只羊長(zhǎng)的（肥瘦程度）都不同，有的很肥，有的很瘦。我們作為一個(gè)牧場(chǎng)的牧場(chǎng)主，最終目的是養(yǎng)出最肥的羊。而我們的羊比較奇葩，每天都會(huì)產(chǎn)仔，并且產(chǎn)完仔就會(huì)死去，令我們牧場(chǎng)羊的數(shù)量保持在一個(gè)確定的數(shù)量上。
為了逼迫羊們?cè)絹?lái)越肥，我們每天殺死最瘦的羊，然后越肥的羊就越有幾率交配生孩子，生出的孩子有可能變肥，也有可能變瘦。這樣長(zhǎng)此以往下去，我們羊群的羊?qū)?huì)越來(lái)越肥，而我們也達(dá)到了我們的目的。
所以簡(jiǎn)單的總結(jié)一下，上面每一頭羊都是一個(gè)“個(gè)體”，整個(gè)牧場(chǎng)就是一個(gè)種群。每一頭羊有“決定肥瘦程度的染色體”與“肥瘦程度”。這個(gè)肥瘦程度就是我們要說(shuō)的遺傳算法的“適應(yīng)度”。每一天我們將其稱之為迭代一次，也就是換一批新羊。
或者用生物上的話來(lái)說(shuō)，每一頭羊都有染色體，染色體決定了他們表現(xiàn)出來(lái)的性狀是怎樣的。所以說(shuō)，染色體決定了每一頭羊的肥瘦程度。
因此我們建立以下對(duì)應(yīng)關(guān)系：
- 整個(gè)牧場(chǎng) -> 一個(gè)種群
- 一頭羊->一個(gè)個(gè)體
- 某頭羊決定肥瘦程度的染色體->該個(gè)體的染色體
- 肥瘦程度->適應(yīng)度
明確了上面四個(gè)基礎(chǔ)概念以后，我們就可以引出他們之間的相互關(guān)系。
種群中包含了若干個(gè)個(gè)體，每個(gè)個(gè)體都擁有兩個(gè)屬性：染色體與適應(yīng)度。每一次迭代中，種群中的個(gè)體數(shù)量不變。
染色體
其實(shí)需要細(xì)講的主要還是染色體。
染色體是遺傳算法與“被求最優(yōu)解模型”直接相關(guān)之處。通常來(lái)說(shuō)一個(gè)模型想要求最優(yōu)解，那么就肯定會(huì)存在變量，通過(guò)控制變量的值讓模型的最終值達(dá)到最優(yōu)。
所以在這里，模型中所有變量就構(gòu)成了一條染色體。其中每一個(gè)變量稱之為染色體上的一個(gè)基因。
比如說(shuō)我們這里有一個(gè)多元函數(shù)$f=f(x, y)$，這個(gè)函數(shù)擁有最大值$f_{max}$，但是對(duì)應(yīng)的最大值點(diǎn)$(x_{max}, y_{max})$我們并不知道，用通常方法也十分難求出來(lái)，所以我們可以利用遺傳算法來(lái)簡(jiǎn)單求解一下。所以就將染色體設(shè)定為兩個(gè)節(jié)點(diǎn)（基因），第一個(gè)節(jié)點(diǎn)為$x$，第二個(gè)節(jié)點(diǎn)為$y$。
這是對(duì)于一個(gè)個(gè)體來(lái)說(shuō)的，也就是對(duì)于單個(gè)個(gè)體，他的染色體值我可以寫(xiě)成一個(gè)向量為
$$chrom = [x, y]$$
適應(yīng)度
那么得到了染色體，模型的最優(yōu)解如何評(píng)價(jià)呢？就是利用適應(yīng)度來(lái)尋找最優(yōu)解。
每個(gè)個(gè)體的適應(yīng)度就相當(dāng)于這個(gè)模型在“這個(gè)染色體的變量的值下的解”。也就是說(shuō)這個(gè)個(gè)體的染色體值為$chrom = [x_1, y_1]$，所以我們把$(x_1, y_1)$帶入到之前的多元函數(shù)中，可以得到這個(gè)函數(shù)的一個(gè)解為$f_1 = f(x_1, y_1)$，解$f_1$就是這一條染色體（個(gè)體）的適應(yīng)度。
尋找最優(yōu)解
對(duì)于整個(gè)種群，我們假設(shè)有$N$個(gè)個(gè)體，所以對(duì)應(yīng)的，也就有$N$條染色體，$N$個(gè)適應(yīng)度。因此可以寫(xiě)成以下形式
$$Chrom = \begin{bmatrix} x_1 & y_1 \ x_2 & y_2 \ \dots & \dots \x_N & x_N \end{bmatrix}$$
$$Fitness = [f_1, f_2, \dots, f_N]^{\mathrm{T}}$$
其中每一行都代表著一個(gè)個(gè)體。
我們?cè)谶@里假設(shè)每個(gè)個(gè)體的染色體的值各不相同，因此適應(yīng)度（模型的解）也就各不相同。所以我們就可以從中挑出來(lái)最大的適應(yīng)度，它就是在當(dāng)前情況下的最優(yōu)解，但不一定是真正的最大值$f_{max}$。
所以接下來(lái)的就是開(kāi)始尋找真正的最大值（最優(yōu)解）。
遺傳算法流程
一次迭代包括以下幾個(gè)過(guò)程：
- 染色體變異。即改變某個(gè)染色體的值；
- 染色體交叉。任意選擇兩個(gè)染色體交換部分基因；
- 計(jì)算適應(yīng)度。計(jì)算每個(gè)染色體在當(dāng)前迭代下對(duì)應(yīng)的適應(yīng)度。
- 優(yōu)勝劣汰。選出最劣適應(yīng)度的染色體，并將其
用最優(yōu)適應(yīng)度染色體替換。
染色體變異
染色體變異作用于每一個(gè)個(gè)體，目的就是修改當(dāng)前染色體，從而讓其變得“更好”，也有可能變得“更壞”。
為了能夠讓已經(jīng)就很優(yōu)的個(gè)體不要貿(mào)然的跌下神壇，讓不算特別好的個(gè)體突破階級(jí)限制進(jìn)入最優(yōu)，我們可以做出以下規(guī)定：
- 適應(yīng)度越優(yōu)的個(gè)體染色體變化范圍越??；
- 適應(yīng)度越劣的個(gè)體染色體變化范圍越大。
這樣子就能夠令整個(gè)種群的階級(jí)隨時(shí)保持流動(dòng)。
假設(shè)某個(gè)個(gè)體的染色體的某個(gè)節(jié)點(diǎn)$x$要發(fā)生變異，我們現(xiàn)在必須已知：當(dāng)前迭代下種群中的最優(yōu)適應(yīng)度$f_{best}$；當(dāng)前個(gè)體的適應(yīng)度$f$。
然后我們產(chǎn)生一個(gè)隨機(jī)數(shù)$rand$，就是這個(gè)節(jié)點(diǎn)的變化值，所以通過(guò)公式
$$x_{new}=x\left[1\pm rand\left(1-\dfrac{f}{f_{best}}\right)^2\right]$$
可以得到新的染色體節(jié)點(diǎn)值$x_{new}$.其中,正負(fù)號(hào)隨機(jī)決定，代表著當(dāng)前染色體節(jié)點(diǎn)值應(yīng)該變大還是變小。
這個(gè)式子代表著，當(dāng)$f$越趨近于$f_{best}$時(shí)，$\left(1-\frac{f}{f_{best}}\right)^2$ 就趨近于0，說(shuō)明對(duì)原$x$的改變?cè)叫。ㄗ兓繋缀鯙?）；當(dāng)$f$遠(yuǎn)離$f_{best}$時(shí)，$\left(1-\frac{f}{f_{best}}\right)^2$越趨近于1，說(shuō)明對(duì)原$x$的改變?cè)酱蟆?/p>
染色體交叉
染色體交叉比較容易，隨機(jī)選擇兩個(gè)染色體，在隨機(jī)選擇一對(duì)節(jié)點(diǎn)，相互交換對(duì)應(yīng)的值即可。
比如有兩個(gè)個(gè)體的染色體為$chrom_m=[x_m, y_m], chrom_n = [x_n, y_n]$，我們選擇將其第一個(gè)節(jié)點(diǎn)上的兩個(gè)節(jié)點(diǎn)進(jìn)行交叉互換，得到新的兩個(gè)染色體值為$chrom_m=[x_n, y_m], chrom_n = [x_m, y_n]$。
計(jì)算適應(yīng)度
計(jì)算適應(yīng)度其實(shí)就是將每個(gè)個(gè)體的染色體帶入到模型中進(jìn)行計(jì)算，計(jì)算出來(lái)其對(duì)應(yīng)的適應(yīng)度。
優(yōu)勝劣汰
為了讓我們種群的適應(yīng)度整體水平上升，我們必須殺死排名最后的那個(gè)個(gè)體。
殺死之后種群數(shù)量就變少了，所以就必須要讓比較優(yōu)良的個(gè)體多生點(diǎn)來(lái)把種群數(shù)量補(bǔ)回來(lái)。在這里我為了方便，直接把最劣的個(gè)體的染色體替換成了最優(yōu)個(gè)體的染色體。
這樣子就是優(yōu)勝劣汰，略微的把整體適應(yīng)度水平提升了一點(diǎn)。
小結(jié)
以上就是遺傳算法的大概流程。因?yàn)檫z傳算法的實(shí)現(xiàn)方法較多，所以這是按照我個(gè)人習(xí)慣整合成的一個(gè)遺傳算法。一般來(lái)說(shuō)，遺傳算法的染色體還可以由二進(jìn)制表示，優(yōu)勝劣汰的方法也有其他方法，在這里我們就不多贅述。
下一章將會(huì)引入MATLAB代碼，引入實(shí)際模型來(lái)進(jìn)行一個(gè)具體的計(jì)算。
諸位喜歡的話麻煩點(diǎn)個(gè)贊吧~
