机器学习和生物信息学实验室联盟

标题: 加强杂交和环境选择的高维目标进化算法 [打印本页]

作者: chencong 时间: 2016-7-13 15:37
标题: 加强杂交和环境选择的高维目标进化算法
本帖最后由 chencong 于 2016-7-13 15:37 编辑

论文标题：A Many-Objective Evolutionary Algorithm With Enhanced Mating and Environmental Selections

作者：Jixiang Cheng, Gary G. Yen, Fellow, IEEE, and Gexiang Zhang, Member, IEEE

论文链接：http://ieeexplore.ieee.org/stamp ... mp;arnumber=7090975

问题描述：解决many-objective optimization 问题（MaOPs）

写作动机：如何评价一个解的收敛程度和多样性问题，如果能做到分别评价，那就可以找出收敛性和多样性都很好的解。

主要工作：本文将diversity和convergence分开来考虑。
1. diversity-directional diversity（DD）
2. convergence-favorable convergence（FC）
将此算法称为MaOEA-DDFC

正文：
[attach]2502[/attach][attach]2502[/attach][attach]2502[/attach][attach]2502[/attach][attach]2502[/attach]

一、Mating selection
Mating selection的过程比较简单，先由支配关系判断、再由FC值，若FC一样则随机选择一个。如选择下图中u，v，显然u,v是非支配的，由（1）计算FC值，若FC（u）<FC（v），则选择u。
[attach]2503[/attach]
[attach]2504[/attach][attach]2504[/attach]
FC是评价解收敛程度的函数，u即解， [attach]2505[/attach]是理想点，可以用每一维的最小值近似得出。
[attach]2506[/attach]表示u在第j维距离理想点的远近，所有维的最大值可以作为u的收敛度评价，即FC越小，则收敛度越高。
w是权重：
[attach]2507[/attach]
由公式（2）可以看出当u在第j维越接近理想点，w在第j维的值越大，表示个体u的第j维更重要。

二、Environment selection
这个过程出现的问题：well distribution poor convergence
提出的方法：DD加上FC
1. 先将合并种群Q非支配排序得到（F1，F2，…….）
2. 当加入Fi就会溢出时，将PUF投影到超平面上，根据DD选择L个解，再根据FC从这L个解中选择出N-P个解，总的来说有3步
1) 投影
[attach]2508[/attach][attach]2508[/attach]
找出每一维的最大值个体（extreme point）就能确定M-1维的超平面，然后是数据的归一化过程：
[attach]2511[/attach]
a 是截距， [attach]2510[/attach]是函数值到理想点的距离（即把理想点移至原点后的函数值）。
投影方式根据文中的说法，我认为是可以将u与原点连成的直线方程求出，和超平面方程联立求出投影点的坐标。
2) DD
DD过程其实是基于KNN算法的，找出投影后点的k个最近的邻居，然后计算距离倒数的均值，越小说明越分散。
[attach]2509[/attach]
然后选择其中DD最小的前L个解再进行FC判断
3) FC
根据公式（1）计算出来的FC值，以一定的概率选择解（概率公式文中没有给出，应该是一个与FC值有关的式子）知道满足数量要求。

三、实验结果
实验将 MaOEA-DDFC与MSOPS,E-MOEA,MOEA/D,HypE,PICEA-G,NSGA-III,SPEA2+SDE比较
Diversity方面除了SPEA2+SDE外都优于其他算法（被SPEA2+SDE全面碾压啊）如下图：
[attach]2513[/attach]
Convergence方面，是最好的，具体如下图：
[attach]2514[/attach]
特别地文中将HV和IGD本身也做成了一个2目标优化的样子，于是有了下面这张图：
[attach]2512[/attach]
不过上图只不过是简单的将排名的平均值作为目标值，这样看来有4个算法是非支配的，具体算法的表现还是要依据实验分析得到，HV和IGD如何权衡也是一大难题。

总结：
文章的思想基于加强选择压力处理Many-objectives问题，个人认为它的创新点主要有2个：
1、提出了两种指标DD和FC可以将解的收敛程度和多样性变成数值的比较问题。
2、在DD中，对于MOEA/D和NSGA-III中出现的在高维情况下，权重向量的某些部分为0的弊端（文中提到），运用了将点投影到平面再考虑分布性的方法。

本文运用的方法比较容易理解，但是感觉实验部分做的不够，用于对比的算法应该更新一些，在IGD方面也被SPEA2+SDE完爆，没有给出HV比较的数值结果。也可以将FC和DD方法单独拿出来使用，运用到其他方法中，作为加强效果的一个小技巧吧。

作者: xzeng 时间: 2016-7-13 16:00
介绍得很清楚，我看懂了{:250:}

作者: chencong 时间: 2016-7-14 10:25
今天做实验发现求FC的权重w的第三种情况时，发现第三种情况w带入FC公式时可以约分，这样FC的每一维数值都变成相同，求MAX没有意义啊。我想第三种情况能不能把w=1/fj-z*去掉比较合理一点.....

作者: daydreamgod 时间: 2016-7-14 17:26
感觉这两个指标还是有很大的改进空间，一篇好论文不但能使人得到启发还能让人想要吐槽。。。

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)