遺傳算法

??遺傳算法(Genetic Algorithm，GA)，最早是由美國的John holland在20世紀70年代提出。算法通過模擬達爾文生物進化論的自然選擇以及遺傳學機理的生物進化過程來搜索問題的最優解。

??遺傳算法是靠大規模數據演變來得到問題的最優解，當然在實際過程中可能受限于數據規模等因素往往得到的結果并不是最優解而是一個相對比較好的結果，這其實也是演化類算法的一大通病。為什么說遺傳算法是靠大規模數據演變來得到問題的最優解？這就要提到算法所需要的數據構成了。算法的數據構成也是仿生而來，首先需要一個由個體組成的種群類比動物里的斑馬群、狼群…，其次一個個體里的數據包含它本身、它的染色體或者基因片段以及一個適應度，適應度是為了方便計算的一個隱性存在，而事實上大自然的動物也都有自己對于環境的適應性，適應度就是評估這個適應性大小的度量值，在算法中適應度一般由待求解問題來決定，所以待求解問題往往類比環境。另外，既然是演變，算法必定會生物進化的過程進行仿生，這里就需要提到遺傳算法的三個主要的算子(操作)，選擇、交叉、變異。以上的基本操作算子，數據構成組成了基本的遺傳算法。

??遺傳算法是如何進行的？

??首先，算法需要初始化一個種群。種群大小，個體上下限，算法停止條件需要人來決定。個體誕生于隨機數，隨機數有上限和下限；然后評價種群中的個體，給出每個個體的適應度，其次，算法應當根據個體的適應度并采取一定的選擇方式選擇待交叉的個體。再次，代交叉的個體進行交叉后誕生新的個體，這一步也是遺傳算法的精髓。從次，算法需要對種群中的某些基因進行變異。最后，留下優秀的個體等待再次評價，交叉…，直至達到算法停止條件。

??遺傳算法的細節。

??在現實生活中我們往往很難從理論上理解一個問題，采用簡陋的歸納推理能夠幫助我們很好的理解問題，即，少數情況成立，我們認為后面所有類似情況都能成立，盡管這種推理到最后不一定正確。以一個簡單實例來說明算法的細節。假如有一個問題需要我們解決，$max(y)=?x^2$，利用遺傳算法求y的最大值。第一步需要根據經驗來決定它的個體取值范圍，這個實例很明顯可以取[-5,5]，還需要定義一個種群大小，這在之前需要確定需求的精度，編碼方式以及長度，即給出染色體的形式，假如精度為，編碼采用二進制，那么編碼長度就為m,m滿足$2^{m?1}<(5?(?5))\times 10^3\le 2^m?1$，也就是m長度要使得這個二進制串能夠完全覆蓋個體的取值范圍且不能剩余過多的空白字符串，在這里編碼長度就為10，假設這個種群里面就只有仨個體，取一個范圍內的隨機數做為第一個體，比如取1.23，那么它的染色體就為$dec2bin(round((1.23?(?5))\times \frac{2^{10}?1}{(5?(?5))}))=1001111101$,dec2bin為十進制轉二進制函數它只能轉正整數，round為取整函數，而染色體轉換為表現型為$round((?5+\frac{5?(?5)}{2^{10}?1})\times bin2dec(1001111101))$，round為舍進函數取小數點后兩位，適應度就為-1.232=-1.5129,這樣的巧妙變換就能使得染色體和表現型相互轉換。利用同樣的方法我們也可以隨機獲得第二個個體-1,染色體為0110011001，適應度為-1，第三個個體2.34，染色體為1011101111，適應度為-5.4756。下一步需要選擇交叉，通常采用選擇的原則是輪盤賭選擇，另外還有錦標賽選擇，自適應輪盤賭選擇，排名選擇，為了簡單介紹，在這里直接采用排名選擇，顧名思義就是直接選擇適應度大的個體進行染色體交叉，顯而易見，-1>-1.5129>-5.4756,選擇第一個和第二個個體進行染色體交叉，隨機或者固定選取一個節點(這里指染色體中的某個位置)，選擇第7個位置交叉那就是第一個染色體前6個，即100111拼接第二個染色體的后4個1001得到1001111001，第二個染色體前6個，即011001拼接第一個染色體后4個1101得到0110011101。他們的表現型分別為，1.19，-0.96，適應度分別為-1.4161，-0.9216，可以發現通過交叉算子似乎獲得了比原先更好的個體，以上就是多點交叉，當然也可以有其他不同種類的交叉方案，比如單點交叉，只交叉一個點位的數據。算法的最后一個算子變異是最容易實現的一個，在這里我們假定第三個個體發生了變異，那么它的染色體的某一位就會發生突變，比如染色體的第3位發生了突變由原先的1011101111->1001101111,它的表現型和適應度也會隨之變化，變為1.09和-1.1881，當然在實際的算法中，變異是需要設定一個閾值當隨機生成的隨機數小于這個閾值的時候才會發生變異，變異并不會時常發生。

