协方差矩阵自适应演化策略学习机制综述
|
摘要
基于协方差矩阵自适应(CMA)的演化策略算法(ES)是一种优秀的、不依赖于梯度信息的随机局部优化算法.基于CMA的学习机制使其对搜索空间的任意可逆线性变换具有不变性,对于病态的、高度不可分的问题有优秀的求解能力.CMA学习机制具有较强的数学理论基础,这对设计其他演化算法有很好的借鉴意义.本文旨在详细分析CMA-ES的各种学习机制,并给出其所依赖的主要理论基础.最后通过实验比较CMA-ES各种变体的优势与不足,并着重比较本文改进的CMA-ES变体与其它变体在性能上的差异.
The evolution strategy( ES) based on covariance matrix adaptation( CMA) is an excellent,gradient-free stochastic local optimization method. The learning mechanism based on CMA enables evolution strategy algorithm to have invariance to any invertible linear transformation of the search space,and to have outstanding capability for solving the illconditioned and/or highly non-separable problems. The learning mechanism of CMA has a solid theoretical foundation in mathematics,which may have a certain reference significance to guide the design of other evolutionary algorithms. This paper aims at analyzing the learning mechanisms of CMA-ES in detail,and providing its main mathematical foundations. Finally,the advantages and disadvantages of various CMA-ES variants are compared by a series of experiments,and the difference in performance is compared seriously between our improved variant and other CMA-ES variants.
The evolution strategy( ES) based on covariance matrix adaptation( CMA) is an excellent,gradient-free stochastic local optimization method. The learning mechanism based on CMA enables evolution strategy algorithm to have invariance to any invertible linear transformation of the search space,and to have outstanding capability for solving the illconditioned and/or highly non-separable problems. The learning mechanism of CMA has a solid theoretical foundation in mathematics,which may have a certain reference significance to guide the design of other evolutionary algorithms. This paper aims at analyzing the learning mechanisms of CMA-ES in detail,and providing its main mathematical foundations. Finally,the advantages and disadvantages of various CMA-ES variants are compared by a series of experiments,and the difference in performance is compared seriously between our improved variant and other CMA-ES variants.
引文
[1]Bck T,Foussette C,Krause P.Contemporary Evolution Strategies[M].Berlin Heidelberg:Springer,2015.7-86.
[2]Das S,Suganthan P N.Differential evolution:a survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.
[3]彭虎,吴志健,等.基于精英区域学习的动态差分进化算法[J].电子学报,2014,42(8):1522-1530.Peng Hu,Wu Zhi-jian,et al.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)
[4]周新宇,吴志健,等.一种精英反向学习的粒子群优化算法[J].电子学报,2013,41(8):1647-1652.Zhou Xin-yu,Wu Zhi-jian,et al.Elite opposition-based particle sw arm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.(in Chinese)
[5]喻飞,李元香,等.透镜成像反学习策略在粒子群算法中的应用[J].电子学报,2014,42(2):230-235.Yu Fei,Li Yuan-xiang,et al.The application of a novel OBL based on lens imaging principle in PSO[J].Acta Electronica Sinica,2014,42(2):230-235.(in Chinese)
[6]Schwefel H.Numerical Optimization of Computer Models[M].New York:John Wiley&Sons Inc,1981.1-389.
[7]Ostermeier A,Gawelczyk A,Hansen N.A derandomized approach to self-adaptation of evolution strategies[J].Evolutionary Computation,1994,2(4):369-380.
[8]Hansen N,Ostermeier A.Adapting arbitrary normal mutation distributions in evolution strategies:the covariance matrix adaptation[A].Proc of IEEE Conference on Evolutionary Computation[C].IEEE,1996.312-317.
[9]Hansen N,Ostermeier A.Completely derandomized selfadaptation in evolution strategies[J].Evolutionary Computation,2001,9(2):159-195.
[10]Hansen N,Muller S D,Koumoutsakos P.Reducing the time complexity of the derandomized evolution strategy w ith covariance matrix adaptation(CM A-ES)[J].Evolutionary Computation,2003,11(1):1-18.
[11]Müller S D,Hansen N,et al.Increasing the serial and the parallel performance of the CM A-evolution strategy w ith large populations[A].Parallel Problem Solving from Nature—PPSN VII[C].Granada:Springer,2002.422-431.
[12]Igel C,Suttorp T,Hansen N.A computational efficient covariance matrix update and a(1+1)-CM A for evolution strategies[A].Proc of the 8th Annual Conference on Genetic and Evolutionary Computation[C].Washington:ACM,2006.453-460.
[13]Grewal M,Andrews A.Kalman Filtering:Theory and Practice Using M ATLAB[M].New York:John Wiley&Sons Inc,2001.25-347.
[14]Igel C,Hansen N,Roth S.Covariance matrix adaptation for multi-objective optimization[J].Evolutionary Computation,2007,15(1):1-28.
[15]Suttorp T,Hansen N,Igel C.Efficient covariance matrix update for variable metric evolution strategies[J].M achine Learning,2009,75(2):167-197.
[16]Ros R,Hansen N.A simple modification in CMA-ES achieving linear time and space complexity[A].Parallel Problem Solving from Nature-PPSN X[C].Berlin Heidelberg:Springer,2008.296-305.
[17]Chen L,Zheng Z,et al.An evolutionary algorithm based on covariance matrix learning and searching preference for solving CEC 2014 benchmark problems[A].Proc of IEEE Congress on Evolutionary Computation[C].Beijing:IEEE,2014.2672-2677.
[18]Ghosh S,Das S,Roy S,et al.A differential covariance matrix adaptation evolutionary algorithm for real parameter optimization[J].Information Sciences,2012,182(1):199-219.
[19]Preuss M.Niching the CMA-ES via nearest-better clustering[A].Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation[C].Portland:ACM,2010.1711-1718.
[20]Li L X,Tang K.History-based topological speciation for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(1):136-150.
[21]杨咚咚,焦李成,等.求解偏好多目标优化的克隆选择算法[J].软件学报,2010,21(01):14-33.Yang Dong-dong,Jiao Li-cheng,et al.Clone selection algorithm to solve preference multi-objective optimization[J].Journal of Software,2010,21(01):14-33.(in Chinese)
[22]Loshchilov I.A computationally efficient limited memory CM A-ES for large scale optimization[A].Proc of the2014 Conference on Genetic and Evolutionary Computation[C].Vancouver:ACM,2014.397-404.
[23]Yang Z,Tang K,Yao X.Large scale evolutionary optimization using cooperative coevolution[J].Information Sciences,2008,178(15):2985-2999.
[24]Hansen N.The CMA Evolution Strategy:A Tutorial[Z].2011.1-34
[25]Suganthan P N,Hansen N,et al.Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization[R].Singapore:Nanyang Technological University,2005.1-50.
[26]Li X,Tang K,et al.Benchmark Functions for the CEC'2013 Special Session and Competition on Large-Scale Global Optimization[R].Cancun:IEEE,2013.1-23.
[27]Arnold D V.Noisy Optimization with Evolution Strategies[Z].Boston:Kluwer Academic Publishers,2002.1-20.
[28]Chen T,Tang K,Chen G,et al.Analysis of computational time of simple estimation of distribution algorithms[J].IEEE Transactions on Evolutionary Computation,2010,14(1):1-22.
[29]Yang P,Tang K,Lu X.Improving estimation of distribution algorithm on multimodal problems by detecting promising areas[J].IEEE Transactions on Cybernetics,2015,45(8):1438-1449.
[30]Beyer H,Deb K.On self-adaptive features in real-parameter evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2001,5(3):250-270.
[2]Das S,Suganthan P N.Differential evolution:a survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.
[3]彭虎,吴志健,等.基于精英区域学习的动态差分进化算法[J].电子学报,2014,42(8):1522-1530.Peng Hu,Wu Zhi-jian,et al.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)
[4]周新宇,吴志健,等.一种精英反向学习的粒子群优化算法[J].电子学报,2013,41(8):1647-1652.Zhou Xin-yu,Wu Zhi-jian,et al.Elite opposition-based particle sw arm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.(in Chinese)
[5]喻飞,李元香,等.透镜成像反学习策略在粒子群算法中的应用[J].电子学报,2014,42(2):230-235.Yu Fei,Li Yuan-xiang,et al.The application of a novel OBL based on lens imaging principle in PSO[J].Acta Electronica Sinica,2014,42(2):230-235.(in Chinese)
[6]Schwefel H.Numerical Optimization of Computer Models[M].New York:John Wiley&Sons Inc,1981.1-389.
[7]Ostermeier A,Gawelczyk A,Hansen N.A derandomized approach to self-adaptation of evolution strategies[J].Evolutionary Computation,1994,2(4):369-380.
[8]Hansen N,Ostermeier A.Adapting arbitrary normal mutation distributions in evolution strategies:the covariance matrix adaptation[A].Proc of IEEE Conference on Evolutionary Computation[C].IEEE,1996.312-317.
[9]Hansen N,Ostermeier A.Completely derandomized selfadaptation in evolution strategies[J].Evolutionary Computation,2001,9(2):159-195.
[10]Hansen N,Muller S D,Koumoutsakos P.Reducing the time complexity of the derandomized evolution strategy w ith covariance matrix adaptation(CM A-ES)[J].Evolutionary Computation,2003,11(1):1-18.
[11]Müller S D,Hansen N,et al.Increasing the serial and the parallel performance of the CM A-evolution strategy w ith large populations[A].Parallel Problem Solving from Nature—PPSN VII[C].Granada:Springer,2002.422-431.
[12]Igel C,Suttorp T,Hansen N.A computational efficient covariance matrix update and a(1+1)-CM A for evolution strategies[A].Proc of the 8th Annual Conference on Genetic and Evolutionary Computation[C].Washington:ACM,2006.453-460.
[13]Grewal M,Andrews A.Kalman Filtering:Theory and Practice Using M ATLAB[M].New York:John Wiley&Sons Inc,2001.25-347.
[14]Igel C,Hansen N,Roth S.Covariance matrix adaptation for multi-objective optimization[J].Evolutionary Computation,2007,15(1):1-28.
[15]Suttorp T,Hansen N,Igel C.Efficient covariance matrix update for variable metric evolution strategies[J].M achine Learning,2009,75(2):167-197.
[16]Ros R,Hansen N.A simple modification in CMA-ES achieving linear time and space complexity[A].Parallel Problem Solving from Nature-PPSN X[C].Berlin Heidelberg:Springer,2008.296-305.
[17]Chen L,Zheng Z,et al.An evolutionary algorithm based on covariance matrix learning and searching preference for solving CEC 2014 benchmark problems[A].Proc of IEEE Congress on Evolutionary Computation[C].Beijing:IEEE,2014.2672-2677.
[18]Ghosh S,Das S,Roy S,et al.A differential covariance matrix adaptation evolutionary algorithm for real parameter optimization[J].Information Sciences,2012,182(1):199-219.
[19]Preuss M.Niching the CMA-ES via nearest-better clustering[A].Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation[C].Portland:ACM,2010.1711-1718.
[20]Li L X,Tang K.History-based topological speciation for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(1):136-150.
[21]杨咚咚,焦李成,等.求解偏好多目标优化的克隆选择算法[J].软件学报,2010,21(01):14-33.Yang Dong-dong,Jiao Li-cheng,et al.Clone selection algorithm to solve preference multi-objective optimization[J].Journal of Software,2010,21(01):14-33.(in Chinese)
[22]Loshchilov I.A computationally efficient limited memory CM A-ES for large scale optimization[A].Proc of the2014 Conference on Genetic and Evolutionary Computation[C].Vancouver:ACM,2014.397-404.
[23]Yang Z,Tang K,Yao X.Large scale evolutionary optimization using cooperative coevolution[J].Information Sciences,2008,178(15):2985-2999.
[24]Hansen N.The CMA Evolution Strategy:A Tutorial[Z].2011.1-34
[25]Suganthan P N,Hansen N,et al.Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization[R].Singapore:Nanyang Technological University,2005.1-50.
[26]Li X,Tang K,et al.Benchmark Functions for the CEC'2013 Special Session and Competition on Large-Scale Global Optimization[R].Cancun:IEEE,2013.1-23.
[27]Arnold D V.Noisy Optimization with Evolution Strategies[Z].Boston:Kluwer Academic Publishers,2002.1-20.
[28]Chen T,Tang K,Chen G,et al.Analysis of computational time of simple estimation of distribution algorithms[J].IEEE Transactions on Evolutionary Computation,2010,14(1):1-22.
[29]Yang P,Tang K,Lu X.Improving estimation of distribution algorithm on multimodal problems by detecting promising areas[J].IEEE Transactions on Cybernetics,2015,45(8):1438-1449.
[30]Beyer H,Deb K.On self-adaptive features in real-parameter evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2001,5(3):250-270.