X演演算法

Ⅰ 誰能解釋基因演演算法

基因演演算法 1975年 John Holland 學者所提出
成為非常著名的演演算法
Genetic Algorithm (GA)
基因演演算法 又稱: 遺傳演演算法
基因演演算法的概念
將問題編碼成 染色體的型式
基因: 0 or 1
染色體: x = 0 1 0 0 1 1 0
設計 適應函數 (fitness function)
f(x) :適應函數，給一 x 可得一 適應值 f(x)
適應值愈高, 表愈適應環境
基因演演算法三個基本動作
選擇(Selection)與復制 (Reproction)：
X = 0 1 0 0 1 1 0
選擇 適應值高 之染色體
復製成多個染色體
基因演演算法三個基本動作
交換 (crossover)：
父：0 1 0 0 1 1 0 0 1 1 1 0 1 0
母：1 0 1 1 0 0 1 1 0 0 0 1 0 1
交換 基因演演算法三個基本動作
突變 (mutation)：
0 1 0 0 1 1 0
1 選擇 產生初始族群
計算適應値 復制 交換
突變 產生下一子代
是否滿足 停止條件
產生最適個體
否是 基因演演算法 基本架構圖
取材自:輔仁大學資管系林文修老師
選擇與 基因操作階段
評估階段 初始階段 生成下一世代
問題否是 生成母體
評估適應函數
符合停止條件？
選擇 復制 交換 突變
開始 結束 編碼 適應函數
領域知識 表現型 基因型
解碼 基因演演算法 之流程圖
取材自:輔仁大學資管系林文修老師
演演算法步驟 Step1：隨機產生N個染色體
Step2：利用適應函數算出每個染色體的適應值
Step3 : 選擇與復制: 選擇 適應值高 之染色體 復製成多個染色體
Step4：利用交換及突變的動作產生新的染色體
Step5：測試新染色體的適應值是否達到門檻值
是：則 停止
否：則 Go to Step3
範例1 假設 x 在 (0,31) 之間，y = x ，求 x = ，y 可得最大值
將問題編碼成 基因的型式
x : 0 0 0 0 0～1 1 1 1 1
設計 適應函數 (fitness function)
f (x) = y = x
範例1 <Step 1, 2, 3>
取4組染色體 x f (x) f (x) /m 復制個數
0 1 1 1 0 (14) 196 0.71 1
1 1 0 0 0 (24) 576 2.07 2
1 0 0 0 1 (17) 289 1.04 1
0 0 1 1 1 ( 7) 49 0.18 0
m = = 278
196+576+289+49
4 範例1 <Step 4.1> 交換
x f (x)
0 1 1 1 0 0 1 0 0 0 (8) 8 = 64
1 1 0 0 0 1 1 1 1 0 (30) 30 = 900
1 1 0 0 0 1 1 0 0 1 (25) 25 = 625
1 0 0 0 1 1 0 0 0 0 (16) 16 = 256
交換 交換 範例1 <Step 4.1> 交換
交換點 下一子代 x f (x)
0 1 1 1 0 2 0 1 0 0 0 8 64
1 1 0 0 0 2 1 1 1 1 0 30 900
1 1 0 0 0 4 1 1 0 0 1 25 625
1 0 0 0 1 4 1 0 0 0 0 16 256
範例1 <Step4.2>突變 (機率0.1)
4個染色體× 5個基因 = 20個基因
20 × 0.1 = 2 有2個基因要突變
1 st：0 1 0 0 0 0 1 1 0 0 (12)
第一個染色體之第3基因突變
3 rd：1 1 0 0 1 1 0 0 0 1 (17)
第三個染色體之第2基因突變
範例1 <Step5>
停止條件有三種可能方法：
設定繁衍代數 (ex：1000代)
收斂 (ex：最佳適應值已50代未改進)
適應值達到門檻
否則，Go to Step3
編碼（coding）-1
運用基因演化演算法的目的是求問題的解，在初始階段的編碼步驟是把與問題相關變數的值（或稱為問題解）以特定編碼的方式將其組合成一條染色體 （chromosome，或稱為字串string），每一條染色體即代表一可能的問題解答，
最簡單而且被廣泛使用的是標准二進位編碼法（Standard binary encoding）。這種編碼法是將染色體內的每個基因用二進位碼{0，1}來表示，而編碼後的染色體即是一串由01組合字串（string）。

Ⅱ 基因遺傳演演算法是個啥求詳解

