今天我們繼續介紹基因演算法作曲。
昨天我們介紹了如何讓電腦看得懂音樂/音符的樣子以及如何對基因演算法裡的個體做設定,今天我們照著步驟來介紹個體之間彼此 交配(Crossover) 的部分。
基因演算法流程:
(1) 產生個體 (Individual)
(2) 交配 (Crossover)
(3) 突變 (Mutation)
(4) 評分 (Fitness Evaluation)
(5) 適者生存不適者淘汰 (Survivor Selection)
(6) 選出最強的個體成為最佳解
所謂的交配,就是...
嗯...
那個...
就是呢...
ㄟ...........
就是洞房囉~
在這個步驟我們必須要讓這一百個親代間彼此交配並生出跟親代同樣數量,也就是一百個子代。
在基因演算法裡面在做交配時有幾個比較常用的方法,例如單點交配 (One-Point Crossover)
雙點交配 (Two-Point Crossover)
多點交配 (Multi-Point Crossover)
套選交配 (Uniform Crossover)
等等,如果全部講解的話讀者們大概會是這樣的狀態
因此我們選其中的雙點交配
來當當作範例詳細解釋交配(Crossover)的時候到底在幹什麼
首先我們先請今天的男女主角出來示範如何執行交配的動作
個體1 (男主角) : [0, 2, 0, 9, 15, 24, 16, 10]
個體2 (女主角) : [6, 2, 9, 17, 17, 17, 3, 17]
而所謂的雙點交配
,就是我們要選擇兩個點來當作 交配的地點 基因轉換的地方,通常是用隨機來決定決定這兩個點的位子,例如我們選擇在第三個音與第六個音當作我們的點位,則這兩個個體就會在第三到第六個音符中間交換彼此間的基因並產生兩個新的子代。
親代個體1 : [0, 2, 0, 9, 15, 24, 16, 10]
親代個體2 : [6, 2, 9, 17, 17, 17, 3, 17]
粗體部分即為要交配的位子,而透過內部基因的轉換,我們就可以得到兩個新的子代個體
子代個體1 : [0, 2, 9, 17, 17, 17, 16, 10]
子代個體2 : [6, 2, 0, 9, 15, 24, 17, 3, 17]
而這樣的過程我們不斷的重複,每次都重新選擇兩個親代來做交配並產生兩個新的子代,直到我們產生出100個子代為止。
除了交配有不同的方法之外,實際上在 挑選親代(Selection) 的時候也有幾個不同的方法,例如輪盤抽選法 (Roulette Wheel Selection)
比較選取法 (Tournament Selection)
由於這部分要等我們解釋到步驟(5)適者生存不適者淘汰後才有辦法解釋,這邊我們先做個簡單的說明:
基本上不管是輪盤法
還是比選法
,主要的目的都是希望挑到比較好的個體來當作交配的親代,類似菁英主義的概念,因為以機率來說,擁有較好基因的父母一般來說更容易交配出較好的子代。但也不全然只有基因較好的個體有機會被選中來交配,這兩種方法裡面都有隨機性讓條件較差的個體依然有交配的機會。
(今天好像整篇都在開車...................)
那麼我們到這邊先告一個段落,明天再來繼續聊聊交配後產生的子代接下來要面對的各種殘酷舞台。