混合遺傳算法綜述

貴州大學(xué)電氣工程學(xué)院 張先煉

中國水電顧問集團(tuán)正安開發(fā)有限公司 王國杰

混合遺傳算法綜述

貴州大學(xué)電氣工程學(xué)院 張先煉

中國水電顧問集團(tuán)正安開發(fā)有限公司 王國杰

遺傳算法是在生物進(jìn)化上面興起的算法,它的應(yīng)用范圍廣，但由于自身有不足之處，如早熟收斂等,則需對算法的收斂速度及搜索能力等問題進(jìn)行處理。本文對遺傳算法的基本思想、操作步驟及主要特點(diǎn),以及存在的問題進(jìn)行了討論,介紹了幾種混合遺傳算法,對于其基本原理,特點(diǎn)及研究方向進(jìn)行了概述。

遺傳算法；混合遺傳算法；收斂；搜索

1.引言

遺傳算法起源于達(dá)爾文“進(jìn)化論”,借鑒生物界的進(jìn)化規(guī)律而來的全局搜索算法,對此,我們需要了解相關(guān)知識,比如：種群、個體、基因、染色體、遺傳與變異等問題,在進(jìn)化論中,繁殖過程,會發(fā)生基因交叉,突變的基因,一些低適應(yīng)度個體逐漸消失,然而高適應(yīng)度個體將會更多［1,2］。對于遺傳算法的應(yīng)用,主要是在一些圖像處理、神經(jīng)網(wǎng)絡(luò)進(jìn)化、組合優(yōu)化等方面,但單獨(dú)的遺傳算法存在很多缺點(diǎn),比如局部搜索的能力弱和未成熟收斂等等,最終導(dǎo)致很難快速找到最優(yōu)解［3,4］。對于遺傳算法的諸多缺點(diǎn),相關(guān)人士有了對應(yīng)的方案去解決,也就是把遺傳算法和其他算法綜合后為混合遺傳算法。本文所提到的模擬退火遺傳算法、量子遺傳算法等等,用來彌補(bǔ)遺傳算法某些不足之處。

2 遺傳算法

2.1 遺傳算法基本思想[4，5]

遺傳算法是一種隨機(jī)搜索的算法,在遺傳機(jī)理與生物自然選擇基礎(chǔ)上發(fā)展而來的算法,能很好的解決最優(yōu)問題。其基本思想是：開始是初始種群的產(chǎn)生,然后對于那些選中的染色體進(jìn)行交叉、變異等操作后產(chǎn)生后代,然后計(jì)算適應(yīng)度值來選擇符合條件的后代,對于不符合條件的后代進(jìn)行淘汰。經(jīng)過若干代遺傳后,該算法會最終收斂于條件最好的染色體,也就能得到最優(yōu)解。

2.2 遺傳算法實(shí)現(xiàn)步驟

一般遺傳算法實(shí)現(xiàn)步驟［1,5］：

編碼方式的選擇→初始種群產(chǎn)生→計(jì)算適應(yīng)度及排序→若不滿足{選擇→交叉→變異→對適應(yīng)度值計(jì)算}等。如圖1所示。

圖1 遺傳算法的流程圖

3 混合遺傳算法

針對一般遺傳算法的局部最優(yōu)陷入、未成熟的收斂、收斂速度慢等,只用簡單的遺傳算法是達(dá)不到的,那么我們可對遺傳算法作恰當(dāng)?shù)母倪M(jìn)或者將與其它搜索算法綜合為混合遺傳算法來解決這些問題。對于那些應(yīng)用廣泛的混合遺傳算法概述如下：

3.1 模擬退火遺傳算法[7，8]

基本思想：模擬退火算法主要運(yùn)用在很大的可搜尋的空間中找問題最優(yōu)解。對于模擬退火,在這個大的搜尋空間中,把它的每一個點(diǎn)都看成是空氣中的分子;分子的能量,就是它本身的動能;然而對于大的搜尋空間中的每一個點(diǎn),同樣類似空氣分子那樣具有 “能量”,該算法的開始是以這個大的搜索空間里的一個任意的點(diǎn),每次都要預(yù)先選擇相應(yīng)的“鄰居”,之后看看在當(dāng)前位置到相應(yīng)的 “鄰居”的概率問題。

研究方向：函數(shù)的最小值問題及TSP問題;選擇設(shè)計(jì)合適退火溫度來調(diào)整整個搜索的進(jìn)程;對于相關(guān)應(yīng)用問題,選擇獲取適當(dāng)?shù)倪m應(yīng)度函數(shù);可以和一些優(yōu)化算法綜合,比如模糊控制,在更大的范圍內(nèi)體現(xiàn)應(yīng)用其優(yōu)點(diǎn)等。

3.2 小生境遺傳算法[5，9]

基本思想：小生境遺傳算法是把每一代的個體劃分成很多類,在此基礎(chǔ)上,選出那些每類中適應(yīng)度更大的一些個體,最后將它們構(gòu)成一個對應(yīng)的群體,之后在特定的種群中和一些不同種群中經(jīng)過特殊的交叉、變異等來得到新的一代。

研究方向：由于小生境遺傳算法多樣性的解,收斂速度及全局尋優(yōu)等優(yōu)點(diǎn),主要針對的是那些復(fù)雜多封峰函數(shù)的優(yōu)化問題的研究。

3.3 混沌遺傳算法[10，11]

基本思想：混沌遺傳算法是在遺傳算法總的變量群體中添加混沌變量,添加混沌變量是因?yàn)樗槍ψ右淮娜后w所進(jìn)行的輕微干擾以及跟著這個過程的進(jìn)行慢慢調(diào)節(jié)相應(yīng)的幅度。再由基本遺傳算法的 “適者生存”規(guī)則,需要對應(yīng)的選擇、交叉、變異,之后對于混沌變量再添加一個小小的混沌擾動,通過后面的不斷進(jìn)化,最終在一個最優(yōu)的環(huán)境下收斂從而得到相關(guān)問題的最優(yōu)解問題。

研究方向：可以通過其遍歷性來進(jìn)行初始種群的產(chǎn)生和變異的操作,能對一般遺傳算法進(jìn)化的代數(shù)得以降低,最優(yōu)解就能很快尋找到,混沌遺傳算法可以有效避免一些早熟及局部收斂等問題。全局的尋優(yōu)能力通過混沌遺傳算法得以很大的提高。最終表明,混沌遺傳算法可以顯著提高計(jì)算效率,對于數(shù)據(jù)的冗余可以相應(yīng)降低,種群多樣性也可以得到保持,具有較大的實(shí)用價值。

3.4 量子遺傳算法[12]

基本思想：基于量子計(jì)算原理,利用量子疊加態(tài)、量子比特的理論和概念,染色體是量子位編碼表征, 對于進(jìn)化搜索的完成是通過量子門更新和量子門作用。量子遺傳算法通過量子門來實(shí)現(xiàn)染色體的演化,將量子的態(tài)矢量引入染色體的編碼。量子遺傳算法有更好的收斂速度和搜索能力,以及種群多樣性等。

研究方向：對于重大挑戰(zhàn)問題的算法設(shè)計(jì)、算法收斂性分析、量子遺傳算法的計(jì)算復(fù)雜性、建立量子遺傳算法機(jī)理分析的數(shù)學(xué)模型等研究。

4 結(jié)語

遺傳算法是生物界的進(jìn)化規(guī)律演化而得來,它不論是在應(yīng)用上,算法設(shè)計(jì)上,還是在基礎(chǔ)理論上,均取得了一定的發(fā)展,諸多領(lǐng)域都有一定應(yīng)用價值,針對它還存在的一些問題和不足,以后將出現(xiàn)更好的方法理論運(yùn)用其中。通過一些其他算法加上遺傳算法綜合的方式應(yīng)用,遺傳算法將會走得更遠(yuǎn)。

[1]馬永,賈俊芳．遺傳算法研究綜述[J]．山西大同大學(xué)學(xué)報(bào),2007,23(3)．

[2]吳玫,陸金桂．遺傳算法的研究進(jìn)展綜述[J]．機(jī)床與液壓,2008,36(3)．

[3]葛繼科,邱玉輝．遺傳算法研究綜述[J]．計(jì)算機(jī)應(yīng)用研究,2008,25(10)．

[4]吉根林．遺傳算法研究綜述[J]．計(jì)算機(jī)應(yīng)用與軟件,2004,21(2)．

[5]杜永貴,石洪獻(xiàn)．混合遺傳算法的研究現(xiàn)狀[J]．科技情報(bào)開發(fā)與經(jīng)濟(jì),2006,16(10)．

[6]吳強(qiáng)．蟻群混合遺傳算法的研究及應(yīng)用[D]．包頭:內(nèi)蒙古科技大學(xué),2011:3-8．

[7]武兆慧,張桂娟,劉希玉．基于模擬退火遺傳算法的關(guān)聯(lián)規(guī)則挖掘[J]．計(jì)算機(jī)應(yīng)用,2005,25(5)．

[8]田東平,遲洪欽．混合遺傳算法與模擬退火[J]．計(jì)算機(jī)工程與應(yīng)用,2006．22．

[9]黃聰明,陳湘秀．小生境遺傳算法的改進(jìn)[J]．北京理工大學(xué)學(xué)報(bào),2004,24(8)．

[10]姚俊峰,梅熾,彭小奇．混沌遺傳算法(CGA)的應(yīng)用研究及其優(yōu)化效率評價[J]．自動化學(xué)報(bào),2002,28(6)．

[11]王芳．混沌遺傳算法研究及其在地震子波提取中的應(yīng)用[D]．北京:中國石油大學(xué),2010:5-6．

[12]周露芳,古樂野．基于量子遺傳算法的二位最大熵圖像分割[J]．計(jì)算機(jī)應(yīng)用,2005,25(8)．

張先煉（1993—），男，貴州遵義人，碩士研究生，貴州大學(xué)電氣工程學(xué)院檢測技術(shù)與自動化裝置專業(yè)，主要研究方向：嵌入式系統(tǒng)與自動化裝置。

王國杰（1992—），女，貴州遵義人，學(xué)士學(xué)位，技術(shù)員，中國水電顧問集團(tuán)正安開發(fā)有限公司。