??在算法中當種群從初始化到選擇到交叉再到變異完整實現后，仍需要從選擇開始重復剩下的操作直至達到人為設定的停止條件，這些停止條件一般為迭代的代數，最優值保持n代沒有變化…

模式定理的簡單證明

??為什么說遺傳算法通過這些選擇交叉變異就能夠獲得相對比較優的值呢？這就要提到它的理論基礎——模式定理。模式就是字面意思，也可以理解為模板，模具或者一個類，模式用"H"表示是通過"1，0，*"來抽象表示一類二進制字符串的，比如一個模式為1*0*,那么無論星號處取1還是0都屬于這個模式。模式定理中有兩個概念其一為模式階(Schema Order),記作O(H),模式階表示一個模式中非*的個數比如0011*1*1*0**的模式階為7，顯然模式階越大那么模式確定性越高，這個模式能夠刻畫的字符串就越少；其二為定義距(Defining Length)，記作δ(H),表示模式中第一個非*字符和最后一個非*字符之間的距離，如0011*1*1*0**的定義距為10-1=9，模式定理的具體內容為：在遺傳算子選擇、交叉、變異的作用下，具有低階、短定義距以及平均適應度高于種群平均適應度的模式在子代中呈指數級增長。

模式定理的證明。

給定一個代數t，假設在t代中的一個模式H下有m個具體的染色體包含在n個個體的種群中，記作$m=m(H,t)$,在t代基于輪盤賭的選擇，那么某個個體被選擇的概率為$P_i=\frac{f(x_i)}{{\sum }_{i=1}^{n}f(x_i)}$，現在我們只說選擇算子，不提交叉和變異，那么在t+1代H模板能夠刻畫的字符串應該有m(H,t+1)個，在t代，用f(H)表示模式H的平均適應度，所有符合H模板的字符串適應度為m(H,t)×f(H),他們被選擇的概率為$\frac{m(H,t)\times f(H)}{{\sum }_{i=1}^{n}f(x_i)}$,m(H,t+1)的期望值為$n\times \frac{m(H,t)\times f(H)}{{\sum }_{i=1}^{n}f(x_i)}$。
$$m(H,t+1)=n\times \frac{m(H,t)\times f(H)}{{\sum }_{i=1}^{n}f(x_i)}=\frac{m(H,t)\times f(H)}{\frac{{\sum }_{i=1}^{n}f(x_i)}{n}}=\frac{m(H,t)\times f(H)}{\overline{f(x)}}$$

當模式H的平均適應度$f(H)>\overline{f(x)}$，模式H下的字符串會增多，當$f(H)<\overline{f(x)}$時，模式H下的字符串會減少，假設模式H的適應度高出或低于種群平均適應度c%,令C= c%，那么$$m(H,t+1)=\frac{m(H,t)\times (\overline{f(x)}\pm C\overline{f(x)})}{\overline{f(x)}}=(1\pm C)\times m(H,t)$$
假設t從第一代記起，那么$m(H,t)=m(H,t)\times (1\pm C{)}^{t?1}$,選擇的作用顯而易見，在種群中模式H的適應度約大它所能表示的字符串會越來越多，模式H的適應度越小它所能表示的字符串會越來越少。

??現在開始考慮染色體的交叉和變異。假定，交叉采用單點交叉的方式進行，那么什么情況下的交叉不會影響到模式，什么情況下的交叉會影響到模式，這就得用到前面提到的概念——定義距。比如模式H為0011*1*1*0**，它的定義距為９，當交叉點位落在第5，7，9，11，12的位置上都不會破壞這個模式，但是這個模式說不定也會有子模式比如00***1*1*0**，所以更貼切的講當點位落在第11，12上也就是落在定義距之外模式H不會被破壞，此時根據古典概型模式H不被破壞的概率為：$$P=1?P_c\frac{\delta (H)}{L?1}$$

δ(H)表示第一個確定數字到最后一個確定數字的距離或者數字間的空格數，L為字符串長度，L-1為其總的距離或者空格數，Pc為交叉概率。

變異算子對模式的影響是通過改變字符串確定位置上的數字，這時需要另外一個定義模式階，模式階表示一個字符串中非*的數字個數，當模式中有一個確定性數字被改變那么模式遭受破壞，首先需要一個變異概率Pm，那么單個染色體不被改變的概率為1-Pm，模式H中O(H)個位置都沒有變異模式才能不被破壞那么變異對模式的影響為$(1?P_m{)}^{O(H)}\approx 1?O(H)\times P_m，(P_m?1)$。

??同時考慮選擇，交叉以及變異算子對模式的影響可得出：$$m(H,t+1)\ge m(H,t)\times \frac{f(H)}{\overline{f(x)}}\times [1?P_c\frac{\delta (H)}{L?1}?O(H)\times P_m]$$

??由上式可以看出，低階、短定義距及平均適應度高于種群的模式更容易留存。

參考文獻：遺傳算法的基本定理推導

總結

以上是生活随笔為你收集整理的遗传算法的简单介绍以及模式定理的简单证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。