A Simple and Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm

1.摘要

基于HV指标来引导搜索迭代的一个很大问题是计算不同解决方案的HV需要的高额时间。针对这个问题，本文提出一个简单且快速的基于HV计算的FV-MOEA算法，它可以迅速更新不同解决方案带来的HV改进。
FV-MOEA的核心思想是，新解的HV改进仅与原解集的部分解有关。 因此，删除不相关的解可以大大降低FV-MOEA的时间成本。 实验研究表明，FV-MOEA不仅比五个经典MOEA(非支配排序遗传算法(NSGA-Ⅱ)、Strength Pareto evolutionary algorithm 2(SPEA2)、基于分解的多目标进化算法(MOEA/D)、基于指标的进化算法和基于S-metric选择的进化多目标优化算法(SMS-EMOA)结果的HV更高，而且与其他基于HV指标的MOEA相比也获得了显著的加速。

2.介绍

原文这部分提到很多基于指标改进的多目标优化文献，他们通常都能表现出优于另外两类算法的性能，读者感兴趣可以去原文细看。
作者提到计算HV是基于指标算法的瓶颈。而目前计算HV通常有两类方法，一种是精确计算，一种是近似计算。前者的优点是准确，但耗时。后者刚好相反。而本文提出的FV-MOEA大大改进了计算的时间成本，且能得到准确的HV。

另外，作者提到本文的FV-MOEA特别适合处理动态地在解集里加入和删除一个解的HV变化。

3.FV_MOEA

$A.$一个解的HV贡献
这里作者首先设计了一个更差支配式子去删除无关解。定义为：

如下图所示，假设当前Pareto set为a,b,c,d,e.则a的HV改进为图中阴影部分的矩形

当使用更差支配式子后，我们可以找出W={w1，w3}。于是点a的HV的改进可以用下面式子计算：

该式子左边的意思是，参考点为R,当前解集为S(在这为a,b,c,d,e)，计算的改进点为一个点a。右边的意思是，参考点R下，a支配的HV减去由W支配的HV。
需要注意的是文中这里没有提到w1-w4是根据b，c，d，e得来的。
有了上面的讨论后，a的HV计算将只与b，d两点有关，这将大大减少重复计算。而关于W的HV计算，文中这里提供了许多参考文献可以直接用来计算，详见原文。

$B.$两个解的HV贡献

假设我们要计算a，b两个解的HV。
a，b的HV为下图中的阴影部分：

首先我们也是用上面式子得到W={w2,w3}。再通过a，b坐标得到点w1。于是a，b两个解的HV可以用下式计算：

于是假设我们删去了a点，则b的新的HV可以用下式计算:

其中S’为b,c,d,e。

经过上面讨论，我们可以迅速计算对于一个点删除或增加的HV变化。

$C.$选择操作伪码

选择操作伪码

第1-3行计算了每个pareto解的HV贡献。第5行找出来最小的HV改进的解j。6-9得到了j和任意一个其他解的HV贡献。第10行更新了HV的贡献。第11行删去点j。重复4-11操作。直到剩下N个解作为下一代父代。

算法框架

第1-2行随机初始化了种群。5-8行生成后代。第9行进行父子代合并。第10行进行非支配排序。11-14利用刚才的排序构建$P_{g+1}$，15-17行利用快速HV计算，将第i个支配层排序。将结果好的加入$P_{g+1}$，使得种群数达到NP。

4.总结

这是近些年非常好的文章，基于指标的方法性能从机理上是会比另外两类更好的，但时间必然也会长一些，鱼和熊掌不可兼得呀。

返回受约束的多目标优化问题优秀论文及总结目录