基于边界点的高维目标进化算法

chencong

论文标题：Many-Objective Evolutionary Algorithm: Objective Space Reduction and Diversity Improvement

论文作者：Zhenan He and Gary G. Yen, Fellow, IEEE

写作动机：
普通的基于非支配排序的遗传算法在解决高维目标优化问题（MaOPs）时所面临的问题主要有：
1、选择压力低下导致的大量的解都是非支配的
2、维数灾难使求解的目标空间太大，效率低下

主要工作：
这篇文章针对上述两个问题，提出了一种高效的方法，主要由以下两个步骤组成：
1、目标空间简化，分成区域内的点和区域外的点。
2.多样性保持策略。

预备知识——Achievement Scalarizing Function (ASF) Method
组会上的ASF讲的不好，在这里补充解释一下，希望有兴趣的同学可以看懂，没兴趣的同学就略过吧。

由公式可以看到，ASF需要理想点Z= ,是每一维最优值的集合，权重向量w= 。
假设我们考虑一个2维优化问题，其中的任意一个点 ，我们展开所求的ASF就是如下两个式子中的较大者。
1、
2、
假设现在我们的F在向量ZW上，我们记为G，如下图所示

则ASF(G)应该等于1,2式中的任何一个（因为在ZW上的点，1,2式的值相等）
然而，当F点在ZW向量的下方时，ASF(F)=  ，此时的ASF(F)=ASF(G)。事实上，直线GH上的任意点的ASF值都是等于 ，为什么呢？因为ASF求的是1,2式的最大值啊，而GH上的点的1式的值都是大于2式的！

同理，直线GK上的任意点的ASF= ，这个值也等于ASF(G)!
我们惊奇的发现同一条的虚线上的点的ASF值时相等的！
于是我们基于点A和点B也能做出两条虚线（即等值线），并且等值线距离Z点的距离越远，ASF值越大，即ASF(F)<ASF(A)<ASF(B)。
所以，我们如果要求所有点解的ASF的最小值，就应该取等值线距离Z点最近的那个点，即取ZW与种群交点O。
当ZW发生变化时，它与种群的交点也在变化，如下图所示，我们可以得到两个边界点O1，O2。


前面提到，文章有两个主要工作，下面分别进行介绍。
一、        目标空间简化

思想：当我们找到真实pareto area的某些边界点，通过这些点大概能推测出pareto area的边界。得到这些边界点后，我们就可以进行第二阶段
边界点——target point
方法——ASF

主要分为以下几步：
1、        对于一个种群，用分类向量（太复杂不说明，用于判别一个个体与哪一维最接近）将其分成M个子种群
2、        在子种群内进行交叉、变异、环境选择，重复1,2步直到满足终止条件
3、        用ASF方法分别找出每一维上的边界点记为target points。
如下图所示：


二、        多样性保持策略
得到边界点以后，我们依据边界点可以得到一个区域，如下图：

文章中的一个重要假设就是：
在边界内的点(inside)是对收敛性起作用的。
在边界外的点(outside)只能使收敛性变差，所以只考虑提高多样性。
所以，选择过程的基本思想是:尽量选择Inside点，多删少补。
具体实现过程如下：

其中 红色字体代表两个选择策略
1、Selection of outside points
目的：inside点不足N时，需要一种策略将outside点补充
思想：target point 和middle point可以大概表示真实的pareto area,选择最接近这两种点的outside点。

2、Diversity operator
目的：消除非支配排序后，Snd>N的问题
思想：非支配关系下，为保持分布性去除靠近的点
步骤：

即计算距离矩阵，每次消除距离最近的点直到满足个数要求为止

实验结果：
和下表五种算法比较，比较DTLZ1~DTLZ7,WFG1~WFG9在5维和10维上的结果，S-metric 即HV

从实验结果可以看到，对比其他五种算法，MaOEA-R&D在多数问题上的效果有提升。


并且对于两个主要步骤起到的作用进行了实验，可以看到当两个步骤结合使用时，其效果是最好的

文章总结：
这篇文章的亮点就是选择了一个区域，认为落在此区域内的点对收敛性起作用，而区域外的点对分布性起作用。在选择区域的方法上使用了ASF，即认为一个在某一维表现最好的点（边界点），它的其他维度值就能作为筛选的指标。文中公式不多，理解后还是让人感觉挺有道理的，用了许多不同的策略，从实验效果来看效果还是挺不错的。

论文链接
[1]ASF: https://www.semanticscholar.org/ ... 8221a0afdf4e1c3/pdf

[2]MaOEA-R&D:http://ieeexplore.ieee.org/stamp ... mp;arnumber=7108005