基因遺傳演演算法主要理論就是優勝劣汰的進化論。
它的主要精神是透過每次迭代都能比上次更進步，逐步演化，表現出針對一個目標函數尋求最佳解的過程。但是因為是隨機搜索，所以雖然基因演演算法設置如交配、突變等來避免，卻仍可能會陷入區域最佳解；也有可能最後得到的不是最佳解，只是在結束條件之前找到的最好的解。

基本的基因演演算法流程：
1.初始化族群：假定這個族群中有4條染色體，每條染色體有5個基因。

基因 -從目標函數的角度來看，就是自變數。
例如：用基因演演算法解目標函數 f(X,Y,Z)=2X+3Y-Z，
限制式為「X,Y,Z＝{1,0}」※，
求目標函數的最大值。
此題目對應到染色體的概念，就有3個基因，
三個基因分別代表X、Y、Z三個自變數的值。
染色體 -單一組解
例如：有很多符合目標函數限制式的（X,Y,Z），
其中一組是（x1,y1,z1）=（1,0,0），
函數值 f(x1,y1,z1)為2*1+3*0-0=2。
此例中，這組解當然不是最佳解，但它是這個題目的一個可行解。
*想像我們用直覺解題，拿張計算紙，把所有可行解都列出來，
然後比較所有我們想得到的可行解，最後可以得
到最佳的一組(X,Y,Z)，因為它的f(X,Y,Z)為最大值。
族群 -多組解的集合
例如：族群中有四條染色體，這四條染色體就是四組可行解。

2.設定交配率和突變率：假定交配率a為0.6，突變率b為0.1。

交配率 -每個世代中，族群內有多少比率的染色體會互相交配。
突變率 -每個世代中，族群內的染色體有多少機率會突變。

3.迭代世代。
For iter=10 -假定做十次優勝劣汰。
3.1. 天擇：在這個世代中，根據每條染色體的權重，隨機選擇母代來產生後代，
用以做下一個運算。
通常使用輪盤法來作天擇，也就是說，
如果染色體甲的解是這個族群中最好的，
那麼甲的權重就是最高的。反之則是最低的。
*輪盤法：假定這次族群為「[1,1,1],[0,1,1],[1,0,1],[1,0,0]」，
四條染色體的適應值分別是「4，2，1，2」，
適應值總和為4+2+1+2=9，
則四條染色體被選到的機會為「4/9，2/9，1/9，2/9」
＝「0.4，0.2，0.1，0.2」。這個機會就是權重。
為了不讓每次選擇都選到同一條染色體，所以只是
「有比較高的機會」選擇到「有更好適應值的染色體」，
而不是一定會選擇這個好適應值的染色體。

3.2. 交配：母代產生後，依照交配率a，隨機選擇染色體來作交配。
比較交配前的子代1和交配後的子代2，在8條染色體中，
選擇適應值最好的4條染色體留下來。
最簡單的交配方式就是交換兩條染色體的某個基因。
*例如，染色體S=[0,1,0]，染色體Q=[1,1,1]，交配位於首位的基因，
則可以得到新的兩條染色體S'=[1,1,0]、Q'=[0,1,1]。

3.3. 突變：交配完後，依照突變率b，決定這一個世代要不要突變。
假設要突變，則若突變後子代3的適應值比突變前子代2好，就用子代3取代子代2。
最簡單的突變方式就是隨機選擇某條染色體的某個基因，改變它。
*例如，隨機選中染色體M=[1,0,1]，隨機突變中間的基因，
得到新染色體M'=[1,1,1] 。

3.4. 更新：最後得到的族群中，所有染色體的適應值。
END For

4. 比較所有染色體的適應值，列出最好的那一個染色體為演演算法最後的解。

※一般使用二元染色體，限制染色體的基因只會等於零或壹。
在此處只是方便解說，所以直接把限制式設成零和壹。
假設我們用二元染色體來解目標函數f(x)=x^2的最大值，限制式為0<=x<=7，x為整數。
用基因演演算法求解，則需要產生log_2(8)=3個基因，
簡單說來，就是用二進位表示一個有限整數值。
（也可以把基因想成電腦的位元數，我們用三個位元來表示一個有限的整數值。）
這樣做的話，突變的方法就是直接把某個基因轉成零或壹，
不用設定要更改多少值（例如加3、加100或減0.8）（基因演演算法應該一般不會這樣做）；
計算適應值時，互相轉換二進位與十進位。

基因三個，則可以表達：
111=2^2+2^1+2^0=4+2+1=7
110=2^2+2^1=4+2=6
101=2^2+2^0=4+1=5
100=4
001=1
000=0
011=3
010=2