典型小生境遺傳算法原理與性能比較分析*

趙 越，茹婷婷

(1.吉林建筑大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林長(zhǎng)春130118；2.吉林建筑大學(xué)基礎(chǔ)科學(xué)部，吉林長(zhǎng)春130118)

近年來，隨著智能計(jì)算領(lǐng)域各項(xiàng)研究的不斷深入，人們對(duì)于遺傳算法的認(rèn)識(shí)也在不斷豐富和提升.與傳統(tǒng)意義上的優(yōu)化算法相比，遺傳算法的通用性和魯棒性更強(qiáng)，故其在各個(gè)領(lǐng)域的應(yīng)用很廣［1-2］.盡管如此，基本遺傳算法本身也存在不盡如人意的地方，主要表現(xiàn)在兩個(gè)方面：一是問題的求解過程中可能會(huì)出現(xiàn)早熟或隨機(jī)漫游現(xiàn)象；二是遺傳算法不具備全局收斂性［3-4］.對(duì)于這些不足，究其根本原因在于缺乏對(duì)種群多樣性的保護(hù)機(jī)制.針對(duì)各種優(yōu)化問題而言，求解的目標(biāo)往往更加全面，即需要全局最優(yōu)解和局部最優(yōu)解.在遺傳算法中引入小生境技術(shù)能夠很好地解決這個(gè)問題.

1 小生境技術(shù)與物種形成過程

在自然環(huán)境當(dāng)中，“物以類聚，人以群分”是一種普遍的現(xiàn)象.這說明生物往往傾向于和其本身在性狀和特征等方面相似的同類在一起生活，并與其同類交配完成后代的增殖.生物的這種生存特點(diǎn)和增殖方式是有其積極意義的.在生物學(xué)上，小生境(niche)是指特定環(huán)境下一種組織的功能，我們也常常把具有共同特性的組織稱為物種(species).

為了說明小生境技術(shù)相對(duì)于基本遺傳算法的優(yōu)勢(shì)所在，我們考察基本遺傳算法應(yīng)用于多峰函數(shù)最大值點(diǎn)的求解與搜索過程.對(duì)于如(1)所示多峰函數(shù)，欲求其最大值點(diǎn).

若選用基本遺傳算法，初始群體的產(chǎn)生常常是以均勻分布的方式隨機(jī)產(chǎn)生.在算法的初始階段，個(gè)體在函數(shù)的定義域內(nèi)分布范圍相對(duì)較寬.伴隨著整個(gè)優(yōu)化過程的不斷推進(jìn)，群體將逐漸聚集到一個(gè)山峰上，我們得到的并非是全部的解.產(chǎn)生這種現(xiàn)象的根本原因是由于單一群體的規(guī)模有限，無法完成對(duì)于定義域內(nèi)所有點(diǎn)的探測(cè).而在實(shí)際應(yīng)用中，常常也需要得到其他山峰的情況.于是我們考慮生物界中的真實(shí)情況，也就是說交叉操作并非完全隨機(jī)，它受物種類別、所在區(qū)域、性別等條件的限制.盡管加入某些限制會(huì)對(duì)算法的性能造成一定影響，但從另一個(gè)角度講它能夠以一定區(qū)域?yàn)橄拗票３址N群的多樣性，這是有現(xiàn)實(shí)意義并被實(shí)驗(yàn)研究證明為有效的方法.因而我們需要對(duì)現(xiàn)有具有代表性的小生境技術(shù)進(jìn)行研究.

2 典型小生境技術(shù)研究

對(duì)于小生境機(jī)制的模擬方法，近年來已經(jīng)出現(xiàn)多種.歸納起來主要有三類，具體如下.

2.1 基于預(yù)選擇機(jī)制的小生境技術(shù)

基于預(yù)選擇機(jī)制的小生境技術(shù)是由Cavicchio于1970年在已有遺傳算法理論基礎(chǔ)上首先提出的.該預(yù)選擇機(jī)制規(guī)定，只有新生成子串的適應(yīng)度超過其父串的時(shí)候，子串才能完成對(duì)父串的替換.也就是說，這種機(jī)制僅允許子代替換與其本身性狀相似的個(gè)體(即父代個(gè)體)，因而該方法能夠有效保持群體的多樣性.更進(jìn)一步講，Cavicchio認(rèn)為該方法可以在群體規(guī)模較小的條件下仍能保持群體的多樣性.基于預(yù)選擇機(jī)制算法的實(shí)現(xiàn)步驟如下.

