欢迎访问《控制理论与应用》期刊网站！

解决动态约束多目标问题的复合预测进化算法

doi: 10.7641/CTA.2023.21101

郭知业，魏静萱

西安电子科技大学计算机科学与技术学院, 陕西西安 710071

基金项目: 国家自然科学基金项目(62272367)资助.

详细信息

作者简介

郭知业硕士研究生,目前研究方向为多目标优化、进化算法,E-mail: muxiaojue00gzy@163.com;

魏静萱副教授,目前研究方向为智能计算、多目标优化、优化理论与方法,E-mail: wjx@xidian.edu.cn.

通信作者

魏静萱，E-mail: wjx@xidian.edu.cn.

Composite predictive evolutionary algorithm for dynamic constrained multi-objective problems

GUO Zhi-ye ， WEI Jing-xuan

School of Computer Science and Technology, Xidian University, Xi’an Shaanxi 710071 , China

Funds: Supported by the National Natural Science Foundation of China (62272367).

摘要

动态约束多目标问题在路口交通管理、节能电力调度等现实场景中出现较多, 其目标函数和约束条件都会随时间(环境)发生连续缓慢变化. 求解这类动态问题的关键, 是有效追踪问题的随环境变化的一组最优解集. 为求解此类问题, 首先, 将约束变化分为2类, 并针对两类变化提出2个约束预测器, 用以追踪可行区域; 其次, 将约束预测器与非线性预测器组合成复合预测策略, 根据问题的不同变化情况使用策略中的对应预测器, 消耗较少的资源获得预测解, 加速寻优过程; 再次, 应用基于分解的多目标优化算法, 将预测解优化得到最终的最优解. 所提出的基于复合预测的动态多目标优化算法在8个动态变化的问题上与6个典型算法进行对比测试, 实验结果表明, 所提算法获得的解集在收敛性和多样性上具有显著优势, 复合预测策略的预测性能较优.

关键词

动态多目标优化 / 进化算法 / 动态约束条件

Abstract

Dynamic constrained multi-objective problems are used in real-world scenarios, such as intersection traffic management and energy-efficient power scheduling. Both the objective functions and constraints undergo continuous slow changes over time (in the environment). The key to solving these dynamic problems is effectively tracking a set of optimal solutions that evolve with environment. To address such problems, firstly, constraint changes are categorized into two types, and two constraint predictors are proposed for tracking feasible regions. Secondly, the constraint predictors are combined with a nonlinear predictor to form a composite predictive strategy. Depending on the specific changes in the problem, the strategy uses the corresponding predictor to obtain predictive solutions with less resource consumption, thus accelerating the optimization process. Finally, a decomposition-based multi-objective optimization algorithm is applied to optimize the predictive solutions, obtaining the ultimate optimal solution. The composite predictive evolutionary algorithm is compared with six typical evolutionary algorithms on eight dynamic problems. The experimental results demonstrate that the proposed algorithm has a significant advantage in terms of convergence and diversity in the solution set, with superior predictive performance of the composite strategy.

Keywords

dynamic multi-objective optimization / evolutionary algorithm / time-varying constraints

1 引言 2 背景知识 3 复合预测进化算法 3.1 复合预测进化算法流程 3.2 复合预测策略 3.2.1 简单预测器 3.2.2 集成预测器 4 实验 4.1 测试函数 4.2 指标 4.3 参数 4.4 对比算法 4.5 实验结果 5 结论

1 引言

在机械设计、资源管理、控制问题等现实问题中需要同时寻找多个相互冲突目标的最优解 ^[1-3]，问题本身也可能随着时间（也称环境，下文统称为环境）发生多次变化，这类问题称之为动态多目标问题 ^[4] . 求解动态多目标问题要在每次变化之前找到当前环境的一组最优解. 研究者常以非支配排序精英算法（nondominated sorting gene algorithm，NSGA-II）^[5]、粒子群算法（particle swarm optimization，PSO）^[6]、基于分解的多目标优化算法（multiobjective evolutionary algorithm based on decomposition，MOEA/D）^[7] 等进化算法实现优化过程，辅以变化检测和变化应对策略来应对问题的动态变化. 一些文献提出的算法仅考虑无约束的动态多目标问题 ^[8-9]，但没有额外的动态约束处理机制. 更进一步的，当问题的目标函数和约束条件都随环境动态变化，就被称作动态约束多目标问题 ^[10] . 问题将被动态的约束条件所影响，每个环境都需要重新搜索满足约束条件的最优解集，致使以上提及的算法都失效.

