Article

On identifying global optima in cooperative coevolution

Authors:

Anthony Bucci,

Jordan B. PollackAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 539 - 544

https://doi.org/10.1145/1068009.1068098

Published: 25 June 2005 Publication History

Get Access

Abstract

When applied to optimization problems, Cooperative Coevolutionary Algorithms(CCEA) have been observed to exhibit a behavior called relative overgeneralization. Roughly, they tend to identify local optima with large basins of attraction which may or may not correspond to global optima. A question which arises is whether one can modify the algorithm to promote the discovery of global optima. We argue that a mechanism from Pareto coevolution can achieve this end. We observe that in CCEAs candidate individuals from one population are used as tests or measurements of individuals in other populations; by treating individuals as tests in this way, a finer-grained comparison can be made among candidate individuals. This finer-grained view permits an algorithm to see when two candidates are differently capable, even when one's evident value is higher than the other's. By modifying an existing CCEA to compare individuals using Pareto dominance we have produced an algorithm which reliably finds global optima. We demonstrate the algorithm on two Maximum of Two Quadratics problems and discuss why it works.

References

[1]

A. Bucci and J. B. Pollack. Focusing versus intransitivity: Geometrical aspects of coevolution. In Erick Cantú-Paz et al., editor, Genetic and Evolutionary Computation Conference - GECCO 2003, volume 2723 of Lecture Notes in Computer Science, pages 250--261. Springer, 2003.]]

Digital Library

Google Scholar

[2]

A. Bucci and J. B. Pollack. A Mathematical Framework for the Study of Coevolution. In K. De Jong, R. Poli, and J. Rowe, editors, FOGA 7: Proceedings of the Foundations of Genetic Algorithms Workshop, pages 221--235, San Francisco, CA, 2003. Morgan Kaufmann Publishers.]]

Google Scholar

[3]

S. G. Ficici. Solution Concepts in Coevolutionary Algorithms. PhD thesis, Brandeis University, Waltham, Massachusetts, 2004.]]

Digital Library

Google Scholar

[4]

S. G. Ficici and J. B. Pollack. Pareto Optimality in Coevolutionary Learning. In European Conference on Artificial Life, pages 316--325, 2001.]]

Digital Library

Google Scholar

[5]

C. M. Fonseca and P. J. Fleming. An Overview of Evolutionary Algorithms in Multiobjective Optimization. Evolutionary Computation, 3(1):1--16, 1995.]]

Digital Library

Google Scholar

[6]

J. Noble and R. A. Watson. Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection. In L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pages 493--500, San Francisco, CA, 2001. Morgan Kaufmann Publishers.]]

Google Scholar

[7]

L. Panait, R. P. Wiegand, and S. Luke. A sensitivity analysis of a cooperative coevolutionary algorithm biased for optimization. In Kalyanmoy Deb et al., editor, Genetic and Evolutionary Computation Conference -- GECCO 2004, volume 3102 of Lecture Notes in Computer Science, pages 573--584. Springer, 2004.]]

Google Scholar

[8]

M. A. Potter and K. A. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1--29, 2000.]]

Digital Library

Google Scholar

[9]

C. D. Rosin. Coevolutionary Search Among Adversaries. PhD thesis, University of California, San Diego, San Diego, California, 1997.]]

Digital Library

Google Scholar

[10]

R. Watson and J. B. Pollack. Coevolutionary dynamics in a minimal substrate. In L. Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, San Francisco, CA, 2001. Morgan Kaufmann Publishers.]]

Google Scholar

[11]

R. P. Wiegand. An Analysis of Cooperative Coevolutionary Algorithms. PhD thesis, George Mason University, Fairfax, Virginia, 2003.]]

Digital Library

Google Scholar

Cited By

View all

Talbi E(2024)Metaheuristics for variable-size mixed optimization problems: A unified taxonomy and surveySwarm and Evolutionary Computation10.1016/j.swevo.2024.10164289(101642)Online publication date: Aug-2024
https://doi.org/10.1016/j.swevo.2024.101642
Sharifi SShin DBriand LAschbacher N(2023)Identifying the Hazard Boundary of ML-Enabled Autonomous Systems Using Cooperative Coevolutionary SearchIEEE Transactions on Software Engineering10.1109/TSE.2023.332757549:12(5120-5138)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3327575
Ma XHuang ZLi XQi YWang LZhu Z(2023)Multiobjectivization of Single-Objective Optimization in Evolutionary Computation: A SurveyIEEE Transactions on Cybernetics10.1109/TCYB.2021.312078853:6(3702-3715)Online publication date: Jun-2023
https://doi.org/10.1109/TCYB.2021.3120788
Show More Cited By

