馬爾可夫模型在遺傳算法中的應(yīng)用

于景茹 李保華 趙澄東

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

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

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

1 引言

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

本文主要是在學(xué)習(xí)了隨機(jī)數(shù)學(xué)和遺傳算法的基礎(chǔ)上，在查閱大量相關(guān)資料的前提下，對(duì)馬爾可夫模型在遺傳算法中的應(yīng)用做了一個(gè)闡述，通過(guò)這樣一個(gè)學(xué)習(xí)與總結(jié)的過(guò)程，促使本人對(duì)遺傳算法和馬爾可夫模型有一個(gè)更為深刻的認(rèn)識(shí)。

2 遺傳算法的基本思想

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

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

我們可以認(rèn)為進(jìn)化是探求更好的串（染色體）的過(guò)程。交叉和變異在探求的過(guò)程中承擔(dān)著一個(gè)導(dǎo)向的任務(wù)。其中交叉率х就是一個(gè)重要的因素，兩個(gè)串以一定的概率χ進(jìn)行交叉。每對(duì)交叉的串是根據(jù)它們的適應(yīng)度進(jìn)行隨意選擇的。一般來(lái)講，交叉算子結(jié)合了兩個(gè)串的優(yōu)勢(shì)從尋求更優(yōu)的結(jié)果。

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

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

遺傳算法是不斷重復(fù)雜交、變異和選擇的過(guò)程。每一種遺傳機(jī)制都與當(dāng)前種群狀態(tài)有關(guān)，而與以前的種群狀態(tài)無(wú)關(guān)。因此遺傳算法是一個(gè)馬爾可夫鏈。Vose于1990年第一次準(zhǔn)確的提出了簡(jiǎn)單遺傳算法的模型。1999年Vose[5]再次對(duì)其做了一定的擴(kuò)展。