iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 5
0
AI & Data

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

【Day05】GA with you - Reproduction & Selection 複製與選擇 (2)

每天的開場好像都差不多
不過不要緊,歡迎堅持下來的你
與我一起努力,就要迎來萬惡的週末
一個昏睡就會忘了發文,希望明天可以見到大家


昨天跟大家提到了隨機選擇(Random Selection Schema)、分裂選擇(Disrupt Selection Schema)、機率選擇(Proportionate Selection Schema)和菁英選擇這幾種
那今天會一一為各位介紹的~~~
Imgur

隨機選擇(Random Selection Schema)

顧名思義就是隨機的方式做選擇,
但當隨機選擇中帶有機率性的去選擇就是機率選擇。

分裂選擇(Disrupt Selection Schema)

機率選擇(Proportionate Selection Schema)

機率選擇故名思義就是透過一個比率來選擇,而又分成了輪盤式選擇、競爭式選擇和等級輪盤式選擇。
在這裏不會僅挑選適應程度最高的原因是這樣的做法可能導致局部最佳解,而非整體最佳解。
這邊就會有人質疑了,為什麼挑選適應程度最好的會發生局部最佳解呢?
假設我現在有10樣要去選擇,但是前三樣我都挑選最好的,後面七樣相較之下都是最差的就會拖垮全體。
所以在挑選時,不會把選擇方式綁死,會有彈性~
希望這樣的解釋大家可以明白~~~

這邊介紹一下機率選擇中的幾個種類:
介紹的時候就假定我們族群(Population)有10個
適應程度列表

1. 輪盤式選擇(Roulette Wheel Selection)
輪盤式可以想像就是用一個輪盤來去選擇
該輪盤個別的大小是會按照適應程度去規劃的
適應程度越好,所佔有的面積就越大
適應程度越差,所佔有的面積就越小
如此以來,在選擇時適應程度越好的,也越有機會被選中
輪盤式選擇

**2. 競爭式選擇(Tournament Selection) **
競爭式選擇,聽起來就很競爭,其實就是“競爭”
他是怎麼競爭呢?
會隨機選取兩個物種,比較其適應程度,適應程度較好的保留,適應程度較差的淘汰
適應程度比較好的就會保留到下一階段的交配Crossover了~
在這邊就可以發現到在選擇時就是物競天擇,當你在環境的適應程度較差時,就會被其他物種所取代

競爭式選擇

3. 等級輪盤式選擇(Rank Based Wheel Selection)
等級輪盤式就比較少聽到了,也是在做研究的時候才發現
那什麼是等級輪盤式呢?
如上面我們所寫的族群列表,會先根據適應程度的大小進行排序,
每一個染色體都會按照適應值程度進行排序
我有算出輪盤式和等級輪盤式之間在面積上所佔比例的差異
可以看到,等級輪盤式會根據他的排名依序遞減他所佔面積的比例
這樣的作法是為了避免收斂速度過快
等級輪盤式選擇克服了停滯或是過早收斂的問題
相較其他的選擇方式也比較穩定
等級輪盤式

菁英選擇

這個選擇機制是建立在上面幾種之後,或是之前也是可以的
從上面可以知道,較好的不一定會被保留,較差的也不一定被淘汰
假設前面我使用「競爭式選擇」,當我的No.1和No.2比較,No.2就會被淘汰,而No.3和No.10比較,No.3被保留
就會發現剩下的可能是No.1,No.3.....
那我們的No.2就這樣被淘汰掉了,是不是太可惜
所以就延伸出了『菁英選擇
這種菁英選擇就是可以去假定我們要保留在這個世代中最好的幾個
這個世代有100個,我要保留最好的5個,我就可以確保最好的這5個染色體被保留下來
就不會發生前面舉例的No.2被淘汰
希望這樣的說明大家可以理解
後面再實作的文章中也會實際使用菁英選擇的方式讓大家可以操縱~~


今天的選擇時光就到這邊了,
話說圖片好多ㄚ~~
想說要用圖片比較清楚的讓大家明白
結果就越做越多張
希望這些圖片有助於大家瞭解
題外話,
說實在的圖片上傳這邊我還有待研究
Imgur的圖片要怎麼讓他再縮小一點???
版面大小的問題希望後面的我可以克服(擦汗)

週末也要記得回來學習喔~~~(對著自己說)
有問題或是表達不清楚的在下面留言告訴我
你的問題或許也是別人的疑慮
謝謝大家


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


上一篇
【Day04】GA with you - Reproduction & Selection 複製與選擇 (1)
下一篇
【Day06】GA with you - Reproduction & Selection 複製與選擇 (3)
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言