动态多目标优化（2019年）《Hybrid of memory and prediction strategies for dynamic multiobjective optimization》

​ 记忆和预测策略相结合的动态多目标优化策略

摘要(Abstract)

本文提出的DMOEA主要包括记忆与预测相结合的策略（HMPS)与基于分解的多目标进化算法(MOEA/D)，最终合成的算法（MOEA/D-HMPS）能够通过检测环境的变化、确定检测到的当前环境变化与历史变化的相似性，并基于此进一步确定响应策略。如果检测到的变化与以往任何一次历史变化都不相同，则基于前两个连续的种群中心的差异性预测将用于在新环境中重定位种群个体。否则，若检测到的变化与之前任何一次变化相同，则采用基于记忆的响应策略来预测种群个体的位置。两种响应机制都现有解的一部分同随机产生的解混合在一起，用于避免由于急剧或不规则变化引起的预测误差的影响。MOEA / D-HMPS已经针对14个基准问题进行了测试，并与最新的DMOEA进行了比较。 实验结果证明了MOEA / D-HMPS在解决各种DMOP方面的效率。

Introduction部分

1、老生常谈内容之一，定义动态多目标问题（DMOP，包括后文中所有DMOP的出现均为此意)的数学形式：

x=($x_1,x_2,...x_{n_t}$x1​,x2​,...xnt​​)代表$n_t$nt​维的决策变量向量，t代表离散的时间实例，$m_t$mt​t代表有多少个目标。$n_t$nt​和$m_t$mt​的值都会随时间变化。F(x,t)代表目标空间向量；p和q分别是不等式约束和等式约束的个数；其中$g_i$gi​(x,t)代表第i个不等式约束；$h_j$hj​(x,t)代表第j个等式约束。$\Omega_x\in R^{n_t}$Ωx​∈Rnt​ 代表可行的决策空间;$\Omega_t$Ωt​代表可行的时间空间;
2、老生常谈内容之二,在DMOP中支配关系、PS、PF的定义：
假设x、y都是候选解,我们定义t时刻,x支配y为：当且仅当在任意一维目标i上,都有$f_i$fi​(x,t)$\leq$≤$f_i$fi​(y,t),并且存在某一维目标j使得$f_i$fi​(x,t)<$f_t$ft​(y,t);符号化表示t时刻x支配y为$x\prec_ty$x≺t​y;如果解x^*不受任何其他解的支配，我们称之为非支配解，并且是pareto最优解，t所有pareto最优解构成的解集符号化表示为$PS_t$PSt​。

相对应的目标向量解集符号化表示为PF_t。

3、老生常谈内容之三，根据不同的PS、PF特征划分的４类DMOP：

1）PS随时间变化，PF固定；
2）PS、PF都随时间变化；
3）PS固定，PF随时间变化；
4）PS、PF都固定，但问题仍随时间变化；
通常研究的焦点聚集在1）2）3）
4、老生常谈内容之四，细数当前存在的DeMOEAs主要应用的策略和局限性：
1）基于预测的策略：专为可预测性的动态变化而设计；
2）基于记忆的策略：用于处理有周期性变化的DMOPs；
3）基于多样性的策略：当发生动态变化易导致多样性丧失时该策略有效；
5、切入正题，表明本文提出的算法所具有的独到优势:
首先分析当前许多DMOPs既具有周期性又具有预测性。因此结合记忆和预测策略用以解决具有这两类特征的动态多目标问题。许多现存的糅杂策略在并未判断该策略是否适用该变化的情况下就采用了这样相结合的响应机制，这很可能导致历史信息无法得到有效的重用。
而本文正是设计了这样一种方法来辨别是否当前环境变化和以往的历史变化相似，用以提高存储信息的重用效率。如果存在相似性，启动记忆响应机制，否则启用预测响应机制。本文设计的记忆驱动的预测策略可以用来响应相似的环境变化和加快收敛速度。并且使用这两者的优势在于能够在保持种群良好分布性的情况下还追踪到变化的PF/PS。与最新的其他动态多目标优化算法在14个基准问题上测试的效果来看，本文提出的MOEA/D-HMPS具有非常强的竞争优势。其主要优势在于：
1）一种有效检测环境变化的固定检测器方法。
2）能够处理相似和不相似变化的两种响应机制。
3）HMPS算法具有较好的鲁棒性。原因是种群一半的个体来自采用记忆-预测相结合策略后经排序的最优秀个体，另一半采用轮盘赌策略决定现有个体被重用或者被随机产生的解替代。
4）在基于分解的多目标优化算法（MOEA/D）框架内采用HMPS算法。

Related work相关工作部分

1、环境检测
1）一些专门检测个体的重新评估。
在每一代都重新评价这些检测个体用以监测各个目标值的变化。这种方式很容易实现但是要求额外的评价函数并且不适应于有噪声的环境。这种专门的探测个体包含固定的和不固定的两类。前者在决策空间随机产生并且在每一代保持不变。而后者从现有种群中随机选择并且每一代都有所变化。
2）通过检测种群数据信息来确定算法行为。
该方式通过检测种群数据信息和算法内在行为之间的差异性。这种方式不需要评价函数但是有可能造成错误的反馈，从而导致没有发生环境变化时反应过度。
2、环境响应
通过算法的表现行为将环境响应的技术分为两类：加速收敛和提高多样性。
1）加速收敛的环境响应技术：包括基于预测的方法，用以解决具有可预测性变化的DMOPs和基于记忆的方法，针对具有周期性变化的DMOPs，这两者都有利于加快收敛速度。
a）预测策略只对具有预测性的动态变化有效,可以通过学习历史的环境变化来预测新的最优解的位置，从而最优解能够快速收敛到新的PS上。
典型的有Hatzakis 和 Wallace提出的FPS（向前反馈预测策略），该算法存储了现有PF的边界点，在一个时间序列的边界点的基础上，FPS使用自回归模型预测新的边界点的位置并且追踪到新的PF。
周爱民等人提出的PPS（种群预测策略）把PS分成中心点和形状两部分。基于一系列的存储中心点，PPS采用一个单变量的自回归模型来预测下一个中心点，通过利用之前的形状(manifolds）来估计下一个形状（manifold）。
吴等人提出的DDS（方向搜索策略）用前两个时刻PS的中心点的移动方向预测新的最优解的位置。Muruganantham 等人提出了一种基于预测的策略,即采用一种线性离散时间卡尔曼滤波用来估计新环境中最优解的位置,生成的算法MOEA / D-KF显示出良好的能力，可以将个体重新定位到更接近新PS的位置，并具有非常不错的性能。
江 和杨圣祥出的稳态世代进化算法(SGEA)表明,当检测到环境变化时，SGEA能够组合现有的历史最优解和从新环境中收集的最差解，用以重定位最优解。
b)记忆策略对于具有周期性的动态变化有效,通过重用已有的最有解或者新种群中的其他最优解来获得较快的收敛性。基于记忆的策略可以显式或隐式地实现。显式的记忆策略中，当环境变化发生时，现有的最有解被重新引进到重新初始化的种群中。而隐式的记忆策略中，为了产生新环境中的个体使用了冗余表现。
比如，王等人提出了两个记忆方案，其中先前的最优解被存储在归档集中，环境发生变化时，第一个方案从归档集中随机挑选个体并引进到种群中。第二个方案也从归档集中随机挑选个体，但在他们并入新种群中之前会先用高斯局部搜索做一些调整。

​ Koo等人提出了一种新的选择性记忆技术来存储之前的归档集中的几何质心和质心方差。当环境发生变化时，选择拥挤距离较小的记忆方案来产生新环境中的个体。彭舟等人提出了能够更有效重用历史解的新的预测和记忆策略（PMS），PMS主张在每个时刻都把非支配个体存储到一个记忆池中，变化来临时，记忆池中存储的个体被重新评价后，将非支配个体选入新种群中。
​ c)除了以上呈现的预测和记忆策略，还有一些加快收敛性的策略。比如Sen等人使用逆建模方法在决策空间中生成个体，这有助于将搜索引向有希望的领域。 江等人提出了一种新的算法框架，将转移学习和传统的MOEA（Tr-DMOEA）解决DMOP。 Tr-DMOEA通过使用基于历史经验的转移学习技术来重新初始化有效种群，以促进进化过程。
​ d)提高多样性的环境响应技术
​ 某些DMOPs的动态变化会导致种群丧失多样性，这时需要引进或者保持种群的多样性。比较经典的有Deb等人提出的动态版本的非支配排遗传算法（DNSGA-II），通常会用变异的解或者随机产生的解来替代种群中的一部分个体以提高环境变化发生后种群多样性。Goh和Tan等人将竞争性和协同性组合起来提出了一种新的动态协同进化算法（dCOEA),dCOEA采用一种竞争机制将随机产生的解并入竞争池中以提高种群多样性。阮干等人提出一种有效的多样性保持策略（DMS）来提高解决动态多目标问题的MOEA的多样性。根据决策空间每一维目标的历史最大最小值的移动方向，DMS估计新环境下决策变量空间每一维目标的边界，然后在估计的区域随机产生个体。
​ 尽管这些基于多样性的策略能有效弥补环境变化发生后出现多样性丧失的情况，但过度的引进多样性有可能对种群收敛带来副作用出的DMOEA主要包括记忆与预测相结合的策略(HMPS)与基于分解的多目标进化算法(MOEA/D)，最终合成的算法（MOEA/D-HMPS）能够通过检测环境的变化、确定检测到的当前环境变化与历史变化的相似性，并基于此进一步确定响应策略。如果检测到的变化与以往任何一次历史变化都不相同，则基于前两个连续的种群中心的差异性预测将用于在新环境中重定位种群个体。否则，若检测到的变化与之前任何一次变化相同，则采用基于记忆的响应策略来预测种群个体的位置。两种响应机制都现有解的一部分同随机产生的解混合在一起，用于避免由于急剧或不规则变化引起的预测误差的影响。MOEA / D-HMPS已经针对14个基准问题进行了测试，并与最新的DMOEA进行了比较。 实验结果证明了MOEA / D-HMPS在解决各种DMOP方面的效率。
３、静态多目标优化

​ 在每两次环境变化之间，DMOP自然是静态MOP。因此，鲁棒性好的MOEA框架对于解决基础MOP也是至关重要的。常规的MOEA通常直接应用于或稍加修改用以解决DMOP，例如非支配的、排序遗传算法II（NSGA-II）、MOEA / D 和基于规则模型的多目标估计分布算法（RM-MEDA）。因为动态变化可能会降低收敛速度或导致多样性损失，所以在解决静态MOP时，主干MOEA应该能够实现快速收敛并保持良好的分布。故DMOEA中的不同组成在解决DMOP的不同方面都起作用。故本文尝试在MOEA / D框架内将内存和预测策略进行混合，以利用每个组成部分来提高DMOP的解的质量。

Proposed algorithm算法提出部分

1、MOEA/D-HMPS的整体框架

初始化种群P，归档集D存储所有探测个体在t时刻每一维目标上的均值，归档集C存储历史时刻内种群的中心，归档集D和C都初始化为空，且在进化搜索过程中由所提出的记忆策略更新。在算法１中，flag标志着当前环境变化是否与历史环境变化相似，index代表归档集D和C中相似环境所在的位置索引。$\overline{F}_{t+1}$Ft+1​记录着t+1时刻探测个体的均值。一旦检测到环境变化，MOEA/D-HMPS能够通过比较$\overline{F}_{t+1}$Ft+1​里的值和归档集D里的值来确定当前变化是否与历史变化相似。flag,index相应地被更新，算法启动环境响应机制，根据当前变化是否相似于历史变化做出不同反应，生成新种群。如果没有检测到环境变化，则采用基本的MOEA/D-DE优化t时刻的静态MOP。

1）环境检测

​ 本文采用固定的探测个体方法，这些探测个体从决策空间随机产生并且在每一代保持固定的值。假设在无噪声干扰的情况下，每一代都重新评价探测个体的目标函数值，并与之前存储的目标值比较，如果发生不匹配则说明发生了环境变化。

2）识别变化类型

​ 一般来说，如果两个时刻追踪到的PS和PF相同，那就意味着这两个动态环境是相似的，意味着下一次相似环境中可以重复利用这些最优解，因而能够提高收敛性能。

​ 算法2中，$\overline F_c$Fc​表示当前环境下探测个体的目标值，详细介绍了归档集D与$\overline F_c$Fc​比较的函数时如何实现的。$\epsilon$ϵ是预先设定的阈值，用以判定前后变化中探测个体每一维目标上的值是否差不多一样，从而最终返回位置索引index和布尔值flag。

3）记忆策略

​ 记忆池中存储非支配解或者当前种群中的最优解，并被重新用于接下来相似环境中。但这样的策略仍有局限性，一方面这些历史非支配解在环境变化之后可能不再是非支配解，另一方面这些存储起来的最优解或信息没有得到充分且有效的重新利用。因此上文提出的识别变化类型能够让存储的最优解得到更有效的重用，另外现有最优种群的中心被存储起来，成为历史最优信息。

​ 存储的历史信息很明显就是两方面：$\overline F_t$Ft​表示t时刻探测个体的目标值，用以判断当前时刻的环境变化是否同以往的历史变化相似，从而方便最优解的重用；$\overline C_t$Ct​代表t时刻种群的中心，一旦发现当前变化同以往变化相同，那么存储的种群中心就会在新环境中引导个体进化和收敛。

​ 归档集的存储与更新过程

检测到第一次变化时，将$\overline F_1$F1​和$C_1$C1​存储起来；

如果检测到第k次变化发现并未相似于之前任何一次变化，则将$\overline F_k$Fk​和$C_k$Ck​存储起来；

如果检测到第k次变化相似于之前某次变化，以第二次为例，则

用$\overline F_k$Fk​和$C_k$Ck​替代$\overline F_2$F2​和$C_2$C2​；

这种存储方式有两方面的优点：简约的存储使得归档集中不存在相似变化的信息；另外即使两次变化极为相似，记忆池中存储和记录的是最新一次变化产生的信息；而且当两个归档集大小超过预设空间时，对其应用先入先出的原则，避免额外占用资源空间；

4）环境响应

​ 针对不与任何一次历史变化相似的环境变化，采用差异性预测策略；

​ 传统的预测方式仅仅利用前后连续时刻内的中心点做文章，而为了防止环境发生的变化无规则或者比较急剧，本文所提的MOEA/D-HMPS引进了一部分现有种群的个体和随机个体来避免可能产生的预测误差；值得注意的是，第一次发生变化时，归档集D和C是空集，故此时新环境中一半的个体来自现有种群中排序最优的个体，一半的个体以随机的方式产生。

其中$x_{t+1}^k$xt+1k​,$x_{t}^k$xtk​,$x_{t-1}^k$xt−1k​分别 代表t+1、t、t-1时刻种群中心个体第k维决策变量；Gaussian（0,d）表示均值为0，标准差为d的高斯扰动，其中标准差d定义如下：

其中$\|C_t-C_{t-1}\|$∥Ct​−Ct−1​∥表示$C_t,C_{t-1}$Ct​,Ct−1​之间的欧式距离；

该预测机制用图示表示如下：

其中黑色的圆圈代表一个个体，曲线上的一系列黑色圆圈代表种群中个体的分布性，红点代表种群的中心点，黑色实心箭头代表前两个时刻的种群移动方向，也是两个中心点的向量差。蓝色虚线箭头代表预测的种群进化方向，t时刻的现有个体和种群预测的进化方向一起用以重新定位t+1时刻的最优个体。由于这种预测方法并不要求精准预测，所以加了高斯扰动增强种群的搜索开采能力。

​ 针对检测到的变化同过去某次环境变化相似的情况，响应记忆机制，即在新环境中重用之前那次变化中最优解的信息。

算法调用相似函数得到相似变化所在索引，重用那次变化的种群中心点$C_{index}$Cindex​和t时刻的种群中心点$C_t$Ct​的向量差预测种群进化方向，结合t时刻的种群个体，从而产生t+1时刻的新种群。用公式表示如下：

有关环境响应的整体算法表示如下：

首先计算t时刻种群P的中心点$C_t$Ct​，并按找适应度值对种群$P_t$Pt​进行排序，对于每一维目标都进行如下操作：如果该个体排在前1/2，则判断flag是否为真，若为真，启用预测响应机制并通过相应的公式得到新的初始化种群$P_{t+1}$Pt+1​；若flag为假，则启用记忆响应机制并通过此时的对应公式同样求得$P_{t+1}$Pt+1​。再采用轮盘赌机制，阈值设为0.5，若随机数小于0.5，则该个体来自决策空间的随机产生，否则将重用现有个体。最终用$C_t$Ct​替代$C_{t-1}$Ct−1​，将$P_{t+1}$Pt+1​作为返回值输出。

5）基本的多目标进化算法

​ 本文采用的是MOEA/D-DE，目前由于其解决连续MOPs时不仅收敛快而且能保持不错的分布性，已经被广泛用于动态多目标优化领域。MOEA / D将问题分解为多个子问题，并根据相邻关系同时优化它们。相邻关系的定义基于目标空间权重向量间的距离，每个个体的适应度值就是聚合函数，这里采用经典的切比雪夫方法作为聚合方式，因为该方案既简单，又具有很好的表现性能。

以上即为《Hybrid of memory and prediction strategies for dynamic multiobjective optimization》的摘要、Introduction及算法提出部分的展示。

这之后的10页篇幅内容就是实验设计、实验结果及讨论、总结与未来工作展望，图表居多，测试问题及评价标准在之前的阅读笔记中有记录，在此不做说明。