遺傳演算法來解最佳化問題的基本歩驟:
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)的機會，此項特性是遺傳演算法則的最大優點。
遺傳演算法只使用適應函數 適應函數作為判斷依據，而不需要其它輔助的資訊(例如梯度)，因此可以使用各種型態的適應函數，並可免除許多繁雜的計算與推導。
遺傳演算法使用機率規則 機率規則方式去引導搜尋方向，屬於盲目的搜尋方法，而不是採用明確的規則，因此較能符合各種不同類型的最佳化問題。
問題
基因表達是以離散的方式加以呈現，故較難應用於求解連續變數之問題。較適用於求解整數變數，離散變數，二元變數等。
係將決策變數編碼為基因方式組成染色體求解，若問題決策變數甚多，導致染色體長度過長，超過電腦記憶體量限制，且結果不佳
仍無法保証求得最佳解
無記憶性，因此會重複搜尋相同的點，增加運作成本
沒有留言:
張貼留言