双模型驱动的多偏好策略自适应差分演化算法

龚懿昀 ,  于海波 ,  王韵 ,  康丽 ,  曾建潮

中北大学学报(自然科学版) ›› 2024, Vol. 45 ›› Issue (05) : 638 -646.

PDF (1517KB)
中北大学学报(自然科学版) ›› 2024, Vol. 45 ›› Issue (05) : 638 -646. DOI: 10.3969/j.issn.1673-3193.2024.05.010
图像处理与计算成像

双模型驱动的多偏好策略自适应差分演化算法

作者信息 +

Dual Model⁃Driven Differential Evolution Algorithm with Multi⁃Preference Strategy Adaption

Author information +
文章历史 +
PDF (1553K)

摘要

为增强代理模型辅助进化算法对高维昂贵优化问题的求解性能, 提出了一种双模型驱动的多偏好策略自适应差分演化算法。该算法基于全局和局部两种代理建模方法, 有机融合了3种具有不同寻优偏好的进化策略。每次迭代, 通过利用优化过程中最优解在线更迭反馈信息, 以序贯方式自适应调整不同进化策略调用频次, 以高效平衡算法的全局勘探和局部开采。为促进种群内个体间优秀信息共享, 设计了一种精英个体驱动的差分扰动策略, 以增量潜在优解区域的最优样本先验。通过处理26个不同规模的高维基准测试问题, 结果表明, 所提算法的收敛性能和优化效率较4种先进的同类型算法在至少17个测试问题上绝对占优。

Abstract

In order to enhance the performance of surrogate-assisted evolutionary algorithms for solving high-dimensional expensive optimization problems, this paper proposed a dual model-driven differential evolution with multi-preference strategy adaption (SOEA-SS). SOEA-SS relied on three multi-preference evolutionary strategies supported by global and local surrogates. At each iteration, SOEA-SS adaptively adjusted the evolutionary strategies in a sequential manner to strike the global exploration and local exploitation equilibrium, according to the online feedback concerning the update of optimal solution. In order to promote the optimal information sharing among the population, an elites-driven differential perturbation strategy was developed to enrich the prior knowledge of the optimal regions. Experimental results show that SOEA-SS has significant superiority over four advanced algorithms on at least 17 out of 26 high-dimensional benchmark problems.

Graphical abstract

关键词

代理模型 / 昂贵优化 / 差分演化 / 策略自适应 / 精英扰动

Key words

surrogate model / expensive optimization / differential evolution / strategy adaption / elite perturbation

引用本文

引用格式 ▾
龚懿昀,于海波,王韵,康丽,曾建潮. 双模型驱动的多偏好策略自适应差分演化算法[J]. 中北大学学报(自然科学版), 2024, 45(05): 638-646 DOI:10.3969/j.issn.1673-3193.2024.05.010

登录浏览全文

4963

注册一个新账户 忘记密码

0 引 言

以多点种群为搜索单元代替独立单点搜索单元进行优化搜索的群体驱动进化算法原理简单、 易操作、 鲁棒性强, 尤其是对问题解析性态的弱依赖性等优势, 使其在航天器设计1、 形态拓扑优化2、 神经网络架构搜索3等实际复杂工程优化领域备受关注并获得广泛应用。其中衍生出的具有代表性的进化变体算法, 如粒子群算法4(Particle Swarm Optimization, PSO)、 差分演化5(Differential Evolution, DE)、 人工蜂群算法6(Artificial Bee Colony, ABC)等, 在应对连续优化问题上具有强劲的收敛性能。然而, 进化算法在对问题解空间的迭代遍历及收敛过程中, 往往涉及适应度函数(性能评估函数)的高频次调用, 使得此类算法在应对伴随理化实验以及高精度仿真等计算昂贵优化问题时常需付出巨大计算成本。鉴于实际工况中性能评估函数的单次调用往往需耗费几小时、 甚至几天的计算周期, 使得进化算法解决计算昂贵优化问题的实用性面临严峻挑战。代理模型辅助的进化算法(Surrogate-assisted Evolutionary Algorithms, SAEAs)为突破进化算法解决计算昂贵优化问题的性能瓶颈提供了新的技术手段。SAEAs通过在迭代过程中利用演化数据训练计算廉价的代理模型逼近计算昂贵的目标函数, 辅助迭代种群个体的适应度函数评估, 大幅缩减了目标适应度函数的调用频次, 显著提升了进化算法处理昂贵优化问题的求解性能。

