適應(yīng)值共享小生境遺傳算法實(shí)現(xiàn)與性能比較分析

趙 越，茹婷婷

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

小生境遺傳算法是近年來(lái)興起的一種進(jìn)化計(jì)算技術(shù).它以遺傳算法為基礎(chǔ)，將遺傳操作中的每一代個(gè)體進(jìn)一步劃分為若干個(gè)類.對(duì)于每一個(gè)類，從中選擇部分適應(yīng)值較高的優(yōu)秀個(gè)體組成一個(gè)群.算法在種群內(nèi)部以及種群與種群之間完成遺傳操作(包括選擇、交叉、變異)，最終產(chǎn)生新一代群體.在算法的實(shí)現(xiàn)過(guò)程中，還可以采用分享機(jī)制、預(yù)選擇機(jī)制和排擠機(jī)制等完成整個(gè)操作過(guò)程.由于小生境遺傳算法能夠更好的保持解空間群體的多樣性，并且具有較好的全局搜索性能和收斂速度，故其在很多優(yōu)化問(wèn)題中有著越來(lái)越廣泛的應(yīng)用[1].下文對(duì)應(yīng)用最多的基于適應(yīng)值共享的小生境遺傳算法進(jìn)行分析和研究.

1 基于適應(yīng)值共享小生境遺傳算法的基本思想

基于適應(yīng)值共享小生境遺傳算法最早是由Goldberg和Richardson于1987年提出的，它是目前為止所有小生境技術(shù)中應(yīng)用最多的方法之一[2].這種算法的基本思想是：將問(wèn)題解空間的峰視為資源，該資源由峰周圍的個(gè)體所共享.共享的方式是將個(gè)體的適應(yīng)值除以資源周圍的個(gè)體數(shù)，也就是說(shuō)，個(gè)體被選擇概率的調(diào)整是通過(guò)降低個(gè)體適應(yīng)值來(lái)實(shí)現(xiàn)的.如果某個(gè)體距離其他個(gè)體較近，則適應(yīng)值降低較多；如果某個(gè)體距離其他個(gè)體較遠(yuǎn)，則適應(yīng)值降低較少.算法通過(guò)這樣的機(jī)制使得排布稀疏的個(gè)體得到更多的機(jī)會(huì)繁衍，從而達(dá)到維持種群多樣性的目的.適應(yīng)值共享方法通常在選擇操作前實(shí)施，以保證隨后的選擇操作能夠根據(jù)共享后的適應(yīng)值進(jìn)行操作.

通常情況下，我們會(huì)對(duì)解空間的信息有一定了解.這部分信息主要包括峰的個(gè)數(shù)(k)或峰的半徑(σ).我們也可根據(jù)事先提供信息量的不同，將適應(yīng)值共享算法分為以下三類：僅使用k的算法，僅使用σ的算法及同時(shí)使用k和σ的算法.到目前為止，僅使用k的代表性算法有結(jié)合適應(yīng)值共享的k均值聚類算法(由Yin等人提出)[3-4]；僅使用σ的算法主要包括標(biāo)準(zhǔn)適應(yīng)值共享算法(由Goldberg等人提出)、清除算法(由Petrowski提出)和結(jié)合適應(yīng)值共享的自適應(yīng)k均值聚類算法(由Yin等人提出).同時(shí)使用k和σ的算法主要包括自適應(yīng)小生境算法(由Goldberg等人提出)和動(dòng)態(tài)小生境共享算法(由Miller等人提出).下面對(duì)常見適應(yīng)值共享小生境遺傳算法的實(shí)現(xiàn)機(jī)理進(jìn)行研究.

2 常見基于適應(yīng)值共享小生境遺傳算法實(shí)現(xiàn)機(jī)理比較分析

2.1 標(biāo)準(zhǔn)適應(yīng)值共享算法

該算法應(yīng)用的前提條件是已知解空間中小生境半徑，并要求峰半徑都相同，算法的主要實(shí)現(xiàn)步驟如下.

step1 完成種群個(gè)體間共享函數(shù)s(dij) 的計(jì)算，公式如(1)所示:

