2012年6月5日 星期二

基因演算法 (三) 突變 (Genetic Algorithm Part III : Mutation)


基因演算法在完成交配過程後,可針對基因進行突變的模擬。由於突變並非經常發生,故有突變率 (Crossover Rate) 的設計;開發程式時,以亂數產生的值決定突變位元、或該位元是否發生突變 (視所採用的突變方式而定)。


若得到的數值小於突變率,則進行動作,反之則否 (筆者較常將突變率設為 0.1),以下將以圖示說明三種突變方式:

1) 單點突變:在基因字串中隨機選一突變點。同時隨機產生突變機率數值(介於 0 與 1 之間),若此數值小於突變率,則將該突變位元進行 0 與 1 互換。



2) 全基因突變:基因字串的每一個位元均視為突變點。針對每一位元均產生一亂數值(介於 0 與 1 之間),若此數值小於突變率,則將該位元進行 0 與 1 互換 。



3) 字罩突變:隨機產生長度與基因碼相同的 0、1 字串 (此即字罩),字罩中為 1 的字元就是突變點。針對每一突變點均產生一亂數值(介於 0 與 1 之間),若此數值小於突變率,則將該位元進行 0 與 1 互換。



完成突變過程後,即得該世代的正式成員,而後再重複 複製交配、突變 來產生下一世代。當發現某世代的最適函數值(Fitness Function Value)不再變動、或已到達原先設定要產生的世代數目,則停止作業,找出最後一世代的最適函數值最大者即為答案。