多目标优化 MOP (一):遗传算法 SPEA 1999
论文:Multiobjective evolutionary algorithms- a comparative case study and the strength Pareto approach 下载地址
Strength Pareto Evolutionary Algorithm (SPEA)的特征:
- 将非支配解存储在另一个不断更新的population中
- 根据一个个体individual支配它的非支配解的个数计算fitness值
- 使用pareto支配关系保存种群多样性
- 为了减少非支配解集并不破坏它的特征,加入了聚类过程
算法过程:
- 初始化:生成种群P和一个空的外部非支配解集P1
- 将P中的非支配解复制到P1中
- 将P1中的支配解删除
- 如果P1中的非支配解的个数大于给定的上限N1,通过聚类的方式修剪P1
- 计算P 和P1中每个个体的fitness
- 采用tournament selection(锦标赛选择)方法从P+P1合集中选择个体到mating pool直到达到满足个数为止
- 根据不同的问题选择不到的crossover和mutation方法
- 直到满足最大迭代次数为止,,否则执行2
fitness assignment的计算过程:
- 对于P1中每个solution都分配一个实数值si,si成为strength,si与P中支配解的数量成正比。若n表示P中被i(P1中的解)支配的个体数量,N表示P中种群数量,则si=n/(N+1) ,fitness值 fi=si
- 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解步骤:
- 初始化聚类集合C,每一个P1中的点构建一个聚类集合
- 如果|C|<=N1,执行5,否则执行3
- 计算每两个cluste的距离d,i1和i2的欧氏距离
- 选择最小距离的两个cluster,合并这两个cluster
- 计算合并后的非支配解集,每个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