對遺傳算法的基本研究

梁望+李亮+王福順

摘要：本文對遺傳算法進(jìn)行了基本的研究，從解碼和譯碼、適應(yīng)度函數(shù)以及遺傳操作這三大部分來展開研究，給出了算法基本求解步驟以及流程圖，最后給出了遺傳算法的應(yīng)用和推廣。

關(guān)鍵詞：遺傳算法；基本求解步驟；遺傳操作

中圖分類號：TP301 文獻(xiàn)識別碼：A 文章編號：1001-828X（2016）022-000-01

一、遺傳算法基本概念

遺傳算法，是計(jì)算數(shù)學(xué)中用于解決最佳化的一種隨機(jī)自適應(yīng)全局優(yōu)化搜索算法，屬于進(jìn)化計(jì)算。它模仿生物遺傳學(xué)和自然選擇機(jī)理，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，基于隨機(jī)自適應(yīng)的全局搜索算法，自然界的“自然選擇”和“優(yōu)勝劣汰”即達(dá)爾文進(jìn)化論，以及生物遺傳學(xué)說這三大原理，為一些難以找到傳統(tǒng)數(shù)學(xué)模型的難題指出了一個(gè)解決方法。

二、遺傳算法三大部分

1.解碼和譯碼

進(jìn)化計(jì)算求解問題的第一步是對問題的可能解進(jìn)行編碼，目的是為了有效地執(zhí)行遺傳操作。這是一個(gè)從問題的解空間到編碼空間的映射。編碼是用簡單的位串的形式來表示結(jié)構(gòu)比較復(fù)雜的問題，譯碼是將問題結(jié)構(gòu)而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程。在自然界生物進(jìn)化中，把位串形式的解得編碼表示叫染色體或基因型（基因表達(dá)）或者叫個(gè)體。原問題結(jié)構(gòu)即一個(gè)染色體解碼后所對應(yīng)的解稱為表現(xiàn)型。編碼空間也稱為基因型空間或搜索空間，解空間也叫做表現(xiàn)型空間。常見的編碼方式有二進(jìn)制編碼、排列編碼、實(shí)數(shù)向量編碼以及結(jié)構(gòu)式編碼等。

2.適應(yīng)度函數(shù)

類似于自然界中的自然生長過程，這一過程會受到很多因素的影響，最終決定該個(gè)體能否適應(yīng)環(huán)境生存發(fā)展。在遺傳算法中的適應(yīng)度函數(shù)體現(xiàn)的就是染色體的適應(yīng)能力，對該種群中每一個(gè)染色體，個(gè)體都能作用，進(jìn)行度量的函數(shù)。在優(yōu)化問題中，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，用來選出最優(yōu)或是局部最優(yōu)。當(dāng)某一個(gè)染色體與問題的最優(yōu)解染色體之間的差距比較小時(shí)，則表明該染色體適應(yīng)度函數(shù)值與最優(yōu)解之間的差值較小，相反，差距比較大時(shí)，則差值較大，有效的反映出兩者之間的差距。在實(shí)際求解問題中選取適應(yīng)度函數(shù)時(shí)有以下幾點(diǎn)要求：1.因?yàn)檫m應(yīng)度函數(shù)要比較排序進(jìn)行選擇，一般選取非負(fù)正值，連續(xù)的單一的2.具有合理性、一致性，較強(qiáng)的通用性3.是要求計(jì)算量較小，具體要根據(jù)實(shí)際問題本身而定。

3.遺傳操作

基本遺傳算法的三個(gè)基本算子：選擇，交叉，變異。

選擇操作是根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)劣成都決定它在下一代是被淘汰還是被遺傳。從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體做準(zhǔn)備。一般采用適應(yīng)度比例法（轉(zhuǎn)輪法）來進(jìn)行選擇，按各染色體適應(yīng)度函數(shù)值的大小比例來決定其被選擇數(shù)目的多少。設(shè)某染色體被選的概率：，其中：Xi為種群中第i個(gè)染色體，f（xi）是第i個(gè)染色體的適應(yīng)度值，Σf（xi）是種群中所有染色體適應(yīng)度值之和。具體選擇步驟如下：（1）計(jì)算各染色體適應(yīng)度值（2）累計(jì)所有染色體適應(yīng)度值（或選擇概率），記錄每個(gè)個(gè)體的適應(yīng)度累加值（或概率累加值）（3）產(chǎn)生一個(gè)隨機(jī)數(shù) r，0< r

交叉操作：產(chǎn)生隨機(jī)數(shù)，隨機(jī)選擇兩個(gè)染色體，作為雙親染色體，根據(jù)實(shí)際情況選取一種合適的交叉方式例如：多點(diǎn)交叉、部分匹配交叉以及順序交叉等來進(jìn)行交叉變換，從而產(chǎn)生新的染色體，作為子輩的染色體。

變異操作：這一操作是在模擬生物進(jìn)化中的基因突變環(huán)節(jié)，由于自然界或是外界環(huán)境發(fā)生改變，而影響了基因型的表達(dá)。在遺傳操作常使用的染色體二進(jìn)制編碼中的變異操作很簡單，若某一基因位為1則突變?yōu)槌?，否則，由0變成1。生物進(jìn)化中的突變可以豐富產(chǎn)生染色體的多樣性，使同一物種有不同的表現(xiàn)型，不斷進(jìn)化發(fā)展。

三、遺傳算法的基本求解步驟

（1）將種群初始化；

（2）利用適應(yīng)度函數(shù)，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值；

（3）按照輪轉(zhuǎn)法進(jìn)行選擇操作，選擇出將要進(jìn)入下一代的個(gè)體，這一環(huán)節(jié)中，適應(yīng)度值大的選擇的概率比較大，小的可能被淘汰，即優(yōu)勝劣汰；

（4）按交叉概率Pc進(jìn)行交叉操作，Pc的取值一般為0.4-0.99；

（5）按變異概率Pm進(jìn)行突變操作，Pm的取值比較小，一般為0.001-0.1；

（6）若沒有滿足某種停止條件，則轉(zhuǎn)第（2）步，否則進(jìn)入下一步。停止條件與具體問題的應(yīng)用有關(guān)，通常情況下設(shè)最大進(jìn)化代數(shù)100-1000代。如果滿足當(dāng)前最優(yōu)解的情況：很長時(shí)間最優(yōu)解沒有變化或是最優(yōu)解達(dá)到一定的誤差則找到最優(yōu)解或滿足解。

流程圖：

四、遺傳算法的應(yīng)用及推廣

遺傳算法是一種新型的優(yōu)化技術(shù)，它的經(jīng)典應(yīng)用領(lǐng)域就是對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化處理；隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，可以利用遺傳算法用來尋求滿意解，它對于組合優(yōu)化中的NP問題非常有效。另外遺傳算法也在生產(chǎn)調(diào)度問題、自動控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和自動程序設(shè)計(jì)等方面獲得了廣泛的運(yùn)用和推廣。

參考文獻(xiàn)：

[1]趙云珍.遺傳算法及其改進(jìn)[D].昆明理工大學(xué)，2005.

[2]梁芳.遺傳算法的改進(jìn)及其應(yīng)用[D].武漢理工大學(xué)，2008.

[3]王志美，陳傳仁.遺傳算法理論及其應(yīng)用發(fā)展[J].內(nèi)蒙古石油化工，2006，（09）：44-45.