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

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

混合遺傳算法綜述

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

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

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

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

1.引言

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

2 遺傳算法

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

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

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

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

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

圖1 遺傳算法的流程圖

3 混合遺傳算法

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

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

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

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

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

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

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

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

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

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

3.4 量子遺傳算法[12]

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

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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