引用本文

季新芳, 张勇, 巩敦卫, 郭一楠, 孙晓燕. 异构集成代理辅助的区间多模态粒子群优化算法. 自动化学报, 2024, 50(9): 1831−1853 doi: 10.16383/j.aas.c210223

Ji Xin-Fang, Zhang Yong, Gong Dun-Wei, Guo Yi-Nan, Sun Xiao-Yan. Interval multimodal particle swarm optimization algorithm assisted by heterogeneous ensemble surrogate. Acta Automatica Sinica, 2024, 50(9): 1831−1853 doi: 10.16383/j.aas.c210223

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

关键词

粒子群优化，多模态优化，高昂计算代价，代理辅助 

摘要

现实生活中的很多黑盒优化问题可归为高计算代价的多模态优化问题(Multimodal optimization problem, MMOP), 即昂贵多模态优化问题(Expensive MMOP, EMMOP). 在处理该类问题时, 决策者希望以尽量少的计算代价(即尽量少的真实函数评价次数)找到多个高质量的最优解. 然而, 已有代理辅助的进化优化算法(Surrogate-assisted evolutionary algorithm, SAEA)很少考虑问题的多模态属性, 运行一次仅可获得问题的一个最优解. 鉴于此, 研究一种异构集成代理辅助的区间多模态粒子群优化(Interval multimodal particle swarm optimization algorithm assisted by heterogeneous ensemble surrogate, IMPSO-HES)算法. 首先, 借助异构集成的思想构建一个由多个基础代理模型组成的模型池; 随后, 依据待评价粒子与已发现模态之间的匹配关系, 从模型池中自主选择部分基础代理模型进行集成, 并使用集成后的代理模型预测该粒子的适应值. 进一步, 为节约代理模型管理的代价, 设计一种增量式的代理模型管理策略; 为减少代理模型预测误差对算法性能的影响, 首次将区间排序关系引入到进化过程中. 将所提算法与当前流行的5种代理辅助进化优化算法和7 种最先进的多模态优化算法进行对比, 在20个测试函数和1个建筑节能实际问题上的实验结果表明, 所提算法可以在较少计算代价下获得问题的多个高竞争最优解.

文章导读

实际生产生活中的许多问题都具有多模态特性, 即存在多个全局或局部最优解, 如药物分子设计[1]、作业车间调度[2]和蛋白质结构设计[3]等. 这类问题称为多模态优化问题(Multimodal optimization problem, MMOP)[4-5]. 在很多情况下, 该类问题又同时存在目标函数评价代价昂贵的现象. 以基于EnergyPlus仿真软件的建筑节能设计问题为例, 在普通电脑上运行一次进化优化算法通常需要几十分钟, 甚至数个小时[6]. 将同时具有多模态特性和高昂计算代价的优化问题称为昂贵多模态优化问题(Expensive MMOP, MMOP)[7]. 

在求解昂贵多模态优化问题时, 决策者往往希望可以同时找到它的多个最优解, 主要原因如下[7-8]: 1)对于很多的实际工程优化问题, 设计师通常希望从差异较大的若干优秀解决方案中自主选择满足不同需求的方案; 2)当采用代理模型辅助的进化优化算法处理该类问题时, 受训练数据不足的影响, 代理模型拟合出的目标函数的全局最优点未必是实际问题的全局最优点. 这些伪最优点会诱导种群舍弃真实最优点, 进而陷入局部收敛. 此时, 同时定位问题的多个优化解, 势必可以提高算法找到真实全局最优解的可能性. 

