The MaxSolve algorithm for coevolution

ABSTRACT

Coevolution can be used to adaptively choose the tests used for evaluating candidate solutions. A long-standing question is how this dynamic setup may be organized to yield reliable search methods. Reliability can only be considered in connection with a particular solution concept specifying what constitutes a solution. Recently, monotonic coevolution algorithms have been proposed for several solution concepts. Here, we introduce a new algorithm that guarantees monotonicity for the solution concept of maximizing the expected utility of a candidate solution. The method, called MaxSolve, is compared to the IPCA algorithm and found to perform more efficiently for a range of parameter values on an abstract test problem.

REFERENCES

• 1: Angeline, P. J., & Pollack, J. B. (1994). Coevolving high-level representations. In Langton, C. G. (Ed.), Artificial Life III, Vol. XVII of SFI Studies in the Sciences of Complexity, pp. 55--71, Redwood City, CA. Addison-Wesley.
• 2: Axelrod, R. (1987). The evolution of strategies in the iterated prisoner's dilemma. In Davis, L. (Ed.), Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence, pp. 32--41, London. Pitman Publishing.
• 3: Barricelli, N. A. (1962). Numerical testing of evolution theories. Part I: Theoretical introduction and basic tests. Acta Biotheoretica, 16 (1--2), 69--98.
• 4: Barricelli, N. A. (1963). Numerical testing of evolution theories. Part II: Preliminary tests of performance, symbio-genesis and terrestrial life. Acta Biotheoretica, 16 (3--4), 99--126.
• 5: Bucci, A., & Pollack, J. B. (2002). Order-theoretic analysis of coevolution problems: Coevolutionary statics. In Proceedings of the GECCO-02 Workshop on Coevolution: Understanding Coevolution.
• 6: Bucci, A., & Pollack, J. B. (2003). A mathematical framework for the study of coevolution. In Foundations of Genetic Algorithms (FOGA-2002), San Francisco, CA. Morgan Kaufmann.
• 7: De Jong, E. D. (2004a). Guaranteeing progress in pareto-coevolution. In Proceedings of the Annual Machine Learning Conference of Belgium and The Netherlands, BeNeLearn-04, pp. 22--29.
• 8: De Jong, E. D. (2004b). The Incremental Pareto-Coevolution Archive. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-04, pp. 525--536.
• 9: Edwin D. De Jong , Jordan B. Pollack, Ideal Evaluation from Coevolution, Evolutionary Computation, v.12 n.2, p.159-192, June 2004 [doi>10.1162/106365604773955139]
• 10: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 11: Sevan G. Ficici , Jordan B. Pollack, A Game-Theoretic Approach to the Simple Coevolutionary Algorithm, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.467-476, September 18-20, 2000
• 12: Ficici, S. G., & Pollack, J. B. (2003). A game-theoretic memory mechanism for coevolution. In Cantúú-Paz et al., E. (Ed.), Genetic and Evolutionary Computation -- GECCO-2003, Vol. 2723 of LNCS, pp. 286--297, Chicago. Springer-Verlag.
• 13: Pablo Jose Funes , Jordan B. Pollack, Evolution of complexity in real-world domains, 2001
• 14: W. Daniel Hillis, Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, v.42 n.1-3, p.228-234, June 1990
• 15: Jansen, T., & Wiegand, R. P. (2003). Exploring the explorative advantage of the cooperative coevolutionary (1+1) EA. In Cantúú-Paz, E., Foster, J. A., Deb, K., Davis, D., Roy, R., O'Reilly, U.-M., Beyer, H.-G., Standish, R., Kendall, G., Wilson, S., Harman, M., Wegener, J., Dasgupta, D., Potter, M. A., Schultz, A. C., Dowsland, K., Jonoska, N., & Miller, J. (Eds.), Genetic and Evolutionary Computation -- GECCO- 2003, Vol. 2723 of LNCS, pp. 310--321, Chicago. Springer-Verlag.
• 16: Kauffman, S. A., & Johnsen, S. (1992). Co-evolution to the edge of chaos: Coupled fitness landscapes, poised states, and co-evolutionary avalanches. In Langton, C., Taylor, C., Farmer, J., & Rasmussen, S. (Eds.), Artificial Life II, Vol. X of SFI Studies in the Sciences of Complexity, pp. 325--369. Addison-Wesley, Redwood City, CA.
• 17: Koza, J. R. (1992). Genetic evolution and co-evolution of computer programs. In Langton, C., Taylor, C., Farmer, J., & Rasmussen, S. (Eds.), Artificial Life II, Vol. X of SFI Studies in the Sciences of Complexity, pp. 603--629. Addison-Wesley, Redwood City, CA.
• 18: Lindgren, K. (1992). Evolutionary phenomena in simple dynamics. In Langton, C., Taylor, C., Farmer, J., & Rasmussen, S. (Eds.), Artificial Life II, Vol. X of SFI Studies in the Sciences of Complexity, pp. 295--312. Addison-Wesley, Redwood City, CA.
• 19: Lubberts, A., & Miikkulainen, R. (2001). Co-evolving a go-playing neural network. In Belew, R. K., & Juillé& Juilléé, H. (Eds.), Proceedings of the GECCO-01 Workshop on Coevolution: Turning Adaptive Algorithms upon Themselves, pp. 14--19.
• 20: Geoffrey F. Miller , Dave Cliff, Protean behavior in dynamic games: arguments for the co-evolution of pursuit-evasion tactics, Proceedings of the third international conference on Simulation of adaptive behavior : from animals to animats 3: from animals to animats 3, p.411-420, July 1994, Brighton, United Kingdom
• 21: Miller, J. (1989). The coevolution of automata in the repeated prisoner's dilemma. Santa Fe Institute working paper 89--003.
• 22: Miller, J. (1996). The coevolution of automata in the repeated prisoner's dilemma. Journal of Economic Behavior and Organization, 29 (1), 87--112.
• 23: Moriarty, D. E., & Miikkulainen, R. (1998). Forming neural networks through efficient and adaptive coevolution. Evolutionary Computation, 5 (4), 373--399.
• 24: Pagie, L., & Hogeweg, P. (1998). Evolutionary consequences of coevolving targets. Evolutionary Computation, 5 (4), 401--418.
• 25: Jan Paredis, Coevolutionary computation, Artificial Life, v.2 n.4, p.355-375, Summer 1995
• 26: Jordan B. Pollack , Alan D. Blair, Co-Evolution in the Successful Learning of Backgammon Strategy, Machine Learning, v.32 n.3, p.225-240, Sept. 1998 [doi>10.1023/A:1007417214905]
• 27: 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]
• 28: Reynolds, C. W. (1994). Competition, coevolution and the game of tag. In Brooks, R. A., & Maes, P. (Eds.), Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, pp. 59--69, Cambridge, MA. The MIT Press.
• 29: Christopher Darrell Rosin, Coevolutionary search among adversaries, University of California at San Diego, La Jolla, CA, 1997
• 30: Schmidhuber, J. (1999). Artificial curiosity based on discovering novel algorithmic predictability through co-evolution. In Angeline, P., Michalewicz, Z., Schoenauer, M., Yao, X., & Zalzala, A. (Eds.), Proceedings of the Congress on Evolutionary Computation, CEC-99, Vol. 3, pp. 1612--1618, Piscataway, NJ. IEEE Press.
• 31: Schmitt, L. M. (2003). Theory of coevolutionary genetic algorithms. In Guo, M., & Yang, L. T. (Eds.), Parallel and Distributed Processing and Applications, International Symposium, ISPA 2003, pp. 285--293, Berlin. Springer.
• 32: Stanley, K. O., & Miikkulainen, R. (2004). Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21, 63--100.
• 33: Richard A. Watson , Jordan B. Pollack, Symbiotic Combination as an Alternative to Sexual Recombination in Genetic Algorithms, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.425-434, September 18-20, 2000
• 34: Watson, R. A., & Pollack, J. B. (2001). Coevolutionary dynamics in a minimal substrate. In Spector, L., Goodman, E., Wu, A., Langdon, W., Voigt, H.-M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M., & Burke, E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-01, pp. 702--709, San Francisco, CA. Morgan Kaufmann.
• 35: Watson, R. A., & Pollack, J. B. (2003). A computational model of symbiotic composition in evolutionary transitions. Biosystems, 69 (2-3), 187209. Special Issue on Evolvability, ed. Nehaniv.
• 36: Werfel, J., Mitchell, M., & Crutchfield, J. P. (2000). Resource sharing and coevolution in evolving cellular automata. IEEE Transactions on Evolutionary Computation, 4 (4), 388.
• 37: Rudolf Paul Wiegand , Kenneth A. Jong, An analysis of cooperative coevolutionary algorithms, 2004
• 38: Wiegand, R. P., Liles, W., & De Jong, K. (2002). Analyzing cooperative coevolution with evolutionary game theory. In Fogel, D. B., El-Sharkawi, M. A., Yao, X., Greenwood, G., Iba, H., Marrow, P., & Shackleton, M. (Eds.), Proceedings of the 2002 Congress on Evolutionary Computation CEC2002, pp. 1600--1605. IEEE Press.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
archive, coevolution, reliability, reliable coevolution