協(xié)同進化多生境遺傳算法

郭方煒+許峰

摘要：為了提高多生境遺傳算法的優(yōu)化效率，提出了一種基于協(xié)同進化的多生境遺傳算法，其基本思想是：將種群分割為若干子種群，每個子種群采用合作型協(xié)同進化方法獨立進化；個體評價采用多生境方法，具體作法為：在對個體的適應值進行共享調(diào)整的同時，在選擇中采用確定性排擠方法，在替換中采用最相似個體適應度最差個體被替換策略，以維持種群的多樣性。數(shù)值實驗表明，上述算法在維持多生境遺傳算法較強全局搜索能力的同時，可適當提高算法運行效率。

關鍵詞：遺傳算法；協(xié)同進化；多生境；多峰函數(shù)；算法效率DOI：10.11907/rjdk.162706中圖分類號：TP312

文獻標識碼：A

文章編號：16727800（2017）004005104

0引言 在多模態(tài)函數(shù)優(yōu)化問題中，需要搜索多模函數(shù)空間的多個極值點。遺傳算法已被證明是求解多模態(tài)函數(shù)優(yōu)化問題的有效算法[1]，其中基于適應值共享的多生境遺傳算法（MultiNiche Fitness Sharing Crowding Genetic Algorithm，MNSCGA）[2]綜合了適應值共享與確定性排擠兩種遺傳算法在維持種群多樣性方面的優(yōu)點，具有較強的多模態(tài)搜索能力。不過，也正是由于基于適應值共享的多生境遺傳算法在選擇、替換中采用了較為復雜的策略，從而使得該算法具有較高的算法復雜度，算法運行效率較低。〖JP〗協(xié)同進化在生物學中是指生物與環(huán)境、生物與生物之間在進化過程中的某種依存關系。Ehrlich和Raven[3]最早提出進化算法中的協(xié)同進化概念，Hillis[4]首先將協(xié)同進化思想引入遺傳算法。此后，陸續(xù)出現(xiàn)了多種協(xié)同進化遺傳算法[58]。由于協(xié)同進化遺傳算法采用多個子種群同時進化，且考慮了子種群間的協(xié)同進化，有類似于并行計算的特點，通常可加快種群的進化進程，提高算法的運行效率。本文將協(xié)同進化思想與多生境排擠策略相結(jié)合，提出了一種基于協(xié)同進化的多生境排擠遺傳算法，并根據(jù)數(shù)值實驗對該算法進行了性能分析。

1多生境排擠遺傳算法 基本遺傳算法采用輪盤賭選擇方式，選擇壓力偏大，不利于維持種群的多樣性。MNSCGA在適應值共享的基礎上，將排擠機制應用到選擇和替換過程，減緩了選擇壓力。此外，在交叉過程中，算法還允許不同生境之間的競爭，從而使得各小生境內(nèi)均保持有一定量的小群體，即多生境排擠。這些方法有效地維持了種群的多樣性，提高了算法的多模態(tài)搜索能力。

1.1排擠選擇 MNSCGA采用排擠選擇方法，具體可分為兩個步驟：從群體中隨機地選擇一個個體Ii；從一個含有Cs個個體的排擠組中選擇與Ii配對的個體Ij，排擠組中的Cs個個體是從整個種群中隨機產(chǎn)生的。Ij的選擇規(guī)則為：在所有排擠組個體中，選擇與Ii最相似的個體作為Ij。

1.2間隔交叉與變異 Mahfoud[9]的研究證實，在小生境遺傳算法中，若采用單點交叉，則子代往往與父代分屬不同的生境。MNSCGA采用的是間隔交叉[2]，即每一對父代個體交叉后只產(chǎn)生一個子代個體。由于根據(jù)排擠規(guī)則，交叉的一對個體的搜索區(qū)間相鄰，所以由間隔交叉所產(chǎn)生的子代個體以很大的概率與其父代個體屬于同一生境。這樣，大大降低了搜索的盲目性。 MNSCGA采用的變異算子與基本遺傳算法大致相同，唯一的區(qū)別是變異操作僅對由間隔交叉產(chǎn)生的那一個子代個體進行。

1.3最相似個體適應值最小替換 MNSCGA采用最相似個體中適應值最小個體替換（Worst Among Most Similar， WAMS）的方法，其操作步驟如下：①對父代和子代群體進行適應值共享調(diào)整；②從父代個體中隨機選擇Cf個排擠組，每組有s個個體；③在每個排擠組中，尋找一個與子代個體最為相似的個體；④比較Cf個個體的適應值大小，挑選出適應值最小的個體將其替換；⑤重復步驟②～⑤，直至完成群體間一次替換。 WAMS方法的示意如圖1所示。

