混合遺傳算法綜述

貴州大學(xué)電氣工程學(xué)院 栗 盼

混合遺傳算法綜述

貴州大學(xué)電氣工程學(xué)院 栗 盼

遺傳算法是一種通過編碼對可能問題解空間搜索求解，能夠在目標(biāo)函數(shù)的導(dǎo)數(shù)信息位置的情況下模擬自然界生物進(jìn)化過程的自組織、自適應(yīng)的過程。能夠盡快確定最優(yōu)值所處范圍，而混合遺傳算法在其基礎(chǔ)上引入其他優(yōu)化算法，以保證遺傳算法全局性能的基礎(chǔ)上大大減小計算量，提高收斂速度。普通的混合遺傳將經(jīng)典的優(yōu)化算法和局部搜索能力融合，平衡深度搜索和廣度搜索。通過對群體進(jìn)行復(fù)制、雜交和變異，通過以自適應(yīng)為原則的選擇機制累積信息，遺傳算法可以保持在解空間不同區(qū)域?qū)Χ鄠€點的搜索，通過交叉算子和變異算子來全面搜索解碼空間，不容易陷入局部最優(yōu)。

遺傳算法；混合遺傳算法；拉馬克進(jìn)化

引言

從簡單到復(fù)雜,從低級到高級的生物進(jìn)化過程本身是一個自然、并行發(fā)生的、穩(wěn)健的優(yōu)化過程,通過“優(yōu)勝劣汰”及遺傳變異,后代種群比前代更加適應(yīng)環(huán)境,末代種群中得最優(yōu)個體。

借鑒上述過程,形成的獨特的隨機搜索算法,即為遺傳算法。初代種群(編碼集合)產(chǎn)生后,按照優(yōu)勝劣汰的原則,通過適應(yīng)度選擇個體,復(fù)制、交叉、變異等自然選擇,產(chǎn)生出具有適應(yīng)環(huán)境的優(yōu)化的群體,循環(huán)往復(fù),漸變式進(jìn)化。

遺傳算法受上述的生物進(jìn)化學(xué)和生物遺傳學(xué)的啟發(fā),使用自適應(yīng)概率搜索技術(shù),其選擇、淘汰、優(yōu)化等運算都是以一種概率的方式來進(jìn)行的,這樣增加了進(jìn)化過程中自適應(yīng)迭代過程的靈活性。由于遺傳算法不依賴尋有問題情境的具體范圍和梯度信息,為較為復(fù)雜的尋優(yōu)問題提供了通用的基本框架。

1 遺傳算法

1.1 遺傳算法特點

作為人工智能系統(tǒng)的重要探究方向和人工生命探究的重要工具,GA是對進(jìn)化系統(tǒng)進(jìn)行的應(yīng)用計算機中的模擬研究,常規(guī)的GA將問題的個體的染色體串編碼,把所求解問題的可行解進(jìn)行編碼,根據(jù)進(jìn)化和遺傳原理,計算機會從某個初始點進(jìn)行搜索,逐一梯次尋到最優(yōu)解范圍。

1.2 Lamarckian進(jìn)化（拉馬克進(jìn)化）和Baldwin效應(yīng)（班德文效應(yīng)）

遺傳算法在傳統(tǒng)的方式基礎(chǔ)上,利用局部搜索來提高種群適應(yīng)性,最終的提高被遺傳算法編碼在字符串上,相當(dāng)于有機體后天學(xué)習(xí)的獲得性性狀直接將編碼反饋到基因型上,這相當(dāng)于一種拉馬克進(jìn)化形式。還有一種形式,不會在基因上對其編碼,而是通過對某種行為的學(xué)習(xí)能力遺傳給下一代,這是一種改變適應(yīng)度曲線的效應(yīng),這種機制就是班德文效應(yīng)。

拉馬克進(jìn)化論點有:(1)生命是連續(xù)的、變化的、發(fā)展的,生物具有不斷增加復(fù)雜性的趨勢。(2)生物以“樹狀”進(jìn)化,從低級到高級且向各個方向發(fā)展。(3)環(huán)境變化引起生活需要的改變,進(jìn)而導(dǎo)致物種產(chǎn)生新的行為和養(yǎng)成新的習(xí)性。在拉馬克的例證中有這么一個事例:以前的長頸鹿由于干旱,時常伸頸取食樹上的葉子,使得脖子越來越長,這些后代獲得的性狀在自然選擇中存活下來。時年累月,成為我們?nèi)缃袼熘拈L頸鹿。將這種進(jìn)化過程用“用進(jìn)廢退”和“獲得性遺傳”原則進(jìn)行了總結(jié)。

