An evolvability-enhanced artificial embryogeny for generating network structures

ABSTRACT

Existing Artificial Embryogeny (AE) models are insufficient to generate a network structure because the possible links are limited to those connecting nodes with their predefined neighbors. We propose a novel network generating AE model capable of generating links connected to predefined neighbors as well those to non-neighbors. This mechanism provides additional flexibility in phenotypes than existing AE models. Our AE model also incorporates a heterogeneous mutation mechanism to accelerate the convergence to a high fitness value or enhance the evolvability. We conduct experiments to generate a typical 2D grid pattern as well as a robot with a network structure consisting of masses, springs and muscles. In both tasks, results show that our AE model has higher evolvability, sufficient to search a larger space than that of conventional AE models bounded by local neighborhood relationships.

References

1. P. J. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-1999, pages 35--43. Morgan Kaufmann Publishers, July 1999.
2. P. Eggenberger. Evolving morphogenesis of simulated 3d organisms based on differential gene expression. In Proceedings of the Fourth European Conference on Artificial Life, pages 205--213. MIT Press, July 1997.
3. D. Federici. Evolving a neurocontroller through a process of embryogeny. In Proceedings of the 8th International Conference on the Simulation of Adaptive Behavior: From Animals To Animats, 8; pages 373--382. MIT Press, July 2004.
4. S. Harding and J. Miller. The dead state: A comparison between direct and developmental encodings. In Genetic and Evolutionary Computation Conference (GECCO-2006) Workshop Program: Complexity through Development and Self-Organizing Representations (CODESOAR), ACM, July 2006.
5. G. S. Horby and J. B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3), 223--246. 2002.
6. R. Kicinger. Generative design in civil engineering using cellular automata. In New Kind of Science 2006 Wolfram Science Conference. June 2006.
7. T. Kowaliw, P. Grogono, and N. Kharma. The evolution of structural design through artificial embryogeny. In Proceedings of IEEE First International Symposium on Artificial Life, pages 425--432. IEEE, April 2007.
8. T. Kowaliw, P. Grogono, and N. Kharma. Environment as a spatial constraint on the growth of structural form. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2007, pages 1037--1044. ACM, July 2007.
9. S. Kumar and P. J. Bentley. The ABCs of evolutionary design: Investigating the evolvability of embryogenies for morphogenesis. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-1999, pages 164--170. Morgan Kaufmann Publishers, July 1999.
10. S. Lucas. Evolving spring-mass models: test-bed for graph encoding schemes. In Proceedings of IEEE Congress on Evolutionary Computation, CEC 2002. pages 1952--1957. IEEE, May 2002.
11. J. F. Miller. Evolving a self-repairing, self-regulating, French flag organism. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2004, pages 129--139. Springer Verlag, June 2004.
12. J. F. Miller and Peter Thompson. Beyond the complexity ceiling: Evolution, Emergence and Regeneration. In Genetic and Evolutionary Computation Conference Workshop on Regeneration and Learning in Developmental Systems, GECCO-2004, Springer Verlag, June 2004.
13. Soda Creative Ltd. Sodaplay homepage. http://sodaplay.com/
14. K. O. Stanley. Comparing Phenotypes with Natural Biological Patterns. In Genetic and Evolutionary Computation Conference (GECCO-2006) Workshop Program: Complexity through Development and Self-Organizing Representations (CODESOAR), ACM, July 2006.
15. K. O. Stanley and R. Miikkulainen. A taxonomy for artificial embryogeny. Artificial Life, 9(2): 93--130. April 2003.
16. S. Uyar, S. Sariel and G. Eryigit. A gene based adaptive strategy for genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2004, pages 271--281. Springer Verlag, June 2004.
17. S. Viswanathan and J. Pollack. How artificial ontogenies can retard evolution. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2005, pages 273--280. ACM, June 2005.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

  • Machine learning

    • Machine learning approaches

      • Neural networks

• Hardware

  • Emerging technologies

    • Circuit substrates

      • Cellular neural networks

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory