適應值共享小生境遺傳算法實現與性能比較分析

趙 越，茹婷婷

(1.吉林建筑大學 計算機科學與工程學院，吉林 長春 130118; 2.吉林建筑大學 基礎科學部，吉林 長春 130118)

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

1 基于適應值共享小生境遺傳算法的基本思想

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

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

2 常見基于適應值共享小生境遺傳算法實現機理比較分析

2.1 標準適應值共享算法

該算法應用的前提條件是已知解空間中小生境半徑，并要求峰半徑都相同，算法的主要實現步驟如下.

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

(1)

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

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

(2)

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

(3)

式(3)中，f(i)為共享前個體i的適應度；

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

應用標準適應值共享算法的前提是要預先知道峰的半徑，假設峰的分布均勻且半徑相同，這在實際問題中是很難滿足的.盡管標準適應值共享算法的搜索效率和運算速度不很理想，但該算法的穩定性較好.故對于問題解空間結構未知的情形，可使用標準遺傳算法求得進一步信息.

2.2 清除算法

標準適應值共享算法需要完成種群中所有個體間距離dij的計算，即種群中所有個體共享小生境內資源.若種群規模較大，則算法的效率將顯著下降.為改進此算法，Petrowski于1996年提出了清除算法，該算法僅將有限資源提供給小生境內的若干最優個體.清除算法的實現步驟具體如下.

step1 將種群內的個體依照適應度降序排列；

step2 將第一個個體選作第一個小生境的中心；

step3 從第二個個體開始順次執行以下步驟直到最末一個個體：

step3.1 若當前個體距離其他所有小生境中心都大于σ，則該個體成為新小生境的中心，并成為優勝者；

step3.2 若當前個體距離某小生境中心小于σ，且這個小生境中個體數量小于k，則將該個體放入該小生境，將該個體記為優勝者，并將小生境中個體數量加1；

step3.3 將其他個體標記為失敗者；

step3.4 將全部失敗者的適應度置零，并保持群體內所有優勝者的適應值不變；

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

如果將標準適應值共享算法中失敗者的共享值看作無限大，而將優勝者的共享值看作1，則清除算法可以作為一種特殊的適應值共享算法.

2.3 結合適應值共享的自適應k均值聚類算法

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

(4)

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

step1 將種群內的個體依照適應度降序排列；

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

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

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

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

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

step7 計算每個個體共享后的適應值；

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

算法的發明人Yin和Germay將適應值共享算法與自適應k均值聚類算法結合使用，結果表明這樣可以提高算法的運行效率.與前兩種適應值共享算法相比較，本算法沒有要求解空間中所有峰半徑均相同.實踐表明，結合適應值共享的k均值聚類算法能夠提高標準適應值共享算法的運行效率.但缺點是算法在接近收斂時可能產生錯誤聚類.

3 幾種適應值共享算法性能比較分析

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

參考文獻：

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

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

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

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