基于差分进化模型的动态多目标优化
文章目录
摘要
本文提出一种新的预测模型同基于分解的多目标进化算法结合起来用以解决多目标动态优化问题。在该模型中，随时间变化的近似pareto最优解(POS)的运动将由质心的运动表示，其他解假定同质心具有相同的运动。使用最近的质心位置的历史记录来建立差分模型，以便在检测到环境变化时估算质心的后续运动，利用其他解的当前位置和估计的质心运动估计他们的最新位置。预测解和一些保留解一起构成一个新种群用以探索新环境，有望分别找到新的POS和/或新的POF。通过20个具有不同动态特性的基准问题，将提出的算法与四种最新的动态多目标进化算法进行了比较。 实验研究表明，该算法是有效的。在处理动态问题方面明显胜过其他参与比较的算法。
Introduction引言
本文中只着眼于解决以下表述形式的DMOPs
minF(x,t)=(f1(x,t),f2(x,t),⋯,fm(x,t))Tsubjecttox∈Ω(1)
m是目标的个数，n为决策变量的个数，x=(x1,x2,⋯,xn)T表示的是决策变量向量，Ω代表决策空间。目标向量F(x,t)由m个随时间变化的目标函数组成。
EDMO的研究涉及测试问题和性能指标的构建，算法的开发以及在现实世界中的应用问题等多个方面。其中开发算法是主流，许多用于EDMO的算法都是从最先用来解决静态多目标优化问题的MOEAs(多目标进化算法）衍生而来，比如NSGA-II，MOEA/D，RE-MEDA和COEA。为了将之应用在动态环境中，首先得对这些MOEAs进行两方面的修改：（1）提高收敛速度（2)检测到环境变化后引入更多差异性个体。动态多目标进化算法任务的一个表述是在每次环境变化之前估算POS和POF，从而能够尽可能密切的追踪到变化的POF或POS。这就要求该算法在静态环境中收敛速度快，这对于在动态环境中的追踪能力也至关重要。
最近的文献中大多数动态MOEA通过以下策略来增加个体的多样性：随机重新初始化，参数调整，基于记忆的重新初始化或基于预测的重新初始化。一般来说基于预测的策略和基于记忆的策略是绑在一块儿的，因为预测模型都要基于种群的历史信息。在许多现实世界的DMOP表述中，问题的目标函数根据一些常规规则变化，而不是在两个连续环境之间随机变化。且很多情况下，问题变化很平缓，但大多数情形都是变化比较迅速。因此人们越来越常用预测策略产生预测解并入到重新初始化的种群中，用来估计新的POF和/或POS。
目前许多MOEA使用了预测策略，但哪种预测模型更适合预测个体的新位置，建立预测模型需要复用多少历史个体，以及当前种群中多少个体被预测个体替代。此外，目前提出的动态MOEA中提议的预测模型似乎很少——最常用的是线性预测模型和自回归模型。为此我们有必要提出更简单有效的预测模型。
MOEA/D自提出以来就被广泛关注和应用，主要是因为它主张把一个多目标优化问题通过聚合函数分解成多个单目标优化子问题，并同时优化他们。本文提出的预测策略也与之相结合。先前环境下通过MOEA/D得到的一些解用于构建预测模型。此外在提出的动态动机中，通过质心的想法提出预测模型，一系列解的质心用于通过检测到环境变化时启用的差分模型来估计其后续运动，用来估计个体的运动趋势。种群中其他解假定有着质心个体相似运动轨迹。因此，它们的新位置至少可以通过其相对于质心的当前位置以及质心的估计运动趋势来近似预测。预测个体和最近的环境变化中保留下来的部分个体共同构成新种群，且探索新的环境。本文的主要贡献如下：
（1）提出的新颖的差分预测模型中，从一阶差分模型扩展到二阶差分模型，用来预测得到的解的质心的运动趋势。
（2）实施了结合MOEA/D的预测策略方案，包括预测哪些个体和以及预测多少个个体。
（3）和最新的四个动态MOEA进行比较，在一些测试问题上分析了其性能。
Background背景
EDMO的挑战
一个MOP的目标函数发生变化可能导致MOEAs出现两种新情形。其一是新环境中的近似pareto最优解可能受到较早环境中的先前解支配，从而不再是最优的。即使如果POF发生变化，实际上这些新的解是新环境中的pareto最优解。这可能会导致新环境中不恰当的丢失POS中的解，直至检测到环境变化并改变了以前的POS解的状态。其二是POS已经趋于稳定，但如果POF发生变化，突然其中部分或全部解受新找到的解支配。这种情况是环境变化的一个潜在的有用指标，意味着任何一个先前解的非支配状态仍然保留，所以应该得到重新评估。鉴于POS中的个体已经充分收敛，其支配关系可以向MOEA表明已经发生环境变化。并且要求应该尽快寻求新的POS，而不必考虑先前已知POS的支配状态。
不像之前解决动态单目标优化问题时常见的那样，种群中的个体不会完全丧失多样性，这样就意味着当前种群中的个体仍然可以产生子代并探索搜索空间，直至这些个体不再是pareto最优。 为了清楚的阐明EDMO的挑战，我们首先在FDA上做了测试，使用MOEA/d作为多目标优化算法。在FDA1中，POS变化而POF不变，对此为了初始化比较简单，我们首先假定变化的时刻是已知的，种群中所有个体都需要重新评价，参考点在下一个环境的初始更新。我们只关心当前个体是否能继续探索搜索空间，因此没有随机重新初始化的解引入至种群。图1(a)表明在变化之前的第一个时间范围内在目标空间内由MOEA/D得到的种群分布。图1(b)表示在第二个时间范围内由该算法得到的种群分布情况。很明显，在变化之前给出评价次数之后该算法并不能很好的逼近真实的POF。种群在目标空间的分布证明个体还是会保持一定程度的多样性，且接着产生不同的子代并且继续寻找新的POS。在第二时间范围的末尾，该算法获得的真实POF近似值比在第一时间范围中找到的近似值更好。这说明，个体可以根据更改之前找到的以前的解，在第二时间范围中搜索新的POS。之前的解有助于在以后的时间范围中搜索新的POS。 但是，即使第二个时间范围中的初始种群来自前一个时间范围中的先前解，该算法仍无法很好地逼近给定数量的评估中的真实POF。
上面的例子说明，对于至少某些EDMO问题，增加个体多样性对于跟踪不断变化的POS并非至关重要。相反，尽可能快速的引导个体向近似的变化POS和POF靠拢才更重要。这也是EDMO最大的挑战，此外对于间歇性变化的问题，检测变化的时刻时该算法的另一个挑战。本文我们只针对第一个挑战。
针对EDMO的预测
预测策略使用的前提是基于这样的假设，即问题的变化至少是某种规律性的，依据某种规则，而不是在连续的环境中没有模式的变化。若不在这个假设之内，那预测策略并不会比其他解决动态多目标优化问题的策略更有效。Hatzakis和Wallace提出了向前反馈预测策略，将一个自回归模型作为预测方法。周爱民等人也选择单变量的自回归模型作为预测方法。在他们的算法中，POS集被分成两部分:一个中心点和一个流形。由一系列历史中心点建立预测模型用来估计下一个时间新的中心点。Koo等人用一种基于先前历史个体的平均权重的方式来估计与预测方向和下次变化的大小。刘等人使用线性回归预测模型策略预测新时刻种群种大部分的个体，并且保留个体会被随机初重新初始化，用以增强种群多样性。吴等人提出一个基于方向的搜索策略来提高动态环境中NSGA-II的性能。在他们的算法中，用线性的向量差的概念采用中心点来估计POS的运动方向，该方向又能通过高斯扰动产生新的个体。这种思想在江和杨的所提算法中也有所体现。Muruganantham等人用卡尔曼滤波组合MOEA/D来解决DMOPs，他们设计了两种用于预测的KF变量：2-D KF和3-D KF。 2-D KF模型是受高斯噪声干扰的一阶线性模型，而3-D KF模型是受高斯噪声干扰的二阶线性模型。 两种变体都是离散的和线性的KF，它们被用来在检测到变化后预测POS的位置。
现有基于预测的策略的缺点
多数现有的基于预测的策略都有一些共同点，因为预测模型会受高斯噪声的干扰。涉及到高斯噪声的原因是存在预测误差，通常预测模型中的两个误差来源分别是：输入和输出。
（1）预测模型的输入是先前环境中近似POS的时间序列。算法未收敛前这些近似的POS可能会偏离路径，这种偏差导致输入错误。
（2）即使输入数据正确，预测模型也可能输出不准确的结果。 预测模型是通过近似POS的时间序列，因此很难估算所有类型的变化。 一般问题改变的模式不一定都复合使用预测模型的前提和假设，这样就会导致预测的位置可能会偏离下一个环境中的真实位置。
说了这么多作者表示在他们的提出的预测模型中将不再设计高斯噪声。此外也将保留更改前的近似POS，以更新种群。
Proposed algorithm算法提出
该预测模型做出以下两个假定：
（1）在一个固定的时间范围内问题保持静态。
（2）连续范围的POS集或POF会根据一些简单规则进行更改。
基于这两个假设，我们提出MOEA/D-DM，其主要步骤如下：
步骤0：初始化种群P，初始化参考点z∗;
步骤１：检测环境变化；
步骤１.１：如果环境变化，转至步骤１.２，，否则转至步骤２；
步骤１.２：预测所选个体的下一个位置，并且更新种群；
步骤１.３：重新评价新种群，更新参考点z∗；
步骤２：执行复制操作，在这个环境中更新种群；
步骤3：如果满足停止的条件则算法停止，否则转至步骤1；
MOEA/D-DM的主要步骤是基于MOEA/D-DE，该算法使用差分进化（DE）运算符和多项式变异算子来产生新的解。在MOEA / D-DE的基础上，添加了步骤1，即检查环境变化，如果发现环境变化，则预测POS的新位置，并更新新的种群。本文将笔墨重点渲染在步骤1.2和1.3中，其他步骤的详细内容可以参考《Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II》一文。在现实世界实际的问题中，我们不具备判断环境变化先验知识，包括环境变化的时刻以及变化程度。有两种方式检测环境变化的时刻，第一种是在每一代对现有个体进行一次函数重评价，第二种就是对于一些被选个体的其他数据信息进行评估。尽管第一种方式容易实现，但必须基于在函数评价时没有噪声这一前提，第二种方式需要一些额外的与问题相关的参数。本文采用第一种方式检测环境变化，且在每一代的初期进行。如果每一维目标上的平均适应度值变化了我们就认为是环境发生了改变。接下来的篇幅是关于如何预测新的POS和检测到环境变化后如何更新新的种群。
3.1 MOEA/D
基于分解的MOEA 把任何一个时刻的问题分成N个单目标优化子问题。本文选取切比雪夫方法作为分解方法λ1,λ2,⋯,λN是均匀分布的一组权重向量，待优化的问题可以分解成N个标量优化子问题，第j个子问题可以描述成：
minimizeg(x∣λj,z∗)=1≤i≤mmax∣fi(x)−z∗∣subjecttox∈Ω(2)
其中z∗=(z1∗,z2∗,⋯,zm∗)T是参考点，而zi∗=min{fi(x),x∈Ω}(针对最小化问题)，MOEA/D能在单次运行中同时优化N个子问题。权重向量λj的邻居定义为在权重向量 集合$ {\lambda1,\lambda2,\cdots,\lambdaN}$中距离它本省最近的几个权重向量。第j个子问题的邻域包含所有权重$\lambdaj$的邻域的权重向量。
3.2 基于差分模型的预测
差分模型是建立在由好几个先前的时间窗口（也叫做环境）下所得的 一连串POS的基础之上。我们假定这一连串的POS符号化成PT−K+1,⋯,PT，下一个环境中的POS可以用如下函数表示出来：
PT+1=fun(PT−K+1,⋯,PT,t)
其中K是之前环境的个数。假设每一个POS集包含N个解，则xit代表在Pt里的第i个解。而在MOEA/D中，由一个特定的权重向量决定的子问题都有一个相关的解，这就意味着xit代表在第t次环境中第i个子问题的解，因此xiT−K+1,⋯,xit是一系列解，描述了第i个子问题中的解随时间的运动。假定N个解都有着相似的动态特征，而且预测模型的目的仅仅是为了进化算法提供初始种群，因而一个通用的预测模型足够描述这些解的运动了。
尽管下一个环境中新的解能够通过之前的解预测到，但怎么保证历史解的准确性是关键。在2.3部分提及过预测误差的存在，另外，在一系列评估期间获得的每个解可能会以不同的方式在环境中偏离其轨迹。因此不准确的历史解将导致预测结果偏离真实值很远。为了减少这种误差，将种群质心运用到描述随时间变化的解的运动中来。假设种群中每个个体的运动趋势都和质心的一样，然而自然情况下不这样，然而考虑到预测出的新位置只是作为下次搜索过程中的起始点，像下面描述的这样的预测误差也就可以接受了。
Ct=∣PT∣1x∈PT∑X(4)
∣PT∣是PT的基数（种群的解个数），x是PT中的解
图2 表明在二维空间中，不同的时间窗口（环境）下解的位置的运动。此时将如图中CT−3,CT−2,CT−1,CTZ这些质心的运动代替当前环境下种群中所有解的运动，预测模型通过几个先前的时刻（其范围可以从1到T）质心的位置来估计在T时刻末CT的运动趋势ΔXT。折衷考虑计算资源和预测准确性之后，根据先前质心的数量设计了两种关于预测趋势ΔXT的方案。
一阶差分：这时默认时变优化问题的变化是线性的，质心仍做匀速运动，
ΔX1T=CT−CT−1(5)
二阶差分：现实世界中的优化问题的变化可能是非线性或者随机的。此模型下描述质心在不同时刻下的运动是变速运动。
ΔX2T=CT−CT−1+(CT−CT−1−CT−1−CT−2)(6)
图3(a)中描述的是二维空间内一阶差分模型下预测的质心的位置。图3(b)描述的则是二阶差分模型下预测的质心位置。图中两个较简短的向量v1,v2分别是上述定义(5)(6)中前后两个向量差CT−CT−1,CT−1−CT−2的表示，离散时间内二阶差分模型考虑质心做匀速运动。
在时间窗口T +1时，PT中其他个体的潜在位置可以预测如下：
xiT+1=xiT+ΔXT,i=1,2⋯,N(7)
在预测新的解决方案之后，应及时更新种群，以适应新的环境。
3.3 更新种群
新种群由两种解组成：先前的旧解和预测解。 在MOEA / D中，在变化之前得到的所有解已根据与之关联的均匀分布的权重矢量自动进行了排列。我们使用参数q（q∈[0，1]）进行控制新种群中预测解的数量。 预测模型生成q * N个解，其余的将由在环境变化之前的保留解组成。
图4 是环境变化之后新种群分布的 一个例子，每个子问题的邻域是由旧的解和预测解组成的。新旧解最终协作使得能够相对快速的追踪到新的POS和POF。如果特定邻域仅包含旧解，那么至少在短期内，该预测将失去对该邻域的影响。
算法1中给出了更新种群的过程。在此过程中，50％的种群成员（q的初始值）接受预测的解，并将它们分配为其他成员（即旧的和预测的解）备用）。预测解从第三时间窗口开始工作，在第三时间窗口中，一阶差分模型用于估计第三时间窗口中的新解。从第四个时间窗口开始，POS的三个前质心被使用。因此，从该点开始采用二阶差分模型，以便在以后的时间窗口中更好地预测POS的新位置。由于历史信息有限，因此无法在第二时间窗口中使用预测模型。故此时将保留所有解以在第二时间窗口中跟踪新POS，因此我们避免对POS使用随机重新初始化方法。算法2中给出了MOEA / D-DM的整个伪代码。
接下来的部分是实验设计和结果展示，在FDA1-5、dMOP1-3、ZJZ、JY测试集上与MOEA/D、MOEA/D-KF、DNGA-II-A、DDS进行比较实验，MIGD指标的均值和标准差显示这篇文章提出的MOEA/D-DM有显著优势。