班德文效應(yīng)觀點為:在生物的群體遺傳中,個體適應(yīng)性對進(jìn)化產(chǎn)生影響,即沒有明確將特定的性能傳給下一代,后代個體繼承的是種學(xué)習(xí)能力。就長頸鹿的例子來講,班德文認(rèn)為,一方面是在長時間的進(jìn)化過程中,學(xué)會到伸長脖子的個體得以存活,然后將這種認(rèn)知能力傳給后代,最終這些個體成為種群主要成員,另一方面?zhèn)€體學(xué)習(xí)到有益行為,會將其變成一種本能。

拉馬克認(rèn)識到了變異的普遍性,否認(rèn)了其隨機性,將新搜索到的個體放入群體中,易陷入局部最優(yōu),收斂速度慢;Baldwin只是修改個體的適應(yīng)度,易獲得全局最優(yōu)解,但速度較慢。共同缺點是局部搜索能力較差和參數(shù)較難選擇。

2 混合遺傳算法的提出

盡管遺傳算法對于各種問題能夠盡快的找到最優(yōu)解的范圍,但就任何一個特殊領(lǐng)域而言,都只是尋到次優(yōu)解,它們往往比不上專門處理該領(lǐng)域問題的算法。

2.1 遺傳算法存在兩個嚴(yán)重的問題

2.1.1 “早熟”問題

“早熟”問題作為遺傳算法的缺陷之一,是一種由于群體喪失多樣性而提前收斂到局部最優(yōu)解的未成熟收斂的情況。主要表現(xiàn)為種群在進(jìn)化過程中,生成的個體具有很高的適應(yīng)度,通過選擇,適應(yīng)下來的個體大部分與其一致或相似,導(dǎo)致群體陷入同一極值而停止進(jìn)化,從而不能得到全局最優(yōu)解。

2.1.2 局部搜索能力低

從本質(zhì)上講,遺傳算子主要是通過交叉算子和變異算子來實現(xiàn)的是隨機搜索,不能保證產(chǎn)生改進(jìn)的后代,其中交叉算子主導(dǎo),而變異算子則是輔助。在算法的初期優(yōu)秀的個體可以主導(dǎo)控制過程,競爭較為激烈;而在算法的晚期,群體中的個體趨于平均值,競爭趨于平緩,交叉操作的結(jié)果會出現(xiàn)很多類似性狀的組合,呈現(xiàn)隨機搜索行為。這直接影響了搜索效率以及尋到全局最優(yōu)解的概率。

2.2 解決

由于以上問題的存在,隨機搜索的收斂速度較慢,而且局部尋優(yōu)能力差,往往只能得到全局的次優(yōu)解,這時我們希望找的給定問題的解的同時隨特定問題而變化,但如果將遺傳算法和原有算法混合,融合原有算法中較為先進(jìn)的優(yōu)化技術(shù)和遺傳算法,這樣同時保持了兩種算法的優(yōu)勢,使得在性能上優(yōu)于這兩種。一般采用傳統(tǒng)優(yōu)化算法的編碼或者在編碼解碼過程中融合專業(yè)知識并且在GA步驟中添加局部搜索兩種混合策略。

3 混合遺傳算法基本原理

由于GA能夠迅速的優(yōu)化到最優(yōu)值的大約92%,但是得到其近似最優(yōu)解就很耗費時間,這表明其在全局的收斂性能優(yōu)秀但是局部較差,但是一些經(jīng)典的遺傳算法具有局部收斂性能較高,精確度較高的優(yōu)勢,將二者融合,能夠互相彌補,以迅速的得到最優(yōu)解。

4 混合遺傳算法實現(xiàn)

4.1 編碼方式

編碼的實質(zhì)是在表型空間與基因型空間之間建立一個映射。傳統(tǒng)的優(yōu)化算法一般采用一種將實數(shù)空間離散化的二進(jìn)制編碼方式。在解決染色體可行性、合法性和唯一性的前提下,使用固定長度的二進(jìn)制符號來表示群體中的個體,其等位基因是由二值符號集{0,1}組成的,初始個體基因值可用均勻分布的隨機值生成。

4.2 交叉和選擇操作