在SAEAs中, 普遍选用的代理模型包括高斯过程7(Gaussian Process, GP)、 径向基函数8(Radial Basis Function, RBF)、 多项式回归9(Polynomial Regression, PR), 以及支持向量机10((Support Vector Machine, SVM)等。相比计算昂贵的性能评估函数, 代理模型的计算成本几乎可忽略不计。目前, 研究者基于模型辅助的优化思路提出了诸多SAEAs算法11, 其大体可分为单一模型辅助的SAEAs、 多模型辅助的SAEAs及集成模型辅助的SAEAs。单一模型驱动的SAEAs往往针对具体问题和其适用条件, 依据经验规则线下选定一种代理模型技术, 并在进化优化过程中仅依赖此单一模型驱动进化优化搜索。比如, 田杰等12选用高斯过程模型逼近高维问题解空间地貌, 辅助社会学习微粒群算法(Social Learning Particle Swarm Optimization, SLPSO)迭代探索解空间中模型估值最优和模型不确定性最大的潜在最优区域。Regis13针对目标和约束昂贵优化问题构建了三次径向基函数模型来分别逼近目标和每个约束函数的地貌空间。同样, Chugh等14采用Kriging模型逼近多目标优化问题中的每个目标, 同时兼顾参考向量分布及种群个体的即时位置来权衡迭代种群的多样性和收敛性。

特定模型性能单一且局限性较大, 因而在解决复杂问题时往往导致算法的鲁棒性和泛化性不足。结合多种具有不同特性的代理模型, 以多模型协同逼近的方式挖掘问题解空间地貌先验, 有助于提高代理模型辅助进化算法对高维复杂计算昂贵优化问题的求解效率。Cai等15通过构建多种代理模型, 建立了基于代理模型引导和邻域划分策略的遗传算法更新机制, 有效改善了种群演化的多样性和算法的鲁棒性。Chen等16集成了全局和局部两种代理模型来搜索最优解, 通过构建全局模型快速定位潜在最优区域, 并利用局部模型围绕当前局部最优邻域深度开采。Zhou等17将整个进化过程界定为多个进化阶段, 并在不同阶段采用不同的代理模型, 通过迭代挖掘不同模型导向的优势个体信息, 有效平衡了种群多样性和收敛性。同样, Li等18将解空间搜索划分为3个进程, 并结合每个进程的寻优特点, 分别选用不同的训练样本构建全局模型和模糊区域导向的局部模型, 并通过深度开采局部模型最优解, 显著提升了算法的全局收敛性能。

多模型辅助的SAEAs独立结合了多种不同特性的单一代理模型, 这有助于准确表征待优化问题的全局和局部解空间地貌特征, 而通过结合集成学习技术构建多模型集成模型辅助SAEAs, 则有助于提高目标适应度预测的鲁棒性, 有效控制了多个独立单一模型评估的不确定性。Wang等19为提高多模型对全局和局部解空间预测的鲁棒性, 降低单一模型诱发的不确定性, 基于Bagging技术分别构建了全局集成模型和局部集成模型, 利用全局集成模型筛选具有发展潜力的候选子代, 并结合局部搜索深度挖掘局部集成模型的最优解。Guo等20为提高集成建模的多样性和集成模型不确定性估计的可靠性, 结合特征选择和特征变换构建了3类不同特征属性的训练样本集, 并以此训练了3组异构基模型, 通过平均集成所有基模型来预测候选解适应度。同时, 基于期望改进和置信下限采集函数, 结合集成模型预测输出及多模型预测输出方差, 设计了一种多模型进化采样策略, 显著提升了集成模型辅助SAEAs的优化效率。Li等21融合多项式回归模型和径向基函数模型两种模型的优势, 有效平衡了迭代种群的广度探索和深度开采, 提高了种群收敛效率。此外, 陈万芬等22通过加权平均集成径向基函数网络模型与Kriging模型来构建高精度的异构集成模型, 以此增强算法处理不确定性信息的能力。

综上所述, 多模型辅助的SAEAs及集成模型辅助的SAEAs在提高种群收敛能力的同时可大幅增强算法在高维昂贵问题解空间的探索力度。为此, 文中提出一种双模型驱动的多偏好策略自适应差分演化算法(SOEA-SS), 以自适应切换策略的模式及时捕获最优解更新状况。主要贡献如下:

1) 提出一种序贯循环的多策略选择模式, 根据迭代最优解的更迭情况, 从策略池中自适应选择进化策略适配迭代种群的进化状态, 兼顾全局探索和局部开发能力的同时加快种群收敛效率。

