多目标进化算法总结.doc

MOGA
是第t代种群中个体,其rank值定义为:
为第t代种群中所有支配的个体数目
适应值(fitness value)分配算法:
将所有个体依照rank值大小排序分类;
利用插值函数给所有个体分配适应值(从rank1到
rank ),一般采用线性函数
适应值共享:rank值相同的个体拥有相同的适应值,
保证后期选择时同一rank值的个体概率相同
最后采用共享适应值随机选取的方法选择个体进入下一代
一种改进的排序机制(ranking scheme):
向量和比较
goal vector:
分为以下三种情况:
1、
2、
当支配时,选择
3、
当支配时,选择
优点:算法思想容易,效率优良
缺点:算法容易受到小生境的大小影响
理论上给出了参数的计算方法
NPGA
基本思想:
1、初始化种***op
2、锦标赛选择机制:随机选取两个个体和和一个Pop的
parison Set)做参照系。若被CS中不少于一
个个体支配,而没有被CS中任一个体支配,则选择。
3、其他情况一律称为死结(Tie),采用适应度共享机制选择。
个体适应度:
小生境计数(Niche Count):
共享函数:
共享适应度(the shared fitness):
选择共享适应度较大的个体进入下一代
优点:能够快速找到一些好的非支配最优解域
能够维持一个较长的种群更新期
缺点:需要设置共享参数
需要选择一个适当的锦标赛机制
限制了该算法的实际应用效果
NPGA II
基本思想:
1、初始化种***op
2、Pareto排序:非支配个体rank=0;其余个体
rank=支配该个体的个体数目
3、锦标赛选择机制:种群中任选两个个体和,
若,则选择;
若是,称为死结(Tie),
采用适应度共享机制选择。
小生境计数(Niche Count):
这里的Pop只包含当前一代里的个体,在NPGA中,
计算公式中的Pop包含当前一代以及已经产生的
属于下一代的所有个体
最后,选择计数较小的个体进入下一代
在计算Niched Count之前还要对函数值进行标准化:
NSGA
和简单的遗传算法的不同点在于selection operator works, crossover and mutation operator是一样的
不一样的共享函数:
表示个体i和j之间的距离
是共享参数,表示小生境的半径
小生境计数(Niche Count):
共享适应值:
最后采用随机余数比例算法选择个体进行重新构造种群的基础
优点:优化目标个数任选
非支配最优解分布均匀
允许存在多个不同的等效解
缺点:计算复杂度过高()
不具有精英保留机制
需要预设共享参数
NSGA II
加入精英保留机制
快速非支配排序方法(Fast Nondominated Sorting Approach):
支配计数:支配解p的解数量
支配解集:解p支配的解集合
计算出每一个解的和,第一级非支配解,单独放入一个集合;
遍历成员q和,逐步递减,如果可以减少为0,将p放入单独的集合Q,构成第二级非支配解;
重复步骤2,直到所有成员全部分类完成。
parison Approach
计算集合I的长度,初始化;
对每一个目标,利用目标值进行排序;
赋予边界点(第一个和最后一个)最大值,确保它们不会被剔除;
循环计算其他点的crowded distance.
其中,I为非支配集合,表示第m个目标在第i个个体处的目标值,
分别表示第m个目标的最大最小函数值
值越小,越拥挤
parison Operator:
if or
Replace the sharing function approach in NSGA
可以一定程度上消除一下两点:
(1)the sharing function 太过于依赖共享参数,不容易设定
(2)the sharing function 时间复杂度达到
算法主循环:
初始种群(),并利用binary tournament selection, bination and mutation operators构建一个子代种群();
合并和,记
第t代:
合并和,记
对进行非支配分类,结果记作
循环计算crowded distance of ,并入
对当前进行crowded distance 排序,选择前个成员并入,确保
利用binary tournament selection, bination and mutation operators构建
进入下一次循环
SPEA
Characters: