筆者曾拿以前在商院修課時寫下 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

 

(c) Y_LEN

 

再來看 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 變數它是浮點數,不再限定是整數。

 

(d) Z_LEN


這裡當練習了。

Q1: 已知 Z 為浮點數變數,範圍為 [-2.1, 3.5 ]。假設精度一樣到小數點以下一位數,也就是 0.1,基因長度至少需多少?

A1 : (3.5 - (-2.1) ) / (2^Z_LEN - 1 ) <= 0.1,可得到 Z_LEN 至少需要 6 才夠。

 

Q2 : 續上題,假設自變數 Z 基因長度為 6,基因內容為 101101,對應到的值域為何?

A2 : 101101 (二進位) = 45 (十進位),2^6 - 1 = 63 使用內差法求對應之值域 z_val

     3.5 - (-2.1)                z_val - (-2.1)
---------------------- =  ---------------------  ,
      63  - 0                         45  -  0

算出得到 z_val = 1.9。

 

編解碼至此結束,吃力正常,看不懂的請自行補充兩個議題:

(1) 二進位轉成十進位 (2) 內插法。

 

 -------------

數值上的編解碼算是非 CS 領域,學基因演算法算吃力的一環,故花了些時間說明,

所有  實數(即小數、浮點數)、二元變數、整數  之基本編碼都講完了,

其他其實還有一點補充,但鑑於會看這篇 blog  的初學者不適合繼續看其他編碼,

怕會愈看愈亂,故本篇敘述就至此吧。

 -------------

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()