學習堅持，堅持學習

何謂「基因演算法」

基因演算法是人類依照生物學中「適者生存，不適者淘汰」的觀念所發展出來的一種演算法

利用「選擇、複製」、「交配」、「突變」等步驟去尋找最適合環境的基因

 

「基因演算法」能做什麼

依上面所說的

那「基因演算法」到底可以做什麼

又對寫程式的人來講「基因演算法」到底能解決什麼類型問題?

基本上「基因演算法」就是一個解決最佳化問題的工具

那又什麼叫最佳化問題?

以下給出幾種例子

1. 旅行推銷員問題
2. 工作排程問題

從「旅行推銷員問題」來看
我們可以隨便決定一條路線 (城市的先後順序)，
而這條路線會對應到一段距離 (歷經全部城市所需要的距離)
目標就是找到一條路線，
並且這條路線對應到的距離是最短的

而「工作排程問題」也是差不多的
我們有n個工作及m台機器
每個工作在每台機器上的執行時間可能有所不同
因此我們需要搜尋一個工作分配方式
所需要花費的時間最短

對這類問題通常對會有一個最大的問題

就是要將全部可行的解 (路徑or工作分配方式) 在有限時間內計算完畢是不可能的

而此類問題大部份也都可能是個NP問題

 

而「基因演算法」就是為了解決這種問題的工具

但做為折衷方案「基因演算法」找到的解不保證是最佳解 (可能只是次佳解)

 

從數學的表示來看

對於「旅行推銷員問題」

x 代表著某一條路徑

f(x) 代表這條路徑的距離

而目標就是找到一個x所對應的 f(x) 最小

很明顯的 x 就是我們要求解的變數

也可以說 x 是我們要最佳化的參數

 

簡述「基因演算法」

首先簡單說明一下「基因演算法」的流程

後面再講解各個東西代表的意義

1. 一開始隨機產生n個染色體 (n由使用者決定)
2. 利用適應函數計算所有染色體的適應值
3. 依每個染色體的適應「選擇、複製」染色體
4. 對留下的染色體進行交配及突變的動作

重複以上動作2-4 (執行完一次2-4的動作稱為1次疊代) 直到收斂

「基因演算法」就是經由上面的步驟一步一步搜尋較好的解

 

染色體、適應函數代表的是? 步驟的意義?

在「基因演算法中」各東西代表的意義

• 染色體：
  代表一個可行的解 (旅行推銷員問題 = 行走城市的先後順序。工作排程問題 = 各個任務該分配到的機器)
  從數學式來看，染色體 =  f(x) 中的 x
   
• 適應函數：
  用來計算某個 x 的適應值 (在旅行推銷員問題中等於求得距離的函數。在工作排程問題中等於花費的時間)
  適應函數在不同的應用會對應到不同的計算方式 (都是由人為所設計)
  從數學式來看，適應函數 = f(x) 中的 f 函數
   
• 選擇、複製：
  主要觀念為「留下好的染色體，排除不好的染色體」
  而在實做上有許多的方式如：輪盤法
  以下講解一下輪盤法，
  假設有4組染色體各自的適應值是4、7、12、15，並且要選擇適應值大的
  我們可以計算出所有染色體的適應值加總 = 38
  則我們給定4組染色體被選擇的機率為[4 / 38]、[7 / 38]、[12 / 38]、[15 / 38]
  
  如果我們想選適應值小的可以將適應值取倒數再進行計算，即[1 / 4]、[1 / 7]、[1 / 12]、1 / 15
  加總 = 228 / 420
  染色體被選擇的機率為[105 / 228]、[60 / 228]、[35 / 228]、[28 / 228]
   
• 交配：
  利用兩組舊的染色體組合得到新的染色體
  
  如上圖所示，而黃色的部份 = 交配的位置 (如何選擇交配的位置也有許多方式，如：單點、多點、遮罩交配)。
  要進行交配的染色體就是由「選擇、複製」所留下的染色體
  而兩個染色體要不要交配是用一個交配機率來決定
  要交配的位置也是隨機決定的
  另外因為交配是由兩組舊的染色體組合而成，所以不會產生未出現的資訊
  從這個角度來看交配是有方向的產生新的染色體 (菁英和菁英產生菁英)
   
• 突變：
  我們會設定一個突變機率來決定某個染色體中的某個基因是否進行突變
  
  如上圖所示，黃色的位置被選擇突變的基因
  將該基因由1轉為0，0轉為1
  突變要改變的資訊是有隨機來決定，因此會產生未出現的資訊
  因此突變是一種沒有方向的產生新的染色體
  使用突變通常是為了避免在搜尋過程中掉入local optimum
   
• 收斂：
  通常會設定為
          1. 疊代次數到達一定次數
          2. 所有染色體都非常相似
   

 

「基因演算法」的流程

假設染色體個數為4，並且染色體的基因數為7

我們實際演練整個過程

(假設我們要找適應值小的，因此給適應值小的有較大的機率被選擇留下)  

(經過「選擇、複製」後，我們發現[0010010]這組染色體多了一個，而[0011010]這組染色體消失了)

接下來我們將留下的染色體兩兩交配 (交配率100%，假設左邊兩個交配，右邊兩個交配，單點交配)

並且利用突變 (紫色為經由突變機率所選擇到的位置)

接著不斷重複以上「評估適應函數」、「選擇、複製」、「交配」、「突變」等步驟

直到收斂

 

「基因演算法」的小細節

1. 每個染色體的不一定是由0、1組成，如
   
   也可以是一個染色體
    
2. 染色體代表的東西不一定代表解的實際狀態
   事實上染色體通常需要經過解碼來得到解的實際狀態，如下圖
   
   (這邊解碼的方式是將染色體每個基因做排序，然後排序後的位置 = 第幾個城市)
   通常解碼方式是由人去設計解碼的方式也有可能影響到找到的解的好壞
   不同的應用解碼的方式也不同
    

 

 

實際應用 - Otsu

如上一篇文章所講到的

當一張影像要找到n個閥值的時後複雜度為Big O(255 ^ n)

為此可以使用「基因演算法」來搜尋而不用全部搜尋

這邊適應函數 = 用Otsu算出來的群內變異量的總和

當然目標是適應函數越小越好 (Otsu要找到一組閥值，求出來的群內變異量的總和最小)

而染色體又代表什麼呢?

假設我們要找 3 個閥值，染色體大概會長成這樣

代表 10、125、180為閥值的位置

如果是5個值染色體會長成這樣

10、70、80、115、130為閥值的位置

那這邊解碼是要做什麼呢?

因為我們要找的閥值通常不希望出現以下情況

1. 一樣的數字
2. 超過255的數字 (以8bit灰階圖切割來說)
3. 數字希望排列過

如下圖：

這些是不被允許的

因此通過解碼

我們需要將這部份改正，如

 

接下來就是套用「基因演算法」的疊代過程直到收斂

找到最好的染色體 (解) 即為閥值

 

結論

1. 「基因演算法」是一個解決最佳化問題工具
    
2. 染色體不代表解的實際狀態，經過解碼後的才是
    
3. 適應函數、染色體、解碼方式在不同應用都不一樣且都需要人為設計

 

新手發文如有錯誤，煩請指正！