针对多模态优化问题, 国内外学者已经提出诸多的进化优化算法. 依据模态处理方法的不同, 这些算法大致可分为3类[9]. 第1类为小生境技术, 其基本思想是采用某种策略产生若干个多样性好的子种群, 使它们分别朝着不同优化解的方向搜索[10-14]. 近年来, 为克服小生境半径对算法性能的影响, 学者们也提出多种无参数的改进小生境技术, 如Li[15]提出的物种形成策略、王湘中等[16]提出的山谷探索法等. 类似地, 张贵军等[17]也设计了一种两阶段退火策略来动态调整小生境半径. 特别地, 文献[18-19]提出的适应值共享策略, 其思想也是根据个体相似性将种群分为不同的子种群. 第2类是种群多样性增强技术, 其基本思想是通过增强种群的多样性来确保算法搜索方向的多样性. 部分代表性方法如Qu等[20]提出的基于局部信息交互的粒子群优化算法、Biswas等[21]提出的局部信息共享的差分进化算法等. 第3类是多目标转换技术, 其主要思想是将单目标多模态问题转化成一般的多目标优化问题进行求解. 变换后问题通常包括两个目标: 一个是给定的多模态问题, 另一个是衡量解多样性的指标[9, 22-23]. 与此同时, 这些算法也在诸多实际问题中获得成功应用, 如药物分子设计[1]、特征选择问题[24]等. 但是, 当处理昂贵优化问题时, 由于需要进行若干次的真实个体评价才能获得问题的最优解, 这些算法依然存在运行代价过高的不足. 

目前, 求解高昂优化问题的进化算法(Evolutionary algorithm, EA)已有很多, 其中最具代表性的是代理辅助的进化优化算法(Surrogate-assisted evolutionary algorithm, SAEA)[25]. 该类方法采用计算便宜的代理模型替代昂贵真实函数来评价个体的适应值, 可以达到降低算法计算代价的目的. 随之, 很多优秀的机器学习方法相继用于产生代理模型[26-29]; 相应地, 诸多典型的SAEA也相继提出[30-32]. 从代理模型的使用规模上, 这些算法可以分为单代理模型辅助的EA和集成代理模型辅助的EA. 部分单代理模型辅助的EA包括多项式回归(Polynomial regression, PR)辅助的EA[29]、支持向量机辅助的EA[33]、径向基函数网格(Radial basis function network, RBFN)辅助的EA[28, 34]和Kriging辅助的EA[35]或高斯过程模型辅助的EA[36-38]等. 通常不同的代理模型具有不同的特性, 适合于不同类型的优化问题. 在没有问题先验知识的情况下, 决策者很难为当前问题提供一个合适的代理模型. 由于没有其他代理模型可以弥补当前代理模型的缺陷, 单代理辅助EA的鲁棒性相对较差. 

通过合理组合多个不同特性的代理模型, 集成代理模型通常可以获得比单一代理模型更为优越的泛化性能. 现有代理模型集成策略可分为异构集成和同质集成两种. 异构集成由多个不同类型的单个代理模型组成, 而同质集成由多个相同类型的单个代理模型组成. 为便于区分, 下文将集成代理模型中的单个代理模型统称为基础代理模型. 在诸多的集成代理模型辅助EA中, 最常用的同质集成代理模型是基于RBFN的集成代理. 文献[39-41]采用RBFN同时构建问题的全局和局部代理模型; Wang等[32]采用Bagging算法构建大量的RBFN代理模型, 并在优化过程中自适应集成这些代理模型. 在研究异构集成代理模型时, 学者们最常用的3种基础代理模型是Kriging、RBFN和PR. 学者们采用不同的策略组合这些基础代理模型, 分别提出不同的集成代理模型[42-48]. 实验表明, 与同质集成代理模型相比, 基于异构集成代理模型的进化优化算法可以显著提高算法的搜索性能[25]. 然而, 这些方法都是面向求解问题的一个全局最优解而设计的. 在很多情况下, 它们只需要保证代理模型在全局最优峰处的精度即可. 除在单目标优化问题中采用异构集成模型, 陈万芬等[49]在处理昂贵多目标优化问题时, 也给出一种基于Kriging和RBFN的异构加权集成代理模型. 然而, 由于其处理对象为包含多个冲突目标的多目标优化问题, 他们提出的代理模型构建和更新方法并不适合昂贵多模态优化问题. 当面对包含多个全局最优解的多模态问题时, 如何同时保证代理模型在多个最优峰/谷处的精度, 需要提出更为高效的代理模型集成和管理策略. 

