混合遺傳算法綜述

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

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

混合遺傳算法綜述

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

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

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

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

1.引言

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

2 遺傳算法

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

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

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

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

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

圖1 遺傳算法的流程圖

3 混合遺傳算法

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

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

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

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

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

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

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

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

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

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

3.4 量子遺傳算法[12]

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

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

4 結(jié)語(yǔ)

遺傳算法是生物界的進(jìn)化規(guī)律演化而得來(lái),它不論是在應(yīng)用上,算法設(shè)計(jì)上,還是在基礎(chǔ)理論上,均取得了一定的發(fā)展,諸多領(lǐng)域都有一定應(yīng)用價(jià)值,針對(duì)它還存在的一些問(wèn)題和不足,以后將出現(xiàn)更好的方法理論運(yùn)用其中。通過(guò)一些其他算法加上遺傳算法綜合的方式應(yīng)用,遺傳算法將會(huì)走得更遠(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)開(kāi)發(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)化效率評(píng)價(jià)[J]．自動(dòng)化學(xué)報(bào),2002,28(6)．

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

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

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

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