面向多目标优化的拐点驱动进化算法

bcdfg

题目：A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization
发表期刊：IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 6, DECEMBER 2015
作者：Xingyi Zhang等

本文主要贡献：
1.       提出了拐点驱动的多目标进化算法。
2.       提出了自适应策略来确定拐点。
3.       大量实验，与到目前为止的一些多目标进化算法的性能进行对比。

基本概念介绍

拐点：pareto前沿面上最＂凹＂的部分。如下图所示，A(1,16),B’(6,11),B(7,6),C(11,6),D(16,1) ，B点是拐点。

算法
主要算法流程

本文的总体框架是类似于 NSGA-ⅱ，其中由以下几个主要部分组成。第一步，随机生成初始的亲本种群，大小为N 。第二步，使用二元竞争策略从亲本种群生成N个子代。在二元竞争策略中，采用以下三个竞争指标，支配关系，拐点标准和加权距离。第三步，父代与子代同时参与非支配排序，采用自适应的策略来确定位于拐点区域的pareto前沿。第四步，进行环境选择，选择作为亲本种群的下一代的N个人。

二元竞争策略生成子代
从父本中随机生成两个个体。如果一个解支配着另一种解，然后选择前一个解。如果这两个解彼此非支配，然后算法将检查它们是否是两个拐点。如果其中只有一个是拐点就选择拐点。如果他们俩都是拐点或他们俩都不是拐点，将用加权距离比较解，有更大的加权距离的解被选择。加权距离一样则随机选择。

采用K临近算法计算点的加权距离。


其中pi表示离P第i近的点， wpi表示pi权重、 disppi表示p和pi之间的欧氏距离， rpi表示距离 disppi之间的排序，1≤ j ≤ k 。一些现有的距离度量方法也可以解决拥挤距离的问题，如网格拥挤距离 (GCD)。


自适应的策略来确定拐点
  
上图所示是具体算法，我们可以通过下面这张图来解释一下是如何选取拐点的。下图是个二目标问题，有9个非支配解。我们先找到f1和f2的最值，计算超平面（在图中就是计算出直线L）。接着我们计算每个点到L的距离，如果一个解A到直线的距离比它的邻居到直线的距离要大的话，那么我们称A是拐点。
我们从图中可以看到，B，E，G点是拐点。当然拐点的确定必须提到领域的问题（如图中长方形虚线框所示为邻域），解的邻域大小会严重影响结果的确定。

关于邻域的确定
一个点的邻域是一个M维空间（M是优化目标数），在每个维度上的边长等于在这个维度上的最大值减去最小值，再乘以rg。

rg −1是 (g−1)代，tg−1是在(g −1)代中拐点数目占解数目的比值。0< T <1 ，T是一个阈值，用来控制拐点比值。方程 (7) 确保那rg在tg−1 远远小于指定的阈值T时将大大减少。当tg−1 很大时rg的减少将变慢。当tg−1 达到给定的阈值T时，rg将保持不变。tg和rg分别，初始化为0 和 1，即t0 = 0 和r0 = 1。


环境选择

环境选择的方法类似于 NSGA-ⅱ，从父代和子代选出作为下一代的父本的种群，是利用精英方法生成子代。而 NSGA-ⅱ采取pareto支配作为环境选择的主要标准，本文则选择拐点。
实验结果
在DTLZ上的结果
IGD RESULTS OF THE FIVE COMPARED ALGORITHMS ON DTLZ1 TO DTLZ7


运行时间
  
在WFG上的结果
HVS OF THEFIVE ALGORITHMS ON WFG1 TO WFG9

运行时间

KnEA的参数T的敏感性
  

当优化目标大于三个以上时建议选择较小的T值
总结
利用NSGAII的思想，加入拐点这个衡量标准使其在高维空间上有不错的效果。