對遺傳算法的基本研究

梁望+李亮+王福順

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

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

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

一、遺傳算法基本概念

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

二、遺傳算法三大部分

1.解碼和譯碼

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

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

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

3.遺傳操作

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

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

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

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

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

（1）將種群初始化；

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

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

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

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

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

流程圖：

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

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

參考文獻：

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

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

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