Robustness in cooperative coevolution

ABSTRACT

Though recent analysis of traditional cooperative coevolutionary algorithms (CCEAs) casts doubt on their suitability for static optimization tasks, our experience is that the algorithms perform quite well in multiagent learning settings. This is due in part because many CCEAs may be quite suitable to finding behaviors for team members that result in good (though not necessarily optimal) performance but which are also robust to changes in other team members. Given this, there are two main goals of this paper. First, we describe a general framework for clearly defining robustness, offering a specific definition for our studies. Second, we examine the hypothesis that CCEAs exploit this robustness property during their search. We use an existing theoretical model to gain intuition about the kind of problem properties that attract populations in the system, then provide a simple empirical study justifying this intuition in a practical setting. The results are the first steps toward a constructive view of CCEAs as optimizers of robustness.

References

1. T. Bäck and H. P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1--23, 1993.]]
2. A. Bucci and J. Pollack. On identifying global optima in cooperative coevolution. In Proceedings of the 2005 Genetic and Evolutionary Computation Conference, pages 539--544. ACM Press, 2005.]]
3. D. Cliff and G. F. Miller. Tracking the red queen: Measurements of adaptive progress in co-evolutionary simulations. In Proceedings of the Third European Conference on Artificial Life, pages 200--218. Springer-Verlag, 1995.]]
4. L. Dias and J. Clmaco. On computing electres credibility indices under partial information. Journal of Multi-Criteria Decision Analysis, 8:74--92, 1999.]]
5. S. G. Ficici. Solution Concepts in Coevolutionary Algorithms. PhD thesis, Brandeis University, Boston, MA, 2004.]]
6. J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998.]]
7. P. Husbands and F. Mill. Simulated coevolution as the mechanism for emergent planning and scheduling. In Proceedings of the Fourch International Conference on Genetic Algorithms, pages 264--270. Morgan Kaufmann, 1991.]]
8. E. Jen. Santa Fe Institute program on Robustness. http://discuss.santafe.edu/robustness/, 2002.]]
9. E. Jen. Stable or robust? what's the difference? Complexity, 8(3):12--30, 2003.]]
10. P. Kouvelis and G. Yu. Robust discrete optimization and its applications. Kluwer, Dordrecht, 1997.]]
11. J. Maynard-Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.]]
12. D. Moriarty and R. Miikkulainen. Forming neural networks through efficient and adaptive coevolution. Evolutionary Computation, 5(4):373--399, 1997.]]
13. J. Mulvey, R. Vanderbei, and S. Zenios. Robust optimization of large-scale systems. Operations Research, 43:264--281, 1995.]]
14. L. Panait, S. Luke, and R. P. Wiegand. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, (To appear), 2006.]]
15. M. Potter. The Design and Analysis of a Computational Model of Cooperative CoEvolution. PhD thesis, George Mason University, Fairfax, Virginia, 1997.]]
16. M. Potter and K. De Jong. The coevolution of antibodies for concept learning. In Proceedings of the Fifth International Conference on Parallel Processing in Nature, pages 530--539. Springer-Verlag, 1998.]]
17. M. Potter and K. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1--29, 2000.]]
18. M. Potter, A. Schultz, and L. Meeden. Heterogeneity in the coevolved behaviors of mobile robots: The emergence of specialists. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 1337--1343. Morgan Kaufmann, 2001.]]
19. M. A. Potter, K. A. De Jong, and J. J. Grefenstette. A coevolutionary approach to learning sequential decision rules. In Proceedings from the Sixth International Conference on Genetic Algorithms, pages 366--372. Morgan Kaufmann, 1995.]]
20. B. Roy. A missing link in or-da: robustness analysis. Foundations of Computing and Decision Sciences, 23:141--160, 1998.]]
21. P. Vincke. Robust solutions and methods in decision-aid. Journal of Multi-Criteria Decision Analysis, 8:181--187, 1999.]]
22. M. Vose. The Simple Genetic Algorithm. MIT Press, 1999.]]
23. R. P. Wiegand. An Analysis of Cooperative Coevolutionary Algorithms. PhD thesis, George Mason University, Fairfax, Virginia, 2003.]]
24. R. P. Wiegand, W. Liles, and K. De Jong. Analyzing cooperative coevolution with evolutionary game theory. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC), pages 1600--1605. IEEE Press, 2002.]]
25. R. P. Wiegand, W. Liles, and K. De Jong. Modeling variation in cooperative coevolution using evolutionary game theory. In Foundations of Genetic Algorithms VII, pages 231--248. Morgan Kaufmann, 2002.]]

Index Terms

• Computing methodologies

  • Artificial intelligence