遺傳算法的應用研究

摘 要：遺傳算法是一種非常重要的搜索算法，特別是在解決優(yōu)化問題上，效果非常好。文章首先介紹了遺傳算法的四個組成部分，以及算法的基本操作步驟，接著探討了遺傳算法的幾個主要應用領域，包括優(yōu)化、生產調度、機器學習、圖像處理、人工生命和數據挖掘等。目前遺傳算法以及在很多方面的應用中取得了較大的成功，但是它在數學基礎方面相對還不夠完善，因而需要進一步研究和完善。

關鍵詞：遺傳算法；優(yōu)化問題；數據挖掘

1 概述

遺傳算法（Genetic Algorithms， GA）一詞源于人們對自然進化系統(tǒng)所進行的計算機仿生模擬研究，是以達爾文的“進化論”和孟德爾的“遺傳學原理”為基礎的，是最早開發(fā)出來的模擬遺傳系統(tǒng)的算法模型。遺傳算法最早是由Fraser提出來的，后來Holland對其進行了推廣，故認為遺傳算法的奠基人是Holland。

隨著遺傳算法的不斷完善和成熟，其應用范圍也在不斷擴大，應用領域非常廣泛，主要包括工業(yè)控制、網絡通訊、故障診斷、路徑規(guī)劃、最優(yōu)控制等。近幾年，出現了很多改進的遺傳算法，改進方法主要包括：應用不同的交叉和變異算子；引入特殊算子；改進選擇和復制方法等。但是，萬變不離其宗，都是基于自然界生物進化，提出的這些改進方法。

2 遺傳算法的原理

遺傳算法是從某一個初始種群開始，首先計算個體的適應度，然后通過選擇、交叉、變異等基本操作，產生新一代的種群，重復這個過程，直到得到滿足條件的種群或達到迭代次數后終止。通過這個過程，后代種群會更加適應環(huán)境，而末代種群中的最優(yōu)個體，在經過解碼之后，就可以作為問題的近似最優(yōu)解了。

2.1 遺傳算法的四個組成部分

遺傳算法主要由四個部分組成[1]：參數編碼和初始群體、適應度函數、遺傳操作和控制參數。編碼方法中，最常用的是二進制編碼，該方法操作簡單、便于用模式定理分析。適應度函數是由目標函數變換而成的，主要用于評價個體適應環(huán)境的能力，是選擇操作的依據。遺傳操作主要包括了選擇、交叉、變異等三種基本操作?？刂茀抵饕校捍LZ，群體大小size，交叉概率Pc，變異概率Pm等。目前對遺傳算法的研究主要集中在參數的調整中，很多文獻建議的參數取值范圍一般是：size取20～200之間，Pc取0.5～1.0之間，Pm取0～0.05之間。

2.2 遺傳算法的基本操作步驟

遺傳算法的基本操作步驟為：

（1）首先，對種群進行初始化；（2）對種群里的每個個體計算其適應度值；（3）根據（2）計算的適應度，按照規(guī)則，選擇進入下一代的個體；（4）根據交叉概率Pc，進行交叉操作；（5）以Pm為概率，進行變異操作；（6）判斷是否滿足停止條件，若沒有，則轉第（2）步，否則進入（7）；（7）得到適應度值最優(yōu)的染色體，并將其作為問題的滿意解或最優(yōu)解輸出。

3 遺傳算法的應用

遺傳算法的應用領域非常廣泛，下面主要就遺傳算法在優(yōu)化問題、生產調度、自動控制、機器學習、圖像處理、人工生命和數據挖掘等方面的應用進行介紹。

3.1 優(yōu)化問題

優(yōu)化問題包括函數優(yōu)化和組合優(yōu)化兩種。很多情況下，組合優(yōu)化的搜索空間受問題規(guī)模的制約，因此很難尋找滿意解。但是，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效。朱瑩等[2]提出了一種結合啟發(fā)式算法和遺傳算法的混合遺傳算法來解決雜貨船裝載的優(yōu)化問題中。潘欣等[3]在化工多目標優(yōu)化問題中應用了并行遺傳算法，實驗結果表明該方法效果良好。王大東等[4]將遺傳算法應用到了清運車輛路徑的優(yōu)化問題求解中，而且仿真結果表明算法可行有效。