国际上对于动态多目标问题的研究集中在目标函数发生规律的连续变化问题上，大体可以划分为两类. 一些文献当检测到问题变化后在种群中引入一些随机个体和变异个体 ^[10-13]，或是在历史环境中收敛性较好的个体 ^[14-15]，然后将问题作为静态多目标问题求解. 然而这些方法缺乏对新环境的了解，只是一种盲目的应对; 另一类方法用数学方法拟合出最优解的变化趋势 ^{[8-9，16-23]}，预测环境变化后的最优解集和最优前沿所在位置. 但很难找到适当的逼近方法来描述变化趋势，这些方法或需求过多预训练资源 ^[9，17]，或时间复杂度过高 ^[18-19]，亦或只能学习出较为简单的变化特征 ^[20-23]，文献 ^[24-26] 针对约束条件也产生变化的动态多目标问题，用适应度较好的个体引导种群进化，但不适用于不同环境间差异过大的情况. 因此，如何克服目前已有方法的缺陷，设计出新的有效的进化算法，在动态环境下快速有效跟踪随环境变化且满足约束的最优解运动轨迹，是本文的一个研究目标.

相比无约束或静态约束优化，动态约束优化的关键是在满足当前环境的约束下，如何使算法快速有效跟踪问题的随环境发生变化的最优解集. 本文针对目标函数和约束条件都发生连续缓慢变化的动态约束多目标问题提出求解算法，当环境连续缓慢变化时，相邻环境的最优解差异较小，可通过预测技术快速求解. 首先，对约束条件的变化提出两类约束预测器，从环境的历史变化中学习约束的变化规律，定位新环境下可行区域的位置，采用一个非线性映射预测器学习目标函数变化的规律 ^[20]; 其次，提出复合预测策略（composite predict），划分问题变化的类别，并选用最适用的预测器应对变化; 最后，将复合预测策略应用于基于分解的多目标优化算法MOEA/D-M2M ^[27]，基于分解的思想能增强多样性，复合预测策略消耗较少的资源就能大幅推进优化过程，保证了收敛性，从而确保算法能够搜索到动态约束多目标问题的最优解集.

本文内容安排如下: 第2节介绍动态约束多目标问题背景知识; 第3节提出了复合预测策略，并用于解决动态约束多目标问题; 第4节进行算法实验.

2 背景知识

动态约束多目标问题（dynamic constrained multiobjective optimization problem，DCMOP）定义如下:

(1)

其中:

Ω \in R^{n}

是决策变量空间; 问题的变化用t的变化来表示，t也称作环境;

x = {(\begin{matrix} x_{1} x_{2} \dots x_{d} \end{matrix})}^{T} ， g （ x ， t ）

是不等式约束; h（x，t）是等式约束; f（x，t）表示在第t个环境下解x对应的目标函数值. 解决动态约束多目标问题就是要在每一个环境内找到当前环境下符合约束条件的最优解，多目标问题的最优解并不止一个，而是一组Pareto解.

Pareto支配: 在t 环境中，若存在两个解 x 和y 使得

\forall i \in {1，2 ， \dots ， m} ， f_{i} （ x ， t ） ⩽ f_{i} （ y ， t ）

且

\exists j \in {1，2 ， \dots ， m} ， f_{j} （ x ， t ） < f_{j} （ y ， t ） ，

则称在t环境中xPareto支配y，记作x <y.

PS（t）: 对于一个解x，· · ·，当前问题所有Pareto解的集合为 pareto solutions（PS），在t 环境下的 PS记为 PS（t）.

PF（t）: PS在目标空间中组成了最优前沿（pareto front，PF），在t环境下的最优前沿记为PF（t）.

约束违反度C（x，t）: 一个解在t环境下的约束违反度可按式（2）计算，其中ε是约束松弛度，使等式约束条件被适当放宽.

\begin{matrix} C (x, t) = \sum_{i = 1}^{n_{g}} m a x \{g_{i} (x, t), 0\} + \\ \sum_{j = 1}^{n_{h}} m a x \{|h_{i} (x, t)| - ε, 0\} . \end{matrix}

(2)

