research-article

Attempt to reduce the computational complexity in multi-objective differential evolution algorithms

Authors:

Martin Drozdik,

Hernan Aguirre,

Kiyoshi TanakaAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 599 - 606

https://doi.org/10.1145/2463372.2463453

Published: 06 July 2013 Publication History

Get Access

Abstract

Nondominated sorting and diversity estimation procedures are an essential part of many multiobjective optimization algorithms. In many cases these procedures are the computational bottleneck of the entire algorithm. We present the methods to decrease the cost of these procedures for multiobjective differential evolution (DE) algorithms. Our approach is to compute domination ranks and crowding distances for the population at the beginning of the algorithm and use a combination of well known data structures to efficiently update these attributes. Experiments show that the cost of improved nondominated sorting is sub-quadratic in the number of individuals. In practice using our methods the overall DE algorithm can run 2 to 100 times faster.

References

[1]

M. Farina and P. Amato. On the optimal solution definition for many-criteria optimization problems. In Fuzzy Information Processing Society, 2002. Proceedings. NAFIPS. 2002 Annual Meeting of the North American, pages 233--238, 2002.

Crossref

Google Scholar

[2]

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, second edition, 2000.

Digital Library

Google Scholar

[3]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm NSGA-II. IEEE Transactions on evolutionary computation, 6(2), 2002.

Digital Library

Google Scholar

[4]

K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multi-objective optimization. In Evolutionary Multiobjective Optimization, pages 105--145. Springer Berlin Heidelberg, 2005.

Crossref

Google Scholar

[5]

S. Huband, P. Hingston, L. Barone, and L. While. A review of multiobjective test problems and a scalable test problem toolkit. Trans. Evol. Comp, 10(5):477--506, oct 2006.

Digital Library

Google Scholar

[6]

M. T. Jensen. Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. IEEE Transactions on Evolutionary Computation, 7(5):503--515, 2003.

Digital Library

Google Scholar

[7]

S. Kukkonen and K. Deb. Improved pruning of non-dominated solutions based on crowding distance for bi-objectve optimization problems. In Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 1179--1186. IEEE Press, 2005.

Google Scholar

[8]

S. Kukkonen and K. Deb. A fast and effective method for pruning of non-dominated solutions in many-objective problems. In Proc. Parallel Problem Solving from Nature - PPSN IX, volume 4193, chapter LNCS, pages 553--562. Springer Berlin Heidelberg, 2006.

Digital Library

Google Scholar

[9]

S. Kukkonen and J. Lampinen. GDE3: the third evolution step of generalized differential evolution. In IEEE Congress on Evolutionary Computation, pages 443--450, 2005.

Google Scholar

[10]

K. Price, R. M. Storn, and J. A. Lampinen. Differential Evolution - A Practical Approach to Global Optimization. Springer, Berlin, Germany, 2005.

Digital Library

Google Scholar

[11]

W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668--676, jun 1990.

Digital Library

Google Scholar

[12]

T. Robič and B. Filipič. DEMO: Differential evolution for multiobjective optimization. Proc. Intl. conf. on Evolutionary Multi-criterion optimization (EMO 2005), Springer, LNCS 3410, pages 520--533, 2005.

Digital Library

Google Scholar

Cited By

View all

Sohrabi Geshnigani FGolabi MMirabbasi RTahroudi M(2023)Daily solar radiation estimation in Belleville station, Illinois, using ensemble artificial intelligence approachesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.105839120:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.105839
Kamkhad NJampachaisri KSiriyasatien PKesorn K(2020)Toward semantic data imputation for a dengue datasetKnowledge-Based Systems10.1016/j.knosys.2020.105803196(105803)Online publication date: May-2020
https://doi.org/10.1016/j.knosys.2020.105803
Drozdik MAkimoto YAguirre HTanaka K(2015)Computational Cost Reduction of Nondominated Sorting Using the M-FrontIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.236649819:5(659-678)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TEVC.2014.2366498
Show More Cited By

Index Terms

Attempt to reduce the computational complexity in multi-objective differential evolution algorithms
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

The proposed constrained differential evolution framework uses nondominated sorting mutation operator based on fitness and diversity information for constrained optimization. This study proposes a new constraint differential evolution framework.Parents ...
Multi-objective optimization using teaching-learning-based optimization algorithm

Two major goals in multi-objective optimization are to obtain a set of nondominated solutions as closely as possible to the true Pareto front (PF) and maintain a well-distributed solution set along the Pareto front. In this paper, we propose a teaching-...
A tri-objective differential evolution approach for multimodal optimization

The multimodal optimization problems (MMOPs) need to find multiple optima simultaneously, so the population diversity is a critical issue that should be considered in designing an evolutionary optimization algorithm for MMOPs. Taking advantage of ...

Comments

Information & Contributors

Information

Published In

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sohrabi Geshnigani FGolabi MMirabbasi RTahroudi M(2023)Daily solar radiation estimation in Belleville station, Illinois, using ensemble artificial intelligence approachesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.105839120:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.105839
Kamkhad NJampachaisri KSiriyasatien PKesorn K(2020)Toward semantic data imputation for a dengue datasetKnowledge-Based Systems10.1016/j.knosys.2020.105803196(105803)Online publication date: May-2020
https://doi.org/10.1016/j.knosys.2020.105803
Drozdik MAkimoto YAguirre HTanaka K(2015)Computational Cost Reduction of Nondominated Sorting Using the M-FrontIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.236649819:5(659-678)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TEVC.2014.2366498
Fu YHuang HYe SLv LZhang HShao L(2015)An Algorithm for Finding Non-dominated Set Based on Two-Dimension SortingBio-Inspired Computing -- Theories and Applications10.1007/978-3-662-49014-3_14(150-160)Online publication date: 24-Dec-2015
https://doi.org/10.1007/978-3-662-49014-3_14
Parija SSahu PSingh S(2014)Differential evolution for cost reduction in cellular network2014 International Conference on High Performance Computing and Applications (ICHPCA)10.1109/ICHPCA.2014.7045313(1-5)Online publication date: Dec-2014
https://doi.org/10.1109/ICHPCA.2014.7045313

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

Multi-objective optimization using teaching-learning-based optimization algorithm

A tri-objective differential evolution approach for multimodal optimization

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations