动态多目标优化研究综述

作者：刘若辰 李建霞 刘静 焦李成

转载自http://cjc.ict.ac.cn/online/onlinepaper/lrc-20207694828.pdf

摘 要 现实生活中，许多优化问题都涉及到同时优化多个相互制约的目标，并且目标函数、约束条件和相关参数都可能 随时间动态变化，这样的问题称为动态多目标优化问题。由于动态多目标优化问题的最优解集存在不确定性，因此如何在环 境发生变化之后快速追踪到新环境的最优解集是解决动态多目标优化问题的难点。本文对动态多目标优化的研究进行了比较 全面的综述，具体内容包括：（1）本文介绍了动态多目标优化的相关理论背景；（2）本文介绍了动态多目标优化问题的分类 并对现有的测试函数进行归纳总结；（3）在对动态多目标优化问题的一般解决方案作简单分析的基础上本文详细讨论了动态 多目标优化算法的研究现状；（4）本文还对动态多目标优化算法的性能评价指标进行了归类介绍；（5）本文通过实验对比了 主流动态多目标优化算法的性能；（6）本文总结了动态多目标优化算法的一些实际应用案例；（7）本文分析了解决动态多目 标优化问题所面临的挑战以及存在的诸多难题。

1 引言

在工业应用和科学研究中存在许多多目标优 化问题 (multi-objective optimization problem, MOP)，这种类型的问题有多个需要优化的目标函 数，同时多个目标函数之间彼此互相制约，一个目 标函数的提升，必定会引起其它目标函数的恶化。在众多的多目标优化问题中，存在一种特殊的多目 标优化问题 --动态多目标优化问题 (dynamic multi-objective optimization problem, DMOP)，这种 优化问题不仅目标函数之间彼此相互制约，并且问 题会随着时间的变化而改变，例如目标函数，约束 或者参数可能会随着时间的变化而变化[1]。

对多目标优化问题来说，不存在一个最优解能 够同时满足优化多个目标函数，因此处理静态多目 标优化问题的目标是寻找一个由非支配解组成的 Pareto 解集 (Pareto Set, PS) [2]，而求解动态多目标 优化问题的目标是追踪随时间变化的 PS，寻找一连 串的不同时刻的 PS。

近年来，越来越多的学者开始关注动态多目标 优化问题的研究，这是因为动态多目标优化具有重 要的理论研究价值，并且动态多目标优化在现实生 活和工业生产的许多方面都具有非常广泛的应用 前景，下面简单地列举几个动态多目标优化算法的 典型应用领域。

从交通运输管理层面考虑，在一个十字路口 处，道路状况、车辆的数目、任务的优先级、突发 状况等多种因素都是随时间动态变化的，如何在综 合考虑上述因素的情况下，管理车辆运行来减少交 通拥堵并实现社会效益的最大化就是一类非常典 型的动态多目标优化问题；从节能环保层面考虑：在一个水火电力调度系统中，如何在总电力需求随 时间动态变化的过程中实现发电的总能源成本和 污染排放量最小化也是一类动态多目标优化问题；从生产调度领域考虑：在不断变化的市场需求下， 产品公司如何在生产产品的过程中实现利润的最 大化、成本的最小化以及环境污染的最小化，这就 是一个动态多目标优化问题。

动态多目标优化问题随时间不断变化的特性， 给解决动态多目标优化问题带来了很大的挑战，算 法不仅要能够追踪到最优解，还要能够快速响应环 境的变化，这些问题导致很难设计出适用于各种动 态多目标优化问题的有效算法，更不要说设计有效 的算法用来解决复杂的实际动态多目标优化问题。

因此，动态多目标优化的研究需要投入更多的精力 来探索动态多目标优化问题的特性，设计高效的算 法来解决各种理论问题和实际问题。本文主要介绍了动态多目标优化的相关理论 背景及动态多目标优化问题的分类、动态多目标优 化算法的研究现状以及性能评价指标、主流动态多 目标优化算法的性能对比及动态多目标优化算法 的实际应用案例，在以上内容的基础上本文总结了 求解动态多目标优化问题存在的诸多难题。

2 动态多目标优化的相关理论背景

3 动态多目标优化问题的分类

