The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms
Abstract
The last decade has seen a surge of research activity on multiobjective optimization using evolutionary computation and a number of well performing algorithms have been published. The majority of these algorithms use fitness assignment based on Pareto-domination: Nondominated sorting, dominance counting, or identification of the nondominated solutions. The success of these algorithms indicates that this type of fitness is suitable for multiobjective problems, but so far the use of Pareto-based fitness has lead to program run times in O(GMN/sup 2/), where G is the number of generations, M is the number of objectives, and N is the population size. The N/sup 2/ factor should be reduced if possible, since it leads to long processing times for large population sizes. This paper presents a new and efficient algorithm for nondominated sorting, which can speed up the processing time of some multiobjective evolutionary algorithms (MOEAs) substantially. The new algorithm is incorporated into the nondominated sorting genetic algorithm II (NSGA-II) and reduces the overall run-time complexity of this algorithm to O(GN log/sup M-1/N), much faster than the O(GMN/sup 2/) complexity published by Deb et al. (2002). Experiments demonstrate that the improved version of the algorithm is indeed much faster than the previous one. The paper also points out that multiobjective EAs using fitness based on dominance counting and identification of nondominated solutions can be improved significantly in terms of running time by using efficient algorithms known from computer science instead of inefficient O(MN/sup 2/) algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast and elitist multiobjective genetic algorithm: NSGA-II
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.996017 · Cited by 50,053
Multi-Objective Optimization Using Evolutionary Algorithms
Deb, K., & Kalyanmoy, D. (2001) · Andalas University Repository (Andalas University) · Cited by 14,918
Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach
Zitzler, E., & Thiele, L. (1999) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.797969 · Cited by 8,798
Comparison of Multiobjective Evolutionary Algorithms: Empirical Results
Zitzler, E., Deb, K., & Thiele, L. (2000) · Evolutionary Computation · doi:10.1162/106365600568202 · Cited by 5,697
Handbook of Evolutionary Computation
(1997) · Institute of Physics eBooks · doi:10.1887/0750308958 · Cited by 2,990
A niched Pareto genetic algorithm for multiobjective optimization
Horn, J., Nafpliotis, N., & Goldberg, D. E. (2002) · Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence · doi:10.1109/icec.1994.350037 · Cited by 2,433
Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy
Knowles, J. D., & Corne, D. W. (2000) · Evolutionary Computation · doi:10.1162/106365600568167 · Cited by 2,286
GENETIC ALGORITHMS FOR MULTI-OBJECTIVE OPTIMIZATION: FORMULATION, DISCUSSION, AND GENERALIZATION
Fonseca, C. M., & Fleming, P. J. (1993) · Cited by 2,056
Scalable multi-objective optimization test problems
Deb, K., Thiele, L., Laumanns, M., & Zitzler, E. (2003) · Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No.02TH8600) · doi:10.1109/cec.2002.1007032 · Cited by 1,627
A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques
Coello Coello, C. A. (1999) · Knowledge and Information Systems · doi:10.1007/bf03325101 · Cited by 1,367
Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. (1973) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(73)80033-9 · Cited by 1,235
SPEA2: Improving the Strength Pareto Evolutionary Algorithm For Multiobjective Optimization
Zitzler, E., Giannakoglou, K., Tsahalis, D., Periaux, J., Papailiou, K., (eds, T. F., Ler, E. Z., Laumanns, M., & Thiele, L. (2002) · Cited by 1,010
The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization
Corne, D. W., Knowles, J. D., & Oates, M. J. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45356-3_82 · Cited by 884
Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules
Fisher, H. F. (1963) · Medical Entomology and Zoology · Cited by 729
Multidimensional divide-and-conquer
Bentley, J. L. (1980) · Communications of the ACM · doi:10.1145/358841.358850 · Cited by 672
PDE: a Pareto-frontier differential evolution approach for multi-objective optimization problems
Abbass, H. A., Sarker, R., & Newton, C. (2002) · Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546) · doi:10.1109/cec.2001.934295 · Cited by 524
M-PAES: a memetic algorithm for multiobjective optimization
Knowles, J. D., & Corne, D. W. (2002) · Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512) · doi:10.1109/cec.2000.870313 · Cited by 359
Jin, Y., Olhofer, M., & Sendhoff, B. (2007) · Cited by 211
Guiding Single-Objective Optimization Using Multi-objective Methods
Jensen, M. T. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36605-9_25 · Cited by 54
Self-citation
Cited by
Multi-objective optimization using genetic algorithms: A tutorial
Konak, A., Coit, D. W., & Smith, A. E. (2006) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2005.11.018 · Cited by 3,440
Evolutionary multi-objective optimization: a historical view of the field
Coello Coello, C. A. (2006) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2006.1597059 · Cited by 1,446
Knowles, J. (2006) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2005.851274 · Cited by 1,254
Deb, K., & Deb, K. (2014) · Search Methodologies · doi:10.1007/978-1-4614-6940-7_15 · Cited by 1,248
Review: Multi-objective optimization methods and application in energy saving
Cui, Y., Geng, Z., Zhu, Q., & Han, Y. (2017) · Energy · doi:10.1016/j.energy.2017.02.174 · Cited by 685
Metadata
- Authors
- Jensen, M. T.
- Venue
- IEEE Transactions on Evolutionary Computation
- Published
- 2003-10
- Volume
- 7
- Issue
- 5
- Pages
- 503-515
- ISSN
- 1089-778X (ISSN-L)
- OpenAlex
- W2126997347
- Cited by
- 458
- References
- 19
- FWCI
- 17.48
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.