2012年6月4日 星期一

基因演算法 (二) 交配 (Genetic Algorithm Part II : Crossover)


基因演算法的交配過程,乃是由複製所得到的結果中,隨機將基因配對,再利用「單點交配」、「雙點交配」、「字罩交配」等方式進行。由於自然界中並非所有被配對的基因都會進行交配,故有交配率 (Crossover Rate) 的產生;開發程式時,則是針對每一組被配對的基因,以亂數值(介於 0 與 1 之間)來決定是否交配,若得到的數值小於交配率,則進行交配,反之則否 (筆者較常將交配率設為 0.8)。



以下將以圖示說明「單點交配」、「雙點交配」、「字罩交配」三種交配方式:

1) 單點交配:隨機選一交配點,將二基因字串自該交配點以後的所有位元進行互換。



2) 雙點交配:隨機選出兩個交配點,將此二基因字串兩個交配點間的所有位元互換。


3) 字罩交配:隨機產生長度與基因碼相同的 0、1 字串 (此即字罩),字罩中為 1 的字元就是要進行互換的部份。


接著進入該世代的第三階段:突變