摘 要:遺傳算法是一種非常重要的搜索算法,特別是在解決優(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.