引用本文

王霞, 王耀民, 施心陵, 高莲, 李鹏. 噪声环境下基于蒲丰距离的依概率多峰优化算法. 自动化学报, 2021,  47(11): 2691−2714 doi: 10.16383/j.aas.c190474

Wang Xia, Wang Yao-Min, Shi Xin-Ling, Gao Lian, Li Peng. Probabilistic multimodal optimization algorithm based on the Buffon distance in noisy environment. Acta Automatica Sinica, 2021,  47(11): 2691−2714 doi: 10.16383/j.aas.c190474

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

关键词

噪声环境，多峰优化，蒲丰距离，依概率 

摘要

针对噪声环境下求解多个极值点的问题, 本文提出了噪声环境下基于蒲丰距离的依概率多峰优化算法(Probabilistic multimodal optimization algorithm based on the Button distance, PMB). 算法依据蒲丰投针原理提出噪声下的蒲丰距离和极值分辨度概念, 理论推导证明了二者与算法峰值检测率符合依概率关系. 在全局范围内依据蒲丰距离划分搜索空间, 可以使PMB算法保持较好的搜索多样性. 在局部范围内利用改进的斐波那契法进行探索, 减少了算法陷入噪声引起的局部最优的概率. 基于34个测试函数, 从依概率特性验证、寻优结果影响因素分析、多极值点寻优和多维函数寻优四个角度进行实验. 证明了蒲丰距离与算法的峰值检测率符合所推导的依概率关系. 对比噪声环境下的改进蝙蝠算法和粒子群算法, PMB算法在噪声环境中可以依定概率更精确地定位多峰函数的更多极值点, 从而证明了PMB算法原理的正确性和噪声条件下全局寻优的依概率性能, 具有理论意义和实用价值.

文章导读

实际优化问题往往存在着多个全局最优解及其他有价值的局部最优解, 我们不仅需要找到全局最优解, 还需要找到局部最优解进行辅助决策, 这类优化问题称为多峰搜索(Multi-peak searching)或多峰优化(Multimodal optimization) 问题[1]. 此外, 实际优化问题总是受到各种随机噪声的影响. 在噪声环境下求解多峰优化问题不仅要求算法能在噪声干扰下寻找真实的极值点位置, 而且希望算法能提供备选的多个优化方案. 噪声的分布往往符合一定的概率关系, 因此噪声环境下的多峰优化问题是一个依概率求解极值点的问题. 其中包含的噪声环境下的寻优问题[2] (Noisy optimization)和多峰优化问题在科学和工程领域中有理论和实际意义. 噪声优化算法的研究可以为机器人[3-5]、智能控制与决策[6-9]、信号识别与测量[10-11]、智能制造[12]等存在噪声干扰的工程优化问题提供优化解决方案.

在噪声优化算法的依概率问题研究方面, 一些学者研究了噪声优化算法的概率模型, 如Nakama[13]和李军华等[14] 研究了噪声环境下遗传算法的 Markov 模型. Ma等[15]使用Markov模型分析了噪声对生物地理优化算法(Biogeography-based optimization, BBO)的影响. Beyer等[16]对自适应进化策略(Self-adaptive evolution strategy, ES)的鲁棒优化模型进行了稳态分析. 但是算法求解优化结果的依概率关系尚无相关研究. 也有一些学者在研究中涉及到了优化算法的依概率问题, 但都是针对无噪声环境下的优化算法, 例如蚁群优化算法[17] (Ant colony optimization, ACO)基于信息素指导依概率为子代个体构建解, 从而将信息素的分布理解为一种特殊的概率分布. 李宝磊等[18]证明了所提出的多元优化算法以概率1 收敛于全局最优解. 董易等[19]证明了所提出的斐波那契树优化算法以概率1 收敛于全局最优解. 针对噪声环境下多峰优化算法的依概率问题尚缺乏相关研究. 对于噪声优化算法的依概率特性研究非常重要, 它可以评估算法搜索优化问题全部极值点的能力, 衡量算法的优化效率, 同时为算法性能的改进和提升指明方向.