2協(xié)同進化遺傳算法

2.1協(xié)同進化基本思想 遺傳算法是建立在進化論基礎上的，強調(diào)優(yōu)勝劣汰，其核心是種群內(nèi)個體的競爭，而忽略了生物其它方面的各種聯(lián)系，如合作、利他和寄生等，因此具有一定的片面性。其實，在自然界中，生物進化主要包括相互制約和相互受益兩類機制，優(yōu)勝劣汰僅僅是制約機制中的一種。基本遺傳算法由于沒有考慮進化中的受益機制，而在對復雜優(yōu)化問題時，往往無能為力。 協(xié)同進化概念最早由Ehrlich和Raven在討論蝴蝶之間進化影響時提出的[3]。Hillis[4]首先將協(xié)同進化引入遺傳算法，提出了協(xié)同進化遺傳算法（Coevolutionary Genetic Algorithm，CGA），其基本思想是[11]：將整個種群分成多個子種群，每個子種群同時進化，進化時不僅考慮同一子種群中個體之間的關系，而且還要考慮不同子種群中個體之間的關系。對個體進行評價時，個體適應度不僅由目標函數(shù)決定，還由其他個體決定。也就是說，子種群之間通過相互作用而共同進化，這樣就彌補了傳統(tǒng)遺傳算法只考慮競爭機制的不足。協(xié)同進化遺傳算法流程如圖2所示。

2.2合作型協(xié)同進化遺傳算法 協(xié)同進化遺傳算法主要有競爭型協(xié)同進化遺傳算法和合作型協(xié)同進化遺傳算法兩種。由于合作型協(xié)同進化遺傳算法（Cooperative Coevolutionary Genetic Algorithm， CCGA）的進化效率較高，且計算復雜度較小，所以逐漸成為協(xié)同進化遺傳算法的主流。CCGA首先將決策變量的空間分割為若干子空間，每個子空間經(jīng)編碼后即構(gòu)成一個子種群，各子種群獨立進行進化。在個體適應度評價時，要將待評價個體與其它子種群中選擇的個體相結(jié)合，構(gòu)成了一個完整解，通過計算此完整解的目標函數(shù)值得到個體適應度。

3協(xié)同進化多生境遺傳算法

3.1算法基本思想 多生境遺傳算法能較好地維持種群的多樣性，具有良好的多峰搜索能力。但由于多生境遺傳算法在適應值共享的基礎上添加了排擠機制，且采用了較為復雜的最相似個體中適應值最小個體替換策略，這就使得此算法的計算復雜度較高，運行效率欠佳。 考慮到協(xié)同進化具有類似于“并行進化”的特點，本文提出一種基于合作型協(xié)同進化思想的多生境遺傳算法（Cooperative Coevolutionary Multiniche Genetic Algorithm， CCMNGA），其基本思想是：將種群分割為若干子種群，每個子種群采用合作型協(xié)同進化方法獨立進化；個體評價采用多生境方法，具體作法為：在對個體的適應值進行共享調(diào)整的同時，〖HJ*3〗在選擇中采用確定性排擠方法，在替換中采用最相似個體適應度最差個體被替換策略，以維持種群的多樣性。

3.2算法步驟 ①將整個種群分成若干個子種群；②對每個子種群采用合作型協(xié)同進化方法進化；③對子種群中的個體進行適應度共享調(diào)整；④對每一個個體i，根據(jù)排擠選擇機制尋找與之匹配的個體j；⑤對個體i和j，以概率Pc進行間隔交叉，以概率Pm進行變異；⑥根據(jù)WAMS方法進行替換，完成種群間的一次迭代；⑦將各種群中的個體合并，計算適應值，進行個體評價；⑧若滿足結(jié)束條件，則算法結(jié)束，否則轉(zhuǎn)②。

4數(shù)值實驗

從圖3、圖4和表2可以看出，CCMNGA不僅搜索到了全部的全局最優(yōu)解，而且精度較高，這充分顯示了CCMNGA較佳的全局搜索能力和局部尋優(yōu)能力。表3和表4分別給出了CCMNGA和MNSCGA對函數(shù)f1（x，y）和f2（x，y）進行10次優(yōu)化的成功率、平均進化代數(shù)和平均運行時間。搜索到全部峰，且滿足表1中的收斂判據(jù)視為成功。