可行区域: 约束违反度为0的解所构成的区域.

UPF（t）和CPF（t）: 对于不考虑约束的最优前沿记为UPF，符合约束条件的最优前沿记为CPF，在t环境下的UPF记为UPF（t），t环境下的CPF记为CPF（t）.

边界解BS（t）: δ是一个较小的正实数，当一个不可行解x的约束违反度小于参数δ，即0 <C（x，t）<δ则认为该解非常接近可行区域的边界，称之为边界解（boundary solution），在t环境中的边界解记为BS（t）.

3 复合预测进化算法

为了在有限的资源下搜索到动态多目标优化问题的最优解集，提出了一种基于复合预测策略的动态多目标优化算法（dynamic multi-objective evolutionary algorithm based on composite predict，DMOEA/CP），下面将依次描述算法流程和复合预测策略.

3.1 复合预测进化算法流程

算法1（见表1）描述了所提算法的执行流程，种群多样性在求解动态多目标问题时至关重要，为在优化过程中保持良好的多样性，将目标空间均匀分割成多个子空间，与进化种群population的各个子种群一一对应，充分搜索整个空间.

目标函数和约束条件的动态变化使得追踪最优解集较为困难，问题的动态性要求算法快速检测到变化，迅速接近新的最优解集，同时能使种群始终保持良好的多样性来搜索未知环境下的可行解.

表1算法1: 基于复合预测策略的动态多目标优化算法

Table1Algorithm 1: Dynamic multi-objective evolutionary agorithm based on composite predict

为避免进化种群聚集在非最优的可行区域，定义了一个规模较小的辅助种群（auxiliary population，AP），用于搜索UPF，进化种群population与辅助种群AP 之间的交流机制引入了多样性，搜索更广泛的空间.

对算法而言环境的变化是未知的，因此，算法需要通过环境变化检测机制检测问题的动态性. DMOEA/CP检测种群中5%的个体约束违反度和目标函数值是否变化，若未变化则应用MOEA/D-M2M的框架迭代优化种群，若有变化则认为环境t产生了变化，为了使种群迅速适应新环境，将应用第3.2节复合预测策略，识别变化类型并预测最优解集的位置.

3.2 复合预测策略

动态约束多目标问题变化的时间间隔短，所以需要通过有效的预测技术快速追踪随环境t在空间中变化的最优解集. 本节提出的复合预测策略将判断变化类型，并使用对应预测策略. 复合预测策略由3个预测器组成，分别为第3.2.1节的简单预测器、第3.2.2节的集成预测器和一个堆叠降噪自动编码器（stacked denoise autoencoder，SDA）^[20] .

SDA预测器是一个具有2个隐层的自动编码器，主要用于处理目标函数的变化，SDA从t − 2环境的最优解集和t − 1环境的最优解集之间学得一个非线性映射，并将映射应用于t − 1环境的最优解集来预测t环境下的最优解集. 若UPF在多个连续环境下都远离可行区域，则CPF更大程度上由可行区域边界决定的，SDA难以从CPF中学得变化规律. 为鉴别这种情况，利用算法1中定义的辅助种群AP来判断是否需要使用SDA预测器，以及预测对象是UPF还是CPF. 而另两个预测器负责处理约束变化，预测边界解.

约束条件的变化可以直观地体现为决策空间中可行区域的变化，为了应对不同程度的约束变化，令检测到变化后的新环境为t，使用如下判定规则: 若

\exists x \in

population

（ t - 1 ） ， C^{t - 1} （ x ） ⩽ 0 \land C^{t} ⩽ 0 ，

即原环境下的可行解在新环境下至少有一个解可行，则认为约束条件变化较小; 否则认为约束条件变化幅度较大.

算法2（见表2）描述了复合预测技术的执行过程，其中简单预测器和集成预测器分别适用于约束变化较小和较大的情况，由算法3（见表3）和算法4（见表4）描述. 当检测到约束条件变化较小，若符合SDA的两种可预测情况，则采用SDA预测器，否则，使用简单生引导种群接近可行区域; 若约束条件发生大幅变化，那么，没有充分理由认为t − 1环境的可行解在t环境下也是可行解，因此，使用2个约束预测器来应对.

3.2.1 简单预测器

约束条件的变化可视作决策空间中可行区域及其边界的变化. 针对这一特性，文章提出一种简单预测器，通过环境变化后的可行解与不可行解来构造向量，指向可行区域，以快速预测可行区域边界的位置.