step1 算法初始化.主要完成初始種群的建立，遺傳參數(shù)的設(shè)定等.

step2 完成種群中所有個(gè)體適應(yīng)度的計(jì)算.

step3 執(zhí)行遺傳操作，即選擇、交叉、變異.

step4 針對(duì)新生成子串和父串的適應(yīng)度大小進(jìn)行比較.若子串的適應(yīng)度比父串的適應(yīng)度高，則子串替換父串；否則保持父串不變.

step5 若滿足算法終止條件，則算法停止；否則返回step2.

2.2 基于擁擠機(jī)制的小生境技術(shù)

1975年，De Jong對(duì)Cavicchi的預(yù)選擇機(jī)制進(jìn)行了改進(jìn)，提出基于擁擠機(jī)制的小生境技術(shù).在該排擠機(jī)制中，De Jong針對(duì)每代群體選擇代間覆蓋的機(jī)制，根據(jù)相似度來完成群體中一部分個(gè)體的替換.算法的具體實(shí)現(xiàn)步驟如下.

step1 算法初始化.主要完成初始種群的建立，遺傳參數(shù)的設(shè)定，排擠因子CF的確定等.

step2 完成種群中所有個(gè)體適應(yīng)度的計(jì)算.

step3 執(zhí)行遺傳操作，即選擇、交叉、變異.

step4 隨機(jī)確定當(dāng)前群體中1/CF個(gè)個(gè)體作為排擠因子成員.

step5 完成新生成個(gè)體與排擠因子成員相似性的比較.

step6 新群體的生成.即使用新生成的個(gè)體選擇排擠因子成員中最相似的個(gè)體完成替換.

step7 若滿足算法終止條件，則算法停止；否則返回step2.

對(duì)于以上算法，執(zhí)行的起始過程由于群體中個(gè)體的差別不大，故替換操作多數(shù)情況下為隨機(jī)選擇；隨著算法不斷執(zhí)行，群體中個(gè)體將形成多個(gè)小生境并逐漸被分類.在這種情況下，該算法選擇與其自身性狀最相似的排擠因子進(jìn)行替換，故能夠保持群體的多樣性.據(jù)De Jong稱，基于擁擠機(jī)制的小生境遺傳算法針對(duì)某些優(yōu)化問題能夠獲得比較滿意的結(jié)果，如多峰函數(shù)求極值等.

2.3 基于共享機(jī)制的小生境技術(shù)

基于共享機(jī)制的小生境技術(shù)是Goldberg和Richardson于1987年提出的.在該機(jī)制中，使用共享函數(shù)來確定每個(gè)個(gè)體在整個(gè)群體中的共享度.一個(gè)個(gè)體共享度的計(jì)算方法為該個(gè)體與整個(gè)群體中所有其他個(gè)體之間共享函數(shù)值之和.共享函數(shù)能夠提供群體中兩個(gè)個(gè)體之間關(guān)系密切程度(根據(jù)基因或表現(xiàn)型的相似性確定)的度量.若共享函數(shù)值較大則表明兩個(gè)個(gè)體間的關(guān)系較密切；反之則表明兩個(gè)個(gè)體間關(guān)系的密切程度不大.

也可以用形式化的方式來表達(dá)這個(gè)問題.設(shè)dij表示兩個(gè)個(gè)體之間關(guān)系的密切程度(度量方式有多種，如海明距離等).若以S表示共享函數(shù)，Si表示個(gè)體i在群體中的共享度，則(其中m為群體中個(gè)體的數(shù)量減1).

在完成群體中所有個(gè)體共享度計(jì)算的基礎(chǔ)上，個(gè)體i的適應(yīng)度f(i)調(diào)整為fs(i)，其中fs(i) =f(i)/Si.據(jù)此可知，基于共享機(jī)制的小生境技術(shù)能夠限制種群中的某一個(gè)或特殊個(gè)體無限制的增殖.目標(biāo)已有的測(cè)試數(shù)據(jù)表明，較基本遺傳算法而言，基于共享機(jī)制的小生境技術(shù)在解決多峰函數(shù)的優(yōu)化問題時(shí)能夠體現(xiàn)出更好的搜索性能.基于共享機(jī)制的小生境遺傳算法的基本實(shí)現(xiàn)步驟如下.