Farina[3]提出，根据 PS 和 PF 动态变化的不同 组合，DMOPs 主要分为以下四类：

 Type I：PSt 改变， PFt 保持不变；

 Type II：PSt 和 PFt 都改变；

 Type III：PSt 保持不变， PFt 改变；

 Type IV：PSt 和 PFt 都保持不变。

目前，很多学者已经提出了许多不同的动态多 目标优化问题，下面我们将对现有的 DMOPs 进行简单的归纳总结，如表 1 所示。所有测试问题的具 体定义见附录 A。值得注意的是，现有的动态多目标优化算法一 般都只是解决前三种类型的 DMOPs，很少有算法 解决 PSt 和 PFt 都保持不变的问题或者四种变化类 型混合出现的 DMOPs。

4 动态多目标优化算法的研究现状

动态多目标优化问题是近 20 年来的新兴问题 之一，求解动态多目标优化问题具有很大的挑战 性，不仅要求算法能够同时优化多个目标，同时还 要求算法能够快速地响应环境的变化，快速追踪到 随时间变化的最优解。

目前，静态多目标优化已经取得了较好的研究 成果，但对于动态多目标优化问题的研究深度还不 够，高效求解动态多目标优化问题的算法还比较 少。近年来越来越多的学者加入到这一研究领域， 提出了很多 动 态 多 目 标 优 化 算 法 (Dynamic Multi-Objective optimization Algorithm, DMOOA) [18] [19] [20] [21] [22]。

4.1 环境变化检测

环境变化检测机制用来检测环境中的变化。当 前变化检测机制的研究主要集中在以下三个方面。

(1) 重新评估解。其主要思路是一部分个体进 行重新评估，如果相邻两次迭代目标函数值有差异 且超过某个阈值，则判定环境已经发生了变化。一 般常用的方法是从种群中随机选取一定比例的个 体进行重评估[1][4][12][23][24]。2016 年，Sahmoud & Topcuoglu 提 出 了 一 系 列 新 的 变 化 检 测 机 制 (Sensor-based Change Detection, SBCD)[25]，这些变 化检测方法主要分为两类：第一类是基于种群的检 测方法，该方法是在种群中选择个体，而选择的方 式有随机选择个体或从不同的非支配等级上选择 个体等；第二类是不基于种群的选择方法，在搜索 空间中随机初始化产生一些个体或者均匀产生一 些个体来检测环境变化。但这种方法对选取多少解 来进行评估尚没有定论，尤其在实际问题中如何平 衡快速检测以及计算复杂度，二者之前难以取舍。

(2) 目标函数值数据的分布估计。Richter[26]提 出的这一检测变化的方法主要思想是判断相邻两 次迭代的目标解集是否属于同一种统计分布，如果 不是就判定为环境没有发生变化。但是统计分布的 相关参数的设定还是一个值得研究的问题。

(3) 稳定状态检测方法。该方法是 2017 年杨圣 祥[27]等人提出的，主要思想是把每一代的种群中的 个体随机排序，然后逐个来重新评估其目标函数 值，如果发现有一个个体的目标函数值在相邻两次 迭代之间有差异，则判定环境发生变化，其余的个 体就无须评估。但是这种方法的时间复杂度对随机 排序的顺序有很强的依赖性。

目前，几乎所有的环境变化检测算子都只是简 单地检测出环境发生了变化，而并未明确地检测出 环境变化的类型和强度，一个优秀的环境变化检测 理应解决上面的问题来为应答机制的设计做好铺 垫，提供指导。

4.2 环境变化应答机制

当变化检测机制检测到环境中的变化时，触发 变化应答机制以适应环境的变化，及时调整搜索方 向，开始搜索新环境的 PS。当前的变化应答机制主 要有以下几类：多样性引入机制，多样性保持机制、 预测机制、记忆机制、自适应应答机制以及基于特 殊模型的应答机制。

4.2.1 多样性引入机制

在求解 DMOPs 时，由于缺乏足够的多样性， DMOOAs 可能无法找到最优解。算法可能已经收敛 到一个特定的区域，当新的环境变化发生时，算法可能无法找到新环境的 PS。因此，当环境发生变化 时，引入多样性可能是有用的。

