[GA] 基因演算法概念細說 (I) - 編解碼 @ Edison.X. Blog

筆者曾拿以前在商院修課時寫下 source code 做 demo ，

< 後續確實有拿來做其它應用 > 一些問題可能是找不到合適書籍或文獻所造成，

在 coding 過四、五個問題後，這裡只簡述一遍 GA 整個流程，

和一般在課本上看到的可能不一樣，因筆者是在商院學的，看的文獻也是偏商的文獻。

這系列講的 GA 問題，是以數學方程式 < non-linear programming >為主，

而不是 GA permuatation 問題。

注意，如果 GA 要學好的話，編碼、解碼要特別熟知特性與其計算方式。

以下說明之數值範圍，開閉區間需注意。

1. 確定問題與變數範圍

想一下問題自變數有哪些，假設自變數有 W, X, Y, Z，另須確定自變數是什麼性質之資料，

如 0/1變數 (雙元變數)、整數變數(一定是整數)、浮點數變數(會有小數點) 等，另外還必須確定變數範圍。

下面探討基於以下變數特性之假設

W : 雙元變數 ( 只有 0/1 這兩個整數之可能)。

X : 整數變數，範圍為 [ -10 , +10 ]

Y : 浮點數變數，範圍為 [0.0 , +2.0]

Z : 浮點數變數，範圍為 [-2.1, 3.5 ]

每個變數之範圍的決定是一個議題，在談論任何演化式演算法的時候，

都會先限定變數的可能範圍，有些範圍是很明顯，

如：是不是男生(0/1)、是否結婚 (0/1) 、養幾個小孩 ( 或許假定 [0, 30] ) 等；

但有些範圍可能是專家的合理推測，或由其它一些專業背景判斷得來。

另，在基因演算法裡，每個自變數都可以叫一種染色體。

假設適應函式為望大，MAX func(W, X, Y, Z)

所以表示一個解包含了 W 染色體、X 染色體、Y 染色體、Z 染色體。

2. 編解碼問題

筆者必須強調，有些問題是在算「順序性」，這些問題的基因長度是固定的。

像是工作排程，已知有哪幾個工作站，工作站數目就是基因長度；

又像是旅行員推銷問題 (tsp)，已知有哪幾個 city，city 個數就是基因長度；

又像是交通運籌問題或一些供應鍊問題等，這些問題都被統稱作 GA permutation，

基因長度都是已知的，但這裡講的並不是針對此問題。

在每個染色體裡面含有的基因長度可能不一定相同，

像 W 染色體長度可能是 1、5、10、20 固定其中一個數值；

Y 染色體長度可能是 2、4、6 、8 固定其中一個數值等，

但通常染色體長度會先經過事前的計算得到，而不會隨便亂設得到，

下述便在說明如何合理的計算，予以決定各染色體適當之長度。

由於基因演算法最早提出來的時候是以二元編碼方式，

故這裡講的方法也都是以二元編碼為主，實數編碼(也就是浮點數、小數)文獻上很少，

即使找到，大多數學味也很濃，簡易的實數編碼後半段再講。

2.1 基因長度決定 < 整數變數 / 雙元變數 >

這是基本知識的前置，一定要懂。如果不懂二進位表示法，請先自行找資料補充。

這裡說個重要結論：若基因長度為 LEN，共可表示 2^LEN 個數。

意思是如果基因長度 = 20，則它可以表示的數字有 2^20 = 1048576 個數，

若下界是從 0 開始的話，表達範圍為 [0, 1048575], 共 2^20 個數；

若下界是從 100 開始的話，表達範圍變 [100 , 1048675], 也是 2^20 個數；

若下界是從 -100 開始的話，表達範圍變 [-100 , 1048475] , 也是 2^20 個數。

一些 Q & A 先補上。

Q1 : 那如果範圍是 [0 , 1048475] 的整數，那基因長度最少要多長才夠表示？

Ans : 因 [0, 1048475] 共 1048475 - 0 + 1 = 1048476 個數

(植樹問題，前後包含的話相減後加一)，故

2^LEN >= 1048476 (記得 LEN 要整數)，故 LEN 選 20，

也就是取 LEN >= log2 ( 1048476 ) 之最小整數。

Q2: 那如果範圍是 [-10 , +10] 的整數，那基因長度最少要多長才夠表示？

