遺傳算法的手工模擬計算示例

為更好地理解遺傳算法的運算過(guò)程，下面用手工計算來(lái)簡(jiǎn)單地模擬遺傳算法的各
個(gè)主要執行步驟。

例：求下述二元函數的最大值：

(1) 個(gè)體編碼
遺傳算法的運算對象是表示個(gè)體的符號串，所以必須把變量 x1, x2 編碼為一種
符號串。本題中，用無(wú)符號二進(jìn)制整數來(lái)表示。
因 x1, x2 為 0 ~ 7之間的整數，所以分別用3位無(wú)符號二進(jìn)制整數來(lái)表示，將它
們連接在一起所組成的6位無(wú)符號二進(jìn)制數就形成了個(gè)體的基因型，表示一個(gè)可
行解。
例如，基因型 X＝101110 所對應的表現型是：x＝[ 5，6 ]。
個(gè)體的表現型x和基因型X之間可通過(guò)編碼和解碼程序相互轉換。

(2) 初始群體的產(chǎn)生
遺傳算法是對群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始
群體數據。
本例中，群體規模的大小取為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過(guò)隨機
方法產(chǎn)生。
如：011101，101011，011100，111001

(3) 適應度汁算
遺傳算法中以個(gè)體適應度的大小來(lái)評定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳
機會(huì )的大小。
本例中，目標函數總取非負值，并且是以求函數最大值為優(yōu)化目標，故可直接
利用目標函數值作為個(gè)體的適應度。

(4) 選擇運算
選擇運算(或稱(chēng)為復制運算)把當前群體中適應度較高的個(gè)體按某種規則或模型遺傳到下一代群體中。一般要求適應度較高的個(gè)體將有更多的機會(huì )遺傳到下一代
群體中。
本例中，我們采用與適應度成正比的概率來(lái)確定各個(gè)個(gè)體復制到下一代群體中
的數量。其具體操作過(guò)程是：
• 先計算出群體中所有個(gè)體的適應度的總和 fi ( i=1.2,…,M );
• 其次計算出每個(gè)個(gè)體的相對適應度的大小 fi / fi ，它即為每個(gè)個(gè)體被遺傳
到下一代群體中的概率，
• 每個(gè)概率值組成一個(gè)區域，全部概率值之和為1；
• 最后再產(chǎn)生一個(gè)0到1之間的隨機數，依據該隨機數出現在上述哪一個(gè)概率區
域內來(lái)確定各個(gè)個(gè)體被選中的次數。

(5) 交叉運算
交叉運算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過(guò)程，它以某一概率相互交換某
兩個(gè)個(gè)體之間的部分染色體。
本例采用單點(diǎn)交叉的方法，其具體操作過(guò)程是：
• 先對群體進(jìn)行隨機配對；
• 其次隨機設置交叉點(diǎn)位置；
• 最后再相互交換配對染色體之間的部分基因。

(6) 變異運算
變異運算是對個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)
行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。
本例中，我們采用基本位變異的方法來(lái)進(jìn)行變異運算，其具體操作過(guò)程是：
• 首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機產(chǎn)生的變異點(diǎn)位置，
其中的數字表示變異點(diǎn)設置在該基因座處；
• 然后依照某一概率將變異點(diǎn)的原有基因值取反。

對群體P(t)進(jìn)行一輪選擇、交叉、變異運算之后可得到新一代的群體p(t+1)。

從上表中可以看出，群體經(jīng)過(guò)一代進(jìn)化之后，其適應度的最大值、平均值都得
到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最佳個(gè)體“111111”。
[注意]
需要說(shuō)明的是，表中有些欄的數據是隨機產(chǎn)生的。這里為了更好地說(shuō)明問(wèn)題，
我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實(shí)際運算過(guò)程中
有可能需要一定的循環(huán)次數才能達到這個(gè)最優(yōu)結果。