2007 年，Deb 等人提出两种环境适应策略（随 机初始化机制和变异机制），并将其引入到非支配 排 序 遗 传 算 法 (Non-dominated Sorting Genetic Algorithm-II, NSGA-II) [28] 中 提 出 DNSGA-II (Dynamic NSGA-II)[1] 来解决 DMOPs，这两种变化 适应策略描述如下：当检测到环境发生变化后，第 一种策略是随机重新初始化一部分个体，替代当前 环 境 得 到 的 最 优 解 集 的 一 部 分 个 体 ， 称 为 DNSGA-II-A；另一种方法是对当前环境最优解集 中的一部分个体进行高斯变异，称为 DNSGA-II-B；将两种策略得到的种群作为新环境的初始种群，来 实现新环境中种群多样性的引入。作者在 FDA2 和 水火电力调度问题上测试了算法性能，实验表明对 于 DNSGA-II-A，随机产生的个体比例为 20%-70% 时算法性能相对较好，对于 DNSGA-II-B，变异个 体的比例设置为 40%-100%时算法性能相对较好。但是作者采用的测试函数比较少，上面的多样性引 入比例并不一定适用于其它的测试函数。

2008 年，Greeff & Engelbrecht 将重新初始化的 环境变化应答机制集成到向量评估多目标优化算 法 (Vector Evaluated PSO, VEPSO) [29] 中提出 Dynamic VEPSO (DVEPSO) [24]来求解 DMOPs，当 环境发生变化之后，算法重新初始化部分粒子的位 置来响应环境变化，并且算法分析了不同初始化比 例对算法性能的影响。通过在 FDA1 和 FDA4 上的 实验证明环境发生变化后初始化所有粒子的位置 时算法性能最好。但是仅根据两个测试函数的实验 得出这样的结论似乎缺乏可信度。之后，作者在 DVEPSO 的基础上做了一系列更深入的研究，探讨 了不同共享机制[30]、不同存档处理机制[31]、不同更 新机制[32]以及不同边界处理方法[33]对算法性能的 影响。

2009 年，Lechuga 基于多目标粒子群优化算法 [34] (Multiple Objective PSO, MOPSO) 提出了动态 多目标 粒子群 优化算法 (Dynamic MOPSO, DMOPSO) [35]，当环境发生变化时，算法采用两种 简单的应答机制：第一种是在每个粒子的当前位置 和历史最优位置中选择较好的作为新环境中粒子 的初始化位置，另一种是新环境中每个粒子的位置 都是重新初始化产生的。作者测试了算法在 FDA1 和 FDA2 上的性能，实验结果表明第二种方法的性能优于第一种方法的性能。作者也表明应该在更多 的测试函数上验证算法的性能。

2009 年，Goh & Tan 为了解决 DMOPs 提出了 一种竞争型--合作型协同进化多目标优化算法 (Dynamic Competitive-cooperation coevolutionary Algorithm, D-COEA)[4]，它结合了自然界中的竞争 和合作机制，以促进协同进化中的自适应问题的分 解。每个子种群将竞争代表多目标优化问题的特定 子组成部分，而最终的获胜者将合作进化以获得更 好的解，通过这种竞争和合作的迭代过程，不同子 种群对各种子组成部分进行优化。当环境发生变化 时，启动竞争机制来决定每个子种群是否需要重新 初始化。作者通过 FDA1, DMOP1-DMOP3 这四个 测试函数验证了算法的性能，实验证明 D-COEA 在 DMOP2 上的性能不是很好。

2017 年，刘若辰等人在多粒子群协同进化算法 [36]的基础上提出一种新型的动态多粒子群协同进 化算法 (Coevolutionary Multi-swarm Particle Swarm Optimizer for Dynamic Multi-objective Optimization, CMPSODMO) [37]，结合一种简单的环境变化应答机 制--随机初始化方法来解决 DMOPs。作者验证了算 法在8个测试函数上的性能，包括DMOP1, DMOP2, FDA1, FDA3, FDA4, HE3, HE5, ZJZ，实验结果表明 算法在 FDA3, HE3 以及 HE5 上性能不好，并且算 法的时间复杂度也是一个值得改进的问题。

