遺傳演算法簡單介紹與MATLAB實現(一)

一點前奏

第一次聽說遺傳演算法是在高三晚上放學回家的路上,同行的小夥伴問我:你知道遺傳演算法么?我自然沒聽說過,於是追問細節。

「聽說遺傳演算法能夠自我迭代,讓他本身系統內的東西進行優勝劣汰的自然選擇,把好的保留下來,次一點的東西就排除掉。是不是特別像人工智慧的那種感覺?」

這麼高端的么?那時候我就對這個演算法產生了一點興趣,畢竟一個演算法是如何做到自我判斷什麼是好什麼是壞。

因為如此,在我接觸到編程以後,我終於有能力去深入研究一下遺傳演算法了。最後覺得,其實這個演算法也沒有當初想得那麼玄乎。

當初年輕不懂事時,對未知的事物有著天然的好奇,自然會把遺傳演算法想的無限大,甚至認為可以自我淘汰不好的代碼,學習優秀的代碼等。

其實現在再看過來,遺傳演算法的本質始終沒變,依舊是優勝劣汰,選出最優秀的個體。只不過它的作用被我規劃成了「求一個系統/模型的最優解」。

遺傳演算法簡介

顧名思義,學過高中生物的都應該可以理解「遺傳」是什麼,染色體變異、染色體交叉等術語應該也能夠大概知道是什麼意思。其實遺傳演算法主要就是模擬這一個過程。

不過我也不是專業搞生物的,高中的知識細節部分我早都忘光了,因此拋開其他的,接下來我用我的理解來定義一下遺傳演算法的過程。

遺傳演算法四個基礎概念

遺傳演算法中,一個基本單位為「個體」,一個種群(系統)中擁有好多個體。每個個體攜帶兩個內容:染色體與適應度。

為了形象起見,我們可以把一個個體比喻成一頭羊,一堆羊聚集在一起就成了一個種群。每一隻羊長的(肥瘦程度)都不同,有的很肥,有的很瘦。我們作為一個牧場的牧場主,**最終目的是養出最肥的羊**。而我們的羊比較奇葩,每天都會產仔,並且產完仔就會死去,令我們牧場羊的數量保持在一個確定的數量上。

為了逼迫羊們越來越肥,我們每天殺死最瘦的羊,然後越肥的羊就越有幾率交配生孩子,生出的孩子有可能變肥,也有可能變瘦。這樣長此以往下去,我們羊群的羊將會越來越肥,而我們也達到了我們的目的。

所以簡單的總結一下,上面每一頭羊都是一個「個體」,整個牧場就是一個種群。每一頭羊有「**決定**肥瘦程度的染色體」與「肥瘦程度」。這個肥瘦程度就是我們要說的遺傳演算法的「適應度」。每一天我們將其稱之為迭代一次,也就是換一批新羊。

或者用生物上的話來說,每一頭羊都有染色體,染色體決定了他們表現出來的性狀是怎樣的。所以說,染色體決定了每一頭羊的肥瘦程度。

因此我們建立以下對應關係:

  • 整個牧場 -> 一個種群
  • 一頭羊->一個個體
  • 某頭羊決定肥瘦程度的染色體->該個體的染色體
  • 肥瘦程度->適應度

明確了上面四個基礎概念以後,我們就可以引出他們之間的相互關係。

種群中包含了若干個個體,每個個體都擁有兩個屬性:染色體與適應度。每一次迭代中,種群中的個體數量不變。

染色體

其實需要細講的主要還是染色體。

染色體是遺傳演算法與「被求最優解模型」直接相關之處。通常來說一個模型想要求最優解,那麼就肯定會存在變數,通過控制變數的值讓模型的最終值達到最優。

所以在這裡,模型中所有變數就構成了一條染色體。其中每一個變數稱之為染色體上的一個基因。

比如說我們這裡有一個多元函數 f=f(x, y) ,這個函數擁有最大值$f_{max} ,但是對應的最大值點 (x_{max}, y_{max}) 我們並不知道,用通常方法也十分難求出來,所以我們可以利用遺傳演算法來簡單求解一下。所以就將染色體設定為兩個節點(基因),第一個節點為 x ,第二個節點為 y

這是對於一個個體來說的,也就是對於單個個體,他的染色體值我可以寫成一個向量為

chrom = [x, y]

適應度

那麼得到了染色體,模型的最優解如何評價呢?就是利用適應度來尋找最優解。

每個個體的適應度就相當於這個模型在「這個染色體的變數的值下的解」。也就是說這個個體的染色體值為 chrom = [x_1, y_1] ,所以我們把 (x_1, y_1) 帶入到之前的多元函數中,可以得到這個函數的一個解為 f_1 = f(x_1, y_1) ,解 f_1 就是這一條染色體(個體)的適應度。

尋找最優解

對於整個種群,我們假設有 N 個個體,所以對應的,也就有 N 條染色體, N 個適應度。因此可以寫成以下形式

Chrom = egin{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}}

其中每一行都代表著一個個體。

我們在這裡假設每個個體的染色體的值各不相同,因此適應度(模型的解)也就各不相同。所以我們就可以從中挑出來最大的適應度,它就是在當前情況下的最優解,但不一定是真正的最大值 f_{max}

所以接下來的就是開始尋找真正的最大值(最優解)。

遺傳演算法流程

一次迭代包括以下幾個過程:

1. 染色體變異。即改變某個染色體的值;

2. 染色體交叉。任意選擇兩個染色體交換部分基因;

3. 計算適應度。計算每個染色體在當前迭代下對應的適應度。

4. 優勝劣汰。選出最劣適應度的染色體,並將其~~用最優適應度染色體~~替換。

染色體變異

染色體變異作用於每一個個體,目的就是修改當前染色體,從而讓其變得「更好」,也有可能變得「更壞」。

為了能夠讓已經就很優的個體不要貿然的跌下神壇,讓不算特別好的個體突破階級限制進入最優,我們可以做出以下規定:

  • 適應度越優的個體染色體變化範圍越小; f
  • 適應度越劣的個體染色體變化範圍越大。

這樣子就能夠令整個種群的階級隨時保持流動。

假設某個個體的染色體的某個節點$x$要發生變異,我們現在必須已知:當前迭代下種群中的最優適應度$f_{best}$;當前個體的適應度$f$。

然後我們產生一個隨機數$rand$,就是這個節點的變化值,所以通過公式

x_{new}=xleft[1pm randleft(1-dfrac{f}{f_{best}}
ight)^2
ight]

可以得到新的染色體節點值 x_{new} .其中,正負號隨機決定,代表著當前染色體節點值應該變大還是變小。

這個式子代表著,當 f 越趨近於 f_{best} 時, left(1-frac{f}{f_{best}}
ight)^2 就趨近於0,說明對原 x 的改變越小(變化量幾乎為0);當 f 遠離 f_{best} 時, left(1-frac{f}{f_{best}}
ight)^2 越趨近於1,說明對原 x 的改變越大。

染色體交叉

染色體交叉比較容易,隨機選擇兩個染色體,在隨機選擇一對節點,相互交換對應的值即可。

比如有兩個個體的染色體為 chrom_m=[x_m, y_m], chrom_n = [x_n, y_n] ,我們選擇將其第一個節點上的兩個節點進行交叉互換,得到新的兩個染色體值為 chrom_m=[x_n, y_m], chrom_n = [x_m, y_n]

計算適應度

計算適應度其實就是將每個個體的染色體帶入到模型中進行計算,計算出來其對應的適應度。

優勝劣汰

為了讓我們種群的適應度整體水平上升,我們必須殺死排名最後的那個個體。

殺死之後種群數量就變少了,所以就必須要讓比較優良的個體多生點來把種群數量補回來。在這裡我為了方便,直接把最劣的個體的染色體替換成了最優個體的染色體。

這樣子就是優勝劣汰,略微的把整體適應度水平提升了一點。


小結

以上就是遺傳演算法的大概流程。因為遺傳演算法的實現方法較多,所以這是按照我個人習慣整合成的一個遺傳演算法。一般來說,遺傳演算法的染色體還可以由二進位表示,優勝劣汰的方法也有其他方法,在這裡我們就不多贅述。

下一章將會引入MATLAB代碼,引入實際模型來進行一個具體的計算。


對知乎編輯器的吐槽

因為知乎不支持Markdown,所以公式還得一點點全部複製粘貼到Tex編輯器中,做無用功。所以讓我對在知乎上同步發表文章不太積極。

在我的CSDN博客上已經更新完了這個遺傳演算法與MATLAB系列,所以有興趣的朋友們可以直接戳鏈接轉到我的博客。

推薦閱讀:

在《爐石傳說》中,不使用金卡的玩家會更有信息優勢嗎?
數學建模如何當好隊長?
數學建模最重要的是思想方法么?
數學建模是如何反作弊的?

TAG:MATLAB | 数学建模 | 算法 |