Ans : 因 [-10 , +10] 共 10 - (-10) + 1 = 21 個數，故

2^LEN >= 21 ，故 LEN 選 5，

也就是取 LEN >= log2(21) 之最小整數。

注意，上述的算法只適用在「整數」，小數算法稍後說明。

再來計算 W, X 之長度就算單多了。

(a) W_LEN :

由於 W 範圍是 [0, 1] 之整數，

故 W_LEN >= log2(1-0+1) = log(2) = 1，取 W_LEN = 1。

(b) X_LEN :

由於 X 範圍是 [-10, +10]之整數，

故 X_LEN >= log2(+10 - (-10) + 1) = log2(21) = 4.39，取 X_LEN = 5。

如果是 W 染色體，要表示它為 0 或 1的話，由於 W_LEN 為 1，所以只可能是 1/0 ，這沒問題。

那 X 染色體呢？這個再進行說明。

由於 X 染色體範圍為 [-10, +10] 在上面我們透過計算的方式求得它的最小長度取 5；

X_LEN 取 5 的話，又因為 X 染色體為二進位編碼，可以表示的內容變成了

<染色體內容> ---> <對應到十進位>

00000 ---> 0
00001 ----> 1
00010 ----> 2
00011 ----> 3
......
11110 ----> 30
11111 ----> 31

表示範圍變成了 [0 , 2^5 - 1] = [0 , 31] ，

這個跟前提定義的， X 染色體範圍是 [-10 , +10] 之整數不一樣耶！

我們只好用個內差法做個轉換的動作。

首先我們知道 X 染色體實際的最小值是 -10 ，

所以當染色體內容為 00000 時代表是 -10；

而其實際最大值是 +10 ，所以當染色體內容為 11111 時代表是 +10

<染色體內容> ---> <對應到十進位> --> <實際對應 X 數值>

00000 ---> 0 (令為 X_DEC_MAX) ---> -10 (令為 X_MIN)
00001 ----> 1
00010 ----> 2
00011 ----> 3
......
11110 ----> 30
11111 ----> 31 (令為 X_DEC_MIN)) ---> +10 (令為 X_UP)

中間的全都用內差法去算，怎麼算？

假設某一條染色體內容是 10010，代表實際的值叫 x_val

(1) 先轉成對應到的十進位，10010 二進位 = 18 十進位 (令為 x_dec_val) 。

(2)

10 - (-10) x_val - (-10)
------------ = ---------------
31 - 0 18 - 0

用這種方式去算出對應到的 x_val 是多少，算出來的 x_val ，

即是染色體為 10010 對應到的實際 x 值，必定介於 [ -10 , +10] 之間，

再把公式寫通用一點：

X_UP - X_LOW x_val - X_LOW
------------------------------------- = ---------------------------------
X_DEC_MAX - X_DEC_MIN x_dec_val - X_DEC_MIN

整理移項後可以得到一個通用的寫法：

(X_UP - X_LOW ) * (x_dec_val - X_DEC_MIN)
x_val = X_LOW + ----------------------------------------------------------
( X_DEC_MAX - X_DEC_MIN)

代進去算答案，

(10 - (-10) ) * (18 - 0 )
x_val = -10 + ----------------------------------------------------------
( 31 - 0)

x_val = -10 + ( 20 * 18) / 31 = -10 + 11.61 = 1.61

疑！答案是 1.61 , 和當初設定的 x 要是整數的要求不一樣耶！

很簡單，將 1.61 四捨五入得到 2 就好。

所以如果 X 染色體的編碼是 10010 的話，對應到實際的數值等於 2。

這部份不熟的話再查一下什麼叫內插法，熟的話算一下

10101 對到的 x_val 是多少，答案是 4 (由 3.54 四捨五入得之)。

2.2 基因長度決定 < 浮點數編碼 >

我們先探討下面這個問題：

如果是在 [0, 1] 之間的浮點數，基因長度挑 2 的話：

編碼 --> 轉十進位 --> 實際值

00 --> 0 --> 0.0000000
01 --> 1 --> 0.3333333
10 --> 2 --> 0.6666666
11 --> 3 --> 1.0000000

中間的 01 /10 對應到的實際值也是用內插法算出來的。

每「步進一個數字」它就增加了0.333333 之數值。