2018 年，Sahmoud & Topcuoglu 提出了一种基 于变化类型检测 (Type Detection, TD) 机制的动态 多 目 标 优 化 算 法 (TD-based NSGA-II, TD-NSGA-II)[25]来解决 DMOPs，类型检测机制描述 如下：根据环境变化前后非支配解的数目的差异可 以判断问题的 PS 是否发生变化。如果差异较大， 说明 PS 发生变化，变化类型是类型一和类型二， 则随机初始化 10%的个体来代替种群中的个体以 此对环境变化做出响应；如果差异较小，说明 PS 未发生变化，变化类型是类型三和类型四，响应环 境变化的方法是通过变异算子在种群中添加一个 随机扰动来响应环境变化。作者验证了算法在 7 个 测试函数上的性能，包括 FDA1, FDA4, FDA5, DMOP1, DMOP2, SJY4, SJY5, 实 验 表 明 TD-NSGA-II 的性能优于 DNSGA-II，但是作者没有 对随机初始化比例设置为 10%给出相应的证明。

多样性引入机制原理简单，易于实现，但是这 种方法只是盲目地对环境变化做出反应，有可能会 误导种群的进化。多样性引入机制的发展历程如图 2 所示。

4.2.2 多样性保持机制

多样性保持机制是相对于引入多样性机制而 言的，这种方法直接将上一时刻的最优解集作为新 时刻的初始种群。

2005 年，尚荣华等人基于克隆选择理论提出了 一种克隆选择算法 (Clonal Selection Algorithm for Dynamic Multi-objective Optimization, CSADMO)[38] 来处理 DMOPs，克隆选择和非一致性变异是该算 法的主要算子。CSADMO 直接将当前环境的 PS 作 为新环境的初始种群。作者仅测试了 CSADMO 在 FDA1 和 FDA4 上的性能，而作者也明确说明应该 用 CSADMO 来解决更多的 DMOPs,来验证算法的 性能优劣。

2006 年，曾三友等人基于正交多目标优化算法 (orthogonal multi-objective evolutionary algorithm-II, OMOEA-II)[39]，提出了一种动态正交多目标优化算 法 (Dynamic OMOEA-II, DOMOEA-II)[40]，该算法 直接采用当前环境的最优解集作为新环境的初始 种群。作者测试了 DOMOEA-II 在 FDA1-FDA3 上 的性能，但是并没有和其它的 DMOOAs 作对比， 因此算法性能的好坏程度没有一个衡量标准。

2014 年，尚荣华等人提出了一种量子免疫克隆 协 同 进 化 算 法 (Quantum Immune Clonal Co-evolutionary Algorithm, QICCA) [41] 来求解 DMOPs，在人工免疫系统基本原理的基础上，该算 法采用免疫克隆选择来解决 DMOPs。QICCA 直接 采用当前环境的最优解集作为新环境的初始种群。作者测试了算法在 FDA1-FDA5 上的性能，实验结 果表明 QICCA 总体性能较好，但是算法的收敛速 度还需要提高以使算法适合解决实际问题。

多样性保持机制的特点是它只适合解决连续 优化问题。它适合解决环境变化较小的 DMOPs， 但是当环境变化剧烈时，它的性能可能很差。

4.2.3 预测机制

在某些情况下，环境变化可能遵循某种可以预 测的模式，因此，找到这种模式的规律来预测下一 个环境变化也是一种响应环境变化的有效方式。

2006，Hatzakis & Wallace 基于排队多目标进化 算法 (Queuing Multi-Objective Optimizer, QMOO) [42]提出了 D-QMOO (Dynamic QMOO)[43]来求解 DMOPs，设计了一种前向预测机制 (Feed-forward Prediction Strategy, FPS) 来适应环境变化，该预测机制描述如下：当环境变化发生时，新环境的初始 种群主要包括三部分个体：通过自回归模型 (Auto Regression, AR) 利用历史信息预测的解，当前环境 的部分非支配解以及产生的部分新的随机解。作者 仅测试了算法在FDA1上的性能，也证明了在FDA1 上预测是有效的，但是作者也表明可以采用其它的 预测模型来解决复杂的优化问题，比如人工神经网 络，贝叶斯模型等，并且可以研究不同的预测模型 所适合的问题类型。

