合作型协同演化算法研究进展

摘要/Abstract

摘要：

合作型协同演化算法是近年来计算智能研究的热点。它运用生物协同演化的思想，通过构建两个或者多个种群，建立它们之间的合作关系。两个或多个种群通过相互合作来提高各自的性能，适应复杂系统的动态演化环境以及大规模演化环境，从而达到种群优化的目的。主要介绍了合作型协同演化算法的研究状况以及国内外研究进展，详细介绍了它的基本结构及对应的研究、基本算法及一些新兴算法，同时介绍了一些在现实生活中的应用，展望了合作型协同演化算法的发展前景。

关键词: 合作型协同演化算法, 问题分解, 子空间相关性

Abstract:

Cooperative coevolution algorithm is a hot research topic in computational intelligence in recent years.Inspired by the principle of natural selection,cooperative coevolution algorithm constructs two or more groups and establishes the cooperative relationship among the groups.Two or more groups cooperates together to improve their performance,be adapted to dynamic evolutionary circumstance of complicated systems and largescale evolutionary circumstance,thus achieving the goal of population optimization.The research state and advances of cooperative coevolution algorithms in domestic and foreign are discussed and surveyed.The paper introduces the three main aspects of cooperative coevolution algorithm: basic structure and corresponding studies,basic and improved algorithms,and some applications in the real life.Finally,research prospects are indicated.

Key words: cooperative coevolution algorithm;problem decomposition;subspace correlation

张凯波，李斌. 合作型协同演化算法研究进展[J]. J4, 2014, 36(04): 674-684.

ZHANG Kaibo,LI Bin. Research overview of cooperative coevolutionary algorithms [J]. J4, 2014, 36(04): 674-684.

参考文献

