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

郭方煒+許峰

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

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

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：16727800（2017）004005104

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

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

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

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

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

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

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

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

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

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

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

4數(shù)值實(shí)驗(yàn)

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

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

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

參考文獻(xiàn)：[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]譚艷艷，許峰.基于適應(yīng)值共享的多生境排擠遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，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（#〗于歆杰，王贊基.自適應(yīng)調(diào)整峰半徑的適應(yīng)值共享遺傳算法[J].自動(dòng)化學(xué)報(bào)，2002，28（5）：816820.

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

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

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

（責(zé)任編輯：孫娟）

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