馬爾可夫模型在遺傳算法中的應用

于景茹 李保華 趙澄東

摘 要：本文介紹遺傳算法的基本思想，提出了遺傳算法的兩個重要的參數交叉率和變異率，并利用馬爾科夫模型對其進行了分析。

關鍵詞：遺傳算法；交叉率；變異率；馬爾可夫模型

DOI：10.16640/j.cnki.37-1222/t.2016.07.241

1 引言

遺傳算法滿足有限馬爾可夫鏈的基本特征，具有齊次性，存在極限概率分布。將馬爾可夫模型用于遺算法，已有相關的研究。例如，在1987年，Goldberg和Segrest[1]運用有限馬爾可夫鏈理論對遺傳算法進行了收斂性分析，Rudolph用齊次有限馬爾可夫鏈證明了帶有選擇、交叉和變異操作的標準遺傳算法收斂不到全局最優解，但是如果讓每一代群體中的最佳個體不參加交叉與變異操作而直接保留到子代，那么遺傳算法是收斂的。

本文主要是在學習了隨機數學和遺傳算法的基礎上，在查閱大量相關資料的前提下，對馬爾可夫模型在遺傳算法中的應用做了一個闡述，通過這樣一個學習與總結的過程，促使本人對遺傳算法和馬爾可夫模型有一個更為深刻的認識。

2 遺傳算法的基本思想

遺傳算法是基于達爾文的自然選擇和進化原理。遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有某種特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因性）是某種基因組合，它決定了個體的形狀的外部表現。初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解。在每一代，根據問題域中個體的適應度大小挑選個體，并借助于自然遺傳學的遺傳算子進行交叉和變異，產生新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應域環境。經過若干代的遺傳后， 就能夠進行適應度最大的個體的搜索， 從而完成最優化問題的最優解的求解。

基本的遺傳操作是由選擇、交叉、變異三個遺傳算子來進行的。選擇是指根據預先定義的適應度函數來隨機的選擇合適的個體進行復制， 并將其拷貝到下一代；交叉是指在繁殖下一代時兩個同源染色體之間通過交叉重組，亦即在兩個染色體的某一相同位置處DNA被切斷，其前后兩串交叉組合形成兩個新的染色體。這個過程成為基因重組，俗稱雜交。變異是指在細胞進行復制時，可能易很小的概率產生某些輔助差錯，從而使DNA發生某種變異，產生出新的染色體，這些新的染色體產生新的性狀。代中選擇兩個個體并在它們之間進行遺傳物質的交換；變異是隨便的改變包含在種群個體中的信息，從而增強種群的多樣性。

我們可以認為進化是探求更好的串（染色體）的過程。交叉和變異在探求的過程中承擔著一個導向的任務。其中交叉率х就是一個重要的因素，兩個串以一定的概率χ進行交叉。每對交叉的串是根據它們的適應度進行隨意選擇的。一般來講，交叉算子結合了兩個串的優勢從尋求更優的結果。

變異算子采用變異率μ扮演多樣性的角色。在均衡的變異中，變異在串的每一位上都進行操作，而每一位以概率μ進行變異。變異率通常設為很低，例如0.1%。如果某一位發生了變異，那么該位就發生了改變，從0變為1或者從1變為0。變異操作的目的是為了增加新的串。

3 遺傳算法的馬爾可夫模型

遺傳算法是不斷重復雜交、變異和選擇的過程。每一種遺傳機制都與當前種群狀態有關，而與以前的種群狀態無關。因此遺傳算法是一個馬爾可夫鏈。Vose于1990年第一次準確的提出了簡單遺傳算法的模型。1999年Vose[5]再次對其做了一定的擴展。