突變 (遺傳演算法)

遺傳演算法裡面,突變是用來維持演算法裡面,族群(population)裡面每一個世代的染色體到下一個世代時,還能夠維持遺傳多樣性的一個遺傳運算元(genetic operator)。這個運算元設計上雷同於生物學方面的突變(這也就是這個命名的由來)。

有一種經典的突變運算元範例,會牽涉到將染色體裡面任意位元從原來的狀態改掉的機率。常用來實做這種突變運算元的方法是對染色體字串的每個位元分別產生一個隨機變數。這個隨機變數用來告訴我們這個特定的位元是否要被修改。這種突變的過程叫做單點突變(single point mutation),因為他的設計基於生物學上的點突變。其他的突變方式包含倒置(inversion)和浮點突變(floating point mutation)。 當基因的設計以排列問題的形式限制,那突變的方式就會變成交換,倒置或者打亂。

遺傳演算法裡面突變的目的在於維持並且提昇多樣性。突變應該要能夠藉由避免讓族群裡的染色體過於相近,來防範演算法掉入區域極值,因此減慢或者停止進化過程。相同的理由也可以用來解釋為何大多數遺傳演算法的系統避免只使用最適合的染色體來產生下一代 ,而是在一些比較適合的裡面隨機(或者半隨機)的選擇出一些來產生下一代。

参见

參考資料