DECA: dimension extracting coevolutionary algorithm

ABSTRACT

Coevolution has often been based on averaged outcomes, resulting in unstable evaluation. Several theoretical approaches have used archives to provide stable evaluation. However, the number of tests required by some of these approaches can be prohibitive of practical applications. Recent work has shown the existence of a set of underlying objectives which compress evaluation information into a potentially small set of dimensions. We consider whether these underlying objectives can be approximated online, and used for evaluation in a coevolution algorithm. The Dimension Extracting Coevolutionary Algorithm (DECA) is compared to several recent reliable coevolution algorithms on a Numbers game problem, and found to perform efficiently. Application to the more realistic Tartarus problem is shown to be feasible. Implications for current coevolution research are discussed.

REFERENCES

• 1: Ashlock, D., Willson, S., & Leahy, N. (2004). Coevolution and tartarus. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 1618--1624, Portland, Oregon. IEEE Press.
• 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: Anthony Bucci , Jordan B. Pollack, On identifying global optima in cooperative coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068098]
• 5: Bucci, A., Pollack, J. B., & De Jong, E. D. (2004). Automated extraction of problem structure. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-04, pp. 501--512.
• 6: De Jong, E. D. (2004a). The Incremental Pareto-Coevolution Archive. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-04, pp. 525--536.
• 7: De Jong, E. D. (2004b). Towards a bounded Pareto-Coevolution archive. In Proceedings of the Congress on Evolutionary Computation, CEC-04, pp. 2341--2348.
• 8: Edwin de Jong, The MaxSolve algorithm for coevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068091]
• 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: Susan L. Epstein, Toward an Ideal Trainer, Machine Learning, v.15 n.3, p.251-277, June 1994 [doi>10.1023/A:1022637925775]
• 11: Sevan Gregory Ficici , Jordan B. Pollack, Solution concepts in coevolutionary algorithms, 2004
• 12: 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
• 13: 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
• 14: Ficici, S. G., & Pollack, J. B. (2003). A game-theoretic memory mechanism for coevolution. In Cantúú-Paz, E., et al. (Ed.), Genetic and Evolutionary Computation - GECCO-2003, Vol. 2723 of LNCS, pp. 286--297, Chicago. Springer-Verlag.
• 15: 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
• 16: Juillé, H., & Pollack, J. B. (1998). Coevolving the "ideal" trainer: Application to the discovery of cellular automata rules. In Proceedings of the Third Annual Genetic Programming Conference.
• 17: Christopher Darrell Rosin, Coevolutionary search among adversaries, University of California at San Diego, La Jolla, CA, 1997
• 18: Astro Teller, The evolution of mental models, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 19: 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
• 20: Watson, R. A., & Pollack, J. B. (2001). Coevolutionary dynamics in a minimal substrate. In Spector, L., et al. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-01, pp. 702--709, San Francisco, CA. Morgan Kaufmann.
• 21: Watson, R. A., & Pollack, J. B. (2003). A computational model of symbiotic composition in evolutionary transitions. Biosystems, 69 (2-3), 187--209. Special Issue on Evolvability, ed. Nehaniv.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
DECA, coevolution, dimension extraction, underlying objectives