协方差矩阵自适应演化策略学习机制综述

doi:10.3969/j.issn.0372-2112.2017.01.033

电子学报 ›› 2017, Vol. 45 ›› Issue (1): 238-245.DOI: 10.3969/j.issn.0372-2112.2017.01.033

协方差矩阵自适应演化策略学习机制综述

李焕哲^1,2, 吴志健¹, 汪慎文², 郭肇禄³

1. 武汉大学计算机学院软件工程国家重点实验室, 湖北武汉 430072;
2. 河北地质大学信息工程学院, 河北石家庄 050031;
3. 江西理工大学理学院, 江西赣州 341000

收稿日期:2015-10-10 修回日期:2016-03-27 出版日期:2017-01-25
- 作者简介:
- 李焕哲,男,1975年生,河北唐山人,武汉大学计算机学院博士研究生,研究方向:智能计算、机器学习.E-mail:lihuanzhe@whu.edu.cn;吴志健,男,1963年生,教授,博士生导师,武汉大学软件工程国家重点实验室副主任,研究方向:智能计算、并行计算和智能信息处理.E-mail:zhijianwu@whu.edu.cn;汪慎文,男,1979年生,副教授,博士后,研究方向为智能计算与机器学习等.E-mail:wangshenwen@whu.edu.cn;郭肇禄,男,1984年生,江西南康人,博士,研究方向为智能计算、并行计算和机器学习.E-mail:gzl@whu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61364025，No.61402481）; 江西省自然科学基金 (No.20151BAB217010）; 河北省自然科学基金 (No.F2015403046）; 武汉大学软件工程国家重点实验室开放基金 (No.SKLSE2014-10-04）; 河北省科学技术支撑项目 (No.12210319）

The Overview of Learning Mechanism of Covariance Matrix Adaptation Evolution Strategy

LI Huan-zhe^1,2, WU Zhi-jian¹, WANG Shen-wen², GUO Zhao-lu³

1. State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan, Hubei 430072, China;
2. School of Information Engineering, Hebei GEO University, Shijiazhuang, Hebei 050031, China;
3. School of Science, JiangXi University of Science and Technology, Ganzhou, Jiangxi 341000, China

Received:2015-10-10 Revised:2016-03-27 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

基于协方差矩阵自适应（CMA）的演化策略算法（ES）是一种优秀的、不依赖于梯度信息的随机局部优化算法.基于CMA的学习机制使其对搜索空间的任意可逆线性变换具有不变性，对于病态的、高度不可分的问题有优秀的求解能力.CMA学习机制具有较强的数学理论基础，这对设计其他演化算法有很好的借鉴意义.本文旨在详细分析CMA-ES的各种学习机制，并给出其所依赖的主要理论基础.最后通过实验比较CMA-ES各种变体的优势与不足，并着重比较本文改进的CMA-ES变体与其它变体在性能上的差异.

关键词: 演化策略, 协方差矩阵自适应, 自适应学习, 多元正态分布

Abstract:

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 ill-conditioned 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.

Key words: evolution strategy, covariance matrix adaptation, adaptive learning, multivariate normal distribution

中图分类号:

TP18

李焕哲, 吴志健, 汪慎文, 郭肇禄. 协方差矩阵自适应演化策略学习机制综述[J]. 电子学报, 2017, 45(1): 238-245.

LI Huan-zhe, WU Zhi-jian, WANG Shen-wen, GUO Zhao-lu. The Overview of Learning Mechanism of Covariance Matrix Adaptation Evolution Strategy[J]. Acta Electronica Sinica, 2017, 45(1): 238-245.

参考文献

[1] Bäck 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 swarm 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 self-adaptation 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 with covariance matrix adaptation (CMA-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 CMA-evolution strategy with 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)-CMA 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 MATLAB[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].Machine 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 CMA-ES for large scale optimization[A].Proc of the 2014 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.

协方差矩阵自适应演化策略学习机制综述

The Overview of Learning Mechanism of Covariance Matrix Adaptation Evolution Strategy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	王毅, 李晓梦, 耿国华, 周琳, 段焱中. 基于直觉模糊熵的混合粒子群优化算法[J]. 电子学报, 2021, 49(12): 2381-2389.
[2]	李焕哲, 吴志健, 郭肇禄, 刘会超, 汪慎文. 基于两阶段搜索算法的多峰函数优化[J]. 电子学报, 2016, 44(6): 1481-1489.