(1)

(1)式中，dij表示群體中個(gè)體i和j間的距離，σ為預(yù)先給出峰的半徑，α為函數(shù)的控制參數(shù)，一般取為1.通常而言，兩個(gè)體間共享函數(shù)值越大，則兩個(gè)體距離越近；

step2 完成種群中個(gè)體的共享值s(i)的計(jì)算，公式如(2)所示；

(2)

式(2)中，m為種群規(guī)模.通常來(lái)講，個(gè)體的共享值越大，則該個(gè)體附近有越多的其他個(gè)體；

(3)

式(3)中，f(i)為共享前個(gè)體i的適應(yīng)度；

step4 使用個(gè)體共享后的適應(yīng)值完成遺傳操作(即選擇、交叉和變異)，完成新一代種群的生成.

應(yīng)用標(biāo)準(zhǔn)適應(yīng)值共享算法的前提是要預(yù)先知道峰的半徑，假設(shè)峰的分布均勻且半徑相同，這在實(shí)際問(wèn)題中是很難滿足的.盡管標(biāo)準(zhǔn)適應(yīng)值共享算法的搜索效率和運(yùn)算速度不很理想，但該算法的穩(wěn)定性較好.故對(duì)于問(wèn)題解空間結(jié)構(gòu)未知的情形，可使用標(biāo)準(zhǔn)遺傳算法求得進(jìn)一步信息.

2.2 清除算法

標(biāo)準(zhǔn)適應(yīng)值共享算法需要完成種群中所有個(gè)體間距離dij的計(jì)算，即種群中所有個(gè)體共享小生境內(nèi)資源.若種群規(guī)模較大，則算法的效率將顯著下降.為改進(jìn)此算法，Petrowski于1996年提出了清除算法，該算法僅將有限資源提供給小生境內(nèi)的若干最優(yōu)個(gè)體.清除算法的實(shí)現(xiàn)步驟具體如下.

step1 將種群內(nèi)的個(gè)體依照適應(yīng)度降序排列；

step2 將第一個(gè)個(gè)體選作第一個(gè)小生境的中心；

step3 從第二個(gè)個(gè)體開始順次執(zhí)行以下步驟直到最末一個(gè)個(gè)體：

step3.1 若當(dāng)前個(gè)體距離其他所有小生境中心都大于σ，則該個(gè)體成為新小生境的中心，并成為優(yōu)勝者；

step3.2 若當(dāng)前個(gè)體距離某小生境中心小于σ，且這個(gè)小生境中個(gè)體數(shù)量小于k，則將該個(gè)體放入該小生境，將該個(gè)體記為優(yōu)勝者，并將小生境中個(gè)體數(shù)量加1；

step3.3 將其他個(gè)體標(biāo)記為失敗者；

step3.4 將全部失敗者的適應(yīng)度置零，并保持群體內(nèi)所有優(yōu)勝者的適應(yīng)值不變；

step4 使用修改后個(gè)體的適應(yīng)度值進(jìn)行遺傳操作(即選擇、交叉和變異)，得到新一代種群.

如果將標(biāo)準(zhǔn)適應(yīng)值共享算法中失敗者的共享值看作無(wú)限大，而將優(yōu)勝者的共享值看作1，則清除算法可以作為一種特殊的適應(yīng)值共享算法.

2.3 結(jié)合適應(yīng)值共享的自適應(yīng)k均值聚類算法

結(jié)合適應(yīng)值共享的自適應(yīng)k均值聚類算法的主要思想如下.首先把群體按照隨機(jī)的方式分為k組，分別與k個(gè)小生境相對(duì)應(yīng)；由個(gè)體的原適應(yīng)度除以個(gè)體的共享值s(i)得到個(gè)體的共享適應(yīng)度.個(gè)體的共享值s(i)由式(4)給出.

(4)

