On identifying global optima in cooperative coevolution

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.
• 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.
• 3: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 4: Sevan G. Ficici , Jordan B. Pollack, Pareto Optimality in Coevolutionary Learning, Proceedings of the 6th European Conference on Advances in Artificial Life, p.316-325, September 10-14, 2001
• 5: C. M. Fonseca and P. J. Fleming. An Overview of Evolutionary Algorithms in Multiobjective Optimization. Evolutionary Computation, 3(1):1--16, 1995.
• 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.
• 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.
• 8: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 9: Christopher Darrell Rosin, Coevolutionary search among adversaries, University of California at San Diego, La Jolla, CA, 1997
• 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.
• 11: Rudolf Paul Wiegand , Kenneth A. Jong, An analysis of cooperative coevolutionary algorithms, 2004

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory

Keywords:
coevolution, cooperative coevolution, pareto coevolution