基于搜索空間分割的協(xié)同進(jìn)化遺傳算法

郭方煒+許峰

摘要：

針對經(jīng)典協(xié)同進(jìn)化遺傳算法在優(yōu)化大決策空間問題時(shí)計(jì)算復(fù)雜度較高的問題，提出了一種基于搜索空間分割的協(xié)同進(jìn)化遺傳算法，其基本思想是：將種群分割為不同規(guī)模的子種群，在進(jìn)化過程中應(yīng)用ε自適應(yīng)方法調(diào)整子種群規(guī)模。復(fù)雜度分析和數(shù)值實(shí)驗(yàn)表明，改進(jìn)后的算法可降低算法計(jì)算量，提高算法的優(yōu)化效率。

關(guān)鍵詞：

遺傳算法；協(xié)同進(jìn)化；空間分割；ε自適應(yīng)調(diào)整；算法效率

DOIDOI：10.11907/rjdk.172249

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）001009203

Abstract：In order to solve the problem of high computational complexity when the classical coevolutionary genetic algorithm is used to optimize the large decision space problem， a cooperative evolutionary genetic algorithm based on the search space segmentation is proposed. The basic idea is that the population is divided into sub populations with different scales， and the ε adaptive method is used to adjust the size of the sub population in the evolutionary process. Complexity analysis and numerical experiments show that the improved algorithm can reduce the computational complexity and optimize the efficiency of the algorithm.

Key Words：genetic algorithm； coevolution； spatial segmentation； adaptive adjustment； algorithm efficiency

0引言

基本遺傳算法（Simple Genetic Algorithm，SGA）是20世紀(jì)70年代提出的一種基于自然進(jìn)化的全局概率搜索優(yōu)化算法[1]，廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、自動(dòng)控制、圖像處理、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域[23]。SGA的全局收斂性較好，但局部搜索能力相對不足，且在搜索過程中易陷于早熟收斂[4]。協(xié)同進(jìn)化思想1964年被首次提出[5]，20世紀(jì)90年代協(xié)同進(jìn)化算法（coevolutionary algorithms，CEA）被提出[67]。目前，協(xié)同進(jìn)化算法已成功應(yīng)用到作業(yè)調(diào)度、人工神經(jīng)網(wǎng)絡(luò)、模式識別和工程設(shè)計(jì)優(yōu)化等領(lǐng)域[710]。

經(jīng)典協(xié)同進(jìn)化遺傳算法在進(jìn)行空間分割時(shí)，沒有采用合適的方法控制種內(nèi)及種間進(jìn)化，無法控制子種群的規(guī)模，導(dǎo)致算法復(fù)雜度較高。本文在已有工作的基礎(chǔ)上，提出了基于搜索空間分割的改進(jìn)協(xié)同進(jìn)化遺傳算法，從理論上分析了算法的復(fù)雜度，并用數(shù)值實(shí)驗(yàn)測評了算法性能。

1空間分割

遺傳算法是一種基于生物遺傳和進(jìn)化優(yōu)化的算法，其基本思想是：交叉機(jī)制能實(shí)現(xiàn)子種群優(yōu)化問題的全局搜索，優(yōu)化問題的局部搜索能利用變異機(jī)制實(shí)現(xiàn)，但是交叉和變異機(jī)制很難通過傳統(tǒng)算法協(xié)調(diào)，易陷于局部最優(yōu)解。針對這一現(xiàn)象，提出一種改進(jìn)的多種群遺傳算法。

本文根據(jù)多目標(biāo)優(yōu)化問題的特點(diǎn)，提出了基于搜索空間分割的多種群協(xié)同進(jìn)化算法，闡述了算法思想、搜索空間分割方法、遺傳算法設(shè)計(jì)、超級個(gè)體集合的形成和更新策略以及種群的生成途徑等，并分析了算法計(jì)算的復(fù)雜性。