2) 提出一种精英个体驱动的差分扰动策略。以精英解个体为导向, 使用差分演化算法对其进行扰动, 产生多个有竞争力的后代个体以增量潜在最优样本邻域的优秀先验, 有效调控了迭代种群多样性和收敛性。

3) 提出的SOEA-SS算法相比4种先进的同类型SAEAs, 在多种不同类型的高维多模态测试问题上具有更强的优化性能。

1 方法描述

本文提出一种双模型驱动的多偏好策略自适应差分演化算法(SOEA-SS),该方法由3种不同偏好的进化策略组成: 1)全局代理模型驱动的进化策略; 2)局部代理模型驱动的进化策略; 3)精英个体驱动的差分扰动策略。每次迭代时, 3种进化策略仅从候选解集中选择一个待评价候选解dbest。同时, 三者根据最优解的在线更迭反馈信息, 自适应切换进化策略, 以适配迭代种群的即时寻优状态, 平衡算法的全局勘探和局部开采。

算法 1 给出了SOEA-SS的伪代码, 其总体框图见图 1, 其中, 虚线表示数据流向。图 1 中, SOEA-SS算法首先采用拉丁超立方采样(Latin Hypercube Sampling, LHS)23初始化种群并计算其真实适应值, 同时用其初始化数据库DB。数据库DB按数据适应度优劣升序排列, 并记录当前全局最优解(Gbest,F(Gbest))。然后, 从3种候选策略(详见算法2算法3算法4)中随机选择一种采样策略驱动迭代种群状态转移。若依托当前进化策略产生的候选解优于当前全局最优解, 则该进化策略直接递进延续至下一代迭代种群。否则, 以序贯方式递进切换下一种进化策略, 以此循环, 直至耗尽所有真实评价次数。最后, 输出最优解。3种进化策略分别按全局代理模型驱动的进化策略、 局部代理模型驱动的进化策略和精英个体驱动的差分扰动策略的顺序进行序贯调整, 其相应伪代码分别见算法2~算法4

算法2给出了全局代理模型驱动的进化策略伪代码。该策略利用数据库DB所有样本构建全局RBF模型, 并以序列二次规划算法(SQP)作为全局搜索引擎搜索RBF模型的最优解xg。为广度探索最优解xg的邻域信息, 将全局最优解Gbest与数据库DB中全部样本按DE/rand/1进行变异(如式(1)所示)产生试探种群Vc1。再将xg与数据库DB中全部样本全交叉产生种群Vc2。然后从Vc1Vc2中随机选择N个样本组成子集合O(t)。最后, 使用建立的全局RBF模型预测集合O(t)xg, 并选择其中预测值最优的样本进行真实计算。

DE/rand/1:

υi=xr1+F(xr2-xr3),

式中: F为缩放比例因子; ir1r2r3ri{1,2,,N}

算法3给出了局部代理模型驱动的进化策略伪代码。该策略以数据库中排名前2d+1的最优样本建立局部RBF模型, 随后使用DE算法作为局部搜索引擎对局部RBF模型覆盖邻域进行局部搜索。将局部最优解xlGbest与数据库DB中前2d+1个最优样本按DE/best/2执行变异(如式(2)所示)产生试探种群Vc3。再将xl与数据库DB中前2d+1个最优样本全交叉产生种群Vc4。然后从Vc3Vc4集中随机挑选N个样本组成子集合Q(t)。最后, 利用局部RBF代理模型预测Q(t)xl, 并计真其估值最优样本dbest的真实适应度。

