摘要
在高维目标空间中，高维优化算法（MaOPs）一般采用一组分布广泛的参考向量来增加到Pareto front的选择压力。然而，很少有研究如何在决策空间中在参考向量的帮助下向Pareto set （PS）方向生成新的解集。因此，我们提出一种新的基于差分进化的繁殖算子。主要思想是利用进化路径来描述种群的运动和预测它的趋势。采用这些进化路径来创造潜在的种群从而加强向PS的收敛速度。进一步地，提出一种自适应机制来适应相关参数的自动变化。该算子被用于两种进化算法框架中，其实验结果表明提出的算子能够加强原来算法的性能。
引言
多目标优化问题（MOPs）涉及多个冲突目标函数。其定义由如下公式表示：
其中为决策空间，
由M个真值目标函数组成，
为目标空间。与单目标优化不同，求解多目标的目的是找到一组均衡解，这些解在决策空间被称为Pareto set（PS），在目标空间中被称为Pareto front（PF）。在过去二十年里，大量的多目标优化算法（MOEA）被提出来求解MOP。这些MOEA在求解MOPs时与传统的方法比有其内在优势：它能够在单次运行中找到Pareto最优解集。而最著名的MOEA算法是通过支配关系对解集进行排序。当然，也需要一种清晰的分布性管理机制来维持种群的多样性。
基于分解的MOEA/D提供了一种交替方法，将MOP分解为许多单目标优化子问题。然后使用进化算法以协作方式优化每个子问题。大量研究显示，MOEA/D在求解规则PF问题时效果要比基于Pareto算法效果好。
虽然这些MOEAs在求解MOPs上非常有效，但是它们在求解目标大于3的高维优化问题MaOPs时遇到了困难。主要的挑战是随着目标维数的增加算法的选择压力退化。虽然MOEA/D最初的设计是为了求解MOPs，但是它的分解策略为设计新的高维优化算法（MaOEAs）提供了有前景的框架。一种方法是将目标空间划分为多个子区域，然后通过聚类函数在每个子区域内选择解集。采用这种方案的MaOEAs有RVEA、MOEA/D-DU等。当每个子区域包含只有一小部分解集时，选择压力将会增加，因此，能够使用传统的Pareto支配方法，例如：非支配排序，来选择解。例如：NSGAIII首先将种群分为不同的非支配层，然后从临界层中通过小生境保持算子选择解集。值得注意的是，虽然NSGAIII没有向MOEA/D那样直接分解MaOP，但是它隐含地分解目标空间，通过小生境保持算子试图保留靠近每个可能的参考点的解来维持种群的多样性。因此，NSGAIII基本上也属于分解算法。另一类算法，例如MOEA/D-M2M，MOEA/DD以及MOEA/PIE，同样有相似的特征。我们知道，以上所有的算法具有下面相同的特点：
1）一组广泛分布的参考点应用到选择算子中能够增加向PF收敛的选择压力。
2）新的解集的生成方式是采用随机方式生成的，事实上，几乎所有的MaOEAs采用的是模拟二进制交叉方法来生成新的接集。这种随机生成方法没有使用搜索方向信息。
也就是说，当在决策空间中生成新的解时，没有利用参考向量来指导向PS方向收搜过程。最近提出了一些基于R2指标的算法，如：MOMBI和MOMBI-II也是如此。自然就引起我们思考：是否有一种有效的方法在一组参考方向的帮助下往PS方向上生成新的解集？为了回答该问题，我们将面临一下几个问题：
1）参考向量组是定义在目标空间的，在决策空间中利用参考向量是非常困难的。
2）许多犯罪算子涉及一些参数，最好的设置是问题自适应。根据世界上没有免费午餐的理论，将这些参数设置为固定值是不合适的。总之，我们期望有一种自适应机制来适应这些参数自动变化。
为了设计新的繁殖算子来解决以上问题，我们首先回顾一些比较常见的繁殖算子。在进化算法中，生成新的候选解的方法可以分为基于解的方法和基于模型的方法。在基于解的方法中，解可以直接从已有的解集中根据某种特殊的规则生成。早期采用的是混合交叉（）。该算子中，子代解集在父代附近均匀生成，其范围与父代解集成比例。SBX是
的扩展，为在父代种群附近生成子代解集提高更高的概率。这使得SBX在MaOEA中特别有用，因为在获得子代解集后种群的分布性不会发生严重的改变。粒子群优化（PSO）是该类别中最著名的生物启发算子之一。与
和SBX不同的是，它利用促进解集来指导搜索，从而展现了高收敛速率。差分进化（DE）是另外一类常见的基于解的算法。它通过用随机选择的父代的比例差异扰乱种群的解集来产生子代解集。因此，它不需要而外的概率分布来探索函数的形状。Sindhya等人认为DE产生的子代是其父代的线性组合。他们还建议父代通过多项式插值法来产生子代。随后，混合算子（HOP）被提出混合多项式插值法和原始DE，并显示了明显的性能优势。注意，虽然DE和PSO已经广泛地应用到了MOEAs，然而实验结果表明它们并不适合求解MaOPs。总之，以上基于解的算子简单而且有效，但是他们很难利用目标空间中的参考向量来引导种群搜索。
在基于模型的方法中，首先构建模型，并使用该模型生成新的解集。估计分配算法（EDAs）属于这一类。在过去十年里，提出了许多多目标EDAs，并显示了它们在求解MOPs以及MaOPs中的前景。这些算法采用参考向量将目标空间划分为多个小的子区域。然后采用相应的解集为子区域在决策空间中构建概率模型。当这些模型迭代更新后，它们能够描述种群的分布和预测向PS移动的趋势。该方法利用参考向量来引导在决策空间的搜索。但是，嵌入到这些算法中的统计学习技术过于复杂导致概率模型的建立需要时间开销。一般而言，这些基于模型的繁殖算子提供了一种在决策空间中利用参考向量的方法，但是它的效率非常低。
除进化计算领域外，在数学规划领域中关于如何使用给定参考向量进行搜索的课题已经研究了很多年。相关的方法被称为“目标指导方法”。Normal-boundary intersection将MOP转化为一系列的目标规划问题，是早期工作的代表。其它代表性的工作包括Combined-objectives repeated line search和Directed search。与传统的启发式搜索方法相比，这些方法提高了算法的收敛速度。但是它们的缺陷是需要目标函数的梯度信息。当这些信息无法获得时，需要采用额外的函数评价或解的邻域结构来估计梯度。通过实验验证，仅采用以上方法很难获得满意的结果。因此，结合传统的优化算法是必不可少的。例如，自适应资源分配可用于确定执行这些方法的概率。另一方法是在目标空间的不同的区域应用不同的搜索策略。然而，如何设计合适的混合策略一直是一个问题。
为了结合以上方法的优势，本文提出一种基于演化路径的DE算子。进化路径首先在协方差矩阵进化策略（CMA-ES），它描述了多待种群的优化路径。通常，它具有一些显著的统计特性，因此它能够描述种群的分布。例如，CMA-ES和多目标CMA-ES应用进化路径来计算种群协方差矩阵的无偏估计。但是如前面所提到的，计算多协方差矩阵由于时间复杂度在MaOEAs中不可行。基于进化路径的DE（DEEP）提供了更简单的方法，利用进化路径来提高DE的收敛速率。但是，该方法仅用于单目标优化。
在本文，我们提出一种新的方法在不提高计算复杂度的情况下利用进化路径。首先，每个参考向量与一组进化路径关联。通过外推法使用该组进化路径计算潜在的解。然后这种潜在的解注入到自适应DE算子中产生子代解。最后，在获得子代和执行完环境选择后，利用新的种群更新相应的进化路径。通过这种方式，进化路径能够为每个参考向量跟踪解曲线，并且加速收敛。进一步地，如果参考向量具有较好的广泛性，提出的算子也将有利于维持子代解集的广泛性和均匀性。
本文的贡献主要归纳为以下几点：
1）提出一种新的方法来构造进化路径并利用它们来产生潜在的解集。我们也提供了一种微妙的方法将这些潜在的解集嵌入到DE算子中来指导搜索。
2）提出一种自适应机制来适应参数的自动变化。我们应用数据结构来存储成功的参数。依靠最近存储的参数来生成新的参数。
3）提出的算子应用到了两个基于分解的MaOEAs中，实验结果验证了该算子能够提高算法的性能。
提出繁殖算子
在本节中，我们首先提供基本思想，然后详细介绍算子的主要部分。
基本思想
为了促进我们的理解，我们采用MOEA/D作为算法框架。MOEA/D在一组参考向量的帮助下将MOP分解成多个子问题。每个子问题保留对应的最好解。在MOEA/D的应用中，一旦最好解被找到，前面的解被新的解遗弃或替换。然而，被遗弃的解可能能够提供有效的信息引导算法搜索。因此，我们的方法是在发生替换操作时收集历史信息。然后我们能够利用这些信息预测潜在的解集增加收敛速度。
以上方法的关键步骤是为子问题收集历史信息。在本文，利用进化路径来完成。进化路径是定义在决策空间的一个向量。我们在每次迭代过程中通过新获得的解的加权求和来计算它。形式上，我们利用
和
分别表示进化路径和新获得的解，对于在第
次替换发生后的第
个子问题。然后，进化路径递归地定义为：
其中为控制参数，
定义为第
个子问题的初始解。
根据上述公式，进化路径是给定子问题的所有历史解的加权求和，这使得它能够合理的描述历史信息。然而，改进化路径中存在控制参数。当
固定不变时，单个进化路径只能描述历史解集的静态状态。然而，我们的目标是利用历史解集预测潜在解集，意味着我们需要一个动态的信息。一个直接的方法是通过不同的
值构造多个进化路径。例如，对于第
个子问题，
描述的是
的初始解。通过一些数学工具，我们能够建立
和
之间的关系。作为一种历史信息，这种关系最终被用来生成潜在的解集。
构造进化路径
本节将介绍如何在MOEA/D中构造进化路径。假设为一组容量为
的向量组。对于每个向量
，假设
为一组D维向量，其中
为正整数，
为在更新率为
的情况下的进化路径。总共
个进化路径被存入到表
中。
1）初始化：首先，采用初始化种群进行初始化。假设
为初始化种群，其中
为第
个解，
为种群大小。然后
中的进化路径设置为一个随机的解：
其中为
之间的随机整数。
2）更新：对于每个参考向量，当它的解被新的解
替换时，它对于的进化路径通过以下公式更新：
图2说明了在对应于第个子问题的前两个替换中如何改变进化路径的。这里
被设置为4,
为初始解。对于收敛性，4个路径的初始值被设置为
。假设
首先被
替换。在这种情况下，四个优化路径位于
和
之间（如图2(a)所示）。当
替换
后，所有进化路径将往
方向移动（如图2(b)所示）。可以发现，在目标空间中，当解往PF方向移动时，对应的优化路径在决策空间中将朝着PS方向移动。当更新率越大，进化路径更容易接近PS。考虑从具有较小更新率的进化路径指向具有较大更新率的方向（例如：从
到
）。如红色箭头描述的，该方向在替换后变得更加准确。下一节，我们将利用该方向加强搜索过程。
生成隐含解
假设，我们考虑
的各个元素为
的函数，那么进化路径有如下特殊性质。
性质一：，其中
为关于
的初始解。
性质二：，其中
为关于
的当前解。
以上性质可以直接从优化路径的初始化和更新规则推导出。并且，从图2中，我们也有如下观察：
观察一：如果，
位于
和
之间。
观察二：如果，
比
更接近
。
在路径优化的帮助下，搜索过程的时间范围被规范到：
视为初始解，
视为当前解，
视为历史中的位置。使用进化路径的基本思想是为了预测有前景的子代：如果我们能够生成
，其中
，它在未来可以被视为一种潜在的解。详细的生成潜在解的过程如下所示。
对于任意，我们有
对点：
。根据这些点，通过等式插值法构造拉格朗日多相似来估计
。
根据上述多相似，我们能够生成潜在解，
。图3提供了
和
情况下的例子。注意，当
超过范围
时，如果
或
过大会使得外推结果不准确。最终，我们限制
且
。
结合进化路径与差分进化
因为很难确定，所以不能直接将潜在解
作为子代。我们提出一直方法将进化路径与DE算子结合来避免参数
的设置。特别地，我们为每个解
生成子代
：
其中和
为从匹配池内随机选择的两个相邻个体。
是消耗的适应度估计的数量，
是运行的最大适应度估计数，
和
为DE算子的两个参数。
与经典的DE算子相比，该算子搜索附近区域而不是
。原因是：由于环境选择，种群将越来越接近真实PF面。根据优化路径的更新规则可知，
比
更接近PS。因此，该方法加强了
方向上的收敛能力。
从公式5中我们可以设置为
.原因如下：
1）为DE算子的缩放参数，其取值范围一般为
。因此，
的取值在
到
之间。下边界使得
为将来潜在解，而上边界是为了防止潜在解远离当前解。
2）在DE中，维持了探索（小的
值）和开发（大的
值）的能力。当
越大，向量差
的随机性越大。另一方面，因为
为高阶多项式，随着
的增加，外推的精度将逐渐减小。为了平衡推进的准确性和随机性，维持
伴随
增加而减少是一个理想的策略。
3）随着
的增加而减小。这样设计使得在早期更多的强调收敛能力，随着搜索过程，这种能力将逐渐降低。除此之外，提出的繁殖算子将退化为标准的DE算子。
参数自适应
由于与DE结合，提出的繁殖算子涉及两个参数：1）和2）
。我们知道，DE的性能依赖于这些参数。这里，我们提出一种新的机制它能够自适应这些参数。这个方法的灵感来源于the suceess-history-based adaptive DE。我们将该工作扩展到了处理MaOPs。
如图4所示，我们保留了历史内存，每个参考向量
包含
个记录，其中
。
的第k个记录包含一对参数
。我们还提供了提示
指示
写入位置。
自适应参数设置机制工作如下;
1)首先，所有参数和
被设置为0.5，所有位置设置为1。
2）在繁殖过程中，我们用如下方式为生成参数：
其中是从
随机选择的整数，
是从标准分布中随机选择的数。当它们的值超出
范围时，
和
需要重新生成。
3）在环境选择之后，如果子代解从选择算子中保留后，它将与对于的参考向量关联。它的参数将存储到第
个历史信息中。更具体地，参数被写入到
指向的条目中。然后，
指向下一个条目。如果
的值大于
时，
设置为1。
图5给出了以上过程。对于某个特定的参考向量，自适应机制能够生成新的参数接近旧的参数。如果新的参数对生成有前景的解有帮助，则这些解又有助于将这些参数传递给附近的参考向量。此外，当新获得的参数进入历史内存中，最旧的参数将被移除。一般而言，以上机制能够从过去的生成有前景的解的经验中学习使得参数逐渐自适应。
以上为提出的繁殖算子的所有元素。我们将以上工作视为两个阶段：繁殖和自适应。启发式代码如算法1和2所示。另外，算法中还采用了多项式变异。
讨论
提出的繁殖算子是为了求解MaOPs。这主要是通过引入受限制的重组方案来实现的。因此，本节将讨论它为什么能够对高维优化问题有帮助。另外，提出的算子使用了外推策略和参数自适应，它与目标指导方法有一定的相似之处。本节将总结它们的不同之处。
1）严格重组机制：在求解MaOPs，随着目标维数的增加，解的支配区域呈指数减少。这会导致非支配解集覆盖到目标空间或决策控制绝大区域。如果重组在两个远离的解中进行，它们的结果可能是破坏性的，因为它们子代也会远离父代。
通过提出的算子获得的子代可以被考虑为四种解的重组：父代解，潜在解，DE算子中使用的两个随机解。为了缓解这个问题，对这种重组添加了两个限制。首先，对于单个父代解，仅使用对应于参考向量
的优化路径来生成潜在解。其次，从限制的匹配池选择两个随机解。因此，子代解可能会接近参考向量
。
另外，参数自适应机制也是受限的。拿MOEA/D为例，子代解仅被它的相邻解替换。也就是说，它的参数只能写入到它相邻解的历史内存中。通过这种方式，彼此接近的解通常具有类似的搜索步骤，这有助于保持种群多样性。
2）与目标指导方法比较：目标指导方法属于数学规划领域利用参考向量来指导在决策空间搜索。但是，它与本文提出的算子有以下重要差异：
1.目标指导方法一般是构造目标和决策变量的关系。在目标空间中给出一个参考方向，决策空间中计算相应的“下降方向”来指导搜索。相反地，我们的算子是尝试找到决策变量与更新速度之间的关系。根据该关系，潜在解能够通过外推直接计算出来。因此，我们的方法没有采用下降方向。
2.因为下降方向，目标指导方法要求计算合适的搜索步长。而在我们的方法中，搜索步长由DE的参数控制，这些参数由参数自适应机制决定。
3.在计算目标指导方法中的下降方向时，通常会考虑决策变量之间的成对依赖关系。它带来了一些计算密集型任务，如矩阵分解和矩阵求逆。相反，我们的算子的所有运算都是分别对每个决策变量执行的。因此，所提出的算子在计算上是有效的。
