非支配排序,拥挤度计算,pareto前沿,A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-II
NSGA算法
NSGA算法缺陷
NSGA-II算法
总结
1. 快速非支配排序法将时间复杂度改进为O(MN2);
2.使用拥塞距离代替代替共享函数算法保持种群多样性;
引入精英保留策略。
非支配排序的复杂度较高: O(MN3) (M是目标函数的个数,N是种群大小);
缺少精英保留策略;
需要人为指定共享参数σshare(共享小生境步骤)。
NSGA: nondominated sorting genetic algorithms-非支配排序遗传算法
nondominated:非支配
例:回家,两目标(费用,时间),均越小越好
动车A(270 , 7),普快B(120 , 10),飞机C(240,2)
C(240,2)支配A(270 , 7);
A(270 , 7)被C(240,2)支配;
B(120 , 10)和C(240,2)不可比,即非支配。
目的:得到一组非支配的解--Pareto最优解集。
1