本文最早發(fā)表在本人博客http://www.gotoli.us/?p=1514

遺傳算法是一個(gè)模擬生物進(jìn)化的算法秽荞，并不是從數(shù)學(xué)推導(dǎo)出來(lái)的。因此很多人直覺(jué)認(rèn)為岗宣，遺傳算法并不需要數(shù)學(xué)基礎(chǔ)蚂会。為什么還有人去探究遺傳算法的數(shù)學(xué)基礎(chǔ)呢？一是滿足我們的好奇心耗式，二是遺傳算法數(shù)學(xué)基礎(chǔ)真的有些用的Ｐ沧　！刊咳！在介紹遺傳算法數(shù)學(xué)基礎(chǔ)之前彪见，先定義一些符號(hào):

因?yàn)橛懈鞣N各樣的編碼方式、變異操作娱挨、交叉操作和選擇操作余指，遺傳算法的形態(tài)呈現(xiàn)多樣性。這里只介紹針對(duì)典型遺傳算法的分析跷坝。那么什么是典型遺傳算法呢酵镜？典型遺傳算法：

1. 編碼方式是二進(jìn)制編碼：基因的取值只能是0或者1。
2. 變異操作將所有染色體所有基因位以pm的概率翻轉(zhuǎn)柴钻。
3. 交叉操作選擇選擇相鄰的個(gè)體淮韭，以pc的概率決定是否需要交叉。如果需要交叉贴届，隨機(jī)選擇一個(gè)基因位靠粪，并交換這個(gè)基因位以及之后的所有基因。
4. 選擇操作有放回地采樣出原種群大小的新一代種群毫蚓，個(gè)體I_i的采樣概率如下所示占键。這種選擇操作又被稱為輪盤賭選擇。

模式定理

模式定理是遺傳算法創(chuàng)始人 J.Holland 在其突破性著作《Adaptation in Natural and Artificial Systems》引入的元潘，用于分析遺傳算法的工作原理畔乙。模式是指編碼空間中相似的模塊，比如[0翩概，,,1]就是一個(gè)模式牲距。染色體[0,1,0,1]和[0,0,0,1]都包含上述的模塊袖订。為了引入模式定理，我們還得介紹一些符號(hào)嗅虏。

有了這些符號(hào)洛姑，我們就可以引入模式定理了。模式定理: 在典型的遺傳算法中皮服，下面公式成立楞艾。

這個(gè)公式是怎么來(lái)的呢？我們先來(lái)看選擇操作對(duì)模式H出現(xiàn)概率的影響龄广。根據(jù)選擇操作硫眯，我們很容易得到如下公式。

我們?cè)倏醋儺惒僮鲗?duì)模式出現(xiàn)概率的影響择同。變異操作將所有基因位以pm的概率翻轉(zhuǎn)两入，因此模式H不被破壞的概率為下面第一個(gè)不等式。經(jīng)過(guò)變異操作敲才，模式H的出現(xiàn)概率為下面第二個(gè)不等式裹纳。

最后我們來(lái)看交叉操作對(duì)模式出現(xiàn)概率的影響。交叉操作選擇選擇相鄰的個(gè)體紧武，以pc的概率決定是否需要交叉剃氧。如果需要交叉，隨機(jī)選擇一個(gè)基因位阻星，并交換這個(gè)基因位以及之后的所有基因朋鞍。因此模式H不被破壞的概率為下面第一個(gè)公式。經(jīng)過(guò)交叉操作妥箕，模式H的出現(xiàn)概率為第二個(gè)公式滥酥。

模式定理的通俗說(shuō)法是這樣的，低階畦幢、短長(zhǎng)以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)坎吻。用公式表示便是下面的公式。

馬爾科夫鏈分析

模式定理簡(jiǎn)單易懂呛讲，能夠簡(jiǎn)要地回答人們的疑惑禾怠》捣睿可能有些偏數(shù)學(xué)的研究者可能覺(jué)得模式定理過(guò)于直白贝搁，沒(méi)有數(shù)學(xué)的“味道”。比如芽偏，模式定理沒(méi)有給出收斂性分析雷逆，包括是否收斂和收斂速度等。因此有研究者引入了“正統(tǒng)”的數(shù)學(xué)分析工具——馬爾科夫鏈污尉，對(duì)遺傳算法進(jìn)行收斂性的研究膀哲。

馬爾科夫鏈的相關(guān)概念:s^{t表示第t時(shí)刻的不同狀態(tài)的概率往产。P表示轉(zhuǎn)移概率矩陣，其中P_{i,j}表示從第i個(gè)狀態(tài)轉(zhuǎn)移到第j個(gè)狀態(tài)的概率某宪。齊次馬爾科夫鏈的第t+1時(shí)刻的狀態(tài)只和第t時(shí)刻有關(guān)仿村，可以用公式s}{t+1} = s^{{t}P表示。若存在一個(gè)自然數(shù)k兴喂，使得P}k中的所有元素大于0蔼囊，則稱P為素矩陣。我們還需要引入兩個(gè)引理衣迷。

引理1: 讓C畏鼓、M 和 S 是概率轉(zhuǎn)移矩陣, 其中 M 所有元素大于 0 和 S所有列必有一項(xiàng)大于0，則乘積 CMS 所有元素大于 0壶谒。

引理2: 讓概率轉(zhuǎn)移矩陣P是一個(gè)素矩陣云矫。隨著k趨近于無(wú)窮，P^k收斂于P{\infty} = \pmb{1}^{T}p{\infty}, 其中p^{\infty}是和初始狀態(tài)無(wú)關(guān)的唯一值汗菜，并且所有元素大于0让禀。

