about 1 year ago

最近對於啟發式演算法相當感興趣,所以決定自己動手研究一番,在網路上看到十分棒的教學
Creating a genetic algorithm for beginners
Applying a genetic algorithm to the traveling salesman problem
Simulated Annealing for beginners
Solving the Traveling Salesman Problem Using Google Maps and Genetic Algorithms:作者將旅行家問題套用在Google Maps上顯示,並用基因演算法解決
程式人雜誌 2014/05:有介紹爬山演算法與模擬退火演算法

我主要會部分翻譯文章內容,並將裡頭的範例程式碼改用JS編寫,最後在canvas上顯示。

基因演算法

基因演算法(GA)主要用來解決複雜的搜尋問題,像是工程上需要透過大量組合去找出最佳解的問題,像是透過不同的元素與架構設計組合出更好、更堅固的產品,在電腦演算法上用來工作排程、解決其他優化問題;
基因演算法主要源自於大自然天擇的概念,不斷經歷基因突變、篩選循環的過程找出最適合環境的基因,看似複雜但其實基因演算法相當的直覺、簡單。
以下是基因演算法的步驟:

  1. 初始化
    基本上是隨機生成
  2. 審核適應度
    計算當前基因的適應程度(fitness),用來表示當前的最佳解(也就是基因)跟我們預期的結果相似度多少,這評判的條件取決於需求,像是越快越好、越耐撞但同時重量不可太重等評估方式
  3. 篩選
    我們希望基因可以越來越進步,所以在篩選階段留下好的(fitter)基因並剔除不好的,篩選的方式有很多種但概念都是一樣的,找出適應度最好的基因。
  4. 交叉配對
    模擬大自然中性別的概念,將篩選出來的基因做交配,保留父代(parent)中好的部分,希望可以組合出更棒的子代。
  5. 改變
    自然中存在著基因突變的現象增加多樣性,同樣的加一些隨機的微小調整於一小段基因上。
  6. 持續2~5步驟,完成一輪稱為一個世代(generation)
終止條件與侷限

終止條件通常是達到預定的目標效果或是超過設定的時間與成本;

基因演算法的侷限在於 可能陷入次佳解,設想今天你在爬山,目標是爬到最高的山丘上,當你爬到某個高點時(peak)你就會以為找到全域最高峰,但有可能只是局部的最高峰而已;

猜數字解決實戰基因演算法

此範例用隨機生成數字列,接著用基因演算法去產生0,1數字列並比對,目標是產生與目標一模一樣的數字列。
如果是暴力法的話,最差運算量大概是 2的n次方,數字列長一點運算量就大得驚人。
以下是我參照教學用JS改寫的範例

在基因演算法中有分成幾個物件

  1. Individual:
    包含基因段的個體,也就是現行解(基因段)
  2. Population:
    群體,也就是多個個體的組合,群體的重點是找出現行最佳解個體、控制交配與突變找出下一代、篩選出下一代的群體,篩選的機制很重要,按照教學是實作競爭法。
  3. Fitness: 評斷個體的適應度,有正確的評判標準是找出最佳解的關鍵。

要套用基因演算法在不同問題上,就需要特別修改Individual的基因段、Population的交配與突變機制、Fitness的評判標準,像是在猜寫數字列題目中,

Individual的基因段 => [1,0,0,1.......]
Population的交配 => child的基因段 genes[i]隨機來自 parent1 genes[i]或parent2的
Population的突變 => child的基因段 genes[i]隨機改變
Fitness的評判標準 => 答案[0,1,1....] 跟 個體基因[1,0,1....]在同一位置上的基因相似度

基本上就是這幾點需要客製化,其中比較麻煩的是交配,要考慮交配時保留父代的優點,其他的流程與篩選方式都不變,接著就來挑戰旅行家問題

旅行家問題

如何將基因演算法套用在旅行家問題(城市到城市間交通成本不一,需要路過所有城市,找出最低的花費)上呢? 首先來思考上面幾點需要客製的問題

/* 基因段,變成城市的代號,每個城市必須出現一次也不可重複出現 */
Individual的基因段 => [1,5,3,4,....]

/* 交配與突變,必須遵照基因段的限制 */
Population的交配 => 為了保留父代優點(片段行程是最優化),先隨機找start/end,取出parent1片段繼承給子代,剩下的行程參照parent2依序補入子代
Population的突變 => 行程上的兩城市順序互換

/* 將基因段換算成旅行成本,越低越好 */
Fitness的評判標準 => 將基因段換算成旅行成本,越低越好

腦袋突然一閃而過 如果city是點,city與city間的交通是線這樣就組成graph,能不能用MST最小展開樹解呢?
當然是不行啊! MST是找出一個樹用最小成本展開所有節點,而旅行家問題要考慮點到點連續的路徑,所以是不同的~

有了以上概念,接著就直接實作,為了方便起見多宣告 city / tour物件,tour管理所有city<->city的交通成本

蟻群演算法

這部分資料有點難找,不然就沒有附程式碼可以參考,後來找到這兩份文件,動手自己將psuedo-code轉為程式碼
An ant colony optimization method for generalized TSP problem
Show ant-colony-optimization-for-solving-the-traveling-salesman-problem

蟻群演算法的內容大概是:

  1. 隨機生成數隻螞蟻,並放在任意的出發點
  2. 每個螞蟻依照費洛蒙,機率性(費洛蒙高者機率高)往下個城市出發,一路到遍歷所有城市
  3. 計算路徑花費,更新費洛蒙,接著回到第二步 iteration數次 費洛蒙的計算公式可以參考第一篇文章,基本上就是路徑花費越高費洛蒙就會調低,所以隨著循環幾次某些路徑的費洛蒙就會提高許多,大多數螞蟻也就往那邊探索。
← Vuejs全端框架 Nuxtjs - 推坑分享與教學 微軟AI服務 - QnAMaker 服務初探與串API →
 
comments powered by Disqus