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

關(guān)鍵詞：遺傳算法；優(yōu)化問題；數(shù)據(jù)挖掘

1 概述

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

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

2 遺傳算法的原理

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

2.1 遺傳算法的四個(gè)組成部分

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

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

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

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

3 遺傳算法的應(yīng)用

遺傳算法的應(yīng)用領(lǐng)域非常廣泛，下面主要就遺傳算法在優(yōu)化問題、生產(chǎn)調(diào)度、自動控制、機(jī)器學(xué)習(xí)、圖像處理、人工生命和數(shù)據(jù)挖掘等方面的應(yīng)用進(jìn)行介紹。

3.1 優(yōu)化問題

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

3.2 生產(chǎn)調(diào)度

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

3.3 自動控制

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

3.4 機(jī)器學(xué)習(xí)

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

3.5 圖像處理

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

[6]黃巍，張美鳳.基于混合遺傳算法的車間生產(chǎn)調(diào)度問題研究[J].計(jì)算機(jī)仿真，2009，26（10）：307-310.

[7]邢曉敏.基于遺傳算法的機(jī)器學(xué)習(xí)方法賦值理論研究[J].軟件導(dǎo)刊[J].2009，8（11）：80-81.

[8]蔣培.基于共同進(jìn)化遺傳算法的機(jī)器學(xué)習(xí)[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2004，27（3）：33-38.

[9]田瑩，苑瑋琦.遺傳算法在圖像處理中的應(yīng)用[J].中國圖象圖形學(xué)報(bào)，2007，12（3）：389-396.

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

[11]劉曉莉，戎海武.基于遺傳算法與神經(jīng)網(wǎng)絡(luò)混合算法的數(shù)據(jù)挖掘技術(shù)綜述[J].軟件導(dǎo)刊，2013，12（12）：129-130.