step1 算法初始化.主要完成初始種群的建立，遺傳參數(shù)的設(shè)定等.

step2 完成種群中所有個(gè)體適應(yīng)度的計(jì)算.

step3 執(zhí)行遺傳操作，即選擇、交叉、變異.

step4 完成種群中所有個(gè)體共享度的計(jì)算.

step5 根據(jù)個(gè)體的共享度重新計(jì)算每個(gè)個(gè)體的適應(yīng)度.

step6 對(duì)子代和父代個(gè)體的適應(yīng)度大小進(jìn)行比較.

step7 用子代個(gè)體替換父代個(gè)體，形成新一代群體.

step8 若滿足算法終止條件，則算法終止；否則返回step3.

2.4 隔離小生境技術(shù)

通過考察自然界中存在地理隔離方式，我們將遺傳算法中的初始群體以某種方式進(jìn)行劃分，得到若干個(gè)子群體.子群體間的進(jìn)化是彼此獨(dú)立的.而各個(gè)子群體由于其平均適應(yīng)度不同，故子群體間的進(jìn)化速度和群體自身規(guī)模通常是有差異的.由于隔離后的子群體的進(jìn)化過程彼此獨(dú)立，故可以針對(duì)各子群體進(jìn)行更為靈活的控制.據(jù)此，我國(guó)學(xué)者提出隔離小生境技術(shù)的概念.另外，自然界中的競(jìng)爭(zhēng)不僅存在于種群中個(gè)體之間，種群與種群之間也存在相互競(jìng)爭(zhēng).也就是說，適者生存的機(jī)制不僅存在于個(gè)體之間，對(duì)于種群也同樣適用.在隔離小生境技術(shù)中，我們通過引入兩級(jí)競(jìng)爭(zhēng)機(jī)制來實(shí)現(xiàn)競(jìng)爭(zhēng)機(jī)制，以保證得到更優(yōu)秀的個(gè)體.

3 幾種小生境技術(shù)性能比較分析

適應(yīng)值共享算法的執(zhí)行起始為選擇階段，該方法通過調(diào)整個(gè)體適應(yīng)值的手段達(dá)到維持種群多樣性的目的.擁擠算法的執(zhí)行起始為替換階段，新個(gè)體以某種方式與老個(gè)體競(jìng)爭(zhēng)完成替換，目的同樣是維持種群多樣性.而遺傳算法的競(jìng)爭(zhēng)機(jī)制為優(yōu)勝劣汰，由于適應(yīng)值共享算法能夠通過調(diào)整個(gè)體適應(yīng)值完成搜索過程，故其對(duì)于解的搜索能力優(yōu)于擁擠算法.

預(yù)選擇機(jī)制通過限定只有子串才能完成對(duì)父串的替換，故該方法能夠在一定程度上維持種群多樣性.但由于該方法較擁擠機(jī)制的靈活度差，故其收斂和搜索性能不及擁擠算法.

隔離小生境遺傳算法為兩級(jí)競(jìng)爭(zhēng)機(jī)制，即子群體中個(gè)體之間的競(jìng)爭(zhēng)和子群體之間的競(jìng)爭(zhēng).子群體個(gè)體間的競(jìng)爭(zhēng)側(cè)重于局部搜索性能，而子群體間的競(jìng)爭(zhēng)側(cè)重于全局搜索性能.故該算法能夠較好的平衡遺傳算法局部搜索與全局搜索間的矛盾.

［1］華潔，崔杜武.基于個(gè)體優(yōu)化的自適應(yīng)小生境遺傳算法［J］.計(jì)算機(jī)工程，2010(1)：200-202.

［2］陸青，梁昌勇，楊善林，張俊嶺.面向多模態(tài)函數(shù)優(yōu)化的自適應(yīng)小生境遺傳算法［J］.模式識(shí)別與人工智能，2009(1)：93-99.

［3］譚艷艷，許峰.自適應(yīng)模糊聚類小生境遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009(4)：56-59.

［4］黃鵾，陳森發(fā)，孫燕，郜振華.一種小生境正交遺傳算法研究［J］.東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2004(1)：135-137.