Index Terms

On identifying global optima in cooperative coevolution

Recommendations

Advanced tutorial on coevolution
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

The advanced tutorial on coevolution continues the topics covered in the introductory coevolution tutorial with a view towards research conducted in the last eight years. We will explore two themes which have recently been identified: interaction, which ...
Supportive coevolution
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Automatically configuring and dynamically controlling an Evolutionary Algorithm's (EA's) parameters is a complex task, yet doing so allows EAs to become more powerful and require less problem specific tuning to become effective. Supportive Coevolution ...
Solving a large sudoku by co-evolving numerals
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Recently we introduced an approach to solving Sudoku problems with co-evolution [4]: Resource-defined Fitness Sharing for Sudoku (RFSS). The idea is to find a set of non-conflicting numerals such that every cell in the puzzle is "covered" by a numeral. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

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: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
329
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Talbi E(2024)Metaheuristics for variable-size mixed optimization problems: A unified taxonomy and surveySwarm and Evolutionary Computation10.1016/j.swevo.2024.10164289(101642)Online publication date: Aug-2024
https://doi.org/10.1016/j.swevo.2024.101642
Sharifi SShin DBriand LAschbacher N(2023)Identifying the Hazard Boundary of ML-Enabled Autonomous Systems Using Cooperative Coevolutionary SearchIEEE Transactions on Software Engineering10.1109/TSE.2023.332757549:12(5120-5138)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3327575
Ma XHuang ZLi XQi YWang LZhu Z(2023)Multiobjectivization of Single-Objective Optimization in Evolutionary Computation: A SurveyIEEE Transactions on Cybernetics10.1109/TCYB.2021.312078853:6(3702-3715)Online publication date: Jun-2023
https://doi.org/10.1109/TCYB.2021.3120788
Rashid AAhmed MSikos LHaskell-Dowland P(2022)Anomaly Detection in Cybersecurity Datasets via Cooperative Co-evolution-based Feature SelectionACM Transactions on Management Information Systems10.1145/349516513:3(1-39)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.1145/3495165
Li GWang GWang S(2021)Two-Population Coevolutionary Algorithm with Dynamic Learning Strategy for Many-Objective OptimizationMathematics10.3390/math90404209:4(420)Online publication date: 20-Feb-2021
https://doi.org/10.3390/math9040420
Rashid AAhmed MSikos LHaskell-Dowland P(2020)Cooperative co-evolution for feature selection in Big Data with random feature groupingJournal of Big Data10.1186/s40537-020-00381-y7:1Online publication date: 4-Dec-2020
https://doi.org/10.1186/s40537-020-00381-y
Rashid AAhmed MSikos LHaskell-Dowland P(2020)A Novel Penalty-Based Wrapper Objective Function for Feature Selection in Big Data Using Cooperative Co-EvolutionIEEE Access10.1109/ACCESS.2020.30166798(150113-150129)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3016679
N M Bazlur Rashid AChoudhury T(2019)Knowledge management overview of feature selection problem in high-dimensional financial data: cooperative co-evolution and MapReduce perspectivesProblems and Perspectives in Management10.21511/ppm.17(4).2019.2817:4(340-359)Online publication date: 26-Dec-2019
https://doi.org/10.21511/ppm.17(4).2019.28
Ma XLi XZhang QTang KLiang ZXie WZhu Z(2019)A Survey on Cooperative Co-Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.286877023:3(421-441)Online publication date: Jun-2019
https://doi.org/10.1109/TEVC.2018.2868770
Duan QQu LShao CShi Y(2019)Hierarchical Decomposition based Cooperative Coevolution for Large-Scale Black-Box Optimization2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9003169(2690-2697)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9003169
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Advanced tutorial on coevolution

Supportive coevolution

Solving a large sudoku by co-evolving numerals