Efficient Nondomination Level Update Method for Steady-State Evolutionary Multiobjective Optimization

Nondominated sorting (NDS), which divides a population into several nondomination levels (NDLs), is a basic step in many evolutionary multiobjective optimization (EMO) algorithms. It has been widely studied in a generational evolution model, where the environmental selection is performed after gener...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2017-09, Vol.47 (9), p.2838-2849
Main Authors: Ke Li, Deb, Kalyanmoy, Qingfu Zhang, Qiang Zhang
Format: Article
Language:English
Subjects:
Computational complexity
Computational modeling
Cybernetics
Evolutionary algorithms
Extreme values
Iterative methods
Multiple objective analysis
nondominated sorting (NDS)
nondomination level (NDL)
Optimization
Pareto dominance
Population
Sociology
Statistics
Steady-state
steady-state evolutionary multiobjective optimization (EMO)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Nondominated sorting (NDS), which divides a population into several nondomination levels (NDLs), is a basic step in many evolutionary multiobjective optimization (EMO) algorithms. It has been widely studied in a generational evolution model, where the environmental selection is performed after generating a whole population of offspring. However, in a steady-state evolution model, where a population is updated right after the generation of a new candidate, the NDS can be extremely time consuming. This is especially severe when the number of objectives and population size become large. In this paper, we propose an efficient NDL update method to reduce the cost for maintaining the NDL structure in steady-state EMO. Instead of performing the NDS from scratch, our method only updates the NDLs of a limited number of solutions by extracting the knowledge from the current NDL structure. Notice that our NDL update method is performed twice at each iteration. One is after the reproduction, the other is after the environmental selection. Extensive experiments fully demonstrate that, comparing to the other five state-of-the-art NDS methods, our proposed method avoids a significant amount of unnecessary comparisons, not only in the synthetic data sets, but also in some real optimization scenarios. Last but not least, we find that our proposed method is also useful for the generational evolution model.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2016.2621008