此外, 代理模型预测的不确定性在SAEA中也扮演着重要的角色. 它会给SAEA带来负面影响, 导致SAEAs搜索停顿或收敛于假最优, 因此, 需要合理使用这些不确定信息. 在SAEA中代理模型不确定性的表示有多种形式, 如采用Kriging模型提供的预测不确定性、利用解与其邻域内训练数据的距离来估计不确定性[50]等. 此外, 在多代理辅助的EA中, 可以采用多个代理模型的预测差值刻画预测值的不确定性[47, 51]. 目前, 大部分SAEA仅将不确定信息引入到代理模型管理, 即用于挑选不确定性较大的解[44, 47, 50-52]进行真实函数评价. 这些方法均从代理模型的角度出发, 期望提高代理模型的精度. 与之不同, 本文从进化角度出发, 将不确定信息融入到个体的适应值评价中, 在减少计算代价的同时避免代理模型不精确导致的进化方向错误等问题. 

可以看出, 虽然用于求解多模态优化问题或高昂优化问题的进化算法已有很多, 但是, 少有算法将两者结合在一起. 2011年Yahyaie等[53]首次给出一种代理辅助的多模态进化优化算法. 首先, 采用自适应网格技术获得目标函数曲面的初始估计; 随后, 利用生成的网格定位问题的局部最优点, 并在局部最优点附近建立多个局部代理模型. 由于仅使用了单一类型的代理模型, 这极大限制了该方法处理复杂多模态优化问题的性能. 为此, 2021年Ji等[7]提出了一种双代理辅助的双种群粒子群优化算法(Dual-surrogate assisted cooperative particle swarm optimization, DSCPSO). 该算法设计了一种双种群协同粒子群优化机制, 用来同时探索和开发问题的多个模态; 构建了一种多模态引导的双层协同代理模型, 用于协助种群快速发现新模态和开发已有模态. 尽管DSCPSO显著提升了PSO处理多模态问题的能力, 但是, 它需要决策者设置多个重要的控制参数, 这在一定程度上限制了它的实际应用效果. 

如前所述, 如果直接使用已有的多模态进化算法求解高昂多模态优化问题, 存在计算耗时的问题. 如果将代理模型辅助的进化算法用来处理该类问题, 至少存在如下3个困难亟待解决: 

1)选择何种代理模型集成策略来拟合所要求解的高昂多模态优化问题. 现有集成策略只需要保证代理模型在全局最优峰/谷处的精度即可. 当面对包含多个全局最优解的多模态问题时, 如何同时保证集成代理模型在多个最优峰/谷处的精度, 需要提出更为高效的模型集成策略. 

2)代理模型的管理, 即需要真实函数评价的个体的选择问题和代理模型的更新问题. 选取的个体既能体现出问题的全部模态信息, 又要保证代理模型在已有模态处的精度. 当问题的模态数和模态位置未知时, 还需要设计的代理模型更新策略能够及时响应模态数量和位置的变化. 

3)当采用代理模型代替真实目标函数来预测种群中个体的适应值时, 预测误差会影响种群的搜索性能. 在不增加模型管理代价的前提下, 如何避免预测误差对算法性能的影响, 也是一个需要解决的挑战性问题. 

鉴于此, 研究一种异构集成代理辅助的区间多模态粒子群优化算法(Interval multimodal particle swarm optimization algorithm assisted by heterogeneous ensemble surrogate, IMPSO-HES), 重点解决多模态特性下的代理模型选择与管理问题. 相对已有进化优化算法, 主要贡献如下: 

1)提出一种基于异构集成的代理模型自主构建策略. 针对算法识别得到的每个模态, 从代理模型池中自主选择合适的异构基础代理模型进行集成. 通过对每个模态建立合适的集成代理模型, 该策略可以同时保证代理模型在多个最优峰/谷处的精度. 

2)给出一种增量式的代理模型管理和更新策略. 在算法迭代过程中, 不断识别可能发现的新模态, 并利用这些模态对应的最优粒子/个体重新构建新的基础代理模型; 同时, 利用这些最优粒子作为填充样本, 重新训练模型池中部分相关的旧基础代理模型. 该策略不仅可以保障模型池中异构基础代理模型的质量, 而且能够节约模型池的管理代价. 

