本人能力有限，此阅读笔记仅为个人见解，如有错误，欢迎批评指正

一、简介

传统优化算法在解决高维多目标优化问题时，面临着两个困难，一个是向真实帕累托面收敛，另一个是保持多样性。对于收敛性，在使用支配解的方法来选择种群时，常常会限制种群的大小，例如NSGA-II和SPEA2，这两种算法都使用基于支配的选择，因此在解决高维多目标问题时会失效。对于多样性，在高维情形下，真实的帕累托前沿通常是非连续的，对于一维二维的情况，PF一般是一维曲线或二维平面，保持多样性通常比较简单，当维数增加时，候选解的分布通常是稀疏的，想要保持多样性就变得比较困难，例如在NSGA-II中使用的拥挤距离。
为了改进传统多目标优化算法在高维多目标问题上的缺点，有学者提出了一些方法，这些方法大致可以分成三类：
第一类：修改支配关系，增强收敛性。
第二类：采用分解的方法，将复杂的问题分解成子问题。有两类基于分解的方法，第一类是将多目标问题分解成单目标问题，在早期使用的是权重聚合的方法，最近使用的是协作进化策略。第二类是将多目标问题分解成一组子问题，例如NSGA-III,尽管第二种方法在某些研究中显示出比第一种更好的性能，但是其研究还只是处于初级阶段。
第三类：基于指标的方法。基于指标的方法不受制于支配关系，但是在高维情况下其计算复杂度较高。
其他：还有一些不处于以上三类的方法。例如，有些学者提出在是使用目标缩减策略是引入用户交互的或参考点的方法。还有同时使用支配和分解的算法（MOEA/DD）。还有使用两归档集的方法（基于指标和支配）。
另外，值得注意的是，使用偏好对于高维多目标问题也是非常重要的，不仅仅是因为用户可能只关注某个部分，但也因为使用有限的种群大小来趋近整个PF面是不太实际的。
受NSGA-III启发，提出了RVEA算法，主要工作如下：
(1)A scalarization approach, termed as the angle penalized distance (APD), is designed to dynamically balance convergence and diversity in many-objective optimization according to the number of objectives and the number of generations.
(2)An adaptive strategy is proposed to adjust the reference vectors to deal with objective functions that are not well normalized.
(3)It is shown that reference vectors can also provide an effective and computationally efficient approach to preference articulation.
(4) To enhance the performance of the proposed RVEA on problems with irregular 2 Pareto fronts, a reference vector regeneration strategy is proposed.
(5) The proposed RVEA is further extended for solving constrained MaOPs.

二、背景介绍

本节首先给出基于分解方法的多目标进化算法的综述，然后，介绍在本文提出的参考向量，包括如何取均匀分布的向量和如何衡量空间中两个向量的关系。

2.1 基于分解的多目标进化算法

本节讲解了一些前人研究的基于分解的多目标进化算法。

2.2 参考向量

为了不失一般性，在本文中使用的向量全部都是第一象限的单位向量并且起点都在原点。理论上，任意向量的单位向量能够通过除以其范数（即模长）求得。然而，实际中，为了产生均匀分布并收敛于PF面的解，需要生成均匀分布的向量。产生均匀分布的向量的步骤如下，首先，利用simplex lattice设计方法在单元超平面上生成一组均匀分布的点。

其中i = 1,…,N 为N个均匀分布的点，M是目标数，H是simplex lattice设计产生的一个正整数，然后相应的单位向量由下式产生：

用次方法将超平面上的参考点映射到超球面（之所以是球面的，因为产生的向量都是单位向量，且起点相同，可以想象成半径为1的球）。由此方法可产生
个个体。

三、RVEA算法

3.1 精英保留

上图是RVEA算法的主框架，从上图我们能看出RVEA使用了类似NSGA-II的精英策略。

3.2 后代产生

在该算法中，没有使用任何交配选择策略来产生父代，而是选择给定的N个个体，来产生后代。

3.3 参考向量指导的选择

（1）目标值转换：

图：目标值转换方法及含义
 