［1］Potter A M, De Jong K A. A cooperative coevolutionary approach to function optimization ［C］∥Proc of the 3rd International Conference on Parallel Problem Solving from Nature, 1994:249257.
［2］Liu Y, Yao X, Zhao Q，et al．Scaling up fast evolutionary programming with cooperative coevolution ［C］∥Proc of the 2001 Congress on Evolutionary Computation, 2001:11011108.
［3］Potter A M , De Jong K A. Evolving neural networks with collaborative species ［C］∥Proc of 1995 Summer Computer Simulation Conference, 1995:340345.
［4］Potter A M, De Jong K A, Grefenstette J J. A coevolutionary approach to learning sequential decision rules ［C］∥Proc of the 6th International Conference on Genetic Algorithms, 1995:366370.
［5］Potter A M , De Jong K A．Cooperative coevolution：An architecture for evolving coadapted subcomponents ［J］．Evolutionary Computation，2000,8(1):129.
［6］Shi Y， Teng H, Li Z．Cooperative coevolutionary differential evolution for function optimization ［C］∥Proc of the 1st International Conference on Natural Computation, 2005:10801088．
［7］Yang Zhenyu, Tang Ke, Yao Xin. Differential evolution for high dimensional function optimization ［C］∥Proc of IEEE Congress on Evolutionary,2007:1.
［8］Omidvar M N, Li X, Yang Z, et al. Cooperative coevolution for large scale optimization through more frequent random grouping ［C］∥Proc of IEEE World Congress on Computational Intelligence ,2010:1.
［9］Wang Y, Li B, Lai X X. Variance priority based cooperative coevolution differential evolution for large scale global optimization ［C］∥Proc of the 2009 IEEE Congress on Evolutionary Computation, 2009:12321239.
［10］Weicker K,Weicker N.On the improvement of coevolutionary optimizers by learning variable interdependencies ［C］∥Proc of the 1999 Congress on Evolutionary Computation, 1999:16271632.
［11］Kim M W, Ryu J W. Species merging and splitting for efficient search in coevolutionary algorithm ［C］∥Proc of the 8th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2004),2004:332341.
［12］Kim M W, Ryu J W. An efficient coevolutionary algorithm using dynamic species control ［C］∥Proc of the 3rd International Conference on Natural Computation, 2007:431435.
［13］Ray T, Yao Xin. A cooperative coevolutionary algorithm with correlation based adaptive variable partitioning ［C］∥Proc of 2009 IEEE Congress on Evolutionary Computation, 2009:983989.
［14］Chen Wenxiang, Weise T, Yang Zhenyu, et al. Largescale global optimization using cooperative coevolution with variable interaction learning ［C］∥Proc of Parallel Problem Solving from Nature, 2010:300309.
［15］Yang Z, Tang K, Yao X. Multilevel cooperative coevolution for large scale optimization ［C］∥Proc of the 2008 IEEE Congress on Evolutionary Computation, 2008:16631670.
［16］Chandra R, Frean M, Zhang Mengjie. Building subcomponents in the cooperative coevolution framework for training recurrent neural networks ［R］.Technical Report, New Zealand:Victoria University of Wellington,2009.
［17］Gomez F,Schmidhuber J,Miikkulainen R.Accelerated neural evolution through cooperatively coevolved synapses ［J］. Journal of Machine Learning Research, 2008(9):937965.
［18］Min Shi. Empirical analysis of cooperative coevolution using blind decomposition ［C］∥Proc of the 13th Annual Conference Companion on Genetic and Evolutionary Computation,2011:141142.
［19］Wiegand R P, Liles W C, De Jong K A. An empirical analysis of collaboration methods in cooperative coevolutionary algorithms ［C］∥Proc of the 2nd Annual Conference Companion on Genetic Evolutionary Computation Conference, 2001:12351242.
［20］Luke S, Sullivan K, Abidi F. Large scale empirical analysis of cooperative coevolution［C］∥Proc of the 13th Annual Conference Companion on Genetic and Evolutionary Computation Conference, 2011:151152.
［21］Panait L, Luke S. Timedependent collaboration schemes for cooperative coevolutionary algorithms ［C］∥Proc of the AAAI Fall Symposium on Coevolutionary and Coadaptive Systems, 2005:1.
［22］Crciun C, Nicoar M, Zaharie D. Enhancing the scalability of metaheuristic by cooperative coevolution ［C］∥Proc of the 7th International Conference on LargeScale Scientific Computing, 2010:310317.
［23］Zhu F, Guan S. Cooperative coevolution of GAbased classifiers based on input decomposition ［J］. Journal of Engineering Applications of Artificial Intelligence, 2008,21(8):13601369.
［24］Wang Chao, Gao Jinghuai. A new differential evolution algorithm with cooperative coevolutionary selection operator for waveform inversion ［C］∥Proc of 2010 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), 2011:688690.
［25］Teng Hongfei, Chen Yu, Zeng Wei, et al. A dualsystem variablegrain cooperative coevolutionary algorithm:Satellitemodule layout design ［J］. IEEE Transactions on Evolutionary Computation, 2010,14(3):438455.
［26］Shi M, Wu H. Pareto cooperative coevolutionary genetic algorithm using reference sharing collaboration［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation,2009:867874.
［27］Shi M. Comparison of Sorting Algorithms for Multifitness Measurement of Cooperative Coevolution ［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation,2009:25832588.
［28］Jansen T, Wiegand R P. Exploring the explorative advantage of the cooperative coevolutionary (1+1) EA ［C］∥Proc of the 5th Annual Conference on International Conference on Genetic and Evolutionary Computation,2003:310321.
［29］Au CK, Leung HF. Biasing mutations in cooperative coevolution ［C］∥Proc of IEEE Congress on Evolutionary Computation, 2007:828835.
［30］Popovici E, De Jong K A. The effects of interaction frequency on the optimization performance of cooperative coevolution ［C］∥Proc of the 8th Annual Conference on Genetic and Evolutionary Computation Conference, 2006:353360.
［31］Popovici E ,De Jong K. Understanding cooperative coevolutionary dynamics via simple fitness landscapes ［C］ //Proc of the 2005 Conference on Genetic and Evolutionary Computation, 2005:507514.
［32］Brest J, Zamuda A, Boskovic B, et al. Highdimensional real parameter optimization using selfadaptive differential evolution algorithm with population size reduction ［C］∥ Proc of IEEE Congress on Evolutionary Computation , 2008:20322039.
［33］Sofge D, De Jong K, Schultz A. A blended population approach to cooperative coevolution for decomposition of complex problems［C］∥Proc of the Congress on Evolutionary Computation, 2002:413418.
［34］van den Bergh F, Engelbrecht A P. A cooperative approach to particle swarm optimization ［J］. IEEE Transactions on Evolutionary Computation, 2004,8(3):225239.
［35］Shi Y, Teng H, Li Z. Cooperative coevolutionary differential evolution for function optimization ［C］∥Proc of the 1st International Conference on Natural Computation, 2005:10801088.
［36］Zou Wenping, Zhu Yunlong, Chen Hanning, et al. Cooperative approaches to artificial bee colony algorithm［C］∥Proc of the 2010 International Conference on Computer Application and System Modeling (ICCASM), 2010:4448.
［37］Karaboga D．An idea based on bee swarm for numerical optimization［R］．Technical ReportTR06, Kayseri:Erciyes University,2005．
［38］Vanneschi L, Mauri G, Valsecchi A, et al. Heterogeneous cooperative coevolution:strategies of integration between GP and GA ［C］∥Proc of the 8th Annual Conference on Genetic and Evolutionary Computation,2006:361368.
［39］Maniadakis M, Trahanias P. Assessing hierarchical cooperative coevolution ［C］∥Proc of the 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI07), 2007:391398.
［40］Parsopoulos K E. Cooperative microdifferential evolution for highdimensional problems［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO 2009), 2009:531538.
［41］Parsopoulos K E. Cooperative microparticle swarm optimization ［C］∥Proc of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, 2009:467474.
［42］Chandra R, Frean M, Zhang Mengjie. A memetic framework for cooperative coevolution of recurrent neural networks ［C］∥Proc of the 2011 International Joint Conference on Neural Networks (IJCNN 2011),2011:673680.
［43］Chandra R, Frean M, Zhang M. A memetic framework for cooperative coevolutionary feedforward neural networks ［R］. Technical Report ECSTR1022, Wellington:School of Computing and Engineering, Victoria University of Wellington, 2010.
［44］Wang Shuaiqiang, Byron J G, Wang Ke, et al. CCRank:Parallel learning to rank with cooperative coevolution ［C］∥Proc of the 25th AAAI Conference on Artificial Intelligence, 2011:12491254.
［45］Bucci A, Pollack J B. On identifying global optima in cooperative coevolution［C］∥Proc of the 2005 Conference on Genetic and Evolutionary Computation, 2005:539544.
［46］Guo Yinan, Cheng Jian, Lin Yong. Cooperative interactive cultural algorithms adopting knowledge migration ［C］∥Proc of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, 2009:193200.
［47］Vo C, Panait L, Luke S. Cooperative coevolution and univariate estimation of distribution algorithms ［C］∥Proc of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms,2009:141150.
［48］Li Xiaodong, Yao Xin. Tackling high dimensional non separable optimization problems by cooperatively coevolving particle swarms ［C］∥Proc of IEEE Congress on Evolutionary Computation, 2009:15461553.
［49］Li Xiaodong, Yao Xin. Cooperatively coevolving particle swarms for large scale optimization ［J］. IEEE Transactions on Evolutionary Computation, 2012,16(2):210224.
［50］Omidvar M N, Li Xiaodong, Yao Xin. Smart use of computational resource based on contribution for cooperative coevolutionary algorithms ［C］∥ Proc of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO’11), 2011:11151122.
［51］Au CK, Leung Hf. Guided mutations in cooperative coevolutionary algorithms for function optimization ［C］∥Proc of the 19th IEEE International Conference on Tools with Artificial Intelligence, 2007:407414.
［52］Aichour M,Lutton E.Cooperative coevolution inspired operators for classical GP schemes ［C］∥Proc of International Workshop on Nature Inspired Cooperative Strategies for Optimization (NICSO’07), 2007:169178.
［53］Omidvar M N, Li Xiaodong, Yang Zhenyu, et al. Cooperative coevolutionary algorithm for large scale optimization through more frequent random grouping ［C］∥Proc of the 2010 IEEE Congress on Evolutionary Computation,2009:18.
［54］Lee ChingHung, Chung Peiyuan, Chang Haohan. A novel hybrid differential evolution algorithm:A comparative study on function optimization ［C］∥ Proc of the International MultiConference of Engineers and Computer Scientists, 2011:16.
［55］Weber M, Neri F, Tirronen V. Shuffle or update parallel differential evolution for largescale optimization ［J］. Soft Computing ,2011,15(11):20892107 .
［56］Hu Chengyu, Wang Bo. Particle swarm optimization with dynamic dimension crossover for high dimensional problems ［J］. Computing Technology and Automation, 2008,28(1):9295. (in Chinesee)
［57］Hu Chengyu,Yan Xuesong,Li Chuanfeng.Particle swarm optimization with dynamic dimension crossover for high dimensional problems ［C］∥Proc of ISICA’08,2008:750759.
［58］Omidvar M, Li X. A comparative study of CMAES on large scale global optimization［C］∥Proc of the 23rd Australasian Joint Conference on Advances in Artificial Intelligence,2010:303312.
［59］Potter M A.The design and analysis of a computational model of cooperative coevolution［D］. Virginia:George Mason University,1997.
［60］GarciaPedrajas N，HervasMartinez C，MunozPerez J．COVNET：A cooperative coevolutionary model for evolving artificial neural networks ［J］. IEEE Transactions on Neural Networks, 2003:14(3):575596.
［61］Kimura S, Ide K, Kashihara A, et al. Inference of Ssystem models of genetic networks using a cooperative coevolutionary algorithmc［J］. Journal of Bioinformatics,2005,21(7):11541163.
［62］Chandra R, Frean M, Zhang Mengjie. A memetic framework for cooperative coevolutionary feedforward neural networks［R］. Technical Report ECSTR1022, Wellington:School of Computing and Engineering, Victoria University of Wellington, 2010.
［63］Ruela A S, Aquino A L L, Guimaraes F G. A cooperative coevolutionary algorithm for the design of wireless sensor networks Track name:Bioinspired solutions for wireless sensor networks ［C］∥Proc of GECCO’11,2011:607614.
［64］Carvalho A. A cooperative coevolutionary genetic algorithm for learning Bayesian network structures［C］∥Proc of GECCO’11 , 2011:11311138.
［65］Supudomchok S, Chaiyaratana N, Phalakomkule C. Cooperative coevolutionary approach for flux balance in bacillus subtilis［C］∥Proc of the 2008 IEEE World Congress on Computational Intelligence, 2008:12261231.
［66］Cao X，Qiao H，Keane J. A lowcost pedestriandetection system with single optical camera ［J］．IEEE Transactions on Intelligent Transportation Systems, 2008,9(1):5867.
［67］Sun Wei, Huo Junzhou, Chen Jing, et al. Disc cutters’ layout design of the fullface rock tunnel boring machine (TBM) using a cooperative coevolutionary algorithm ［J］. Journal of Mechanical Science and Technology, 2011,25(2):415427.
［68］Nebti S, Boukerram A. An improved radial basis function neural network based on a cooperative coevolutionary algorithm for handwritten digits recognition ［C］∥Proc of the 2010 International Conference on Machine and Web Intelligence (ICMWI), 2010:464468.
［69］Yusoh Z I M, Tang Maolin. A cooperative coevolutionary algorithm for the composite SaaS placement problem in the cloud ［C］∥Proc of ICONIP’10, 2010:618625.
［70］Liang C H, Chung C Y, Wong K P, et al. Parallel optimal reactive power flow based on cooperative coevolutionary differential evolution and power system decomposition ［J］. IEEE Transactions on Power System, 2007, 22(1):319323.
［71］Dias L M S D M, Pacheco M A I C. Refinery scheduling optimization using genetic algorithms and cooperative coevolution ［C］∥Proc of the 2007 IEEE Symposium on Computational Intelligence in Scheduling(CISched 2007),2007:151158.
［72］Wu A, Zhang Jin, Chung H. Decoupled optimal design for power electronic circuits with adaptive migration in coevolutionary environment ［J］. Journal of Applied Soft Computing, 2011,11 (1):2331.
［73］Zhou Xiang, Bao Zhenqiang, Wang Guijun, et al. Optimization of fuzzy jobshop scheduling with multiprocess routes and its coevolutionary algorithm ［C］∥Proc of the 4th International Conference on Intelligent Computation Technology and Automation, 2011:866870.
［74］Panait L, Luke S. Cooperative multiagent learning:The state of the art ［J］. Journal of Autonomous Agents and MultiAgent Systems, 2005,11(3):387434.
［75］Panait L, Luke S, Wiegand R P. Biasing coevolutionary search for optimal multiagent behaviors ［J］. IEEE Transactions on Evolutionary Computation, 2006,10(6):629645.
［76］Au CK, Leung HF. On the behavior of cooperative coevolution in dynamic environments［C］∥Proc of the 2008 IEEE Congress on Evolutionary Computation, 2008:28272836.
［77］Au CK, Leung HF. Investigating collaboration methods of random migrant scheme in cooperative coevolution［C］∥Proc of the 2009 IEEE Congress on Evolutionary Computation, 2009:27012707.
［78］Nema S, Goulermas J Y, Sparrow G, et al. A hybrid cooperative search algorithm for constrained optimization ［J］. Structural and Multidiscplinary Optimization, 2011,43(1):107119.
［79］Boonlong K, Maneeratana K, Chaiyaratana N. Determination of erroneous velocity vectors by cooperative coevolutionary genetic algorithm ［C］∥Proc of the 2006 IEEE Conference on Cybernetics and Intelligent Systems, 2006:16.
［80］Li Wei. Research on the diagnosis learning technology based on the cooperative evolution mechanism［C］∥Proc of the 2009 International Conference on Computational Intelligence and Software Engineering, 2009:14.
［81］Li Wei. Research on the application analysis technology for cooperative fault diagnosis ［C］∥Proc of the 8th World Congress on Intelligent Control and Automation, 2010:57905793.
附中文参考文献：
［56］胡成玉,王博. 基于动态维度交叉的粒子群高维函数优化［J］.计算技术与自动化, 2009,28(1):9295.