A fast and elitist multiobjective genetic algorithm: NSGA-II
A fast and elitist multiobjective genetic algorithm: NSGA-II
复制标题
DOI：
10.1109/4235.996017
复制
发表时间：
2002-04-01
影响因子：
14.3
通讯作者：
Meyarivan, T
中科院分区：
文献类型：
--
作者：
Deb, K;Pratap, A;Meyarivan, T
使用非支配排序和共享的多目标进化算法（EA）主要因其：1）O（MN 3）计算复杂性（其中M是目标数，N是种群大小）; 2）非精英方法; 3）需要指定共享参数而受到批评。在本文中，我们提出了一个非支配排序为基础的多目标EA（MOEA），称为非支配排序遗传算法II（NSGA-II）。它克服了上述三个困难。具体来说，一个快速的非支配排序方法与O（MN 2）的计算复杂度。此外，提出了一种选择算子，它通过结合亲本和后代种群并选择最佳（相对于适应度和传播）N个解决方案来创建交配池。困难的测试问题的仿真结果表明，所提出的NSGA-II，在大多数问题中，是能够找到更好的传播的解决方案和更好的收敛附近的真正的帕累托最优前沿相比，帕累托存档的进化策略和强度帕累托EA-其他两个精英MOEA，特别注意创建一个不同的帕累托最优前沿。此外，我们修改了优势的定义，以便有效地解决约束多目标问题。对一个五目标七约束非线性优化问题的仿真结果表明，该算法比另一种约束多目标优化算法具有更好的性能。
MuItiobjective evolutionary algorithms (EAs) that use nondominated sorting and sharing have been criticized mainly for their: 1) O(MN3) computational complexity (where M is the number of objectives and N is the population size); 2) nonelitism approach; and 3) the need for specifying a sharing parameter. In this paper, we suggest a nondominated sorting-based multiobjective EA (MOEA), called nondominated sorting genetic algorithm Il (NSGA-II). which alleviates all the above three difficulties. Specifically, a fast nondominated sorting approach with O(MN2) computational complexity is presented. Also, a selection operator is presented that creates a mating pool by combining the parent and offspring populations and selecting the best (with respect to fitness and spread) N solutions. Simulation results on difficult test problems show that the proposed NSGA-II, in most problems, is able to find much better spread of solutions and better convergence near the true Pareto-optimal front compared to Pareto-archived evolution strategy and strength-Pareto EA-two other elitist MOEAs that pay special attention to creating a diverse Pareto-optimal front. Moreover, we modify the definition of dominance in order to solve constrained multiobjective problems efficiently. Simulation results of the constrained NSGA-II on a number of test problems, including a five-objective seven-constraint nonlinear problem, are compared with another constrained muItiobjective optimizer and much better performance of NSGA-II is observed.