多目标优化 MOP （二）：遗传算法 SPEA2 2001

论文：SPEA2: Improving the Strength Pareto Evolutionary Algorithm For Multiobjective Optimization  

首先说一下SPEA2与SPEA算法的不同之处(见SPEA)：

1. 采用一种改进的适应度分配策略，计算每一个个体支配的个数和配其他个体 支配的个数
2. 一种更精确的搜索策略，采用最近邻密度估计技术
3. 一种心的存档截断方法

SPEA的不足：

1. fitness assignment，被同一个存档个体支配的其他个体具有相同的fitness值，这降低了选择压力，使得SPEA更像一个随机搜索算法
2. density estimation,如果很多个体是不相关的，例如不互相支配，很难从支配关系中获得信息，这其实在多目标优化中很常见（目标数大于等于3的）。居于聚类的方式只使用了archive中的个体，而不是整个种群
3. archive truncation存档截断，虽然聚类技术可以在保持算法特征的同时减少非支配解，但是丢失了外部solution。而这些解应该被保存在archive中一保持好的多样性

SPEA2算法步骤：

1. 初始化(Initialization)：生成初始种群P0和一个空的存档（外部存档）P0,P0为空集，t=0
2. 适应度分配（Fitness assignment）：计算PT和PT的适应度值
3. 环境选择（Environmental selection）：将所有PT和PT的个体复制到PT+1,如果 种群个数超过N(archive size)，采用截断操作（truncation operator），如果合并后的种群个数少于N则用PT和PT中的支配解填充PT+1
4. 终止条件（Termination）：如果当前迭代数t>=T或者其他停止标准满足，将A作为PT+1中非支配解所代表的决策变量集合输出
5. 选择方式（Mating selection）：对PT+1采用binary tournament selection放入mating pool
6. 变异（Variation）：对mating pool中的个体进行重组和变异，PT+1作为最后的种群，t=t+1转到2

SPEA2 使用了一个fine-grained fitness assignment 策略，包含了density information。此外，外部存档大小是固定的，而SPEA中的外部存档可能随时间而改变。关于聚类技术，党非支配解数量超过存档限制时，，截断技术并不会使得boundary points丢失。另一个与SPEA不同之处是只有存档中的个体参与mating selection过程。

Fitness Assignment 适应度分配：

为了避免同一个外部存档中个体支配的其他个体具有相同的适应度值，SPEA2同时考虑支配解和非支配解。

具体的做法是对PT和PT中的每个个体分配一个strength value S(i),代表被当前个体支配的solution个数。

在S(i)的基础上定义了raw fitness R(i)，代表i被支配的solution个数， R(i)=0表示非支配解， R(i)越大支配i的个体越多

虽然raw fitness提供了一种niching mechanism小生境机制的pareto支配排序理念，但是单大部分个体是非支配关系时可能作用不大。此音引入了density information区分相同raw fitness value的个体。SPEA2中的density estimation technique是一种适应性的K近邻方法，任意点的density是k个邻居点的距离函数。这篇文章直接取第k个邻居的距离倒数作为density estimate。

k的值是种群和存档个数和的开平方，

density ，分母部分保证D(i)的值大于0并且小于1

个体i的fitness值

fitness的执行时间由density estimator决定,S和R的计算复杂度是，

Environmental Selection 环境选择：

复制所有非支配解集（fitness值小于1的解），从archive和种群复制到下一代archive中。

此时有三种情况：

1）如果下一代种群PT+1个数等于N,选择过程结束

2）如果下一代种群PT+1个数<N,选择PT和PT中个体fitness值大于1的个体排序，取fitness值最小的（N - PT+1个数）个solution

3）如果下一代种群PT+1个数>N, 采用archive truncation procedure从PT+1中逐一删除直到个数等于N，

代表个体i与第k个邻居的距离，上面公式表示具有最小距离的个体被选中删除，如果有多个个体都是距离最小值，则考虑第二个最小距离值，以此类推。

截断操作的最长运行复杂度是，但是平均复杂度小于，因为一般个体的距离在第二或第三个邻居处回不同。

实验设置：

算法对比：实验对比了SPEA,NSGA2,PESA

测试问题：组合优化问题（背包问题：750个物体的2.3.4目标，one-point crossover和 Point mutations）和连续变量问题（Sphere Model (SPH-m)，Kursawe’s function (KUR)，ZDT6，QV等，采用SBX-20 operator和a polynomial distribution mutation）