多目标优化 MOP （一）：遗传算法 SPEA 1999

论文：Multiobjective evolutionary algorithms- a comparative case study and the strength Pareto approach  下载地址

 

1. 将非支配解存储在另一个不断更新的population中
2. 根据一个个体individual支配它的非支配解的个数计算fitness值
3. 使用pareto支配关系保存种群多样性
4. 为了减少非支配解集并不破坏它的特征，加入了聚类过程

算法过程：

1. 初始化：生成种群P和一个空的外部非支配解集P1
2. 将P中的非支配解复制到P1中
3. 将P1中的支配解删除
4. 如果P1中的非支配解的个数大于给定的上限N1,通过聚类的方式修剪P1
5. 计算P 和P1中每个个体的fitness
6. 采用tournament selection（锦标赛选择）方法从P+P1合集中选择个体到mating pool直到达到满足个数为止
7. 根据不同的问题选择不到的crossover和mutation方法
8. 直到满足最大迭代次数为止，，否则执行2

fitness assignment的计算过程：

1. 对于P1中每个solution都分配一个实数值si，si成为strength，si与P中支配解的数量成正比。若n表示P中被i（P1中的解）支配的个体数量，N表示P中种群数量，则si=n/(N+1) ，fitness值 fi=si
2. P中解的fitness等于P1中支配该解的非支配解的Si值相加+1

fitness的计算如图所示，（a）中有3个非支配解，7个支配解，左上角的fitness=3/8计算过程是：支配3个解/（N中解的个数+1），矩形框内解的计算同理，不同的是有交叉区域的话要求和，如19/8就是三个非支配解的和加1，即3/8+5/8+3/8+1

上面两个图反映了解的分布情况，（a）中浅色的区域fitness要比深色区域更小，多样性更好。（b）显示了strength问题，一个solution如果有更多的neighbor它的fitness就越大，受到更大的惩罚。

在某些情况下，pareto解集可能相当的大，外部非支配解的解集大小影响了SPEA的性能。因为党太多的非支配解可能降低选择压力和搜索性能，同时strength niching mechanism依赖于非支配解grid网格的均匀分布，如果P1中的解分布不均匀，fitness assignment很可能偏向某个搜索区域而导致种群分布的不均衡。对于上面的问题采用average linkage method聚类解决。

聚类算法减少pareto解步骤：

1. 初始化聚类集合C，每一个P1中的点构建一个聚类集合
2. 如果|C|<=N1,执行5，否则执行3
3. 计算每两个cluste的距离d，i1和i2的欧氏距离
4. 选择最小距离的两个cluster，合并这两个cluster
5. 计算合并后的非支配解集，每个cluster选择一个代表individual，这里选取的是聚类中心（与类中其他点的平均距离最小）作为代表解

实验部分：

测试了0/1背包问题的九个不同设置，与4个算法进行了对比：

• Vector Evaluated Genetic Algorithm（VEGA）:binary tournament selection
• Aggregation by Variable Objective Weighting(HLGA):weighted-sum method,continuously updated sharing
• Niched Pareto Genetic Algorithm(NPGA):
• Nondominated Sorting Genetic Algorithm(NSGA):continuously updated sharing

selection:binary tournament selection

crossover:crossover (one-point),0.8

mutation:0.01