DE/best/2:

υi=xbest+F(xr1-xr2+xr3-xr4),

式中: xbest表示当前种群最优解; F为缩放比例因子; ir1r2r3r4ri{1,2,,N}

算法4给出了精英个体驱动的差分扰动策略伪代码。在该策略中, 全局最优解Gbest与数据库中最优的N个样本点分别使用了DE/rand/1与DE/best/2算子产生试探种群Vc5Vc6。随后, 计算子种群中每个个体与Gbest的欧氏距离, 将距离值最小的样本点与数据库中前N个最优样本全交叉产生试探种群Vc7, 再次计算种群Vc7中每个个体与Gbest的欧氏距离, 并选择其中距离值最小的关联样本dbest对其进行真实计算。

图 2 绘制了优化过程中精英个体驱动的差分扰动策略与无精英个体驱动的差分扰动策略经4个不同演化阶段的候选解分布概况。其中, 紫色点表示目标函数全局真实最优解所在位置, 蓝色圆点表示精英个体驱动的差分扰动策略下当前迭代中每个子代的位置分布; 橘红色点表示无精英扰动情况下迭代最优解所在位置分布。由图2(a)~图 2(d) 可见, 经多子代扰动搜索获得的扰动最优解质量在不同优化阶段均显著优于无子代扰动搜索, 表明精英个体驱动的差分扰动策略导引的种群寻优能力与收敛效率要显著优于无精英扰动的搜索策略, 更有利于辅助提升算法的求解性能。

2 实验验证

本节利用SOEA-SS算法优化求解具有单峰零点最优、 多峰零点最优和复杂非对称、 多峰、 非零点最优等不同模态类型、 最优属性和问题规模的6个常规测试用例及8个CEC 2014 part B中的复杂测试用例, 以验证SOEA-SS的有效性和求解效率, 并选用4种先进的同类型算法包括SA-COSO24、 SHPSO25、 SAMSO26和CA-LLSO27与SOEA-SS进行性能对比。表 1 给出了所选测试问题的名称和基本特征。此外, 采用95%置信度水平下的Wilcoxon双侧秩和检验评价所提方法与对比算法间的显著性差异, 并采用符号“+” “-”和“≈”分别表示所提方法SOEA-SS的求解性能显著优于、 显著劣于和等同于其他对比算法。

2.1 参数设置

SOEA-SS算法的种群规模N设定为100, 尺度因子F=0.8, 交叉概率CR=1, 交叉策略均采用二项交叉(Binomial Crossover)。全局和局部RBF模型均采用Cubic函数进行建模。此外, 各算法最大真实评价次数MaxFes=1 000。算法SA-COSO、 SHPSO、 SAMSO和CA-LLSO的其他参数配置与相关原始文献参数配置一致。实验所涉算法均在Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz的台式机上运行, 且各算法独立运行30次取其统计结果, 包括各对比算法最优解的统计均值和方差。

2.2 SOEA⁃SS对比4种先进算法的实验结果

本节选用4种先进的同类型算法(包括SA-COSO、 SHPSO、 SAMSO和CA-LLSO)进行对比实验。表 2 给出了所提算法SOEA-SS与对比算法在所选18个测试问题上的计算结果, 测试维度分别选取30维, 50维和100维。

表 2 中F1是一个单模态问题, F2为具有狭窄盆谷特性的多模态问题, F3为对称多极值多模态测试问题, F4、 F5和F6均为多极值、 多模态测试问题, 且F5和F6具有非对称解空间结构。由表 2 可见, 对于大多数测试问题而言, SOEA-SS的求解性能要显著优于其他4种对比算法。