在上图中，我们可以看到，f_(t,i)是转换前的目标向量，f_(t,i)^{'是转换后的目标向量，Z_t}min是每个目标向量中最小的值构成的点，称为理想点，Z_(t,i)^min是第i个目标向量中的最小值。上述转换公式，有两种作用。
第一种：保证所有的目标向量都在第一象限并使覆盖范围最大。（在第一象限的向量的特点是：每一维的值非负，用一个大的数减一个小的数，值大于零，因此保证了目标都在第一象限。又因为Z_(t,i)^min是第i个目标向量中某个值，因此，在使用转换公式时，必有至少一个值为0，若向量的某一位为0，则向量处于坐标轴形成的平面上，以三维为例，三个位于坐标轴形成的平面上的单位向量比其他任何情况围出的面积都要大，覆盖面积达到最大）
第二种：使得理想点移动到原点，由第一种作用可知，当向量进行转化时，至少有一维的值变为0，会将向量拖拽至原点。
(2) 种群划分
在完成向量的转化后，接下来的步骤就是将种群P_t划分到N个子种群中，划分的方法是：计算种群中每个个体和其最近的向量，将该个体划分到与其最近的向量的种群中，因为有N个参考向量，所以会划分为N个子种群，从N个子种群中选择最合适的个体，两个向量的空间位置关系由余弦准则来确定。

注意：当角度越小时，余弦值越大。

(3) 角度惩罚距离计算APD
角度惩罚距离公式为：

 

在高维多目标问题中，由于候选解在目标空间中分布的比较稀疏，在整个进化过程中将收敛性和多样性放在同等地位并不是一个好方法。理想情况下，在进化初期，应该侧重于收敛性，将种群尽可能的逼近至PF面，而在进化的后期，种群开始接近PF面时，应该更加注重多样性。而公式P（θ_(t,i,j)）正是为了满足上述需求来设计的，在进化初期，即t<<t_max时，P（θ_(t,i,j)）≈0，因此d_(t,i,j)≈||〖f'〗_(t,i) ||,即d_(t,i,j)的值约等于向量的长度，在进行后代选择时考虑的是向量的长度即收敛性。

而在后期，t值渐渐增大，占主要影响地位的就变成了θ_(t,i,j)，也即多样性占主导地位。

3.4 参考向量自适应过程

当PF面是归一化的时候，使用一组均匀分布向量能够产生一组均匀分布的解，然而，当PF面未归一化时，用均匀分布的向量则无法产生均匀分布的解，因此，我们需要使向量能够自适应，来产生均匀分布的解。
为什么目标值归一化不适合于RVEA算法呢？原因有如下两个：
（1）目标值归一化会改变点在空间中的位置，因此，向量的长度可能会发生变化，由于角度惩罚距离公式与向量的长度有关，所以使用目标值归一化会影响选择策略。
（2）目标值归一化的过程会在目标值规模发生变化时需要执行。
综上所述，使用目标值归一化会频繁的更改选择策略，因此会影响算法的稳定性和收敛性。
虽然目标值归一化不适用于RVEA算法，但是，仍然适合于选择策略中与向量长度无关的算法，例如：NSGA-III，因为不会改变其偏序关系，所以仍然适用。
在RVEA算法中，提出了参考向量自适应公式：

其中各个符号的意义如下：

下面举一个具体的自适应例子：

通过上述的自适应方法，能够实现在不均匀分布的PF面上得到均匀分布的解。
参考向量自适应算法如下图所示：
 

其中f_r为frequency，即控制更新的频率。
下图为自适应算法实现的参考向量自适应：

值得注意的是：参考向量自适应只适用于能够缩放的问题，不能保证能够适用于解集分布不规则的问题，例如不连续的或者退化的问题（退化的问题如DTLZ5和DTLZ6，其PF是一条曲线，而不是面），为了能够处理不规则面的问题，因此在第六节中提出了另一种参考向量再生的方法。

3.5时间复杂度

RVEA总的时间复杂度为O（MN^2），具体分析参考原论文。

四、对比试验

本节参考原文。

五、确立偏好

本节标题翻译不知是否正确，欢迎讨论。
下图为具体过程：

带偏好的进化算法，目的是在由用户指定偏好区域中，生成一组均匀分布的解。在本节中的方法是，用户指定偏好区域，然后确定偏好区域的中心向量和半径，半径范围在（0,1）之间。然后，在子区域均匀分布的向量由以下图公式产生：

公式中的符号意义如下图：

V_i本身就是均匀分布的向量，为什么通过上述公式就能够产生均匀分布的向量，原因如下图：

六、处理不规则PF面

在某些问题中，PF面由于各种各样的原因，PF面十分的不规则。例如，由于约束问题，目标空间中某些解集无法取得，因此，当使用均匀分布的向量时，某些向量可能没有被分配个体，使得解集的数量变少。为了解决不规则PF面带来的问题，最直接的方法就是重新产生参考向量，将无效的参考向量（无效的参考向量指的是没有分配个体的参考向量）替代，在NSGA-III中，使用了替换参考点的方法，值得参考。但是，有一个难点就是，我们不知道何时执行参考向量重生的过程，因为即使对于规则的PF面，参考向量也有可能失效。在NSGA-III中的做法是，保留原始的参考点集，产生新的参考点加入其中。
在RVEA中，仍然保留原始的参考向量，用新的参考向量替代（记为V^*）。和NSGA-III不同的是，采用的是替换原则，而不是增加删除原则。
算法框架图如下：
 

值得注意的是：在算法4的第十三行，产生的随机值是从0开始的，因为向量已经被翻译过，所以每一维的最小值总是为0。将每一维的值调整到0到该维最大，则总有个体会被分配到该向量。
该方法存在一个缺陷，因为产生的向量是全局随机产生的，因此，在小区域的解集密度无法得到保证。

七、处理约束问题

在实际问题中，通常都存在着约束，因此，在本节中提出约束处理的方法。约束违反函数如下图：

下图时公式中符号的意义：

算子<α>，当α是负数时，返回-α,即返回一个正数，后面的绝对值表示里面的表达式不等于0时返回正数。个体约束违反值越大，越不容易被选中，因此也被称作惩罚函数。
约束问题的精英选择策略如下：

算法思想是：首先，将违反约束的个体的下标索引加入集合S中，如果S的大小和子种群的大小相等，即没有可取的解。此时选择违反约束度最小的值作为下一代的父代；否则，选择APD值最小的个体作为下一代的父代。