2007 年，周爱民等人采用基于正则模型的分布 估计算法 (A Regularity Model-based Multiobjective EDA, RM-MEDA) [44]，同时设计了新的变化应答机 制 -- 基于预测 的种群初始化方法 (Predicted Re-initialization, PRI) ， 提 出 了 RM-MEDA/PRI (PRI-based RM-MEDA)[17]来解决 DMOPs，当检测 到环境变化时，根据历史环境最优解的位置变化来 预测新环境中个体的位置，并用高斯噪声干扰新种 群来避免算法陷入局部最优。作者测试了算法在 FDA1 和 ZJZ 上的性能，实验证明算法性能比较理 想。但是实验结果也表明时间窗的宽度对性能有显 著影响，时间窗越宽，算法性能越好，时间复杂度 越高，因此选择合适的时间窗宽度来平衡算法性能 和时间复杂度是一个值得研究的问题。

2010 年，Koo 等人提出了一种动态多目标进化 梯 度 搜 索 (multi-objective evolutionary gradient search, DMO-EGS)[5]来解决 DMOPs，DMO-EGS 的 创新点是设计了一种梯度预测机制，它能够根据历 史环境的信息预测下一次环境变化的方向和幅度。作者测试了算法在 FDA1, FDA3, DIMP1 以及 DIMP2 上的性能，实验证明当环境变化较快时，算 法性能不理想，并且作者也提出用更好的预测模型 来预测梯度进而提高算法的性能。

2013 年，周爱民等人基于 RM-MEDA，同时设 计了一种基于种群的预测机制 (Population Prediction Strategy, PPS) 来响应环境变化，提出了 PPS-RM-MEDA (PPS-based RM-MEDA)[12]来求解 DMOPs, PPS 描述如下：种群被分为中心点和流形， 历史时刻的几个中心点可以预测产生新时刻的中 心点，而历史时刻的流形可以用来预测产生新时刻 的流形，利用预测得到的中心点和流形可以产生新 时刻的初始种群。作者在 FDA1, FDA4, DMOP1, DMOP2 以及新提出的四种测试函数 ZF5-ZF8 上测 试了算法性能，实验证明 PPS 优于 FPS 以及随机初 始化方法，但是由于前期历史信息积累不足，因此 PPS 前期性能很不好，作者建议结合其他的应答机 制组成混合机制来响应环境的变化。

2014 年，刘若辰等人提出了一种非支配排序协 同 进 化 多 目 标 算 法 (Non-dominated Sorting Cooperative Coevolution Dynamic Multi-objective Optimization based on a Predictive Model, PNSCCDMO) [45] 来解决 DMOPs，当环境发生变化 时，算法采用线性回归模型作为环境变化适应机 制，用前两个时刻的最优解集预测产生新时刻的初 始种群。作者验证了算法在 DMOP1, DMOP1 以及 FDA1-FDA4 上的性能，性能相对比较理想，但是 该算法采用的预测机制与 PRI 相同，因此选择多少 个历史环境的信息来预测新环境的初始种群是一 个值得考虑的问题。

2015 年，郑金华等人在 RM-MEDA 中引入了 基于引 导个体的预测 策略 (Prediction Strategy based on Guide Individual, GIPS) ， 提 出 了 GIPS-RM-MEDA (GIPS-based RM-MEDA)[46]来解 决 DMOPs，该预测机制通过种群中心点的位置变 化预测最优解所在的方向，进而产生新环境的初始 种群。作者通过大量的测试函数验证了算法性能， 包括 FDA1-FDA4, DMOP1-DMOP3, ZF5-ZF9，实验 结果表明 GIPS 性能优于 PPS，但是需要指出的是前期的环境变化中收集的信息可能存在误差，导致 算法在某几次环境变化上的预测不准确。

2015 年，武燕等人设计了两种定向搜索策略 (Directed Search Strategy, DSS)，DSS1 被用作环境 变化应答机制，DSS2 是一种局部搜索机制用来加 速算法收敛，将 DSS 与基于差分进化 (Differential Evolutionary, DE) 的 NSGA-II[28] 结合提出 NSGA-II/DE+DSS (DSS-based NSGA-II with DE)[23] 来求解 DMOPs，当环境发生变化时，DSS1 通过在 前两个历史环境的最优解集的中心点的移动方向 上生成期望个体，来预测产生新环境初始种群；DSS2 通过在连续两次迭代之间最优解集的移动方 向生成期望个体来加速种群收敛。作者测试了算法 在 FDA1, FDA4, DMOP1, DMOP2 以及 ZF5-ZF10 上的性能，实验结果证明DSS性能优于FPS和PPS。值得注意的是，如果环境变化很剧烈，则新问题与 先前问题不太相关，DSS 可能效果不好。

