推荐星级：
- 1
- 2
- 3
- 4
- 5
协方差矩阵自适应演化策略学习机制综述
资料介绍
基于协方差矩阵自适应(CMA)的演化策略算法(ES)是一种优秀的、不依赖于梯度信息的随机局部优化算法.基于CMA的学习机制使其对搜索空间的任意可逆线性变换具有不变性,对于病态的、高度不可分的问题有优秀的求解能力.CMA学习机制具有较强的数学理论基础,这对设计其他演化算法有很好的借鉴意义.本文旨在详细分析CMA-ES的各种学习机制,并给出其所依赖的主要理论基础.最后通过实验比较CMA-ES各种变体的优势与不足,并着重比较本文改进的CMA-ES变体与其它变体在性能上的差异.
部分文件列表
| 文件名 | 大小 |
| 协方差矩阵自适应演化策略学习机制综述.pdf | 1M |
部分页面预览
（完整内容请下载后查看）1
Vol． 45 No． 1
Jan． 2017
第
期
电
子
学
报
2017
1
ACTA ELECTRONICA SINICA
年
月
协方差矩阵自适应演化策略学习机制综述
1，2
1
2
3
， ， ，
李焕哲 吴志健 汪慎文 郭肇禄
( 1．
，
武汉大学计算机学院软件工程国家重点实验室 湖北武汉
430072;
2．
，
河北地质大学信息工程学院 河北石家庄
050031; 3．
，
江西理工大学理学院 江西赣州
341000)
:
( CMA)
( ES) 、
是一种优秀的 不依赖于梯度信息的随机局部优
摘
要
基于协方差矩阵自适应
的演化策略算法
．
化算法 基于
CMA
， 、
的学习机制使其对搜索空间的任意可逆线性变换具有不变性 对于病态的 高度不可分的问题有优
． CMA
，
．
秀的求解能力
CMA-ES
学习机制具有较强的数学理论基础 这对设计其他演化算法有很好的借鉴意义 本文旨在详细分
CMA-ES ，
各种变体的优势与不足
，
．
析
的各种学习机制 并给出其所依赖的主要理论基础 最后通过实验比较
CMA-ES
．
变体与其它变体在性能上的差异
并着重比较本文改进的
:
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
演化策略 协方差矩阵自适应 自适应学习 多元正态分布
TP18 0372-2112 ( 2017) 01-0238-08
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 01． 033
:
:
A
:
文章编号
文献标识码
电子学报
The Overview of Learning Mechanism of
Covariance Matrix Adaptation Evolution Strategy
1，2
1
2
3
LI Huan-zhe ，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)
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 pa-
per aims at analyzing the learning mechanisms of CMA-ES in detail，and providing its main mathematical foundations． Final-
ly，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
．
习和使用一个可变尺度的协方差矩阵 变异对于演化
1
引言
，
策略来说非常重要 因为它主要通过随机变异来改变
［1］
［2，3］
，
演化策略 属于一种随机搜索算法 主要用于解
，
搜索点的位置 而不像差分演化算法
和粒子群优
［4，5］
决现实世界中一些传统优化算法难于处理的优化问
化
算法通过个体间的差分向量或向优秀个体学习
， ， ， ．
题 例如不连续 不可微 高维度等 它通过对已找到的
．
的机制来改变搜索点位置 变异操作是驱动演化策略
优秀的搜索点增加一个随机向量来改变搜索的步长和
．
算法最重要的动力来源
， ．
方向 这个步骤通常称之为变异 在优化过程中适当地
，
为了控制变异操作 用于控制变异分布的策略参
，
利用这些变异更新协方差矩阵信息 允许搜索分布学
， ( ) 、
数被引入 这些策略参数包括全局 整体 步长 单独步
: 2015-10-10;
: 2016-03-27; :
责任编辑 李勇锋
收稿日期
修回日期
:
基金项目 国家 自 然科学基金
( No． 61364025，No． 61402481) ;
( No． 20151BAB217010 ) ;
( No．
江西省自然科学基金
河 北 省 自 然 科 学 基 金
( No． 12210319)
河北省科学技术支撑项目
F2015403046) ;
( No． SKLSE2014-10-04) ;
武汉大学软件工程国家重点实验室开放基金
239
1
:
李焕哲 协方差矩阵自适应演化策略学习机制综述
第
期
， ，
长及搜索分布的旋转角度 这些策略参数是内生的 和
( 1 + ) -CMA-ES
λ
，
算法 从而提出了
( 1
分解方法应用于
．
搜索点的分布密切相关 优秀的策略参数会提高由它
+
) -Cholesky-CMA-ES，
λ 并将该算法应用于求解多目标
［15］
， ，
所生成的搜索点被选中的概率 反之 被选中并被遗传
． 2009
Suttorp
Igel
在
优化问题
年
等
的工作基础上进
，
到下一代的搜索点也影响对策略参数的调整 这一策
， Cholesky
行改进 在
因式分解方法中解决了演化路径计
( Mutation
， -1 ( ， ) -CMA-ES
算的问题 使得具有秩 更新的 μ λ 算法
w
略参数调整的过程被称为变异策略参数控制
［6］
2
Strategy Parameter Control，MSC)
．
MSC
设置往
传统的
( n ) ，
这很大程度上提高了
的计算复杂度也降为了 Θ
，) -CMA-ES
，
往需要特定的先验知识 而且优良的参数设置会因问
(
． 2008
μ
λ
算法在高维问题上的运行效率
w
［16］
， ，
题而异 对于通常的现实问题而言 并没有对策略参数
Ros
年
等
提出一种以对角协方差矩阵替换常规协方
，
最佳选择的特定知识可用 所以策略参数调整很难达
，
差矩阵的方法 该方法把算法时间和空间复杂性降到
．
到满意 的 效 果 因 此 自 适 应 的 策 略 参 数 应 运 而 生
，
．
了线性的 由于对角矩阵的引入导致该方法失去了对
［6］
Schwefel
方法通常被称为相关变异 通过对搜索分布进行任意
角度的旋转及步长控制可生成任意方向的正态变异分
1981
，
在
年提出了搜索分布旋转角自适应 该
，
搜索空间的旋转不变性 以致在某些不可分的问题上
，
，
性能下降严重 但是在一些高维可分的问题上却性能
， ．
优异 甚至在某些高维多峰问题上也性能良好 经过多
， ，
布 不过这种方法依赖于坐标系 不具有对搜索空间线
，CMA
年完善改进
学习机制已经成为演化策略中对策
［7］
． Ostermeier
1994
性变换的不变性
机化的步长控制
等
在
年提出了去随
，
略参数控制最行之有效的一种方法 并成功应于全局
［17，18］
［19，20］
［14，21］
( Derandomized Mutative Step-Size Con-
、
、
、
大规模优
优化
多峰优化
多目标优化
［22，23］
trol，DSC) ，
可以在小种群下自适应控制单独的步长变
．
化
等领域
［8］
． Hansen
Ostermeier
1996
DSC
年提出了基于
异
和
在
CMA-ES
中的学习机制主要包括协方差矩阵自适
，
概念的协方差矩阵自适应学习机制 协方差矩阵的引
．
应和整体步长自适应 这两种学习机制相互独立的进
，
入使得搜索分布可以完全独立于坐标系 具有对搜索
，
行自适应学习 整体步长的自适应并不依赖于协方差
． Hansen Oster-
和
空间 任 意 可 逆 线 性 变 换 的 不 变 性
，
矩阵的自适应 这样做的目的是为了加快收敛的速度
，
［9］
meier
2001
年在前面工作的基础上提出了完全去
于
但是这两种学习机制都依赖于对已选择的多元正态随
， “
随机化的协方差矩阵自适应学习机制 引入 去随机
．
机变量的学习
” “ ” ，
化 和 积累演化路径 两个概念 以消除随机性对搜索
2
理论基础
，
分布波动的影响 使策略参数的改变确定性的与目标
． 2002 2003 Müller Hansen
和 年 和
参数的变化相联系
，
为了把协方差矩阵自适应学习机制阐述清楚 本
［10，11］
- ，
提出了秩 μ 更新机制 该机制可充分利用在较
等
文把协方差矩阵自适应学习的主要理论基础总结为定
，
大种群中所包含的信息 通过利用这些信息来减少运
1
5 (
到定理
) ． ，
篇幅关系证明部分被省略 另外 定理
理
．
行时间和增强全局搜索能力
6
7
和定理 为有关
Cholesky
，
因子增量更新的相关定理
，
在协方差矩阵更新过程中 需要用到对协方差矩
［12，15］．
引自文献
．
阵的特征分解 一个普通协方差矩阵特征分 解 需 要
2. 1
协方差矩阵自适应学习的主要理论基础
3
( n )
， n ．
步 其中 为问题维度 为了把特征分解的复杂
Θ
1
n x
维随机向量 符合多元正态分布
定理
若
［9］
，Hansen
度降为二次的
等
使用了对协方差矩阵进行
， ) -PUd-CMA
N( 0，I) ，
则它的任意线性组合
y = Ax +
μ 服从多元正态
T
m × n
， (
延迟分解的方法 提出了 μ
，
算法 但是
λ
N( ，AA ) ～ AN( 0，I) +
μ
，
μ 其中
A
∈
．
w
分布
［12］
n
． 2006
Igel
等
这种方法会使用过时的变异分布
Cholesky
年
把
2
n
如果有限个 维向量
x ，…，x
1
，
给每
定理
∈
m
，
因式分解方法引入协方差矩阵更新 把对协方
N( 0，1)
， N( 0，1) x
正态分布随机数 则
个向量乘以一个
+ … + N( 0，1) x
1
Cholesky
差矩阵的显式更新改为对协方差矩阵
因子的
是一个均值为零向量的多元正态分
m
m
， ，
更新 这种方法不需要显式更新协方差矩阵 而通过对
T
N( 0，
x x ) ．
i
布
∑
i
Cholesky
，
因子的更新来隐式更新协方差矩阵 该方法把
i = 1
3
2
3
C
一个实对称正定矩阵 可特征分解为
定理
( n )
( n ) ．
他们提出的
算法计算复杂度从 Θ
降为了 Θ
2
T
BD B ，B
，B
C
的每一列对应 的一个特征
为正交矩阵
-1 ，
这种增量更新技术属于秩 更新 被经常用于卡尔曼
［13］
; D
，D C
的每个对角元素对应 的一个
向量
为对角矩阵
． Igel
Cholesky
滤波领域
等把这种
因式分解方法应用
( 1 + 1) -Cholesky-
， B
特征值的平方根 并且每个对角元素与 中的相应列
( 1 + 1) -CMA-ES
，
到了
中 由此提出了
算法 在该算法中取消了演化路径的使用 这
( 1 + 1) -Cholesky-CMA-ES
．
对应
CMA-ES
．
，
T
4
v =［v ，…，v ］ ，n 2， A
≥ 令
n
定理
对于非零向量
导致
算法在求解某些问题时
1
T
［14］
= vv ， A
则
:
满足以下结论
． 2007
Igel
Cholesky
直接把 因式
学习效率变慢
年
等
更多>>
最新上传
- 打赏
- 30日榜单
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
cai0603 打赏3.00元 3天前
用户：CJQ_ENJOY
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
cai0603 打赏3.00元 3天前
用户：dongshao
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic下载 打赏310.00元 3天前
用户：gsy幸运
-
21ic下载 打赏310.00元 3天前
用户：zhengdai
-
21ic下载 打赏310.00元 3天前
用户：小猫做电路
-
21ic下载 打赏310.00元 3天前
用户：liqiang9090
-
21ic下载 打赏270.00元 3天前
用户：kk1957135547
-
21ic下载 打赏160.00元 3天前
用户：w178191520
-
21ic下载 打赏160.00元 3天前
用户：w1966891335
-
21ic下载 打赏50.00元 3天前
用户：w993263495
-
21ic下载 打赏40.00元 3天前
用户：w993263495
-
21ic下载 打赏90.00元 3天前
用户：cooldog123pp
-
21ic下载 打赏30.00元 3天前
用户：sun2152
-
21ic下载 打赏40.00元 3天前
用户：xzxbybd
-
21ic下载 打赏40.00元 3天前
用户：铁蛋锅
-
21ic下载 打赏30.00元 3天前
用户：happypcb
-
21ic下载 打赏50.00元 3天前
用户：forgot
-
21ic下载 打赏10.00元 3天前
用户：xuzhen1
-
21ic下载 打赏20.00元 3天前
用户：wanglu6666
-
21ic下载 打赏5.00元 3天前
用户：人间留客
-
21ic下载 打赏5.00元 3天前
用户：jyxjiyixing
-
21ic下载 打赏5.00元 3天前
用户：akae_du
-
21ic下载 打赏5.00元 3天前
用户：ouyang_56
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
xlhtracy 打赏10.00元 3天前
-
xlhtracy 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
xlhtracy 打赏5.00元 3天前
-
czmhcy 打赏1.00元 3天前
资料：bitboy
全部评论(0)