NSGA族
NSGA的缺陷：
(1)非支配排序的时间复杂度很大，为$O(MN^3)$,其中M为目标函数的数量，N为种群规模。
(2)不支持精英策略。精英策略在保持好的个体及加速向Pareto前沿收敛方面有很好的表现
(3)需要自己指定共享参数，该参数对种群的多样性产生很大的影响
NSGA-II
NSGA一II算法的基本思想为:首先,随机产生规模为N的初始种群,非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群;其次,从第二代开始,将父代种群与子代种群合并,进行快速非支配排序,同时对每个非支配层中的个体进行拥挤度计算,根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群;最后,通过遗传算法的基本操作产生新的子代种群:依此类推,直到满足程序结束的条件。
主要贡献
(1)快速非支配排序：
(2)保留多样性：提出拥挤比较法替换共享函数法，$I[i].m$为I集合中第i个个体第m个目标函数的值。
#### 主程序
SPEA算法族
SPEA (O($N^3$))
其中适应度的分配方式以及聚类算法等请看参考博客
SPEA-II
- SPEA的缺点
- (1)Fitness Assignment:当P’成员只有一个时，P中所有成员的适应度是相同的。此时SPEA会退化为随机搜索算法
- (2)Density Estimation: 群落分布太稀疏，以至于许多成员之间不存在相互支配关系。若能添加密度信息，那么就能更有效的搜索非支配成员。Clustering仅对P’有效，而对P没有影响。
- (3)Archive Truncation:clustering算法会删减P’中的成员，这其中也有可能包含了外部支配解，造成了信息截断，不利于非支配解的扩散。
DMOEA-$\epsilon C$
- 主要创新点：
- (1)explicitly decomposes an MOP into a series of scalar constrained optimization subproblems by selecting one of the objectives as the main objective function and associating each subproblem with an upper bound vector.
- (2)a main objective alternation strategy is proposed
- (3)a solution-to-subproblem matching procedure is designed to place the nearest solution to each subproblem and is utilized after the main objective alternation strategy
- (4)subproblem-to-solution matching procedure is proposed to find a subproblem with the minimum constraint violation value for a new generated solution.
