2012年4月22日 星期日

Genetic Algorithm solve Optimization Problem

遺傳演算法的三個主要運算子為複製(reproduction)或稱選擇、交配(crossover)、以及突變 (mutation)。


遺傳演算法來解最佳化問題的基本歩驟:

1)將問題要處理的所有資料編碼成稱為染色體(chromosonl)的字串
2)依問題的複雜程度,由所有染色體中隨機産生n個初始字串,這n個染色體可被稱為母體、族群(Population)
3)定義選擇規則(Selection),依據求解之條件設計的適應函數(fitness function)來選出)適應值高的染色體到交配池(mating  pool)中,挑選過程中依適應值高低比例複製(reproduction)到交配池中
4)再依交配(crossover)及突變 (mutation)過程的運算繁衍出子孫(offspring),到此為一個世代(Generation)
5)在毎一個世代中,都要對所新産生的染色體,評估其適應性(Fitness)評估否正在逼近問題的最佳解。
6)利用選擇規則(Selection),將具有高適應性的子代保留,以形成新的母代族群進行下一輪的遺傳過程。 


經過幾個世代之後,最後演算法會收歛至最佳的染色體。





















Selection (選擇)方法之一:
輪盤法(Roulette Wheel )
 


原則上 適應性愈高之染色體被複製的機率愈大;因以機率隨機選擇,故適合度低的染色體仍有機會被複製。

 crossover(交配)方法之一:
Single point crossover (單點交配)










在選擇的兩條染色體中,隨機選取一個交配點,並交換兩條染色體中此交配點後所有位元。

Mutation (突變)方法之一:
二元編碼之突變:
隨機選擇1或多個bits做數値反轉的動作。




若突變率為0.1,上述染色體(chromosonl)長度為8,母體(Population)假設有5條,那麼就有40個bits,突變率0.1表示有4個bits要突變,若為隨機選擇1個bit就是5條挑4條隨機選擇位置反轉1個bit


設定停止條件:
1)執行設定的世代數
2)前後世代最佳值之差異低於設定的極小值
3)成熟率大於設定值
成熟率表示族群中有多少比例的染色體具有相同的基因,當族群中絕大部分的染色體都具有相同基因時,交配也無法産生一個不同的子代,此時即為收斂(亦稱為成熟)。例如設定成熟率 ≥80%時停止

範例

欲求解f(x)的最大值,其中f(x) = x^2,x 為介於 0至31間的整數。


在運用遺傳演算法求解最佳化問題時,需事先規劃三個主要問題:

決定編碼型態 ((Encoding) Encoding)
決定遺傳演算法的演化機制(Select Crossover Mutation)
定義適應函數(Fitness Function)


編碼 (Encoding) 型態方式上,利用二進位的位元編碼方式,將十進位數值0編成00000的位元,十進位數值31 編成 11111 的位元。

選擇 (Select) 的方法上我們使用輪盤選擇法(roulette wheel selection)
交配的機制我們選擇單點交配(single point crossover),並將交配機率設定為 1.0
突變的機制選擇單點突變(one point mutation),並將突變機率設定為 0.1


適應函數 (Fitness Function):我們可以直接以此函數當做為適應函數,即:f(x) = x^2 .

Step 1:

我們設定族群大小為 4,由問題之解答空間隨機抽取四個數値:
-------------------------------------------------

母代編號    隨機抽取之數値 x     二元編碼
      1                   14                            01110
      2                   24                            11000
      3                   17                            10001
     4                      7                            00111
-------------------------------------------------

Step2:
計算現有族群中毎一條染色體的適合度値(Fitness value)。

-----------
 x        f(x)
14      196
24      576
17      289
7         49
----------

Step3:
選擇:自現有族群中,以輪盤法依毎條染色體的適合度比例,重複隨機選擇染色體












在起始族群中的第一個字串被複製一個至交配池中,第二個字串被複製二個至交配池中,第三個字串被複製一個至交配池中,第四個字串則被淘汰。由上表得知,計算出來的期望值 (第四欄) 與真實的複製個數很接近。亦即適應度高的字串被大量複製到下一子代;而適應度低的字串則被淘汰。


Step4:
交配:隨機至交配池中抽取兩母代,以隨機産生的交配點進行交配産生子代,並計算子代的適合度










Step5:
突變:由於我們設定的突變機率為 0.1,而族群中的基因總數為族群大小乘上毎個字串的編碼位元數,也就是 4 ×5 = 20。因此,族群中將被突變的基因總數為 20 ×0.1 = 2,亦即,有兩個基因將被突變。我們隨機地挑選兩個字串中的各一個基因來作突變,並計算突變後的適度。


Step6:測試停止條件
測試是否符合停止條件。若是則停止,否則回至歩驟3,以進行下一代的演化。

遺傳演算法則之主要特性

遺傳演算法則是以"參數編碼"的方式進行運算而不是參數本身,因此可以跳脱搜尋空間上的限制。

遺傳演算法則同時考慮搜尋空間上多個點    多個點而不是單一個點,因此可以比傳統的啓發式解法較快地獲得整體最佳解 整體最佳解(global   optimum), 並 可 以 降 低 陷 入 區 域 最 佳 值(local optimum)的機會,此項特性是遺傳演算法則的最大優點。

遺傳演算法只使用適應函數       適應函數作為判斷依據,而不需要其它輔助的資訊(例如梯度),因此可以使用各種型態的適應函數,並可免除許多繁雜的計算與推導。

遺傳演算法使用機率規則       機率規則方式去引導搜尋方向,屬於盲目的搜尋方法,而不是採用明確的規則,因此較能符合各種不同類型的最佳化問題。

問題

基因表達是以離散的方式加以呈現,故較難應用於求解連續變數之問題。較適用於求解整數變數,離散變數,二元變數等。

係將決策變數編碼為基因方式組成染色體求解,若問題決策變數甚多,導致染色體長度過長,超過電腦記憶體量限制,且結果不佳
仍無法保証求得最佳解
無記憶性,因此會重複搜尋相同的點,增加運作成本




















沒有留言:

張貼留言