2015 年，刘若辰等人结合改进的分解进化多目 标优化算法 (multi-objective evolutionary algorithm based on decomposition, MOEA/D) [47] 和正交预测 (Orthogonal Predictive, OP)模型提出 OPMOEA/D (OP-based MOEA/D)[48]来求解 DMOPs，当环境发生 变化时，算法基于正交设计方法的预测模型从前两 个时刻的最优解集中得到代表性的组合集，然后再 从组合集中选择出有利于种群进化的个体作为新 时刻初始种群的一部分个体。作者测试了算法在 DMOP1, DMOP2, FDA1 以及 FDA3-FDA5 上的性 能，结果表明算法在 DMOP1 和 DMOP2 上性能不 佳。

2015 年，刘若辰等人在基于非支配邻居选择的 多目标免疫算法 (Nondominated Neighbor Immune Algorithm, NNIA)[49] 的基础上设计了一种自适应 差分交叉算子 (Adaptive Differential Evolution)，并 且结合一种改进的预测模型 (Predictive Model) 提 出 PDNNIA[50] (Predictive Model and Adaptive Differential Evolution based Dynamic NNIA) 来解决 DMOPs，当环境发生变化时，算法利用前两个时刻 的最优解集来预测产生新环境的初始种群。作者测 试 了 算 法 在 DMOP1, DMOP2, FDA1 以 及 FDA3-FDA5 上的性能，结果表明 PDNNIA 不适合 解决 PS 保持不变，PF 随时间变化的两目标问题以 及 PS 随时间变化，PF 保持不变的三目标问题。

2015 年，刘若辰等人基于 NNIA，提出基于预 测策略的动态多目标免疫优化算法 (Prediction Strategy-based Dynamic Multiobjective Immune Optimization, PSDMIO)[51]，当环境发生变化时，算 法利用前几个环境下的最优 Pareto 解集来预测产生 新环境的初始种群。通过在DMOP1, DMOP2, FDA1 以及FDA4测试函数上的实证研究证明PSDMIO 不 适合解决 PS 不随时间变化而 PF 随时间变化的 DMOPs。

2016 年，Muruganantham 等人在 MOEA/D-DE (MOEA/D based on DE)[52]中引入基于卡尔曼滤波 (Kalman Filter, KF)[53] 的 预 测 机 制 ， 提 出 MOEA/D-KF (MOEA/D based on KF)[54]来求解 DMOPs，当环境发生变化时，算法采用一种评分机 制来决定采用基于 KF 的预测机制还是采用随机初 始化方法。作者使用 13 个测试函数 (DMOP1, DMOP2, FDA1-FDA5, ZF5-ZF10) 测试了算法的性 能，结果表明 MOEA/D-KF 在 DMOP1, ZF7 以及 ZF9 上性能不理想，仍需要采取一些措施来改进算 法的性能，比如局部搜索策略、多样性维护策略、 方向引导搜索机制等。

2017 年，邹娟等人在 RM-MEDA 的基础上， 设计了基于中心点和拐点的预测机制 (Prediction Strategy based on Center Points and Knee Points, CKPS) 来响应环境变化，提出了新的动态多目标优 化 算 法 CKPS/RM-MEDA (CKPS-based RM-MEDA)[55]来解决 DMOPs，该预测机制描述如 下：(1) 通过前两个环境的非支配解集的中心点变 化来预测新环境的非支配解集的位置；(2) 该预测 机制选择拐点作为每个环境的历史信息，然后用 AR 自回归模型预测新环境的拐点；(3) 根据问题的 复杂程度，随机产生一部分个体来增加种群的多样 性；将上面三部分个体合成一个种群作为新环境的 初始种群。作者测试了算法在 DMOP1-DMOP3, FDA1-FDA4 以及 ZF5-ZF10 上的性能，结果表明 CKPS 在部分测试函数上性能不如 PPS。作者也表 明如何更好地分割拐点，更好地跟踪 PF，从而更 好的体现拐点的优势，是未来研究的另一项重要工 作。

