Co-evolving an effective fitness sample: experiments in symbolic regression and distributed robot control

ABSTRACT

We investigate two techniques for co-evolving and sampling from a population of fitness cases, and compare these with a random sampling technique. We design three symbolic regression problems on which to test these techniques, and also measure their relative performance on a modular robot control problem. The methods have varying relative performance, but in all of our experiments, at least one of the co-evolutionary methods outperforms the random sampling method by guiding evolution, with substantially fewer fitness evaluations, toward solutions that generalize best on an out-of-sample test set.

REFERENCES

• 1: Forrest H. Bennett, III , Eleanor G. Rieffel, Design of Decentralized Controllers for Self-Reconfigurable Modular Robots Using Genetic Programming, Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware, p.43, July 13-15, 2000
• 2: Forrest H. Bennett, III , Brad Dolin , Eleanor G. Rieffel, Programmable Smart Membranes: Using Genetic Programming to Evolve Scalable Distributed Controllers for a Novel Self-Reconfigurable Modular Robotic Application, Proceedings of the 4th European Conference on Genetic Programming, p.234-245, April 18-20, 2001
• 3: Bojinov, Hristo, Casal, Arancha, and Hogg, Tad. "Emergent Structures in Modular Self-reconfigurable Robots." IEEE Intl. Conf. on Robotics and Automation (ICRA), 2000.
• 4: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 5: Brad Dolin , Forrest H. Bennett, III , Eleanor G. Rieffel, Methods For Evolving Robust Distributed Robot Control Software: Coevolutionary And Single Population Techniques, Proceedings of the The 3rd NASA/DoD Workshop on Evolvable Hardware, p.21, July 12-14, 2001
• 6: Ficici, Sevan G., Pollack, Jordan B. "Pareto Optimality in Coevolutionary Learning." Computer Science Technical Report CS-01-216, 2001.
• 7: Floreano, D., Mondada, F., and Nolfi, S. "Co-evolution and Ontogenetic Change in Competing Robots." Robotics and Autonomous Systems, 1999.
• 8: Haith, Gary L., Colombano, Silvano P., Lohn, Jason D., and Stassinopoulos, Dimitris. "Coevolution for Problem Simplification." Proc. 1999 Genetic and Evolutionary Computation Conference, (GECCO-99), 1999.
• 9: Thomas Haynes , Roger L. Wainwright , Sandip Sen , Dale A. Schoenefeld, Strongly Typed Genetic Programming in Evolving Cooperation Strategies, Proceedings of the 6th International Conference on Genetic Algorithms, p.271-278, July 15-19, 1995
• 10: Hillis, Daniel W. "Co-evolving Parasites Improve Simulated Evolution as an Optimization Procedure." Artificial Life II, Addison-Wesley, 1991.
• 11: Hugues Juillé, Incremental Co-Evolution of Organisms: A New Approach for Optimization and Discovery of Strategies, Proceedings of the Third European Conference on Advances in Artificial Life, p.246-260, June 04-06, 1995
• 12: Juillé, Hugue, Pollack, Jordan B. "Coevolving the 'Ideal' Trainer: Application to the Discovery of Cellular Automata Rules." Proceedings of the Third Annual Genetic Programming Conference, 1998.
• 13: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 14: Lee, W., Hallam, J., and Lund, H. "A Hybrid GP/GA Approach for Coevolving Controllers and Robot Bodies to Achieve Fitness-Specified Tasks." Proceedings of IEEE 3rd International Conference on Evolutionary Computation, 1996.
• 15: Sean Luke , Charles Hohn , Jonathan Farris , Gary Jackson , James A. Hendler, Co-evolving Soccer Softbot Team Coordination with Genetic Programming, RoboCup-97: Robot Soccer World Cup I, p.398-411, January 1998
• 16: McNutt, Greg. "Using Co-evolution to Produce Robust Robot Control." Genetic Algorithms and Genetic Programming at Stanford, (Stanford University Bookstore) 1997.
• 17: Christopher D. Rosin , Richard K. Belew, Methods for Competitive Co-Evolution: Finding Opponents Worth Beating, Proceedings of the 6th International Conference on Genetic Algorithms, p.373-381, July 15-19, 1995
• 18: Christopher Darrell Rosin, Coevolutionary search among adversaries, University of California at San Diego, La Jolla, CA, 1997
• 19: Moshe Sipper, Co-evolving non-uniform cellular automata to perform computations, Physica D, v.92 n.3-4, p.193-208, May 1, 1996 [doi>10.1016/0167-2789(95)00286-3]
• 20: Soule, T. "Using Genetic Algorithms to Evolve Cooperative Teams." Proceedings of the Genetic and Evolutionary Computation Conference, 2001
• 21: Werfel, Justin, Mitchell, Melanie, and Crutchfield, James P. "Resource Sharing and Coevolution in Evolving Cellular Automata." IEEE Trans. Evol. Comp., 1999.
• 22: Yim, Mark, Lamping, John, Mao, Eric, Chase, J. Geoffrey. "Rhombic Dodecahedron Shape for Self-Assembling Robots." Xerox PARC SPL TechReport P9710777, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
co-evolution, distributed control, fitness cases, genetic algorithms, genetic programming, robot control, symbolic regression