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

混合遺傳算法綜述

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

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

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

引言

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

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

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

1 遺傳算法

1.1 遺傳算法特點(diǎn)

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

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

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

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

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

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

2 混合遺傳算法的提出

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

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

2.1.1 “早熟”問(wèn)題

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

2.1.2 局部搜索能力低

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

2.2 解決

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

3 混合遺傳算法基本原理

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

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

4.1 編碼方式

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

4.2 交叉和選擇操作

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

4.3 變異操作

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

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

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

4.5 局部搜索（常見(jiàn)的幾種混合遺傳算法）

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

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

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