非常好的了解遺傳算法的例子
遺傳算法的手工模拟計算示例
為更好地了解遺傳算法的運算過程，下面用手工計算來簡單地模拟遺傳算法的各
個主要執行步驟。
例：求下述二進制函數的最大值：
(1) 個體編碼
遺傳算法的運算對象是表示個體的符号串，是以必須把變量 x1, x2 編碼為一種
符号串。本題中，用無符号二進制整數來表示。
因 x1, x2 為 0 ~ 7之間的整數，是以分别用3位無符号二進制整數來表示，将它
們連接配接在一起所組成的6位無符号二進制數就形成了個體的基因型，表示一個可
行解。
例如，基因型 X＝101110 所對應的表現型是：x＝[ 5，6 ]。
個體的表現型x和基因型X之間可通過編碼和解碼程式互相轉換。
(2) 初始群體的産生
遺傳算法是對群體進行的進化操作，需要給其淮備一些表示起始搜尋點的初始
群體資料。
本例中，群體規模的大小取為4，即群體由4個個體組成，每個個體可通過随機
方法産生。
如：011101，101011，011100，111001
(3) 适應度汁算
遺傳算法中以個體适應度的大小來評定各個個體的優劣程度，進而決定其遺傳
機會的大小。
本例中，目标函數總取非負值，并且是以求函數最大值為優化目标，故可直接
利用目标函數值作為個體的适應度。
(4) 選擇運算
選擇運算(或稱為複制運算)把目前群體中适應度較高的個體按某種規則或模型遺傳到下一代群體中。一般要求适應度較高的個體将有更多的機會遺傳到下一代
群體中。
本例中，我們采用與适應度成正比的機率來确定各個個體複制到下一代群體中
的數量。其具體操作過程是：
• 先計算出群體中所有個體的适應度的總和 fi ( i=1.2,…,M );
• 其次計算出每個個體的相對适應度的大小 fi / fi ，它即為每個個體被遺傳
到下一代群體中的機率，
• 每個機率值組成一個區域，全部機率值之和為1；
• 最後再産生一個0到1之間的随機數，依據該随機數出現在上述哪一個機率區
域内來确定各個個體被選中的次數。
(5) 交叉運算
交叉運算是遺傳算法中産生新個體的主要操作過程，它以某一機率互相交換某
兩個個體之間的部分染色體。
本例采用單點交叉的方法，其具體操作過程是：
• 先對群體進行随機配對；
• 其次随機設定交叉點位置；
• 最後再互相交換配對染色體之間的部分基因。
(6) 變異運算
變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的機率進
行改變，它也是産生新個體的一種操作方法。
本例中，我們采用基本位變異的方法來進行變異運算，其具體操作過程是：
• 首先确定出各個個體的基因變異位置，下表所示為随機産生的變異點位置，
其中的數字表示變異點設定在該基因座處；
• 然後依照某一機率将變異點的原有基因值取反。
對群體P(t)進行一輪選擇、交叉、變異運算之後可得到新一代的群體p(t+1)。
從上表中可以看出，群體經過一代進化之後，其适應度的最大值、平均值都得
到了明顯的改進。事實上，這裡已經找到了最佳個體“111111”。
[注意]
需要說明的是，表中有些欄的資料是随機産生的。這裡為了更好地說明問題，
我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實際運算過程中
有可能需要一定的循環次數才能達到這個最優結果。
- 收起