2017 年，丁进良等人在 NAGA-II[28]中引入新 的预测机制，提出了基于参考点预测的动态多目标 优化算法 (Prediction Strategy for Dynamic Multi-objective Optimization Algorithm based on Reference Point, PDMOP)[56]来解决 DMOPs，该预测 机制描述如下：对关联到相同参考点的个体建立时 间序列，并对这些时间序列通过线性回归模型预测产生新环境下的初始种群从而实现对环境变化做 出响应。作者通过 4 个测试函数 FDA1, FDA3-FDA5 验证了算法的性能，PDMOP 能够较好地适应不同 环境的动态变化。但是实验采取的测试样例不充 分，应该在更复杂的测试函数上验证算法的性能。

2017 年杨圣祥等人提出了一种新型的稳态泛 化 动 态 多 目 标 优 化 算 法 (Steady-state and Generational Evolutionary Algorithm, SGEA) [27]来求 解 DMOPs，其以稳态方式检测环境变化并响应环 境变化，当检测到环境变化时，新环境初始化种群 包括两部分：一部分个体是当前环境中分布较好的 个体，另一部分个体通过最优解的移动方向和移动 步长来预测产生。作者在 FDA 系列和 DMOP 系列 问题上测试了算法的性能，结果表明 SGEA 能够有 效地跟踪随时间变化的 PF，但如果问题的变量之 间联系比较紧密或者环境的变化导致了显著的多 样性损失时，SGEA 的性能可能不是很理想。

2017 年，郑金华等人在 RM-MEDA 中引入了 一种混合多样性保持机制 (Diversity Maintenance Strategy, DMS) ，提出 了 DMS-RM-MEDA (DMS-based RM-MEDA)[57]来解决 DMOPs，该预测 机制描述如下：首先基于中心点的移动方向，预测 产生接近下一个 PF 的一些个体，其次采用逐步搜 索的方法在决策空间中生成一些分布均匀的个体， 最后在下一个可能的PS区域内随机产生一些个体， 将上面产生的个体合并到一个种群中通过非支配 排序产生新环境的初始种群。作者通过大量的测试 函数测试了算法的性能， 包 括 FDA-FDA4, DMOP1-DMMOP3, ZF5-ZF9 ， 实 验 结 果 表 明 DMS-RM-MEDA 在大多数测试问题上表现良好， 除了 FDA2。同时作者也提出使用机器学习中其它 预测方法来预测新环境的 PS 是一个值得研究的方 向。

2018 年，巩敦卫等人设计了一种多方向预测机 制 (Multi-directional Prediction, MDP) 结合粒子群 优化算法提出 MDP-PSO (MDP-based PSO) [58]来解 决 DMOPs，MDP 利用时间序列模型预测代表性个 体的多个进化方向，为种群的进化提供指导。作者 测试了算法在 FDA1-FDA5, JY5, ZF8 上的性能，结 果表明在处理复杂 DMOPs 时，MDP-PSO 得到的解 的多样性不好。

2018 年，陈得宝、邹峰[59]等人提出了一种基于 模 糊 推 理 和 一 步 预 测 的 混 合 种 群 预 测 策 略 (Population Prediction Strategy based on Fuzzy Inference and One-step Prediction, FIOPPS) 来响应 环境变化，同时提出 MOTLBO/D (Multi-objective Teaching Learning-based Optimization with Decomposition)，主要思路是将多目标分解机制引 入到基 于 教 学 的 优 化 算 法 (TeachingLearning-based Optimization Algorithm TLBO) 中来 保 持 种 群 多 样 性 。

通 过 在 FDA1-FDA3, DMOP1-DMOP3 以及 ZF5-ZF9 上的数值实验，作 者发现 FIOPPS 并不能实现在所有的测试函数上都 表现良好。并且作者指出算法设计应该考虑如何利 用较少的特征个体来预测解集的变化趋势，以减少 时间复杂度和空间复杂度。

基于预测的应答机制特点是：如果每次预测足 够可靠的，那么这种应答机制将非常有效。然而错 误的预测可能会误导进化搜索。通常，基于预测的 策略对具有周期性环境变化的 DMOPs 更有效。预测机制的发展里程碑如图 3 所示。