今天我們來把整個基因演算法作曲系列做一個完結。
前幾天我們花了很多篇幅一一講解整個基因演算法作曲的各種細節,包含個體與參數的設定、Crossover與Mutation的實做以及Fitness Function該如何設計,今天我們就來看看最後的適者生存、不適者淘汰 (Survivoe Selection) 的部份。
流程複習:
(1) 產生個體 (Individual)
(2) 交配 (Crossover)
(3) 突變 (Mutation)
(4) 評分 (Fitness Evaluation)
(5) 適者生存不適者淘汰 (Survivor Selection)
(6) 選出最強的個體成為最佳解
我們來整理一下這幾天我們做好設定的實驗參數以及其他設定:
在我們經過前面五個步驟之後,我們手上有的應該是
參數:個體 (Representation)
: 八個音符所組成的音樂。個體數量 (Population Number)
: 100個。音符範圍
: 0~24的數字 (中音Do到高兩個八度的Do)。交配的方法
: Two-Point Crossover。交配的機率 (Crossover Rate)
: 0.9。
(這個部份我前面講Crossover的時候漏掉了,但因為交配機率通常都是設定為比較高的值且相較於突變機率影響的沒有太大,所以就在這邊快速做個補充說明就好。)突變的方法
: 隨機突變 (Random Mutation)。突變的機率 (Mutation Rate)
: 1/8。適應值函數
: 基於樂理規則所設計出來的評估。演化的世代 (Generation)
: 100代。
個體:
100個親代以及每個親代對應的適應值(Fitness Score)
100個經歷過突變的子代以及對應的適應值(Fitness Score)
而接下來我們就要進到步驟(5)的適者生存不適者淘汰 (Survivor Selection)。
這個部份其實非常的單純且直觀,就如字面上的意思,我們依照每一個個體的 適應值 (Fitness Score) 來決定哪100個個體可以在Survivor Selection中存活下來並成為下一個新世代的親代; 而剩下的100個個體則被淘汰 (單壓!)。
一般來說,在做Suvivor Selection的時候有兩種常用的方式:
年輕人不講武德! - (μ , λ)
(念法: mu comma lambda)
μ表示的是親代的個體而λ則代表子代的個體,在 (μ , λ) 的淘汰機制裡面,年輕人不講武德,來騙!來偷襲!老年人大意了阿,沒有閃!
在步驟(5)的時候所有的親代會直接全數淘汰而所有子代自動成為下一個世代的親代。在這樣的機制下很容易會把所有個體裡面的最佳解給淘汰 (如果最佳解存在於親代之中)。
總要敬老尊賢吧! - (μ + λ)
(念法: mu plus lambda)
相對於不講武德的年輕人們, (μ + λ) 在演化上比較合理,一般稱之為菁英主義 (Elitism) 。
在敬老尊賢的前提下,親代並不會直接被淘汰,而是把所有親代與子代放在一起比較它門的Fitness Score,以一百個親代與一百個子代來說,在這兩百個個體裡面Fitness Score排名前一百的存活下來並成為下一個世代的親代 (適者生存); 而後面的一百名則被淘汰出場 (不適者淘汰)。因此下一個世代裡面組成親代的,有可能是這個世代裡的親代也可能是子代,端看誰得到的Fitness Score比較高。
在得到前一百名的個體之後 (部份親代+部份子代組成),這一百個個體成為新的親代並回到步驟(2),接著不斷的重複步驟(2)到步驟(5)直到演化的代數(100 Generation)為止。在這過程當中好的基因有高度的機率被保存下來 (好的基因代表在評分時可以拿到較好的評分,因次擁有好的基因的個體比較容易存活),而這些基因會在經過交配後傳承給子代,因此在整個演化的過程中,目的就是希望把所有好的基因留存並把差的基因給汰換掉。當我們到了最後一個世代後,再從最後這一百個個體裡面選出評分 (Fitness Score) 最高的,而這個個體就是我們最終演化出來的音樂。
最後我們快速補充一下Day 19我們說到的如何挑選交配的親代的方法:
除了交配有不同的方法之外,實際上在 挑選親代(Selection) 的時候也有幾個不同的方法,例如
輪盤抽選法 (Roulette Wheel Selection)
比較選取法 (Tournament Selection)
由於這部分要等我們解釋到步驟(5)適者生存不適者淘汰後才有辦法解釋,這邊我們先做個簡單的說明:
基本上不管是輪盤法還是比選法,主要的目的都是希望挑到比較好的個體來當作交配的親代,類似菁英主義的概念,因為以機率來說,擁有較好基因的父母一般來說更容易交配出較好的子代。但也不全然只有基因較好的個體有機會被選中來交配,這兩種方法裡面都有隨機性讓條件較差的個體依然有交配的機會。
這邊在做挑選的時候,也是以個體的評分值來當作參考依據,以菁英主義的概念來說,越強大的父母越有機會生出優良的小孩。
我們先解釋一下比較選取法 (Tournament Selection)
是如何運作的:
首先比較選取法 (Tournament Selection)
裡面我們會決定每次要選多少來做比較,例如2
-Tournament就是每次抓兩個個體出來,評分高的成為交配人選一,另外一個放回去; 然後再重新抓兩個個體出來比較,評分高的成為交配人選二,另外一個一樣放回去。而數字設定的越高,代表每次要抓出來比較的人數越多,也代表是否更加著重菁英主義。想想看如果今天我們設定的是2
,而你的評分在所有親代裡面排名倒數第二名,那麼雖然機率很低,但如果被抓出來和你比較的剛好是倒數第一名,則恭喜你成功進入交配環節; 但如果今天我們設定的是5
,那麼一來不但倒數四名都沒有機會進入交配環節,就連排名中間的也都必須承受更大的壓力 (每次挑選你都必須擊敗其他四人,因此精英能夠勝出的機率更高)。
而輪盤法
則是提供所有個體都有交配的機會,即使你是所有個體中最差的。
輪盤法的運作方式是依照每個個體的分數排名來做比例調整,在一個圓盤中評分越高的所占的比例則越高,被選中的機率也更大; 但即使是排名倒數第一的仍然有機會雀屏中選,只是機率相較其他競爭者低很多。
到此我們的基因演算法作曲告一段落,明天我們再來看看類神經網路要如何套用到作曲上面。