3)首次引入区间数来表示模型预测得到的粒子适应值, 并给出一种基于区间排序的粒子位置更新策略. 相对传统基于精确值的粒子比较策略, 该策略同时考虑了粒子预测适应值的大小和不确定程度, 其得到的粒子排序结果更为可靠. 

相对DSCPSO (Dual-surrogate assisted coperative PSO)[7]等已有方法, IMPSO-HES具有如下优势或改进: 

1) DSCPSO采用两个种群分别实现问题新模态的搜索和旧模态的开采, 而IMPSO-HES只需单个种群即可实现上述目标, 其所需控制参数更少. 

2) DSCPSO仅利用了RBFN来构建双层代理模型, 而IMPSO-HES同时采用了两类代理模型, 即RBFN和PR. 一方面, 由于RBFN和PR的组合可以处理更多类型的优化问题, IMPSO-HES的应用范围更广; 另一方面, 由于IMPSO-HES可以从模型池中为每个粒子自主选择合适的基础代理模型, 其得到的粒子评估结果更为准确. 

3)在DSCPSO中, 当数据库发生变化时需要重新构建所有的代理模型; 与之不同, IMPSO-HES采用增量式方法有选择性地更新部分基础代理模型, 可以减少代理模型的更新代价. 

4) IMPSO-HES考虑到了代理模型预测的不确定性, 其得到的粒子排序结果相对更为可靠. 

本文结构安排如下: 第1节主要介绍相关工作; 第2节详细介绍所提IMPSO-HES的框架及其改进策略; 第3节和第4节则在数值问题和建筑能源实例上验证所提算法的有效性; 第5节总结全文并给出研究展望. 

图 1  IMPSO-HES的框架图

图 2  精确评价和区间评价策略下IMPSO-HES所得GS值

图 3  精确评价和区间评价策略下IMPSO-HES所得VR值

针对昂贵多模态优化问题, 本文提出一种异构集成代理辅助的多模态粒子群优化算法, 即IMPSO-HES. 在更新模型池时, 通过种群反馈信息自适应调整RBFN和PR被选择的概率, 可以使构建的模型池更适合处理当前优化问题. 设计的基于模态的基础代理模型选择策略, 可以让不同粒子选择更适合自己的基础代理模型进行集成, 提高集成代理模型的预测精度. 提出的两阶段增量式模型更新策略, 在提高集成代理模型的质量同时减少了模型的训练代价. 此外, 引入的区间适应值评价策略和PSO自适应更新策略, 在提高算法探索能力的同时提升了最优解的精度. 在20个基准测试函数和1个建筑能源优化问题上的实验结果表明, 相比12种典型对比算法, 在有限计算资源内, 所提算法在获得较好全局最优解的同时, 也能找到较多的全局最优解或局部最优解. 

尽管在处理昂贵多模态优化问题时IMPSO-HES表现出较好的性能, 但是目前这方面的研究工作相对较少, 仍有很多问题需要进一步研究. 首先, 本文仅采用常用的2类代理模型. 代理模型的种类多样, 集成其他代理模型是否会获得更好的结果需要进一步研究; 另外, 含约束昂贵多模态优化问题和昂贵多目标多模态优化问题也是未来需要研究的课题. 

作者简介

季新芳

中国矿业大学信息与控制工程学院博士研究生. 2013年获得中国矿业大学硕士学位. 主要研究方向为代理辅助进化优化, 多模态优化. E-mail: mimosa_615615@126.com

张勇

中国矿业大学信息与控制工程学院教授. 2009年获中国矿业大学控制理论与控制工程专业博士学位. 主要研究方向为智能优化, 数据挖掘. 本文通信作者. E-mail: yongzh401@126.com

巩敦卫

中国矿业大学信息与控制工程学院教授. 1999年获得中国矿业大学博士学位. 主要研究方向为进化计算与应用. E-mail: dwgong@vip.163.com

郭一楠

中国矿业大学信息与控制工程学院教授. 主要研究方向为智能优化算法与控制, 数据挖掘. E-mail: nanly@126.com

孙晓燕

中国矿业大学信息与控制工程学院教授. 2009年获中国矿业大学控制理论与控制工程专业博士学位. 主要研究方向为进化计算, 机器学习. E-mail: xysun78@126.com