对于复杂多模态测试函数F6, 其地貌呈现两个平坦多极值区域, 其最优解位于地貌中边界狭窄盆谷区域。该问题设置了一个位于原点位置上且与全局最优解具有相似适应度水平级的局部最优, 这对优化算法探索和开采性能提出了极大挑战, 而SOEA-SS能够很好地跳出这个局部最优。由于集成了自适应策略选择的架构, 使得SOEA-SS对不同环境地貌的适应能力显著提升, 且精英个体驱动的差分扰动策略使得种群在收敛过程中更好地保持了多样性。计算所提算法与其他对比算法的双侧Wilcoxon秩和检验, 结果表明: 相比SA-COSO和SHPSO, 所提SOEA-SS至少在15个测试问题上显著占优; 相比SAMSO和CA-LLSO, 所提SOEA-SS至少在12个测试问题上显著占优, 且SOEA-SS获得了最佳Friedman平均排名值1.83, 表明了所提算法强劲的运算效率及高鲁棒性。

2.3 SOEA⁃SS求解CEC 2014 part B的实验结果

为进一步验证SOEA-SS算法的求解效率, 采用SOEA-SS对CEC 2014 part B29中的8个经典测试问题进行优化求解, 问题规模控制为30维, 分别表示为F7~F14。鉴于上一轮对比中SHPSO和SAMSO的良好性能, 进一步考察SOEA-SS与SHPSO和SAMSO在该组测试集上的性能差异, 统计结果见表 3。由各算法的Friedman检验结果可见, SOEA-SS得分最高(1.38), 其在8个测试问题中的5个问题上明显优于SHPSO和SAMSO, 说明SOEA-SS相对于问题规模和复杂度而言, 具有较强的鲁棒性。

3 结 论

针对高维昂贵优化问题设计了一种双模型驱动的多偏好策略自适应差分演化算法SOEA-SS。该算法以序贯方式自适应调整多种不同特性的进化策略, 显著提高了算法的收敛效率。为了强化算法挖掘迭代种群优秀信息的能力, 设计了一种精英个体驱动的差分扰动策略, 实现了算法对潜在最优区域的高效开采。实验结果表明, 对于30维、 50维和100维的高维复杂基准测试问题, 所提SOEA-SS算法相较4种先进的同类型算法在收敛性能和优化效率方面均具有显著的性能优势。

尽管如此, 由实验结果可见, SOEA-SS在求解部分具有特定复杂地貌的测试问题如函数F10、 F11和F14时, 其求解性能较其他同类型算法并不占优。其原因可能是由于模型精度受限导致迭代种群多样性衰退加速, 致使算法早熟收敛。故在下一步工作中, 将考虑设计高效的模型保真度管理策略以提高代理模型的预测精度, 同时将考虑在不同搜索阶段动态优调迭代种群多样性, 以期提升SOEA-SS对复杂问题场景的泛化性。

参考文献

[1]

BAYSAL OELESHAKY M E. Aerodynamic design optimization using sensitivity analysis and computational fluid dynamics[J]. Aiaa Journal199230(3): 718-725.

[2]

ZHAO WGUPTA AREGAN C Det al. Component data assisted finite element model updating of composite flying-wing aircraft using multi-level optimization[J]. Aerospace Science and Technology201995: 105486.

[3]

ELSKEN TMETZEN J HHUTTER Fet al. Neural architecture search: A survey[J]. Journal of Machine Learning Research201920(55): 1-21.

[4]

KENNEDY JEBERHART R. Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks, 2002: 1942-1948.

[5]

STORN RPRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization199711(4): 341-359.

[6]

LI YSONG XGUAN W. Mobile robot path planning based on ABC-PSO algorithm[C]// 2022 IEEE 6th Information Technology and Mechatronics Engineering Conference (ITOEC), 2022: 530-534.

[7]

TIAN JTAN YZENG Jet al. Multiobjective infill criterion driven gaussian process-assisted particle swarm optimization of high-dimensional expensive problems[J]. IEEE Transactions on Evolutionary Computation201923(3): 459-472.

[8]

PARK JSANDBERG I W. Universal approximation using radial-basis-function networks[J]. Neural Computation19913(2): 246-257.

[9]

KRITHIKAA MMALLIPEDDI R. Differential evolution with an ensemble of low-quality surrogates for expensive optimization problems[C]//IEEE Congress on Evolutionary Computation (CEC), 2016: 78-85.

[10]

LOSHCHILOV ISCHOENAUER MSEBAG M. Comparison-based optimizers need comparison-based surrogates[C]//Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I, 2010: 364-373.

[11]

