基于局部信息共享的小生境差分进化算法

chencong

论文标题：Inducing Niching Behavior in Differential Evolution Through Local Information Sharing

论文作者：Subhodip Biswas, Souvik Kundu, and Swagatam Das, Senior Member, IEEE

问题描述：多模态优化（multimodal optimization ）的目的是找出问题的所有全局极值解或有意义的局部极值解。传统的遗传算法也属于多模态优化的一种，特别是遗传算法+小生境（Niching）模型发挥着重要作用。多模态有几种基本的小生境模型：拥挤度（crowing）、共享（sharing）、清楚（clearing）等。

PS:多模态和多目标感觉差不多，查了资料也没有具体的解释，文章的前面部分在介绍几种小生境模型，看的费劲，下面我只介绍我感兴趣的，觉得可以用于多目标优化的内容。

差分进化算法：differential evolution（DE）
    DE算法最大的特点是以变异方式产生新个体
    基本思想：对每个个体，随机选取与之不同的三个个体r1,r2,r3，求其中两个个体的矢量差并乘上一个比例缩放因子R，接着与第三个个体矢量求和。


Locally Informative Niching Differential Evolution（LoINDE）
    解决的问题：随机选择过程没有偏好，即使使用基于距离的概率选择，也有可能选择到Less fit 的个体。        如下图，红色点表示当前最优的向量（即个体），绿色点表示距离指标差但是适应度优的向量，黑色表示距离指标好但是适应度稍差的向量。如果只基于距离，将会选择黑色点，但是我们需要选择的是有更好适应性，但距离又不相隔太远的点。
       

基本思想:不仅用相似程度指导种群个体，而且用适应度选择参与变异的个体。

Framework:
初始化种群为 ，表示第G代有Np个D维的个体。

亲和力矩阵（affinity matrix）EG,即距离矩阵，矩阵元素为欧式距离。


梯度矩阵（gradient matrix）SG, f是适应度值，简单来说就是第i行记录的是比第i个体适应度高的个体的差距。
有了这两个矩阵，我们可以进一步计算概率矩阵PE,PS


PE代表与个体i距离越近的个体越容易被选择。
PS代表比个体i适应值越高的个体越容易被选择，这两个公式都看成是归一化过程吧。

最后将两个指标整合成一个统一的矩阵L


根据L，就能由竞争选择，得出K个个体i的邻居，k-neighborhood 。
接着文章定义了两种产生的个体类型
1、第一种个体类型增强局部最优解的搜索能力


2、第二种个体类型增强了多样性的保护


然后用差分算法模型产生新个体




p1,p2可由L得到

最后文章将LoINDE用到了两个小生境模型，试验效果给出的数据来看是好的，由于不是我关心的重点，所以没有深究。

文章总结
   文章公式多进而参数也多，算法多，算法里面还有公式，而且解释模糊，看的人挺晕的。其实选择这篇文章是觉得它的局部解选择方法可以用来改善多目标优化中的交叉策略，大部分的交叉策略是随机选择，我有看到一些文章用基于K-NN算法进行交叉。这篇文章的选择策略不仅可以用于小生境模型，也可以作为——先产生一部分额外局部解，与随机交叉产生解一同环境选择——的策略。

原文参考：http://ieeexplore.ieee.org/stamp ... mp;arnumber=6778013