從表3和表4中可以很清楚地看出，無論對相對較簡單的多峰函數(shù)f1（x，y）還是比較復雜的多峰函數(shù)f2（x，y），CCMNGA和MNSCGA兩種算法搜索多峰的能力基本相當，均保持較高的成功率。但CCMNGA的平均進化代數(shù)和平均運行時間明顯低于MNSCGA，特別對于復雜多峰函數(shù)f2（x，y），優(yōu)勢更加明顯。這在一定程度上表明，引入了協(xié)同進化機制，確實可以提升多生境遺傳算法的運行效率。

5結(jié)語 本文針對多生境遺傳算法運行效率較低的缺陷，提出了一種基于合作型協(xié)同進化思想的多生境遺傳算法。數(shù)值實驗結(jié)果表明，改進后的算法不僅保持了多生境遺傳算法多峰搜索能力高的優(yōu)點，而且在一定程度上提高了算法的運行效率。 需要指出的是，由于小生境遺傳算法特別是協(xié)同進化遺傳算法的理論基礎還很薄弱，譬如整個種群如何合理分組、子種群的規(guī)模能否自適應變化、如何確定搜索區(qū)域、如何選擇代表個體等問題尚沒有明確的結(jié)論[1213]。另外，本文對改進算法的性能研究只是根據(jù)對測試問題的對比實驗，這無疑在一定程度上影響了結(jié)論的普適性。

參考文獻：[1]MILLER B L，SHAW M J.Genetic algorithms with dynamic niche sharing for multimodal function optimization[C].In： IEEE International Conference on Evolutionary Computation， Piscataway， NJ： IEEE Press，1996：786791.

[2]譚艷艷，許峰.基于適應值共享的多生境排擠遺傳算法[J].計算機工程與應用，2009，45（5）：4649.

[3]EHRLICH P R，RAVEN P H.Butterflies and plants：a study in coevolution[J].Evolution，1965（18）：586608.

[4]HILLIS W D.Coevolution parasites improve simulated evolution as an optimization procedure[C].Proceeding of 2nd Artificial Life Conference，New York： AddisonWesley，1991：25369.

[5]PENAREYES C A，SIPPER M.Fuzzy CoCo：a cooperative coevolutionary approach to fuzzy modeling[J].Fuzzy System，2001，9（5）：727737.

[6]IORIO A W，LI X D.Parameter control within a cooperative coevolutionary genetic algorithm[C].Proceedings of Parallel Problem Soling from Nature，Berlin：SpringerVerlag，2002：247256.

[7]IORIO A W，LI X D.A cooperative coevolutionary multiobjective algorithm using nondominated sorting[C].Proceedings of 2003 Genetic and Evolutionary Computation Conference，San Mateo：Morgan Kaufmann，2004：537548.

[8]SIM K B，LEE D W，KIM J Y.Game theorybased coevolutionary algorithm，a new computational coevolutionary approach[J].International Journal of Control， Automation， and Systems，2004，2（4）：463474.[9]MAHFOUD S W.Simple analytical models of genetic algorithms for multimodal function optimization[R].IlliGAL Report No. 93001，Dept. of Computer Science， University of Illinois，UrbanaChampaign，1993.〖ZK）〗[10]〖ZK（#〗于歆杰，王贊基.自適應調(diào)整峰半徑的適應值共享遺傳算法[J].自動化學報，2002，28（5）：816820.

[11]祝勤友，許峰.自適應鄰居結(jié)構(gòu)元胞遺傳算法[J].軟件導刊，2015，14（11）： 3942.

[12]鞏敦衛(wèi)，孫曉燕.協(xié)同進化遺傳算法理論及應用[M].北京：科學出版社，2009.

[13]焦李成，劉靜.協(xié)同進化計算與多智能體系統(tǒng)[M].北京：科學出版社，2006.

（責任編輯：孫娟）

Abstract：In order to improve the optimization efficiency of multiniche genetic algorithm， a multiniche genetic algorithm based on coevolution is proposed. The basic idea is that the population is divided into several subpopulations， and each subpopulation evolves independently using cooperative coevolutionary method. Multiniche method is used to individual evaluation， and the specific methods is that individual adaptive value is share adjustment at the same time， the deterministic crowding method is used to choice， and WAMS is used to replace， so that maintain the diversity of population. Numerical experiments show that the algorithm can improve the operation efficiency of the algorithm， while maintaining the strong global searching ability of the multi niche genetic algorithm.

Key Words： Genetic Algorithm； Coevolution； MultiNiche； Multipeak Function； Algorithm Efficiency