基于搜索空間分割的協同進化遺傳算法

郭方煒+許峰

摘要：

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

關鍵詞：

遺傳算法；協同進化；空間分割；ε自適應調整；算法效率

DOIDOI：10.11907/rjdk.172249

中圖分類號：TP312

文獻標識碼：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世紀70年代提出的一種基于自然進化的全局概率搜索優化算法[1]，廣泛應用于函數優化、組合優化、自動控制、圖像處理、機器學習、數據挖掘等領域[23]。SGA的全局收斂性較好，但局部搜索能力相對不足，且在搜索過程中易陷于早熟收斂[4]。協同進化思想1964年被首次提出[5]，20世紀90年代協同進化算法（coevolutionary algorithms，CEA）被提出[67]。目前，協同進化算法已成功應用到作業調度、人工神經網絡、模式識別和工程設計優化等領域[710]。

經典協同進化遺傳算法在進行空間分割時，沒有采用合適的方法控制種內及種間進化，無法控制子種群的規模，導致算法復雜度較高。本文在已有工作的基礎上，提出了基于搜索空間分割的改進協同進化遺傳算法，從理論上分析了算法的復雜度，并用數值實驗測評了算法性能。

1空間分割

遺傳算法是一種基于生物遺傳和進化優化的算法，其基本思想是：交叉機制能實現子種群優化問題的全局搜索，優化問題的局部搜索能利用變異機制實現，但是交叉和變異機制很難通過傳統算法協調，易陷于局部最優解。針對這一現象，提出一種改進的多種群遺傳算法。

本文根據多目標優化問題的特點，提出了基于搜索空間分割的多種群協同進化算法，闡述了算法思想、搜索空間分割方法、遺傳算法設計、超級個體集合的形成和更新策略以及種群的生成途徑等，并分析了算法計算的復雜性。

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

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

6結語

本文從空間分割的角度出發，提出了空間規模自適應調整的協同進化遺傳算法。復雜度的理論分析和數值實驗結果均表明：與經典協同進化遺傳算法相比，改進后的算法在一定程度上降低了解的計算復雜度。

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

參考文獻：

[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.

（責任編輯：杜能鋼）endprint