3.2 生產調度

在復雜生產調度方面，遺傳算法也發(fā)揮了很大的作用。韋勇福等[5]將遺傳算法應用到了車間生產調度系統(tǒng)的開發(fā)中，并建立了最小化完工時間目標模型，成功開發(fā)了車間生產調度系統(tǒng)模塊，并用實例和仿真驗證了該方法的可行性。張美鳳等[6]將遺傳算法和模擬退火算法相結合，提出了解決車間調度問題的混合遺傳算法，并給出了一種編碼方法以及建立了相應的解碼規(guī)則。

3.3 自動控制

在自動控制領域中，遺傳算法主要用于求解的大多也是與優(yōu)化相關的問題。其應用主要分為為兩類，即離線設計分析和在線自適應調節(jié)。GA可為傳統(tǒng)的綜合設計方法提供優(yōu)化參數。

3.4 機器學習

目前，遺傳算法已經在機器學習領域得到了較為廣泛的應用。邢曉敏等[7]提出了將遺傳算子與Michigan方法和基于Pitt法的兩個機器學習方法相結合的機器學習方法。蔣培等[8]提出了一種基于共同進化遺傳算法的機器學習方法，該方法克服了學習系統(tǒng)過分依賴于問題的背景知識的缺陷，使得學習者逐步探索新的知識。

3.5 圖像處理

圖像處理是一個重要的研究領域。在圖像處理過程中產生的誤差會影響圖像的效果，因此我們要盡可能地減小誤差。目前，遺傳算法已經在圖像增強、圖像恢復、圖像重建、圖像分形壓縮、圖像分割、圖像匹配等方面應用廣泛，詳見參考文獻[9]。

4 結束語

遺傳算法作為一種模擬自然演化的學習過程，原理簡單，應用廣泛，已經在許多領域解決了很多問題。但是，它在數學基礎方面相對不夠完善，還有待進一步研究和探討。目前，針對遺傳算法的眾多缺點，也相繼出現了許多改進的算法，并取得了一定的成果?？梢灶A期，未來伴隨著生物技術和計算機技術的進一步發(fā)展，遺傳算法會在操作技術等方面更加有效，其發(fā)展前景一片光明。

參考文獻

[1]周明，孫樹棟.遺傳算法原理及應用[M].國防工業(yè)出版社，1999，6.

[2]朱瑩，向先波，楊運桃.基于混合遺傳算法的雜貨船裝載優(yōu)化問題[J].中國船艦研究，2015：10（6）：126-132.

[3]潘欣，等.種群分布式并行遺傳算法解化工多目標優(yōu)化問題[J].化工進展，2015：34（5）：1236-1240.

[4]王大東，劉競遙，王洪軍.遺傳算法求解清運車輛路徑優(yōu)化問題[J].吉林師范大學學報（自然科學版），2015（3）：132-134.

[5]韋勇福，曾盛綽.基于遺傳算法的車間生產調度系統(tǒng)研究[J].裝備制造技術，2014（11）：205-207.

[6]黃巍，張美鳳.基于混合遺傳算法的車間生產調度問題研究[J].計算機仿真，2009，26（10）：307-310.

[7]邢曉敏.基于遺傳算法的機器學習方法賦值理論研究[J].軟件導刊[J].2009，8（11）：80-81.

[8]蔣培.基于共同進化遺傳算法的機器學習[J].湖南師范大學自然科學學報，2004，27（3）：33-38.

[9]田瑩，苑瑋琦.遺傳算法在圖像處理中的應用[J].中國圖象圖形學報，2007，12（3）：389-396.

[10]周劍利，馬壯，陳貴清.基于遺傳算法的人工生命演示系統(tǒng)的研究與實現[J].制造業(yè)自動化，2009，31（9）：38-40.

[11]劉曉莉，戎海武.基于遺傳算法與神經網絡混合算法的數據挖掘技術綜述[J].軟件導刊，2013，12（12）：129-130.