求解全局优化问题的正交协方差矩阵自适应进化策略算法摘要：针对协方差矩阵自适应进化策略(cmaes)求解高维多模态
函数时存在早熟收敛及求解精度不高的缺陷, 提出一种融合量化
正交设计(od/q)思想的正交cmaes算法。首先利用小种的cmaes 进行快速搜索, 当算法陷入局部极值时, 依据当前最好解的位置
动态选取基向量, 接着利用od/q构造的试验向量探测包括极值附近区域在内的整个搜索空间, 从而引导算法跳出局部最优。通过对6个高维多模态标准函数进行测试并与其他算法相比较, 其结果表明, 正交cmaes算法具有更好的搜索精度、收敛速度和全局寻优性能。
关键词：协方差矩阵自适应进化策略；正交设计；高维多模态；进化策略；函数优化
hybrid orthogonal cmaes for solving global optimization problems
huang ya.fei  1,2 * , liang xi.ming 1, chen yi.xiong  1
1. school of information science and engineering, central south university, changsha hunan 410083, china ;
2. school of electric and information engineering, changsha
university of science and technology, changsha hunan 410114, china
abstract:
in order to overcome the shortcomings of covariance matrix adaptation evolution strategy(cmaes), such as premature convergence and low precision, when it is used in
high-dimensional multimodal optimization, an hybrid algorithm combined cmaes with orthogonal design with quantization(od/q) was proposed in this study. firstly, the small population cmaes was used to realize a fast searching. when orthogonal cmaes algorithm trapped in local extremum, base vectors for od/q were selected dynamically based on the position of current best solution. then the entire solution space, including the field around extreme value, was explored by trial vectors generated by od/q. the proposed algorithm was guided by this process jumping out of the local optimum. the new approach is tested on six high-dimensional multimodal benchmark functions. compared with other algorithms, the new algorithm has better search precision, convergent speed and capacity of global search. in order to overcome the shortcomings of covariance matrix adaptation evolution
strategy (cmaes), such as premature convergence and low precision, when it is used in high.dimensional multimodal optimization, a hybrid algorithm combined cmaes with orthogonal design with quantization (od/q) was proposed. firstly, the small population cmaes was used to realize a fast searching. when orthogonal cmaes algorithm trapped in local extremum, base vectors for od/q were selected dynamically based on the position of current best solution. then the entire solution space, including the field around extreme value, was explored by trial vectors generated by od/q. the proposed algorithm was guided by this process jumping out of the local optimum. the new approach was tested on six high.dimensional multimodal benchmark functions. compared with other algorithms, the new algorithm has better searching precision, convergence speed and capacity of global search. key words:
covariance matrix adaptation evolution strategy (cmaes); orthogonal design; high.dimensional multimodal; evolutionary strategy (es); function optimization
0 引言
科学、工程和商业等领域存在大量全局优化问题, 通常可将它们描述为有界约束函数:
协方差矩阵自适应进化策略(covariance matrix adaptation evolution strategy, cmaes)是在进化策略(evol
ution strategy, es)的基础上发展起来的一种高效搜索算法  ［1］ , 它将es
的可靠性、全局性与自适应协方差矩阵的高引导性结合起来, 对求解非凸非线性优化问题具有较强的适应性, 目前以其良好的寻优
性能在优化领域备受关注  ［2-5］ 。然而, 在对全局优化问题(特别是高维多模态函数)的求解中, cmaes仍存在早熟收敛、精度较差的缺陷。近年来, 针对进化算法在处理高维多模态函数时收敛慢、求解精度低的不足, 不少学者将正交设计引入其中, 相继提出了正交遗传算法  ［6-8］ 、正交差分演化算法  ［9-10］ , 一定程度上提高了算法的全局搜索能力, 取得了较好的效果, 但这些改进算法未能同时兼顾搜索效率和求解精度。为此, 本文提出一种新的正交cmaes混合求解算法, 新算法以收敛较快的cmaes 为基本算法, 利用量化正交设计方法帮助cmaes跳出局部最优, 改善算法的求解精度。通过6个高维多模态测试函数的数值实验, 验证了正交cmaes算法在全局寻优、收敛速度和求解精度等方面的良好性能。
1 cmaes
进化策略是一种采用实数编码在连续空间中进行随机搜索的算法, 个体突变是该算法的主要算子, 借助一维正态分布n (x,σ), 突变首先作用于步长σ用以调整个体x的突变强度, 然后作用于旋转角α用以调整x 的突变方向。对于旋转角的设定主要依据经验而得, 一般以5°的角度作为标准差并对其做随机扰动来决定个体下一步的旋转角, 采用这种方式对旋转做调整产生的无效突变浪费
了大量的计算成本。
为克服es的局限性, cmaes采用多维正态分布n (m,c)中的协方差矩阵c直接描述体突变分布的旋转和尺度, 将前代搜索步的信息引入到协方差矩阵和步长的更新中, 依据当前代最优子与前
一代体均值m之间的关系更新协方差矩阵来实现整个体突变方向的调整, 而个体则是由 n (m,c)抽样获得。这样的突变模式
更具有引导性, 下面简单阐述这一思想。
由多维正态分布的定义知c是对称正定的, 对其进行特征值分解
可得c=bd 2b  t , 其中bb  t =i,b的列向量由c的
特征向量正交基组成;d为对角阵, 对角元素是c的特征值的平方根。于是,n(m,c)可改写成不同形式  ［11］
2 基于量化的正交设计(od/q)
正则化协方差基于量化的正交设计是leung等  ［6］ 在正交设计思想的基础上提出的一种数值优化方法。正交设计是一种非常流行的实验设计法，它利用正交表安排少数几次实验，就能到最好或者较好的

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。