這個 0.33333 怎麼算出來的？

1. 因為假設基因長度為 2，所以表示範圍為 [0, 2^2-1] = [0, 3]

2. 因為實際表達範圍是 [0, 1]，所以精度為 (1-0) / (3-0) = 0.33333

再來看 Y 染色體部份， Y 染色體它是浮點數，範圍是 [0 , +2.0]，

如果染色體長度給 3 的話，

編碼 --> 轉十進位 --> 實際值

000 --> 0 --> 0.0000000
001 --> 1 --> ...
010 --> 2 --> ...
011 --> 3 --> ...
100 --> 4 --> ...
101 --> 5 --> ...
110 --> 6 --> ...
111 --> 7 (2^3-1)--> 2.0000000

我們可以算出，它「每步進一個單位」，實際值會增長 (2-0) / (7-0) = 0.285，

< 注意到，上面的 7 ，是因為染色體長度 = 3，2^3 - 1 = 7 >

意思是說，到時候求出來的值，最小的精確度只會到 0.285，

如果求出來的 Y 值應該是 0.68，那麼這種長度設計下，

結果只有可能是 0.285 + 0.285 = 0.57，

或是 0.285 + 0.285 + 0.285 = 0.885，

然而不論是 0.57 還是 0.885 ，這兩個數值對於 0.68 都有相當的差異。

所以在決定浮點數之染色體長度時，應該是要先決定，

這個變數精準度應該要到哪裡才對。

現假設想要精準到小數點以下 1 位數，也就是 0.1 ，

因為範圍是 [0.0 , 2.0] ，令染色體長度為 Y_LEN ，能滿足精度 0.1，

故可列出式子出來：

(2 - 0) / (2^Y_LEN - 1 ) <= 0.1 ，

< 注意上面的 (2-0) 是從 Y 變數給的範圍出來的 >

解這個式子可再移項，但即使用試誤法也沒差 < 其實推出來了，懶得再用文字寫數學式 >，

Y_LEN = 1 時 : 2 / (2-1) = 2 > 0.1 ，精度條件不成立
Y_LEN = 2 時 : 2 / (4-1) = 0.6666 > 0.1 ，精度條件不成立
Y_LEN = 3 時 : 2 / (8-1) = 0.28571 > 0.1 ，精度條件不成立
Y_LEN = 4 時 : 2 / (16-1) = 0.13333 >0.1，精度條件不成立
Y_LEN = 5 時 : 2 / (32-1) = 0.0645 < 0.1 ，精度條件成立

得到的結論是：

滿足浮點變數 Y (範圍為 [0, 2]) 精度為 0.1 時，基因長度「最少」要為 5。

為什麼說「至少」要為 5？因為實際上基因長度可以再增加，

而且基因長度愈長時，精度就愈小。如

Y_LEN = 6 : 精度 = 2 / (2^6 - 1) = 2 / 63 = 0.0317
Y_LEN = 7 : 精度 = 2 / (2^7 - 1) = 2 / 127 = 0.01574
Y_LEN = 8 : 精度 = 2 / (2^8 - 1) = 2 / 255 = 0.00784

所以要準到小數二位數的話，長度就「最少」為 8。

注意三件事：

1. 基因長度最好不要超過 31 < 上限其實是 53 ，但寫 ga 的大概不多人會注意到這問題 > ，不然出來的結果容易出包。

2. 若依值域、精度算出來，基因長度要滿足精度需要，必須超過 31 的話，設計必須詳細設計，這會是個麻煩的問題。

3. 雖然長度愈長，可表示的精度就愈小，但一般設計是設計成「剛好可表達該精度即可」，原因是精度愈小、基因長度愈長，要演化到近似最佳解的時間就愈久。

那怎麼解碼？

答案是一樣是用內差法，內差法原理上述已說過，就不再多說明了，

直接來個練習。

Q : 已知 Y 變數值域為 [0, 2.0] 之浮點數，基因長度為 5，當 Y 染色體內容之基因為 01010 時，對應到的數值為何？

A : 01010 之十進位為 10，使用內插法

y_val - 0 10 - 0
----------------------- = -------------- ，
2 - 0 31 - 0

可算得 y_val = 0.6451629，注意唷！這裡不用再四捨五入，因為 Y 變數它是浮點數，不再限定是整數。