在噪声环境下多极值点寻优问题的研究方面, 元启发式算法作为解决确定性优化问题的一种主流方法, 其在噪声环境中的优化性能受到了越来越多的关注. 李军华、黎明等[14, 20-22]分析了噪声对遗传算法的影响以及正态随机噪声对适应度评价的影响机理, 提出了多次评价一次采样的动态适应度评价方法. 许多学者通过将假设检验(Hypothesis test, HT)、最优计算量分配(Optimal computing budget allocation, OCBA)技术、反向学习法、自动学习机(Learning automata, LAs)、重采样、聚类算法、加权搜索中心等多种策略引入粒子群优化算法(Particle swarm optimization, PSO)中[23-29], 以提高算法的鲁棒性. 这些优化算法能够在噪声环境中找到接近全局最优的极值点, 但都没有求解其他极值点. 在多峰优化问题的研究中, 许多多峰函数优化算法[1, 30-31]能搜索到多峰函数的多个极值点. 但大部分算法只针对确定性环境, 并未考虑噪声环境下的多峰优化问题. Jamil等[32] 对蝙蝠算法(Bat algorithm)进行了改进, 使其适用于无噪声环境和有噪声环境, 将其应用到多峰函数优化问题中, 可以找到多峰函数的多个全局极值点. 然而遗憾的是, 文中并未讨论多个局部极值点的情况, 且极值点的坐标并未明确给出. 尽可能多的搜索局部极值点能为生产实际提供更多样化的优化方案. 此外, 为了提供明确的优化方案, 实验结果应给出极值点的适应度值和对应的解, 以便为实际应用提供明确的决策变量[33].

蒲丰投针问题是一个几何概率问题. 它是法国科学家蒲丰(Buffon)在1777年的论著 《或然性算术试验》 中提出的. 蒲丰投针原理反映了几何概率的特征及处理方法, 衍生出了蒙特卡洛(Monte-Carlo)方法. 其概率规律在探矿、近似计算中得到广泛应用, 但在优化算法中的应用尚无相关研究. 在噪声环境中通过随机方式探索多峰函数的极值点与蒲丰投针问题具有相似的概率解释. 本文将蒲丰推导得到的定概率原理应用于噪声环境下的多极值点寻优问题, 从概率的角度出发, 提出了噪声环境下基于蒲丰距离的依概率多峰优化算法(Probabilistic multimodal optimization algorithm based on the Button distance, PMB), 推导证明了蒲丰距离和极值分辨度共同依概率决定算法的峰值检测率. 依据蒲丰距离划分全局搜索空间, 并在局部范围内利用改进的斐波那契法进行局部寻优, 针对多维函数, 采取多级划分策略, 从而提高求解精度和算法效率. 通过算法依概率收敛特性实验, 验证了PMB算法在噪声环境下能够依固定概率找到多个极值点; 通过设置不同的噪声强度与蒲丰距离进行实验, 分析了噪声强度与蒲丰距离对算法求解结果的影响; 通过对比噪声环境下的改进蝙蝠算法, 表明了PMB算法具有很好的多极值点寻优特性和定位精准性; 通过对比PSO算法在多维函数上的表现, 证明了PMB算法在噪声环境下对多维函数寻优的有效性.

第1节对噪声环境下的多峰优化问题进行数学描述, 并说明评价指标. 第2节详细描述了本文提出的PMB算法的基本原理和理论推导. 第3节是论文的仿真实验与结果分析, 用以验证算法的有效性. 第4节给出结论和将来的研究方向.

图 1  极值分辨度

图 2  函数波形与极值点

图 4  式(9)证明示意图

针对噪声环境下的多极值点寻优, 本文采用一种定概率的方法来解决这类随机优化问题. 从蒲丰投针的定概率原理出发, 提出了噪声环境下基于蒲丰距离的依概率多峰优化算法(PMB). 理论推导证明了蒲丰距离和极值分辨度依概率影响算法的峰值检测率. 验证了在不同的噪声条件下, PMB算法依概率收敛到函数的多个极值点, 且算法找到全局极值点概率高于找到局部极值点的概率; 验证了蒲丰距离影响PMB算法的全极值点寻优性能和求解极值点的定位精度, 噪声强度影响算法的峰值检测率和定位精度; 对比噪声环境下的改进蝙蝠算法, PMB算法具有更好的极值点定位精度和较好的多极值点寻优特性; 对比PSO算法在5维CEC2013测试函数集上的表现, PMB算法具有更好的多维函数寻优能力、抗噪声性能和多极值点寻优性能. 从而使得PMB算法能在生产实际中提供更准确的决策变量和更多的优化方案. 噪声环境下的依概率优化算法的理论和应用研究刚刚起步, 作者后续工作将进一步研究提高PMB算法对高维问题的处理效率.

作者简介

王霞

云南大学博士研究生. 主要研究方向为智能优化算法. E-mail: wangxiacsu@163.com

王耀民

云南大学博士研究生. 主要研究方向为SDN, 数据中心和智能优化算法. E-mail: 18988081898@189.cn

施心陵

云南大学信息学院教授. 主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学. 本文通信作者. E-mail: xlshi@ynu.edu.cn

高莲

云南大学信息学院讲师. 主要研究方向为生物医学信号处理. E-mail: ylbgl123@sina.com

李鹏

云南大学信息学院副教授. 主要研究方向为输变电系统安全诊断、预警与维护决策研究. E-mail: lipeng@ynu.edu.cn