我們把整個(gè)種群的狀態(tài)看成馬爾科夫鏈的一個(gè)狀態(tài)s，交叉陨界、變異和選擇操作則構(gòu)建了一個(gè)概率轉(zhuǎn)移矩陣堆缘。我們來(lái)分析0<pm<1和1<=pc<=1時(shí)概率轉(zhuǎn)移矩陣的性質(zhì)。讓C,M,S分別表示交叉普碎、變異和選擇操作帶來(lái)的概率轉(zhuǎn)移吼肥，整體概率轉(zhuǎn)移矩陣P=CMS。1) 經(jīng)過(guò)變異操作麻车，種群狀態(tài)s_i轉(zhuǎn)化成種群狀態(tài)s_j的概率(pm)^{h}(1-pm){nL-h} > 0缀皱，其中h是兩個(gè)種群之間不同值的基因位數(shù)量。也就是說(shuō)动猬，M是素矩陣啤斗。2) 經(jīng)過(guò)選擇操作，種群狀態(tài)s_i保持不變的概率為

正統(tǒng)的優(yōu)化算法分析第一個(gè)要關(guān)心的問(wèn)題是彼水，優(yōu)化算法能不能收斂到全局最優(yōu)點(diǎn)崔拥。假設(shè)全局最優(yōu)點(diǎn)的適應(yīng)度值為maxf，收斂到全局最優(yōu)點(diǎn)的定義如下

典型遺傳算法其實(shí)并不收斂凤覆。具體的證明我就不列了（感興趣的同學(xué)可以之間看論文 [Rudolph and Günter,1994])链瓦，直接說(shuō)下思路：根據(jù)引理2，我們可以知道典型遺傳算法會(huì)收斂到一個(gè)所有種群狀態(tài)概率都大于0的概率分布上；因此之后慈俯，不包含全局最優(yōu)解的種群一定會(huì)不停出現(xiàn)渤刃，從而導(dǎo)致上面的公式不成立。實(shí)際上贴膘，幾乎所有遺傳算法代碼都會(huì)將保持已發(fā)現(xiàn)最優(yōu)解卖子。加了這個(gè)變化之后的遺傳算法是收斂的。思路也是蠻簡(jiǎn)單的：根據(jù)引理2刑峡，我們可以知道典型遺傳算法會(huì)收斂到一個(gè)所有種群狀態(tài)概率都大于0的概率分布上;那么包含全局最優(yōu)解的種群一定會(huì)不停出現(xiàn)揪胃，保持已發(fā)現(xiàn)最優(yōu)解的做法會(huì)使得上面的公式成立。

看到這部分氛琢，我笑出聲來(lái)喊递。為什么呢？因?yàn)檫@段分析實(shí)際用處其實(shí)不大阳似。大家想啊骚勘，如果我們不考慮之前種群并隨機(jī)生成新種群（也就是我們說(shuō)的瞎蒙），構(gòu)造出來(lái)的概率轉(zhuǎn)移矩陣也是素矩陣（P中所有元素的值相等）撮奏。也就是說(shuō)俏讹，瞎蒙也是可以收斂哦。因此上面的分析更多地是追求一種結(jié)構(gòu)的美感畜吊，對(duì)現(xiàn)實(shí)實(shí)踐并沒(méi)有什么卵用泽疆。

模式定理屬于腳踏實(shí)地型，注重解決人們對(duì)遺傳算法的疑惑玲献，注重解決實(shí)際問(wèn)題殉疼。馬爾科夫鏈屬于仰望星空型，注重將遺傳算法納入到一個(gè)更廣大的理論系統(tǒng)中捌年。其實(shí)除了這種兩種分析思路之外瓢娜，還有一種思路。這種思路考察父代和子代種群平均適應(yīng)度變化礼预。但這種分析思路沒(méi)有產(chǎn)生太多后續(xù)工作眠砾，這邊就不再介紹了，有興趣的同學(xué)可以直接看論文 [Altenberg and Lee, 1995]托酸。

理論分析的用處

遺傳算法理論分析可以指導(dǎo)實(shí)際問(wèn)題褒颈。我們用一個(gè)分配問(wèn)題做引子。兩位文秘a和b需要處理n件文書(shū)励堡；由于兩位文秘熟悉領(lǐng)域不一樣谷丸，兩人處理同一件文書(shū)所需要的時(shí)間不同；怎么分配文書(shū)念秧，使得總工作時(shí)間最短淤井。遺傳算法可以解決這個(gè)問(wèn)題布疼，有兩種編碼方案：

方案一:我們使用二進(jìn)制編碼摊趾。第i位基因是0币狠，則將第i件文書(shū)分配給a；第i位基因是1砾层，則將第i件文書(shū)分配給b漩绵。比如n=3,[1,0,1]表示第1和第3件文書(shū)給a文秘，第2件文書(shū)給b文秘肛炮。

方案二:我們使用排序編碼止吐。一個(gè)個(gè)體代表了文書(shū)的排序方案。第i位基因值是j侨糟，則將第j件文書(shū)排在第i位碍扔。兩位文秘同時(shí)處理文書(shū)，其中一位處理手頭的文書(shū)秕重，則按排序順序取下一件文書(shū)處理不同。

哪一種編碼方式比較好呢？有興趣的同學(xué)可以析下哪種編碼方式比較好溶耘。先賣個(gè)關(guān)子二拐，具體答案將在下一篇——遺傳算法的變種和多目標(biāo)遺傳算法中介紹。

參考文獻(xiàn)

Altenberg, Lee. "The schema theorem and Price’s theorem." Foundations of genetic algorithms 3 (1995): 23-49.
J. Holland, Adaptation in Natural and Artificial Systems, The MIT Press; Reprint edition 1992 (originally published in 1975).
Rudolph, Günter. "Convergence analysis of canonical genetic algorithms." Neural Networks, IEEE Transactions on 5.1 (1994): 96-101.