選擇的基礎(chǔ)是達(dá)爾文的適者生存理論。合適的選擇壓力很重要,初始階段壓力希望小,最終壓力希望大,選擇的作用使得群體最優(yōu)解所在區(qū)域移動,遺傳算法本質(zhì)上是一種概率性的自適應(yīng)迭代性的尋優(yōu)算法,交叉算子反映隨機信息的交換,產(chǎn)生新的基因組合即新個體,選擇算子則是以適應(yīng)度為選擇原則的再生行為。

4.3 變異操作

根據(jù)基因變異原理,對自然選擇出的個體的某些基因,按照變異的概率,執(zhí)行異向轉(zhuǎn)化,某個程度上可以看做對某位基因的取反。

4.4 適應(yīng)度函數(shù)

適應(yīng)度一般用來表示生物界的適者生存,適應(yīng)度函數(shù)則是用來評判個體優(yōu)劣的標(biāo)準(zhǔn)。一般通過適應(yīng)度變換開維持個體之間的合理差距以及限制競爭、維持物種多樣性。

4.5 局部搜索（常見的幾種混合遺傳算法）

小生境算法:生物界中,交叉并不是完全隨機的,有很多因素的制約,從遺傳算法的角度來看,顯然缺乏對可能的交叉效果方面的考慮,會使優(yōu)化效率降低,為了解決這種問題,將小生鏡技術(shù)與雙親變異相結(jié)合,提出替換與本身性狀類似的個體的預(yù)選擇機制、用群體代間覆蓋方式的排擠機制、利用共享函數(shù)選擇的共享機制的小生境技術(shù),來維護(hù)群體的多樣性。

自適應(yīng)算法:由于用不變的參數(shù)控制進(jìn)化過程,容易影響交叉和變異概率,易導(dǎo)致早熟,所以用自適應(yīng)調(diào)整遺傳算法的控制參數(shù)的思想混合定量評價指數(shù),以滿足系統(tǒng)實時性以及全局收斂性。

免疫遺傳算法:遺傳算法的交叉和變異算子都是在一定概率下的迭代搜索,所以在個體進(jìn)化的過程中不可避免的出現(xiàn)退化,故借鑒免疫系統(tǒng)的動態(tài)的自維持、多樣性的遺傳機理和對異物快速反應(yīng)等機理,以達(dá)到抑制優(yōu)化過程的退化現(xiàn)象,避免“早熟”情況的出現(xiàn)。

模擬退火算法則根據(jù)循環(huán)進(jìn)化過程能夠增強和保持生物種群的多樣性,具有較強的局部搜索能力,在循環(huán)過程中能同時接受使目標(biāo)函數(shù)變好的狀態(tài)以及概率接受變差的狀態(tài)點,則能通過擺脫局部最優(yōu)解達(dá)到全局最優(yōu)解。

其余的情況,可根據(jù)選擇的遺傳算法進(jìn)行具體操作,例如梯度法等。

5 結(jié)語

遺傳算法的收斂速度較慢以致影響全局收斂性,這是目前改善遺傳算法性能的主要克服的問題。一些研究已經(jīng)針對增強收斂性能提出了多種改進(jìn)途徑,并在多種實際領(lǐng)域中獲得了良好的應(yīng)用效果。本文綜述了基于遺傳算法的混合遺傳算法的起因、原理以及算法的實現(xiàn),可對混合遺傳算法有了大概的了解,在此基礎(chǔ)上有針對性的對混合遺傳算法進(jìn)行研究,可以解決現(xiàn)實生活中的很多難題。但是由于時間和經(jīng)驗等原因,混合遺傳算法還有很大的改進(jìn)和提升空間,有待我們以后深入研究。

［1］喬建忠,雷為民,李本忍,滕弘飛.混合遺傳算法研究及其應(yīng)用［J］.小型微型計算機系統(tǒng),19(12).

［2］黃浩鋒,陳少英.混合遺傳算法概述［J］.科學(xué)技術(shù),2008,04.

［3］張智霞.混合遺傳算法及應(yīng)用實例［J］.青海大學(xué)學(xué)報,2004,02.

［4］辛海濤.混合遺傳算法及其應(yīng)用［J］.軟件導(dǎo)刊,2010,05.

［5］焦李成,公茂果.拉馬克進(jìn)化、班德文效應(yīng)與自然計算［A］.第十一屆中國人工智能學(xué)術(shù)年會.西安,2006.

栗盼（1992—），女，河北南宮人，碩士研究生，研究方向：嵌入式系統(tǒng)與自動化裝置。