一种基于支配和分解的多目标优化进化算法学习笔记

    由于最近我的算法老师给的我一篇算法文章，论文名为《An Evolutionary Many-Objective Optimization

Algorithm Based on Dominance and Decomposition》作者是Ke Li, Student Member, IEEE, Kalyanmoy Deb, Fellow, IEEE, Qingfu Zhang, Senior Member, IEEE, and Sam Kwong, Fellow, IEEE，作为一个对多目标优化问题从来没接触过的人，这可着实花了我不少时间来琢磨，下面我就讲讲在这篇论文中的我所理解的算法。

名词解释：

• EF:理论上的pareto最优向量集
• EMO:进化多目标优化
• EA：进化算法
• MOEA:多目标进化算法
• MOEA/D:基于分解的多目标进化算法
• MOEA/DD:基于支配和分解的多目标优化进化算法
• NSGA-II:非支配排序遗传算法

多目标优化：

    首先，多目标优化的概念就是好比说：你想买车，但是呢，你又想买的车价格低，又想油耗低，安全性高，但是我们都知道这个常识，汽车的价格越低，各个性能就差，此时的价格低，油耗低，安全性高就组成了一个具有相互冲突的目标函数。多目标优化问题（MOP）可以描述为：

• J、K：不等式和等式约束条件的个数
• 决策空间：即可行域，满足gj(x)和hk(x)约束的一块x区域,可看做定义域
• 目标空间：
• m个相互冲突的目标函数：
• 候选解（决策变量）：

f1,f2,....fm对应上面买车的例子的就是价格，油耗，安全性能。基于分解就是把F（x）分解成m个标量化的小目标，求F（x）的最小值，可以转化成求所有的f1,f2,....fm合成的最小值，但是这个时候又会出现一个问题，那就是f1可能是想得到一个最大值，就比如f1为安全性，f2为油耗，f3为价格，则我们把f1转化成求最小值，可以使用取f1的倒数，即f1=1/f1，那么，f1,f2,....fm都是越小越好的，则最后取得的F（x）就是最小的。    

• 收敛性：Pareto解集与真实的最优解集（EF）尽可能的接近，越接近越好
• 多样性：沿着EF方向解扩散，即在目标空间中分布范围尽可能广（EF左右  全方位扩散）。由此可见解集的收敛性和多样性是相互冲突的

随着目标数量的增加，在种群中几乎所有的解（x）都变得彼此不支配。这句话可以理解为：可以设想一下，原来两解X1和X2是相互支配，我们只需要它们其中一个保留其中一个来作为支配解（即Pareto最优解），但是当添加一个目标时，可能这两个解就会变得相互不支配，那我们就要将两个解都保留下来作为Pareto最优解，放入下一次迭代中，那么对于基于Pareto支配关系选择，无法明显而且快速的区分并选出Pareto最优解，反而会由于解大部分都保留下来，增加了更新过程中对后代解的选择压力，大大延缓了进化过程（迭代次数增加），然而促进了种群的多样性。

分解方法：

文章中采用的是PBI分解方法

d1用来评价x对EF的收敛性，d2是衡量种群多样性的一种方法。PBI方法的优化问题被定义为：