WANG XWANG GSONG Bet al. A novel evolutionary sampling assisted optimization method for high dimensional expensive problems[J]. IEEE Transactions on Evolutionary Computation201923(5): 815-827.

[12]

田杰, 孙超利, 谭瑛, .基于多点加点准则的代理模型辅助社会学习微粒群算法[J].控制与决策202035(1): 131-138.

[13]

TIAN JieSUN ChaoliTAN Yinget al. Similarity-based multipoint infill criterion for surrogate-assisted social learning particle swarm optimization[J]. Control and Decision202035(1): 131-138. (in Chinese)

[14]

REGIS R. Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions[J]. IEEE Transactions on Evolutionary Computation201418(3): 326-347.

[15]

CHUGH TJIN YMiettinen Ket al. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation201822(1): 129-142.

[16]

CAI XGAO LLI X. Efficient generalized surrogate-assisted evolutionary algorithm for high-dimensional expensive problems[J]. IEEE Transactions on Evolutionary Computation202024(2): 365-379.

[17]

CHEN CWANG XDONG Het al. Surrogate-assisted hierarchical learning water cycle algorithm for high-dimensional expensive optimization[J]. Swarm and Evolutionary Computation202275: 101169.

[18]

ZHOU X GZHANG G J. Abstract convex underestimation assisted multistage differential evolution[J]. IEEE Transactions on Cybernetics201747(9): 2730-2741.

[19]

LI GZHANG QLIN Qet al. A three-level radial basis function method for expensive optimization[J]. IEEE Transactions on Cybernetics202252(7): 5720-5731.

[20]

WANG XGAO LLI X. Multiple surrogates and offspring-assisted differential evolution for high-dimensional expensive problems[J]. Information Sciences2022592: 174-191.

[21]

GUO DJIN YDING Jet al. Heterogeneous ensemble-based infill criterion for evolutionary multiobjective optimization of expensive problems[J]. IEEE Transactions on Cybernetics201949(3): 1012-1025.

[22]

LI FCAI XGAO L. Ensemble of surrogates assisted particle swarm optimization of medium scale expensive problems[J]. Applied Soft Computing201974: 291-305.

[23]

陈万芬, 王宇嘉, 林炜星.异构集成代理辅助多目标粒子群优化算法[J].计算机工程与应用202157(23): 71-80.

[24]

CHEN WanfenWANG YujiaLIN Weixing. Heterogeneous ensemble surrogate assisted multi-objective particle swarm optimization algorithm[J]. Computer Engineering and Applications202157(23): 71-80. (in Chinese)

[25]

HELTON J CDAVIS F J. Latin hypercube sampling and the propagation of uncertainty in analyses of complex systems[J]. Reliability Engineering & System Safety200381(1): 23-69.

[26]

SUN CJIN YCHENG Ret al. Surrogate-assisted cooperative swarm optimization of high-dimensional expensive problems[J]. IEEE Transactions on Evolutionary Computation201721(4): 644-660.

[27]

YU HTAN YZENG Jet al. Surrogate-assisted hierarchical particle swarm optimization[J]. Information Sciences2018454-455: 59-72.

[28]

LI FCAI XGAO Let al. A surrogate-assisted multiswarm optimization algorithm for high-dimensional computationally expensive problems[J]. IEEE Transactions on Cybernetics202151(3): 1390-1402.

[29]

WEI F FCHEN W NYANG Qet al. A classifier-assisted level-based learning swarm optimizer for expensive optimization[J]. IEEE Transactions on Evolutionary Computation202125(2): 219-233.

[30]

SUGANTHAN P NHANSEN NLIANG J Jet al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[C]//Natural Computing, 2005: 341-357.

[31]

LIU BCHEN QZHANG Qet al. Behavioral study of the surrogate model-aware evolutionary search framework[C]//IEEE Congress on Evolutionary Computation (CEC), 2014: 715-722.

基金资助

国家自然科学基金青年基金项目(62106237)

国家自然科学基金联合基金项目(U21A20524)

山西省自然科学基金项目(202203021222057)

AI Summary AI Mindmap
PDF (1517KB)

341

访问

0

被引

详细

导航
相关文章

AI思维导图

/