为了实现通过向量指向可行区域变化方向这一思想，需要将种群中的解分类来构建简单预测器. 令当前环境记为t，前一环境记为t − 1，在约束条件变化后，边界解的约束违反度也会随之变化，根据环境变化前后每个解的是否为可行解将解分为4个类别: FS⁻，FS⁺，BS⁻，BS⁺，其定义可用式（3）表示，即

\{\begin{matrix} x \in {F S}^{-} (t) \Leftrightarrow C^{t - 1} (x) = 0 \land C^{t} (x) > 0 \\ x \in {F S}^{+} (t) \Leftrightarrow C^{t - 1} (x) > 0 \land C^{t} (x) = 0 \\ x \in {B S}^{-} (t) \Leftrightarrow x \in B S (t - 1) \land C^{t} (x) > C^{t - 1} (x) \\ x \in {B S}^{+} (t) \Leftrightarrow C^{t - 1} (x) > 0 \land C^{t} (x) < C^{t - 1} (x) \land \\ x \in B S (t) \end{matrix}

(3)

简单预测器（simple predictor，SP）构造规则描述如下: 从BS⁻或FS⁻中选择一个起始点x，从BS+或FS+选择一个终点x′，令d = x′− x为一个方向向量，d将代表可行区域的移动方向，再利用梯度下降法计算出满足式（4）的向量长度w，并得到一个预测解，若该预测解是新环境下的边界解，则认为该预测器构造成功，预测器的计数器加1，将方向向量d和长度w作为SP的属性组保留下来.

\{\begin{matrix} 0 < C (x + w \times d) ⩽ δ, \\ s o l u t i o n = x + w \times d . \end{matrix}

(4)

表2算法2: 复合预测策略

Table2Algorithm 2: Composite predictive strategy

根据起点和终点的选择，预测器相对应地分为 4 类，SPs_i表示第i类简单预测器的集合，不同类的预测器的区别在于: 1）SPs₁为起点取自BS⁻（t），终点取自 BS⁺（t）; 2）SPs₂ 为起点取自BS⁻（t），终点取自 FS⁺（t）; 3）SPs₃为起点取自 FS⁻（t），终点取自 BS⁺（t）; 4）SPs₄ 为起点取自 FS⁻（t），终点取自 FS⁺（t）.

预测器的构建过程中产生的解仅评估约束违反度，不计算目标函数值，以节省计算资源.

在使用SP时，所选取的起点需要与构建该SP时的起点类型一致. 若预测器预测失败则其计数器count减少0.5，并在之后的预测中被使用的概率降低直至淘汰. 相对应的，预测成功的预测器被使用的概率得到提高，以此获得更准确的预测结果.

3.2.2 集成预测器

约束变化大时，可行区域在新环境中远离原来的位置，但基于不同环境之间存在关联的假设，仍然可以利用历史信息来做预测工作.

此时获得可行区域整体的变化方向将更有利于种群接近可行区域，而简单预测器方向向量和长度反映了历史环境中可行区域的位移，因此，将多个同类简单预测器集成来获得可行区域的位移信息.

表3算法3: 简单预测器

Table3Algorithm 3: Simple predictor

4 实验

4.1 测试函数

研究 ^[24] 使用式（5）所表达的模型，在文献 ^[28] 的基础上增强了环境的变化幅度，按可行区域大小、不考虑约束的最优前沿的连续性和凹凸变化，设计了8个测试问题. 其中参数设置详见文献 ^[24] .

s.t. \{\begin{array}{l} \cos θ \times (f_{2} (x, t) - e) - \\ \sin θ \times f_{1} (x, t) - m (t) ⩾ \\ a \times ∣ \sin (b π \times (\sin θ^{'} \times \\ {(f_{2} (x, t) - e) + \cos θ^{'} \times f_{1} (x, t))}^{c}) |^{d}, \\ s l \times f_{1} (x, t) + f_{2} (x, t) - z (t) < 0, \\ z (t) > m (t) . \end{array}

(5)

表4算法4: 集成预测器

Table4Algorithm 4: Intergrate predictor

4.2 指标

令PF^∗表示在目标空间中从真实最优前沿上均匀采样的一组点，OPF表示算法所得最优前沿上的点.

反世代距离（ inverted generational distance，IGD）^[29] 为

I G D = \frac{\sum_{p \in {P F}^{*}} m i n d (p, O P F)}{|{P F}^{*}|},

(6)

min d（p，OPF）表示点 p 到OPF 上的最小欧氏距离，IGD可评价算法的收敛性能和分布性能，其值越小算法的收敛性和多样性越好.

超体积比例（hyper volume ratio，HVRatio）指标 ^[30] : 超体积（hyper volume，HV）^[31] 可以有效衡量收敛性和多样性，HVRatio的最大值为1，越接近1表明算法所得结果越好.

H V R a t i o = \frac{H V (O P F)}{H V ({P F}^{*})}

(7)

SP指标可以评估OPF的分布均匀情况，该值越小则OPF均匀性越好.

S P = \sqrt{\frac{\sum_{i = 1}^{| O P F |} {(D_{i} - \bar{D})}^{2}}{| O P F | - 1}},

(8)

其中: D_i是OPF中第i个点与其最近点的距离，

\bar{D}

表示所有D_i的均值.

为体现所有环境中的整体性能，实验将使用3个指标在多个环境下的均值和方差来表示一次测试结果，分别表示为平均反世代距离（mean inverted generational distance，MIGD）、MHVRatio、平均分布性（mean spacing，MSP）. 使用runtime指标记录算法的CPU运行时间，其单位为s.

4.3 参数

环境变量t = 1，2，· · ·，20，为保证对比算法的公平性，参照文献 ^[26] 的实验设置，在首次环境变化前算法运行10000次函数评估（function evaluation，FE），之后环境的变化频率为3000FE，即在一个环境中若约束评估次数与目标函数评估次数之和达到3000，则当前环境发生变化，一个规模为100的种群消耗3000FE相当于种群迭代优化15次.

决策变量为10维，所有算法的种群规模与DNSGA-II ^[10] 一致，即N=100，DMOEA/CP的其余参数经 8组参数对比实验后设置如下: 辅助种群 AP 大小为 N/5，边界解阈值 δ 设置为 2，每类预测器个数 nz = ⌊N/8⌋，梯度下降步长step=0.1.

4.4 对比算法

基于复合预测策略的动态多目标优化算法（DMOEA/CP）与动态约束多目标优化算法（dynamic NSGAII，DNSGA-II ^[10]、动态约束多目标进化算法（dynamic constrained multiobjective evolutionary algorithm，dCMOEA）^[24]、无约束多目标算法MOEA/DM2M ^[27]、静态约束多目标算法C-NSGA-II ^[32]、基于参考向量的方法（reference vector guided evolutionary algorithm，RVEA）^[33]，以及基于种群预测的动态多目标算法（population prediction strategy，PPS）^[34] 进行对比. 本文算法基于 MOEA/DM2M算法实现，其计算复杂度与该算法相同为O（MN²），M是问题的维度，N是种群规模.

4.5 实验结果

表5中拥有最佳性能的实验结果用黑色加粗表示，每个单元格内的值是30次独立运行结果的均值和方差. 括号内若为浮点数则是方差值，若为a/30则表示在该问题上30次运行有a次没有找到可行解. 在DMOEA/CP这一列的runtime指标以x : y的形式呈现，x 表示完整的DMOEA/CP运行时间， y是复合预测策略占用时间. 经Wilcoxon符号秩和检验后+，−符号表示该算法与DMOEA/CP在同一问题上的指标对比，+表示显著更优，−表示显著更差.

根据表5结果，所提出的DMOEA/CP在所有问题的MIGD和MHV Ratio指标上达到最优，表明该算法的收敛性和多样性在这组算法中最佳. dCMOEA在 7个测试问题中都拥有最佳 MSP值，其均匀性最好. RVEA运行速度最快.

在30次独立运行中，RVEA算法均未能收敛到最优前沿，CNSGAII平均在6个环境下未能找到可行解，这两个算法没有引入环境变化应对机制，说明仅依赖静态优化算法难以使种群适应快速变化的环境. PPS算法求解在所有问题上均有10个环境无可行解，这是由于种群在前几个环境下未收敛，以致算法在后续环境预测错误，误导种群进化.

DMOEA/CP是以MOEA/D-M2M为进化框架的算法，MOEA/D-M2M仅在3个测试问题的所有环境都找到了可行解，其较差性能表明该算法本身无法应对动态多目标问题，而DMOEA/CP的收敛性和多样性表现最佳，这表明复合预测策略是有效的. PPS和DMOEA/CP都需要2个历史环境的最优解集作为先验知识，但复合预测策略引入了SDA预测器来应对前2个环境的空缺，使约束预测器获得最优解集作为指导信息，并在后续环境中这两个预测器正确引导种群收敛，稳定处理动态约束多目标问题.

以DCMOP1为例观测，DMOEA/CP比其他算法消耗更多CPU时间，其中复合预测策略耗时0.3 s，这意味着复合预测策略占用了20%到25%的计算时间为算法追踪最优解集的位置，而在与其它算法相同的函数评估次数下，种群收敛性和多样性具有显著提升.

图1展示了所有算法在测试问题5上的的函数评估次数与当前种群的IGD指标. IGD指标衡种群收敛性，每次环境变化后原有解在新环境下不再是最优解集，因此，种群的IGD值上升，且上升幅度越大，新环境下的种群收敛性越差. PPS在每个环境变化时曲线上升幅度最大，DCMOEA/CP在多个环境变化时IGD值变化最小，以图2环境t= 5变为t= 6（即横坐标18000FE 前后）为例，PPS 的种群在环境变化后的 IGD 值达到 30.6，而DCMOEA/CP的IGD 值仅由 0.1上升至 0.23，进一步证明复合预测策略的优越性.

图1测试问题1各算法IGD值变化

Fig.1IGD value changes of each algorithm on test Problem 1

图2以问题1为例，展示了DMOEA/CP与其它算法在各环境中所获得的Pareto解集，其中黑色实线部分表示真实Pareto前沿，DMOEA/CP所获得解用红色空心圆表示，在展示的4个环境中，DMOEA/CP解集最接近真实前沿面，且均匀分布在前沿面上. PPS算法仅在1个环境下获得未收敛到 Pareto 前沿的解集，说明 PPS追踪可行区域的能力较差. CNSGAII仅在第19个环境下收敛到部分Pareto前沿，其多样性缺失说明在当前环境陷入了局部最优. MOEA/D-M2M在3个环境中仅有少部分收敛到前沿面，在第17个环境中无法稳定收敛. 此外DNSGA-II，dCMOEA和RVEA种群能与前沿面保持相对近的距离，但其结果都显著差于 DMOEA/CP. 可知DMOEA/CP的解集更具竞争力，在多个环境下其解集更逼近真实Pareto前沿，且解集分布范围更广，这印证了在面对这类Pareto前沿凹凸性和连续性动态变化、约束区域同时变化的问题时，复合预测策略的有效性，能快速跟踪随环境变化的最优解集.

表5模糊控制规则

Table5Fuzzy control rules

图2问题1各算法最终优化解集

Fig.2The final optimum solution sets in Problem 1

5 结论

在动态约束多目标问题中，目标函数和约束条件都可能发生变化，在搜索最优解时，不仅要考虑优化目标函数值，还要同时满足约束条件，而且问题会发生动态变化，需要在有限资源下快速找到每个环境的最优解集. 文献 ^[24] 提出的8个测试函数在最优前沿的连续性、凹凸性和可行区域的大小上产生动态变化，算法需要具备较强的搜索能力才能快速适应新环境.

在实验中，为保证算法对比的公平性，以3000FE 作为变化频率. 实验表明静态约束多目标算法和无约束动态多目标算法在面对动态约束多目标问题时，前者的种群不能快速适应新环境，后者无法应对复杂的约束条件变化. DMOEA/CP使用了复合预测策略，结合简单预测器、集成预测器和SDA预测器得以应对复杂的环境变化.

然而，DMOEA/CP对于DCMOP的处理仍有不足，算法所得最优解集虽然具有良好的收敛性和多样性，但解集的均匀性没有达到理想程度. 尽管预测器的构建部分节省了部分函数评估次数，但基于分解的算法框架需要对种群进行多次分配操作，增加了运行耗时. 此外，预测策略需要从历史信息中充分学习，迫于快速变化的环境，算法为预测策略所分配的计算资源十分有限，而且预测器将目标函数和约束条件的变化分开处理，对最优解的搜索难以一步到位，因此，设计一个学习能力更强的、能直接预测最优解的方法是未来的研究目标.

图1测试问题1各算法IGD值变化

Fig.1IGD value changes of each algorithm on test Problem 1

下载: 全尺寸图片

图2问题1各算法最终优化解集

Fig.2The final optimum solution sets in Problem 1

下载: 全尺寸图片

表1算法1: 基于复合预测策略的动态多目标优化算法

Table1Algorithm 1: Dynamic multi-objective evolutionary agorithm based on composite predict

下载: 全尺寸图片

表2算法2: 复合预测策略

Table2Algorithm 2: Composite predictive strategy

下载: 全尺寸图片

表3算法3: 简单预测器

Table3Algorithm 3: Simple predictor

下载: 全尺寸图片

表4算法4: 集成预测器

Table4Algorithm 4: Intergrate predictor

下载: 全尺寸图片

表5模糊控制规则

Table5Fuzzy control rules

下载: 全尺寸图片

图1测试问题1各算法IGD值变化

Fig.1IGD value changes of each algorithm on test Problem 1

图2问题1各算法最终优化解集

Fig.2The final optimum solution sets in Problem 1

表1算法1: 基于复合预测策略的动态多目标优化算法

Table1Algorithm 1: Dynamic multi-objective evolutionary agorithm based on composite predict

表2算法2: 复合预测策略

Table2Algorithm 2: Composite predictive strategy

表3算法3: 简单预测器

Table3Algorithm 3: Simple predictor

表4算法4: 集成预测器

Table4Algorithm 4: Intergrate predictor

表5模糊控制规则

Table5Fuzzy control rules

图(2) / 表(5)

引用本文

郭知业, 魏静萱. 解决动态约束多目标问题的复合预测进化算法. 控制理论与应用, 2025, 42(2): 335 – 343

复制

GUO Zhiye, WEI Jingxuan. Composite predictive evolutionary algorithm for dynamic constrained multiobjective problems. Control Theory & Applications, 2025, 42(2): 335 – 343

Copy

计量

图1测试问题1各算法IGD值变化

Fig.1IGD value changes of each algorithm on test Problem 1

图2问题1各算法最终优化解集

Fig.2The final optimum solution sets in Problem 1

表1算法1: 基于复合预测策略的动态多目标优化算法

Table1Algorithm 1: Dynamic multi-objective evolutionary agorithm based on composite predict

表2算法2: 复合预测策略

Table2Algorithm 2: Composite predictive strategy

表3算法3: 简单预测器

Table3Algorithm 3: Simple predictor

表4算法4: 集成预测器

Table4Algorithm 4: Intergrate predictor

表5模糊控制规则

Table5Fuzzy control rules

EATON J, YANG S X, GONGORA M. Ant colony optimization for simulated dynamic multi-objective railway junction rescheduling. IEEE Transactions on Intelligenct Transportation Systems,2017,18(11):2980-2992.

SAXENA D K, RAY T, DEB K,et al. Constrained many-objective optimization: A way forward. IEEE Congress on Evolutionary Computation. Trondheim, Norway: IEEE,2009:545-552.

SAUL Z M, ALFREDO A M, CARLOS A C C. Constrained multiobjective aerodynamic shape optimization via swarm intelligence. Proceedings of 16th Genetic and Evolutionary Computation Conference. Vancouver, Canada: ACMSIGE,2014:81-88.

LIU Ruochen, LI Jianxia, LIU Jing,et al. A survey on dynamic multiobjective optimization. Chinese Journal of Computers,2020,43(7):1246-1278.(刘若辰, 李建霞, 刘静, 等. 动态多目标优化研究综述. 计算机学报,2020,43(7):1246-1278.)

DEB K, PRATAP A, AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

KENEDY J, EBERHART R. Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks. Perth, WA, Australia: IEEE,1995:1942-1948.

ZHANG Q, HUI L. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation,2008,11(6):712-731.

MURUGANANTHAM A, TAN K C, VADAKKEPAT P. Evolutionary dynamic multiobjective optimization via Kalman filter prediction. IEEE Transactions on Cybernetics,2016,46(12):2862-2873.

JIANG M, WANG Z Z, GUO S H,et al. Individual-based transfer learning for dynamic multiobjective optimization. IEEE Transactions on Cybernetics,2021,51(10):4968-4981.

DEB K, RAO U, KARTHIK S. Dynamic multi-objective optimization and decision making using modified NSGA-II: A case study on hydro-thermal power scheduling. Proceedings of the 4th International Conference on Evolutionary Multi-criterion Optimization. Berlin, Heidelberg: Springer,2007:803-817.

GREEFF M, ENGELBRECHT A P. Solving dynamic multi-objective problems with vector evaluated particle swarm optimisation. IEEE Congress on Evolutionary Computation(IEEE World Congress on Computational Intelligence). Hong Kong, China: IEEE,2008:2917-2924.

LIU R C, LI J X, FAN J,et al, A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multiobjective optimization. European Journal of Operational Research,2017,261(3):1028-1051.

SAHMOUD S, TOPCUOGLU H R. Sensor-based change detection schemes for dynamic multi-objective optimization problems. Proceedings of the IEEE Symposium Series on Computational Intelligence. Athens, Greece: IEEE,2016:1-8.

WANG Y, LI B. Investigation of memory-based multiobjective evolutionay algorithm in dynamic environment. IEEE Congress on Evolutionary Computation. Trondheim, Norway: IEEE,2009:630-637.

SAHMOUD S, TOPCUOGLU H R. A memory-based NSGA-II algorithm for dynamic multi-objective optimization problems. Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag,2016.

ZHOU A, JIN Y, ZHANG Q. A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics,2013,44(1):40-53.

JIANG M, WANG Z, HONG H,et al. Knee point-based imbalanced transfer learning for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation,2020,25(1):117-129.

JIANG M, HUANG Z, QIU L,et al. Transfer learning-based dynamic multiobjective optimization algorithms. IEEE Transactions on Evolutionary Computation,2017,22(4):501-514.

LIU Z, WANG H. Improved population prediction strategy for dynamic multi-objective optimization algorithms using transfer learning. IEEE Congress on Evolutionary Computation. Kraków, Poland: IEEE,2021:103-110.

ZHAO Q, YAN B, SHI Y,et al. Evolutionary dynamic multiobjective optimization via learning from historical search process. IEEE Transactions on Cybernetics,2021,52(7):6119-6130.

CHEN M, XU Z, WEINBERGER K Q,et al. Marginalized denoising autoencoders for domain adaptation. Proceedings of the 29th International Coference on International Conference on Machine Learning. Madison, WI, USA: Omnipress,2012:1627-1634.

FENG L, ZHOU W, LIU W,et al. Solving dynamic multiobjective problem via autoencoding evolutionary search. IEEE Transactions on Cybernetics,2022,52(5):2649-2662.

FENG L, ONG Y S, JIANG S,et al. Autoencoding evolutionary search with learning across heterogeneous problems. IEEE Transactions on Evolutionary Computation,2017,21(5):760-772.

CHEN Q, DING J, YANG S,et al. A novel evolutionary algorithm for dynamic constrained multiobjective optimization problems. IEEE Transactions on Evolutionary Computation,2020,24(4):792-806.

BU C, LUO W, YUE L. Continuous dynamic constrained optimization with ensemble of locating and tracking feasible regions strategies. IEEE Transactions on Evolutionary Computation,2017,21(1):14-33.

AZZOUZ R, BECHIKH S, SAID L B,et al. Handling time-varying constraints and objectives in dynamic evolutionary multi-objective optimization. Swarm and Evolutionary Computation.2018,39:222-248.

LIU H, GU F, ZHANG Q. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Transactions on Evolutionary Computation,2014,18(3):450-455.

AZZOUZ R, BECHIKH S, SAID L B. Multi-objective optimization with dynamic constraints and objectives: New challenges for evolutionary algorithms. Genetic and Evolutionary Computation Conference. New York, USA: Association for Computing Machinery,2015:615-622.

CARLOS A C C, CORTES N C. Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines,2005,6(2):163-190.

LAMONT G, VELDHUIZEN D V. Multi-objective Evolutionary Algorithms: Classification, Analyses,and New Innovations. Graduate School of Engineering Air University: ProQuest Dissertations and Theses,1999.

ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

WOLDESENBET Y G, YEN G G, TESSEMA B G. Constraint handling in multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation,2009,13(3):514-525.

ZHOU A M, JIN Y C, ZHANG Q G. A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics,2014,44(1):40-53.

CHENG R, JIN Y C, OLHOFER M. A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.