iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
0

又迎來了最困難的週三滿堂日

打起精神更新~~


在昨天跟大家介紹了圖片
後來在查資料的時後發現他跟交配有點像似
他有單點突變、雙點突變和字罩突變(套選突變)
那我們就簡單介紹這幾個

單點突變(single point mutation)

這個就是昨天說介紹到的
隨機的指定一個基因(Gene)進行突變
單點突變

雙點突變(two-point mutation)

這個跟單點突變十分相似
不同在於突變點有兩個
就是會隨機選機染色體中的兩個基因(Gene)進行突變
雙點突變

套選突變(字罩突變)(Uniform mutation)

Uniform mutation常見的講法均一突變套選突變字罩突變
在寫了這麼多篇後發現其實好比較常有人稱這種方式為字罩突變
因為他有運用到 遮罩(Mask) 的部分
透過遮罩(Mask)去控制要突變的基因(Gene)
套選突變


以下就是純屬介紹額外的突變種類(就是頗學術理論層面的突變)

此外,還有在資料中查到倒置突變(inversion mutation)Scrable MutationSwap Mutation....
(從這邊開始有講錯的務必跟我說啊啊啊~)

倒置突變(Inversion Mutation)

什麼是倒置突變呢?
就是會將染色體中某部分的基因序列倒置
(千萬別打我,就真的是這樣rrr)
那他是怎麼樣運作呢?
老樣子,用圖片說明
倒置突變
從圖片中可以發現會隨機選定兩個突變點
再將兩個突變點之間的基因序列進行反轉(substring)
進而產生新的染色體
而這樣的做法,保留了大量的訊息卻也打亂了原先的順序

Scramble mutation

這個的中文應該是干擾突變/打亂突變(????
中文資料比較少,沒有看到一個固定(多數)的講法
這個其實跟倒置突變有點相似
基因的內容並不會改變
而是改變了染色體中某一段基因的位置
就是把某段基因序列打亂
Scramble mutation的做法也是會選擇兩個突變點
之後將這兩個突變點的基因(Gene)打亂但不改變內容
有點像是大風吹改變位置
一樣用圖片說明
Scramble Mutation

交換突變(Swap Mutation)

學過一些排序程式的朋友對於這個單字Swap應該就不陌生了
就是交換(Swap)的意思
所以就是把染色體中兩個基因(Gene)的位置進行交換
交換突變的作法也是要先選出兩個突變點
再將突變點的基因(Gene)進行交換
Swap Mutation

透過圖片的說明大家有沒有更懂一些呢~
希望這些突變的介紹可以讓大家更加理解突變


今天回顧昨天寫的時候發現講的有一點點的不清楚在於為什麼要用突變的部分~
並不是說透過突變就一定可以避免區域最佳解等等
而是透過突變的特性來避免一整個世代/族群裡的染色體都過於相似
舉例來說,我都覺得樹都要長個高才較好(可能只有我)
所以把矮的樹都淘汰掉了
剩下的樹是不是都過於接近
但是在其他平行時空(?)卻可能發現某一種矮的樹更適合我們
所以要透過突變來防止結果掉入一個解中
使得進化過程漸漸趨近於某一個解或是就此停止
(還記得基因演算法的中止條件嗎???達到目標就會結束)
所以這個道理也可以用來說明為什麼基因演算法避免使用最適合/最優秀的染色體來產生子代
而是會透過交配/突變等機制來隨機的產生一些不一樣(奇怪)的子代(offspring)


明天會給大家帶來整個基因演算法流程的複習
之後就要正式開始我們的實作的部分
相信有些朋友心想這傢伙終於要開始介紹實作了
我也知道很多朋友看我的系列都是為了實作基因演算法
不想看這些漏漏長的理論說明
但我還是覺得有充分的學理知識再開始會比較好
(因為以前BOSS問我的時候我都答不清楚)
(還常常講錯沒有搞懂原理就開始寫程式)
(明明是自己不認真還想拖大家下水xdd)

p.s.打完今天的文章都懷疑自己突變/圖片傻傻分不清楚 一直打錯字


相關資料來源:

  • 林豐澤・2005。演化式計算上篇:演化式演算法的三種理論模式。智慧科技與應用統計學報,3(1),1-28。
  • 林豐澤・2005。演化式計算下篇:基因演算法以及三種應用實例。智慧科技與應用統計學報,3(1),29-56。
  • 林昇甫、徐永吉・2009。遺傳演算法及其應用・五南圖書出版。
  • 突變(遺傳演算法)。2013。突變(遺傳演算法)。維基百科,自由的百科全書。
  • Soni, N., & Kumar, T. (2014). Study of various mutation operators in genetic algorithms. International Journal of Computer Science and Information Technologies, 5(3), 4519-4521.

上一篇
【Day09】GA with you - Mutation 突變 (1)
下一篇
【Day11】GA with you - GA Process Review 流程回顧
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言