求解全局优化问题的正交协方差矩阵自适应进化策略算法

求解全局优化问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的正交协方差矩阵自适应进化策略算法 求解全局优化问题的正交协方差矩阵自适应进化策略算法 摘要:针对协方差矩阵自适应进化策略(cmaes)求解高维多模态 函数时存在早熟收敛及求解精度不高的缺陷, 提出一种融合量化 正交 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 (od/q)思想的正交cmaes算法。首先利用小种群的cmaes 进行快速搜索, 当算法陷入局部极值时, 依据当前最好解的位置 动态选取基向量, 接着利用od/q构造的试验向量探测包括极值附 近区域在内的整个搜索空间, 从而引导算法跳出局部最优。通过对 6个高维多模态 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 函数进行测试并与其他算法相比较, 其结果表 明, 正交cmaes算法具有更好的搜索精度、收敛速度和全局寻优性 能。 关键词:协方差矩阵自适应进化策略;正交设计;高维多模态;进化 策略;函数优化 hybrid orthogonal cmaes for solving global optimization problems huang ya.fei1,2*, liang xi.ming1, 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)是在进化策略(evolution strategy, es)的基础上发展起来的一种高效搜索算法1,, 它将es的可靠性、全局性与自适应协方差矩阵的高引导性结合起来, 对求解非凸非线性优化问题具有较强的适应性, 目前以其良好的寻优性能在优化领域备受关注2-5,, 在对全局优化问题(特别是高维多模态函数)的求解中, cmaes仍存在早熟收敛、精度较差的缺陷。近年来, 针对进化算法在处理高维多模态函数时收敛慢、求解精度低的不足, 不少学者将正交设计引入其中, 相继提出了正交遗传算法6-8,9-10,, 一定程度上提高了算法的全局搜索能力, 取得了较好的效果, 但这些改进算法未能同时兼顾搜索效率和求解精度。为此, 本文提出一种新的正交cmaes混合求解算法, 新算法以收敛较快的cmaes为基本算法, 利用量化正交设计 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 帮助cmaes跳出局部最优, 改善算法的求解精度。通过6个高维多模态测试函数的数值实验, 验证了正交cmaes算法在全局寻优、收敛速度和求解精度等方面的良好性能。 1 cmaes 进化策略是一种采用实数编码在连续空间中进行随机搜索的算法, 个体突变是该算法的主要算子, 借助一维正态分布n(x,σ), 突变首先作用于步长σ用以调整个体x的突变强度, 然后作用于旋转角α用以调整x 得, 一般以5?的角度作为标准差并对其做随机扰动来决定个体下一步的旋转角, 采用这种方式对旋转做调整产生的无效突变浪费了大量的计算成本。 为克服es的局限性, cmaes采用多维正态分布n(m,c)中的协方差矩阵c直接描述群体突变分布的旋转和尺度, 将前代搜索步的信息引入到协方差矩阵和步长的更新中, 依据当前代最优子群与前一代群体均值m之间的关系更新协方差矩阵来实现整个群体突变方向的调整, 而个体则是由n(m,c)抽样获得。这样的突变模式更具有引导性, 下面简单阐述这一思想。 由多维正态分布的定义知c是对称正定的, 对其进行特征值分解可得c=bd2bt, 其中bbt=i,b的列向量由c的特征向量正交基组成;d为对角阵, 对角元素是c的特征值的平方根。于是,n(m,c)可改写成不同形式11, 2 基于量化的正交设计(od/q) 基于量化的正交设计是leung等6, 础上提出的一种数值优化方法。正交设计是一种非常流行的实验设计法,它利用正交表安排少数几次实验,就能找到最好或者较好的 实验条件,因此它被广泛地用于寻优。设lm(qk)为具有k个因素和q个水平的正交表,其中l表示拉丁方,m表示水平组合数。lm(qk)的每一行表示一种水平组合,也就是一次实验。用户利用lm(qk)只需完成m次实验便可找出一组好的因素水平组合。然而,如果用户尝试所有的因素水平组合,则需要完成qk(m)次实验。正交设计的概念、性质及正交表lm(qk)的构造算法见文献,12,。 基于量化的正交设计(orthogonal design with quantization, od/q)6,:给定两个体(称为基向量)a=(a 1,„,an)和b=(b1,„,bn),a与b对变量xi定义了以下搜索区域:,min(ai,bi),max(ai,bi),。首先对该搜索区域进行量化,将xi划分为以下q个水平: 3 正交cmaes混合算法 3.1 基本思想 在对高维多模态函数进行全局优化时,由于函数本身具有大量极值点,cmaes经过多次迭代后,各变参数(包括协方差矩阵、步长及进化路径等)已变化很小,致使cmaes搜索能力大为弱化。若此时仍未找到全局最优解,则cmaes再无“后劲”跳出局部极值,导致算法“早熟”。在揭示了cmaes的缺陷后,本文提出在cmaes中引入量化正交设计(od/q)方法,期望在cmaes算法“停滞不前”时,借助od/q探测全局优化问题(1)的搜索空间,以帮助cmaes进行局部求精或跳出 小局部。需要注意的是,od/q的执行基于正交表lm(qk),由正交表构造的m个个体的全局探测能力与向量a和b有直接关系,也就是说,由od/q产生的个体是否有助于cmaes,a、b的选取是关键。 为便于od/q的执行,在cmaes,每隔g1代就将种群最好个体和算法变参数分别存入集合v={vn|n=1,2,„}和s={sn|n=1,2,„},其中:vn表示第ng1代的最好个体,s n表示第ng1代的变参数子集合(包括c、σ、pc、pσ)。若算法的最好目标函数值保持g2代不变,则认为cmaes已陷入局部最优,此时需执行od/q。设计所需的两向量a和b如下选取。 随机选择某元素vi?v,并令e=l+r1(u-l),这里u=(u 1,„,un)、l=(l1,„,ln)分别是问题(1)的上、下界, r1=rand(0,1),即e为l和u确定的超长方体主对角线上的随机点。若‖e-vi‖?ε(ε为一小正数),则令: a=x1:λ b=x1:λ+(e,vi)(14) 否则,令: a=(l+u)/2 b=l,+r2×(u,l, )(15)(14)中的x1:λ最好个体;式(15)中的r 2=rand(0,1),l,=(„,lk-1,uk,lk+1,„)和u,=(„,uk-1,lk,uk+1,„)是将l与u的任意一对对应分量交换后得到的。易知,式(15)中的a为l和u确定的超长方体中心,b为该超长方体某对角线上的随机点。式(14)表明,如果vi与e距离够大,则利用od/qx1:λ附近进行局部搜索;若vi与e距离太小,仍用式(14)选取a和b显然不利于od/q,此时需用式(15)确定正交设计所需的两向量,以便od/q 3.2 正交cmaes算法步骤 根据3.1节所述思想,将od/q与cmaes有机融合,本文提出了基于od/q的cmaes算法(简称正交cmaes算法,记为ocmaes/q),算法步骤如下。 算法2 ocmaes/q算法。 步骤1 参数设置及初始化。执行算法1的步骤1,步骤2,并设g1 4 实验结果与分析 4.1 实验设置 为了检验本文提出的ocmaes/q算法的性能,从文献,8,中选取6个函数作为测试集(函数标号与文献,8,相同),并与其他3种性能较好的算法进行实验结果的比较。这些函数属于多模态函数,每个 函数都具有多个局部极值点,例如f2和f3有11n局部极值点,搜索过程极易陷入局部最优,因此它们能检验算法的多峰搜索能力。 数值实验在matlab中完成,对所有的测试函数,种群大小λ取40,μ=λ/2,g1=20,g2=15,t=3,ε=0.1,其他参数的设置同文献,11,。需要指出的是,并不是实验向量越多算法跳出局部越快,因为实验向量多导致函数评价次数多,增加了计算开销。通过反复实验比较,本文算法中的正交设计使用正交表l9(34)。ocmaes/q算法运行g=1000代或者找到最优解则终止运行。对每个测试函数,在相同条件下独立运行50次,并记录其平均函数评价次数(m.fes)、平均最优值(m.best)和标准差(standard deviation，std)。 4.2 数值结果及比较 为了对比实验结果,将ocmaes/q算法与经典的oga/q算法6, lea算法13,hsoga算法8,行比较,结果如表1所示。 由表1可以看出,本文的ocmaes/q算法在所有测试函数的平均最优值、平均函数评价次数、标准差上的结果明显优于oga/q和lea算法的结果,这 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 ocmaes/q算法与oga/q、lea这两种算法相比,无论是在搜索精度、收敛速度还是在跳出局部最优的能力方面,性能都有显著提高。hsoga算法在遗传算法中引入了自适应正交交叉 算子和局部搜索策略,在复杂高维的函数优化中,显示出良好的性能8,ocmaes/q算法同hsoga算法相比,虽然对于测试函数f2和f3,获得相同的全局最优所需的平均函数评价次数要多,但是对于f1, f6, f8和f9 次数,ocmaes/q比hsoga要少,且在标准差上低几个数量级,其中对函数f6和f9,ocmaes/q算法搜寻到的平均最优值好于hsoga算法。以上分析表明,与hsoga算法相比,ocmaes/q算法具有更高的收敛精度和更好的稳定性。 为了验证在cmaes算法中引入量化正交设计的有效性,将cmaes算法(算法1)与ocmaes/q算法(算法2)在6个测试函数上的计算结果作对比分析,参数设置如下:λ=40,算法1的其他参数同文献,11,,算法2的其他参数如前所述。为公平起见,cmaes算法以函数评价次数作为终止运行条件,取值同ocmaes/q算法。独立运行50次的结果如表1最后两列,不难看出cmaes算法在对函数f1, f 8寻优时陷入了局部极值,且对f2, f6, f9精度比ocmaes/q的结果差。图2是cmaes和ocmaes/q算法对函数 f1和f8,cmaes算法在陷入局部最优后无法从中跳出,而引入od/q后,ocmaes/q算法能利用实验向量搜索包括极值附近区域在内的整个寻优空间,全局寻优能力大大提高。图2中ocmaes/q寻优曲线的几次幅度较大 的阶跃反映了算法跳出局部最优的过程。 4.3 参数对算法性能的影响 下面讨论算法参数的改变对ocmaes/q算法性能的影响。文献,11,对cmaes算法中的众多参数作了详细讨论,并给出了各参数的建议值,因为上述实验中对这部分参数取值同文献,11,,故接下来主要讨论种群大小λ、g1和g2 析中,除了所讨论的参数外,其他参数的设置与4.1节完全相同,为了公平,各种情况以函数评价次数作为终止条件。 表2列出了g1和g2ocmaes/q算法的求解结果。由表中数据对比可看出,g1和g2,即算法在迭代过程中保存的解个数较少、执行od/q次数偏少的情况下,在求解函数f1和f8时出现早熟收敛,未找到全局最优解,并且其他几个函数的求解精度也比较低。当g1=15、g2=10时,相比4.1节中的设置,求解结果的精度提升不明显,说明取值g 1=20、g2=15是比较合适的。3给出了在不同种群规模(λ20、30、40和60)的情况下ocmaes/q算法求解f1和f3 趋势,图3(b)只给出了f3200代的收敛曲线,此时四种情况都已收敛到全局最优解。由图3易知,初始种群越大,ocmaes/q算法收敛越快,但需注意到,对于相同的迭代次数,种群大的算法需要更多的函数评价次数,故从算法效率来考虑,种群规模设置要适当 小一些。从图3(a)看出,当λ=20和30时,ocmaes/q求解f 1时陷入了局部最优,当λ=40和60时,算法能找到f1全 局最优解。综合以上因素并考虑算法的寻优效率和求解精度,对于 本文的测试函数集,种群大小取为40较合适。 5 结语 本文首先介绍了cmaes算法,指出了它在求解高维多模态函数时存 在易陷入局部最优的不足,然后引入基于量化的正交设计来克服这 些缺陷,提出一种量化正交设计与cmaes的混合求解算法,即 ocmaes/q算法。仿真实验表明,在高维多峰函数优化中,ocmaes/q 算法表现出较强的全局搜索能力,同时具有搜索精度高、收敛速度 快的特点。最后讨论了参数对算法性能的影响。下一步的研究工作 是如何将该方法应用到高维的约束优化和多目标优化问题中。 : ,1, hansen n, ostermeier a. adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation,c,// proceedings of the 1996 ieee conference on evolutionary computation. piscataway: ieee, 1996:312-317. ,2, hansen n, ostermeier a. completely derandomized self.adaptation in evolution strategies,j,. ieee transactions on evolutionary computation, 2001, 9(2):159-195. ,3, suttorp t, hansen n, igel c. efficient covariance matrix update for variable metric evolution strategies,j,. machine learning, 2009, 75(2):167-197. ,4, 周文杰, 徐勇. 基于cma.es算法的支持向量机模型选择,j,. 计 算机仿真, 2010,27(4):163-166. ,5, 苏国韶, 武振兴, 燕柳斌. 基于自适应协方差矩阵进化策略的结 构可靠度计算,j,. 四川建筑科学研究, 2011, 37(2): 13-16. ,6, leung y w, wang y p. an orthogonal genetic algorithm with quantization for global numerical optimization,j,. ieee transactions on evolutionary computation, 2001, 5(1): 41-53. ,7, wang y, liu h, cai z, et al. an orthogonal design based constrained evolutionary optimization algorithm,j,. engineering optimization, 2007,39(6):715-736. ,8, 江中央, 蔡自兴, 王勇. 求解全局优化问题的混合自适应正交遗 传算法,j,. 软件学报, 2010, 21(6): 1296-1307. ,9, 曾三友,魏巍,康立三,等. 基于正交设计的多目标演化算法,j,. 计算机学报, 2005, 28(7): 1153-1162. ,10, 拓守恒, 汪文勇. 求解高维多模优化问题的正交小生境自适应差 分演化算法,j,. 计算机应用, 2011, 31(4): 1094-1098. ,11, hansen n. the cma evolution strategy: a comparing review,c,// towards a new evolutionary computation: advances on estimation of distribution algorithms. berlin: springer, 2006: 75-102. ,12, fang k t, wang y. number.theoretic methods in statistics,m,. new york: chapman & hall, 1994. ,13, wang y p, dang c y. an evolutionary algorithm for global optimization based on level.set evolution and latin squares,j,. ieee transactions on evolutionary computation, 2007,11(5):579-595.