iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
0
AI & Data

GA Note - 基因演算法的世界系列 第 11

【Day11】GA with you - GA Process Review 流程回顧

歡樂星期四XDDD
因為明天沒課(開心)
但是要報Paper還有計畫等著我呢(崩潰)


今天的內容呢大家可能會覺得搞什麼
出一篇什麼Review
出來充篇數的是嗎(怒)
但是這篇是為了明天做準備的
不知道前面的10篇文章大家有沒有認真看
希望大家還有繼續在追蹤這個系列

有鑒於前面的內容太過於長篇大論
所以出一篇簡單的瀏覽與複習
讓沒有認真看我前面的文章也可以快速銜接上
何謂是基因演算法
基因演算法的流程
先來個總覽
基因演算法流程
想必大家對這張圖並不陌生吧
今天會用程式的角度來講解這個流程

Step 1 - 設定參數

在圖片中沒有看到
但要設定什麼參數呢??

  1. 族群的大小(Population Size):每一個世代有多少個染色體
  2. 染色體的長度(Length of Chromosone):一個染色體中包含了多少個基因(Gene)
  3. 交配機率(Crossover Rate/Probability):發生交配的機率,並不是每次都會發生,而是達到交配機率才會進行交配
  4. 突變機率(Mutation Rate/Probability):發生突變的機率,也是要達到突變機率才會進行突變,通常突變率會設定在0.005~0.01之間,不會設定過高
  5. 終止條件(Termination Criteria):可以設定適應值的程度或是世代數等等來進行收斂

Step 2 - 初始族群(Initialize Population)

前面第一步驟定義的族群的大小
前面是讓自己知道,開始撰寫的時候就把數值帶入即可
那麼這麼就會要透過這個大小來產生出一定數量的染色體(Chromosome)

Step 3 - 計算適應函數(Calculate Function)

所謂的適應函數就是用於計算染色體對於目前條件或是目標的適應程度
(以自然界來說,可以理解成該目前這個物種對於現在環境的適應程度)

在程式撰寫過程中,適應函數就會像是一個額外的函數
當你將染色體當成參數帶入其中

而適應函數所計算出來的值就稱之為「 適應值(Fitness Value)
而這個適應值也可以用來當作終止條件之一
例如當適應值大於某數,則滿足停止條件,就會結束整個流程。

Step 4 - 交配(Crossover)

在交配的階段會根據透過Step1發生交配
交配的種類就主要有單點交配、雙點交配和字罩交配這三種,其餘的交配方式可以回到

【Day07】GA with you - Crossover 交配 (1)
【Day08】GA with you - Crossover 交配 (2)

Step 5 - 突變(Mutation)

而到了突變階段也會透過Step1所設定的突變率去計算
會讓每一個染色體都計算是否要突變
當該染色體的突變率低於所設定的突變率時則會產昇突變

突變主要是開發新的搜尋區域,發現更多可能性,避免發生區域最佳解。

【Day09】GA with you - Mutation 突變 (1)
【Day10】GA with you - Mutation 突變 (2)

Step6 - 計算終止條件

經過交配、突變後會再次計算新的子代的適應程度,
並判斷是否有符合終止條件,
當符合終止條件,就會結束基因演算法的計算流程;
而若不符合終止條件,則會回到Step3反覆執行,
直到符合終止條件。


明天就要正式開始了
接來的一週(大約)都會來介紹R語言如何實作
之後在介紹Python如何實作
在這邊有任何相關的想法都可以留言告訴我
(雖然都沒有人留言 傷心)
思考有需要出一篇安裝R的教學嗎???
但是大家應該可能或許都已經在其他的大神那邊拜讀過了(掙扎ing)
反正,明天的內容是什麼等明天的我來思考(欠揍)
老話一句,希望明天可以見到大家
也希望這個系列給予在這條古老的路上的人有所幫助


相關資料來源:

  • 林豐澤・2005。演化式計算上篇:演化式演算法的三種理論模式。智慧科技與應用統計學報,3(1),1-28。
  • 林豐澤・2005。演化式計算下篇:基因演算法以及三種應用實例。智慧科技與應用統計學報,3(1),29-56。
  • 林昇甫、徐永吉・2009。遺傳演算法及其應用・五南圖書出版。

上一篇
【Day10】GA with you - Mutation 突變 (2)
下一篇
【Day12】GA with you - Develop on R 環境安裝
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言