iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
0

先來複習一下昨天講的的東西,再來開始吧!
(又是一樣的開頭,沒梗啦~~)


我們提到了 交配(Crossover) 的單點、雙點以及多點的方式
這些方式的差異在於是交換點的數量

  • 單點法就是透過單一一個交換點將染色體做區分
  • 雙點法則是以兩個交換點將染色體截斷分成兩個部分
  • 多點法是以多個交換點將兩個染色體的基因互換

今天要講解的一樣是交配的部分~~~
基因演算法流程-交配

昨天還有一個交配法- 套選交配(uniform crossover method) 沒有說完
幫大家回憶一下這幾種交配的方式(當然可能全部不只這些,這邊說的是常見的)
基因演算法-交配種類

套選交配(uniform crossover)

套選交配又被稱之為均勻交配
那為什麼會有這個交配方式呢?
從上面的單點、雙點甚至是多點
可以發現到會一次替換掉某一整段的基因(Gene)
而這樣的做法可能會使那一整段的基因(Gene)可能已經有部分收斂了
但是卻被取代掉
導致已經收斂到好的程度的基因序列消失
所以就會延伸出套選交配
套選的方式會產生一組二進為的編碼->稱之為遮罩(mask)
透過遮罩的方式來比對父染色體
當遮罩中編碼為1的基因位置就必須兌換
進而產生出新的結果
這樣講有點難懂,直接透過圖片來講解吧~~

這個部分有點小難度(一點點)
那我會透過數字和字母的方式來說明
(1) 數字
首先,原始的父染色體
可以看到中間我放了一個遮罩(mask)
透過這個遮罩去變換需要替換的基因
當遮罩(mask)的數字為1的時候
就表示我要將其替換掉或是交換

套選交配-原始
更換的位置可以看到底色有所不同
將兩者的基因(Gene)互換
套選點交配-完成
這樣就會產生新的染色體~

(2) 字母
上面的變換不知道大家有沒有理解
那我換成英文字母來講解,讓大家更能夠瞭解
首先,原始的父染色體
可以看到中間我放了一個遮罩(mask)
透過這個遮罩去變換需要替換的基因

當遮罩(mask)的數字為1的時候
就表示我要將其替換掉或是交換

套選交配-原始
更換的位置可以看到底色有所不同
將兩者的基因(Gene)互換
套選點交配-完成
這樣就會產生新的染色體~

今天為大家介紹完基因演算法的 交配 的部分
希望大家可以理解這部分的概念
有任何問題都可以在下方提問
這樣的講解方式讓大家可以更清楚理解基因演算法的細節
一步一步帶著大家理解
後面就剩下突變(mutation)的部分
理論的部分講完就要開始實作囉~~~
p.s.如果圖片有做錯的地方也請多多提醒,做得眼花撩亂


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


上一篇
【Day07】GA with you - Crossover 交配 (1)
下一篇
【Day09】GA with you - Mutation 突變 (1)
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言