引用本文

任志刚, 梁永胜, 张爱民, 庞蓓. 基于一般二阶混合矩的高斯分布估计算法. 自动化学报, 2018, 44(4): 635-645. doi: 10.16383/j.aas.2017.c160739

REN Zhi-Gang, LIANG Yong-Sheng, ZHANG Ai-Min, PANG Bei. A Gaussian Estimation of Distribution Algorithm Using General Second-order Mixed Moment. ACTA AUTOMATICA SINICA, 2018, 44(4): 635-645. doi: 10.16383/j.aas.2017.c160739

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160739

关键词

高斯分布估计算法，概率密度椭球体，早熟收敛，协方差矩阵 

摘要

针对传统高斯分布估计算法（Gaussian estimation of distribution algorithms，GEDAs）中变量方差减小速度快、概率密度椭球体（Probability density ellipsoid，PDE）的长轴与目标函数的改进方向相垂直，从而导致算法搜索效率低、容易早熟收敛这一问题，提出一种基于一般二阶混合矩的高斯分布估计算法.该算法利用加权的优秀样本预估高斯均值，并根据沿目标函数的改进方向偏移后的均值来估计协方差矩阵.理论和数值分析表明，这一简单操作可以在不增大算法计算量的前提下自适应地调整概率密度椭球体的位置、大小和长轴方向，提高算法的搜索效率.在14个标准函数上对所提算法进行了测试，由统计出的Cohen's d效应量指标可知该算法的全局寻优能力强于传统高斯分布估计算法；与当前先进的粒子群算法、差分进化算法相比，所提算法可以在相同的函数评价次数内获得9个函数的显著优解.

文章导读

分布估计算法(Estimation of distribution algorithm, EDA)是一类典型的基于模型的进化算法.与基于交叉和变异等遗传操作的其他进化算法相比, EDA具有较强的理论基础, 而且可以成功求解大量不同类型的连续和离散优化问题, 近年来一直是进化计算领域的研究热点[1-3].

本文重点研究面向连续问题的EDA, 这类算法通常采用高斯概率模型(Gaussian probability model, GPM)描述优解的分布.根据对各变量之间相关关系的处理方式, 高斯EDA (Gaussian EDA, GEDA)可以分为变量无关的EDA、部分变量相关的EDA、全变量相关的EDA, 其代表性算法分别为PBIL_c (Population based incremental learning)[1]和UMDA_c (Univariate marginal distribution algorithm)[1, 4]、EGNA (Estimation of Gaussian networks algorithm)[4-5]、EMNA_g (Estimation of multivariate normal density algorithm)[1].

GPM为EDA的理论分析提供了诸多方便, 但同时也有一些不足, 其中最显著的一点是, 直接由常用的极大似然估计(Maximum~likelihood~estimation, MLE)计算出的变量方差会快速减小, 导致算法的探索能力急剧下降.已有研究通过保持各方差值至少为1[6]、将估计出的方差固定地放大一定倍数[7]、利用协方差矩阵(Covariance matrix, CM)的特征值修改方差[8]以及根据采样解的改进情况自适应地调整方差[9-10]等策略来弥补这一不足.其中, Bosman等学者提出的自适应方差缩放策略影响最为广泛[10].他们建议当算法在远离均值的位置找到更优解时增大方差, 而当算法在连续多次迭代内找不到更优解时减小方差.除方差快速减小这一不利因素之外, 与CM相对应的概率密度椭球体(Probability density ellipsoid, PDE)的长轴还倾向于与目标函数的改进方向相垂直, 这会大大降低GEDA的搜索效率[11-12]. Cai等学者首次发现了这一现象, 并将其与方差收缩问题合并处理, 提出了基于概率分布交叉熵的自适应方差缩放策略[11]. Bosman等学者则提出了预期均值偏移策略, 该策略尝试采用两组分别以预估均值和偏移均值为中心的较优解来估计CM, 从而改变PDE长轴的方向[12].将该策略与前期提出的自适应方差缩放策略相结合后, Bosman等学者构建了一种称为AMaLGaM的有效EDA[13].

除上述研究之外, 文献[14-16]分别通过引入混沌变异算子、正则化技术、多群体-多模型方法来增强GPM对不同问题的适应性; 文献[17-19]则放弃GPM, 分别采用直方图模型、粒子滤波、Copula函数来估计优解的概率分布; 文献[20]在直方图模型的基础上, 进一步利用局部搜索技术提升EDA的优化性能; 文献[21]则尝试采用有监督学习方法估计优解的条件概率分布, 并借助Gibbs采样技术提高搜索效率.这些研究工作在改进EDA性能的同时, 也将算法模型复杂化, 并引入了较多难以设置的自由参数.

本文在分析传统GEDA性能弱化原因的基础上, 提出一种简单高效的GEDA.该算法在每次迭代中首先根据选择出的优秀样本预估出一加权均值, 然后显式地利用预估均值的目标函数值将其偏移至一个更有希望的解区域中, 最后根据所选优秀样本关于偏移后均值的二阶混合矩来估计CM.这一简单操作可以在不增大算法计算量的前提下, 自适应地调整PDE的位置、大小和长轴方向, 使之尽可能与当前解区域的结构特征相契合, 从而提高算法的搜索效率.根据CM的计算方式, 本文将所提算法命名为基于一般二阶混合矩的高斯分布估计算法(General-second-order-mixed-moment based GEDA, GSM-GEDA).

图 1  传统GEDA中PDE的变化示意图

图 3  长轴长度随迭代次数的变化情况

图 4  长轴与目标函数改进方向之间的夹角余弦随迭代次数的变化情况

概率密度椭球体(PDE)的位置、大小和长轴方向是影响高斯分布估计算法(GEDA)性能的关键.本文在分析传统GEDA性能弱化原因的基础上, 提出了一种基于一般二阶混合矩的高斯分布估计算法(GSM-GEDA).该算法以沿目标函数改进方向偏移后的加权均值作为协方差矩阵(二阶混合中心矩)的矩中心, 一方面将PDE引导至一个更有希望的解区域; 另一方面可以自适应地增大PDE的大小, 并使PDE的长轴方向趋近于目标函数的改进方向.理论分析和数值实验均证明了上述结论的正确性.此外, 在14个标准函数上的数值测试还表明, GSM-GEDA的求解质量优于现有的GEDA以及其他一些先进的进化算法.下一步工作将研究设计更为系统化的均值偏移策略, 并在实际的复杂优化问题中检验GSM-GEDA的有效性.

作者简介

梁永胜

西安交通大学电信学院自动化系硕士研究生.2015年获得西安交通大学电信学院自动化系学士学位.主要研究方向为机器学习与智能计算.E-mail:liangyongsheng@stu.xjtu.edu.cn

张爱民  

西安交通大学电信学院自动化系教授.主要研究方向为控制理论与控制工程, 复杂系统的建模、优化与控制.E-mail:zhangam@mail.xjtu.edu.cn

庞蓓  

西安交通大学电信学院自动化系硕士研究生.2016年获得西安交通大学电信学院自动化系学士学位.主要研究方向为机器学习与智能计算.E-mail:beibei@stu.xjtu.edu.cn

任志刚  

西安交通大学电信学院自动化系副教授. 2010年获得西安交通大学工学博士学位.主要研究方向为机器学习与智能计算, 复杂系统的建模、优化与控制.本文通信作者.E-mail:renzg@mail.xjtu.edu.cn