跳至內容

染色體 (遺傳演算法)

維基百科,自由的百科全書

遺傳演算法裏面,一個染色體(chromosome,有時候也叫做基因,genome)是一些引數構成的集合,用來定義遺傳演算法嘗試解決問題的各種答案可能。 染色體常常使用一個簡單的字串來表示,不過有很多種其他的資料結構也可以使用。

染色體設計

[編輯]

染色體的設計跟引數使用是根據被解決問題的特殊需求來設定的。一個簡單的範例是,我們假設一個問題是要找出一個整數,介於0和255之間,且能給出這個函數的極大值。(一般這個問題不會使用遺傳演算法,因為直接計算可以很快的找到解答。不過我們這裏只是作個簡單的範例。)我們所有可能的解答是0到255的整數,而這一些可能都可以用一個8位元的二進位字串來表示。 因此,我們就可以選用8位元的二進位字串來作為我們的染色體。這樣的話,如果在我們族群(population)裏面其中一個染色體代表的答案是155這個整數,那染色體本身可能就是10011011這個字串。

更實際一點的問題是我們可能想要解決一個旅行推銷員問題。對這個問題,我們的目的是要找出一個距離最短,讓我們的推銷員可以拜訪完所有城市的順序。假設我們現在有六座城市,分別是 A、B、C、D、E、和F。那麼一個照順序列出拜訪城市的字串可能就是一個不錯的染色體設計。這樣設計的話,像是DFABEC就是我們可能在族群內遇到的其中一個染色體。

會在遺傳演算法裏面使用到的突變運算元(mutation operator)和交配運算元(crossover operator)對整個族群的影響也必須要在設計染色體的時候給予考量。

參考資料

[編輯]