對遺傳算法的基本研究

梁望+李亮+王福順

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

關鍵詞：遺傳算法；基本求解步驟；遺傳操作

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

一、遺傳算法基本概念

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

二、遺傳算法三大部分

1.解碼和譯碼

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

2.適應度函數

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

3.遺傳操作

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

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

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

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

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

（1）將種群初始化；

（2）利用適應度函數，計算種群中每個個體的適應度值；

（3）按照輪轉法進行選擇操作，選擇出將要進入下一代的個體，這一環節中，適應度值大的選擇的概率比較大，小的可能被淘汰，即優勝劣汰；

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

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

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

流程圖：

四、遺傳算法的應用及推廣

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

參考文獻：

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

[2]梁芳.遺傳算法的改進及其應用[D].武漢理工大學，2008.

[3]王志美，陳傳仁.遺傳算法理論及其應用發展[J].內蒙古石油化工，2006，（09）：44-45.