空間分割算法思想是：首先將較大的搜索空間分割為多個(gè)子空間，然后在每個(gè)子空間上由一個(gè)子種群不斷進(jìn)化優(yōu)化，分別將不同的遺傳算法應(yīng)用到子種群內(nèi)部和子種群之間，由遺傳算法運(yùn)算產(chǎn)生新的種群和新的個(gè)體，以其覆蓋成新的子空間；采用Pareto最優(yōu)解[7]提交方法、超級個(gè)體集合更新策略，以保證高效找到Pareto最優(yōu)解。

對于多目標(biāo)優(yōu)化問題中的整個(gè)搜索空間而言，子空間應(yīng)該是完備的，每個(gè)子空間之間最好是隔離的，整個(gè)搜索空間S的分割可用S1，S2，…，SNS表示，其中，子空間的數(shù)目設(shè)定為NS，則有∪Nsi=1Si=S，Si∩Sj=，1≤i，j≤Ns。

6結(jié)語

本文從空間分割的角度出發(fā)，提出了空間規(guī)模自適應(yīng)調(diào)整的協(xié)同進(jìn)化遺傳算法。復(fù)雜度的理論分析和數(shù)值實(shí)驗(yàn)結(jié)果均表明：與經(jīng)典協(xié)同進(jìn)化遺傳算法相比，改進(jìn)后的算法在一定程度上降低了解的計(jì)算復(fù)雜度。

由于協(xié)同進(jìn)化算法的理論體系尚不成熟，算法性能很難從理論層面進(jìn)行證明，而只能根據(jù)對比實(shí)驗(yàn)加以說明。提高經(jīng)典協(xié)同進(jìn)化遺傳算法優(yōu)化效率的方法有多種，如組織進(jìn)化、引進(jìn)多智能體等。本文采用的空間分割方法與其它方法相比，優(yōu)點(diǎn)是可以與自適應(yīng)調(diào)整方法相結(jié)合，缺點(diǎn)是對解的質(zhì)量基本沒有改進(jìn)，這完全符合優(yōu)化中的“沒有免費(fèi)的午餐定理（No Free Lunch， NFL）”。

參考文獻(xiàn)：

[1]HOLLAND J H.Adaptation in natural and artificial systems [M].Cambridge（USA）：MIT Press，1975（41）：559577.

[2]GOLDBERG D E.Genetic algorithms in search，optimization.and machine learning[M].New Jersey：Addison Wesley Publishing Company，1989.endprint

[3]PLANT W R，SCHAEFER G，NAKASHIMA T.An overview of genetic algorithms in simulation soccer[C].2008 IEEE Congress on Evolutionary Computation.Hong Kong：IEEE Press，2008：38983905.

[4]CAO XIAN BIN，LUO WENJIAN，WANG XIFA.A coevo1ution pattern based on ecological population competition model[J].Journal of Software，2001，12（4）：556562.

[5]EHDICH P R，RAVEN P H.Butterflies and plants：a study in evolution[J].Evolution，1964（18）：586608..

[6]ROSIN C D，BELEW R K.New methods for competitive evolution[J].Evolutionary Computation，1997，5（1）：129.

[7]CARTLIDGE J，BULLOCK S.Combating evolutionary disengagement by reducing parasite virulence[J].Evolutionary Computation，2002，12（2）：193222.

[8]JONG K A DE.The analysis of the behavior of a class of genetic adaptive system[D].Michigan：University of Michigan，1975.

[9]SCHAFFER J D，CARUANA R A，ESHELMAN L J.A study of control parameters affecting online performance of genetic algorithms for function optimization[C].Proceedings of the 3rd International Conference on Genetic Algorithms.Los Altos（USA）：Morgan Kaufmann Publish，1989：5160.

[10]DONG HONGBIN，HUANG HOUKUAN，YIN GUISHENG，et al.An overview of the research on evolutionary algorithms[J].Journal of Computer Research and Development，2008，45（3）：454463.

[11]AGUIRRE H， TANAKA K.Adaptive εranking on manyobjective problems [J].Evolutionary Intelligence， 2009（2）：183206.

（責(zé)任編輯：杜能鋼）endprint