式中，dic表示個(gè)體i與第c組中心之間的距離；nc表示第c組中個(gè)體數(shù)量；α通常取為1.一般說(shuō)來(lái)，需預(yù)先給定參數(shù)dmax和dmin的值.dmax表示某個(gè)聚類中的個(gè)體和該聚類中心之間距離的最大值；dmin表示聚類中心之間距離的最小值.若存在兩組中心距離小于dmin，則將此兩組合并為一組；若存在與所有組中心距離均大于dmax的個(gè)體，則以該個(gè)體形成一個(gè)新組.算法的具體實(shí)現(xiàn)步驟如下.

step1 將種群內(nèi)的個(gè)體依照適應(yīng)度降序排列；

step2 在[1，N]之間隨機(jī)生成整數(shù)k，并將其作為初始小生境的數(shù)量；

step3 將排列后的前k個(gè)個(gè)體分別作為小生境中心放入不同的小生境中.檢查是否所有小生境間距離均大于dmin，若不滿足，則將小生境合并，并選擇新的小生境中所有個(gè)體的中心；

step4 針對(duì)其它N-k個(gè)個(gè)體，計(jì)算其與已有小生境中心間距離.若距離比dmax大，則生成新小生境，并以該個(gè)體作為小生境中心.否則將該個(gè)體放入距離最近的小生境中.檢查小生境中心之間距離是否都比dmin大，若不滿足則合并對(duì)應(yīng)的小生境；

step5 所有個(gè)體放置完成以后，將小生境中心固定，按照最小距離原則把所有個(gè)體安排到最近的小生境中；

step6 按式(4)完成種群中每個(gè)個(gè)體的共享值s(i)的計(jì)算；

step7 計(jì)算每個(gè)個(gè)體共享后的適應(yīng)值；

step8 按照共享后的適應(yīng)值完成遺傳操作(包括選擇、交叉和變異)，并形成下一代種群.

算法的發(fā)明人Yin和Germay將適應(yīng)值共享算法與自適應(yīng)k均值聚類算法結(jié)合使用，結(jié)果表明這樣可以提高算法的運(yùn)行效率.與前兩種適應(yīng)值共享算法相比較，本算法沒有要求解空間中所有峰半徑均相同.實(shí)踐表明，結(jié)合適應(yīng)值共享的k均值聚類算法能夠提高標(biāo)準(zhǔn)適應(yīng)值共享算法的運(yùn)行效率.但缺點(diǎn)是算法在接近收斂時(shí)可能產(chǎn)生錯(cuò)誤聚類.

3 幾種適應(yīng)值共享算法性能比較分析

適應(yīng)值共享算法的執(zhí)行在遺傳算法的選擇階段之前.算法通過(guò)修改個(gè)體的適應(yīng)度實(shí)現(xiàn)種群的多樣性，以防止算法早熟并提高搜索的效率.標(biāo)準(zhǔn)適應(yīng)值共享算法通常認(rèn)為峰的分布是均勻的，并具有相同半徑，但實(shí)際問(wèn)題的求解中很難滿足這個(gè)要求.但由于標(biāo)準(zhǔn)適應(yīng)值共享算法運(yùn)行效率穩(wěn)定，所以該算法可以滿足對(duì)峰的探索性需要.而結(jié)合適應(yīng)值共享的k均值聚類算法能夠減少標(biāo)準(zhǔn)適應(yīng)值共享算法的時(shí)間，提高算法運(yùn)行效率，但接近收斂時(shí)可能發(fā)生錯(cuò)誤聚類.在實(shí)際應(yīng)用中我們需要根據(jù)實(shí)際情況完成適應(yīng)值共享小生境遺傳算法的設(shè)計(jì).

參考文獻(xiàn)：

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

[2]周洪偉，徐松林，徐靜.改進(jìn)的小生境遺傳算法[J].微計(jì)算機(jī)信息，2007(18):208-209.

[3]張俐.基于小生境遺傳算法的MTSP問(wèn)題求解[J].系統(tǒng)工程，2009(7):119-121.

[4]徐程，鄭洪源.基于小生境遺傳算法的關(guān)聯(lián)規(guī)則挖掘研究[J].中國(guó)制造業(yè)信息化，2008(23):67-70.