Advanced techniques for the creation and propagation of modules in cartesian genetic programming

ABSTRACT

The choice of an appropriate hardware representation model is key to successful evolution of digital circuits. One of the most popular models is cartesian genetic programming, which encodes an array of logic gates into a chromosome. While several smaller circuits have been successfully evolved on this model, it lacks scalability. A recent approach towards scalable hardware evolution is based on the automated creation of modules from primitive gates.

In this paper, we present two novel approaches for module creation, an age-based and a cone-based technique. Further, we detail a cone-based crossover operator for use with cartesian genetic programming. We evaluate the different techniques and compare them with related work. The results show that age-based module creation is highly effective, while cone-based approaches are only beneficial for regularly structured, multiple output functions such as multipliers.

REFERENCES

• 1: X. Cai, S. L. Smith, and A. M. Tyrrell. Positional Independence and Recombination in Cartesian Genetic Programming. In Proceedings 9th European Conference on Genetic Programming (EuroGP), volume 3905 of LNCS, pages 351--360. Springer, 2006.
• 2: Janet Clegg , James Alfred Walker , Julian Frances Miller, A new crossover technique for Cartesian genetic programming, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277276]
• 3: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 4: Ernesto Damiani , Valentino Liberali , Andrea Tettamanzi, Evolutionary Design of Hashing Function Circuits Using an FPGA, Proceedings of the Second International Conference on Evolvable Systems: From Biology to Hardware, p.36-46, September 23-25, 1998
• 5: H. de Garis. Evolvable Hardware -- Genetic Programming of a Darwin Machine. In Proceedings International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA). Springer, 1993.
• 6: K. Glette and J. Torresen. A Flexible On-Chip Evolution System Implemented on a Xilinx Virtex-II Pro Device. In Proceedings 6th International Conference on Evolvable Systems (ICES), volume 3637 of LNCS, pages 66--75. Springer, 2005.
• 7: Kyrre Glette , Jim Torresen , Moritoshi Yasunaga, Online Evolution for a High-Speed Image Recognition System Implemented On a Virtex-II Pro FPGA, Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems, p.463-470, August 05-08, 2007 [doi>10.1109/AHS.2007.83]
• 8: Tetsuya Higuchi , Nobuki Kajihara, Evolvable hardware chips for industrial applications, Communications of the ACM, v.42 n.4, p.60-66, April 1999 [doi>10.1145/299157.299172]
• 9: Tetsuya Higuchi , Tatsuya Niwa , Toshio Tanaka , Hitoshi Iba , Hugo de Garis , Tatsumi Furuya, Evolving hardware with genetic learning: a first step towards building a Darwin machine, Proceedings of the second international conference on From animals to animats 2 : simulation of adaptive behavior: simulation of adaptive behavior, p.417-424, August 1993, Honolulu, Hawai, United States
• 10: I. Kajitani, I. Sekita, N. Otsu, and T. Higuchi. Improvements to the Action Decision Rate for a Multi-Function Prosthetic Hand. In Proceedings 1st International Symposium on Measurement, Analysis and Modeling of Human Functions, 2001.
• 11: Didier Keymeulen , Marc Durantez , Kenji Konaka , Yasuo Kuniyoshi , Tetsuya Higuchi, An Evolutionary Robot Navigation System Using a Gate-Level Evolvable Hardware, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.195-209, October 07-08, 1996
• 12: Didier Keymeulen , Masaya Iwata , Yasuo Kuniyoshi , Tetsuya Higuchi, Online Evolution for a Self-Adapting Robotic Navigation System Using Evolvable Hardware, Artificial Life, v.4 n.4, p.359-393, October 1998 [doi>10.1162/106454698568648]
• 13: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 14: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 15: R. A. Krohling, Y. Zhou, and A. M. Tyrrell. Evolving FPGA-based Robot Controllers using an Evolutionary Algorithm. In Proceedings of the 1st International Conference on Artificial Immune Systems (ICARIS), pages 41--46, September 2002.
• 16: Weixin Liu , Masahiro Murakawa , Tetsuya Higuchi, ATM Cell Scheduling by Function Level Evolvable Hardware, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.180-192, October 07-08, 1996
• 17: J. Miller. An Empirical Study of the Efficiency of Learning Boolean Functions using a Cartesian Genetic Programming Approach. In Proceedings Genetic and Evolutionary Computation Conference (GECCO), pages 1135--1142, 1999.
• 18: Julian F. Miller , Peter Thomson, Cartesian Genetic Programming, Proceedings of the European Conference on Genetic Programming, p.121-132, April 15-16, 2000
• 19: J. F. Miller, P. Thomson, and T. Fogarty. Designing Electronic Circuits Using Evolutionary Algorithms. Arithmetic Circuits: A Case Study. In "Genetic Algorithms and Evolution Strategies in Engineering and Computer Science, pages 105--131. John Wiley and Sons, 1998.
• 20: Mehrdad Salami , Masahiro Murakawa , Tetsuya Higuchi, Data Compression Based on Evolvable Hardware, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.169-179, October 07-08, 1996
• 21: L. Sekanina. Virtual Reconfigurable Circuits for Real-World Applications of Evolvable Hardware. In Proceedings 5th International Conference on Evolvable Systems (ICES), pages 186--197. Springer, 2003.
• 22: L. Sekanina and V. Drabek. Automatic Design of Image Operators Using Evolvable Hardware. In Proceedings 5th IEEE Design and Diagnostics of Electronic Circuits and Systems, pages 132--139, 2002.
• 23: Adrian Thompson, Evolving Electronic Robot Controller that Exploit Hardware Resources, Proceedings of the Third European Conference on Advances in Artificial Life, p.640-656, June 04-06, 1995
• 24: Adrian Thompson , Paul Layzell, Analysis of unconventional evolved electronics, Communications of the ACM, v.42 n.4, p.71-79, April 1999 [doi>10.1145/299157.299174]
• 25: J. Torresen. Two-Step Incremental Evolution of a Prosthetic Hand Controller Based on Digital Logic Gates. In Proceedings 4th International Conference on Evolvable Hardware (ICES), volume 2210 of Lecture Notes in Computer Science. Springer, 2001.
• 26: J. Torresen. Evolving Multiplier Circuits by Training Set and Training Vector Partitioning. In Proceedings 6th International Conference on Evolvable Hardware (ICES, pages 228--237. Springer, 2003.
• 27: Vesselin K. Vassilev , Julian F. Miller , Terence C. Fogarty, On the Nature of Two-Bit Multiplier Landscapes, Proceedings of the 1st NASA/DOD workshop on Evolvable Hardware, p.36, July 19-21, 1999
• 28: J. A. Walker and J. F. Miller. Evolution and Acquisition of Modules in Cartesian Genetic Programming. In Proceedings 7th European Conference on Genetic Programming (EuroGP), volume 3003 of LNCS, pages 187--197. Springer, April 2004.
• 29: J. A. Walker and J. F. Miller. Improving the Evolvability of Digital Multipliers Using Embedded Cartesian Genetic Programming and Product Reduction. In Proceedings 6th International Conference on Evolvable Systems(ICES), volume 3637 of LNCS, pages 131--142. Springer, 2005.
• 30: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
automatically defined functions (adfs), cartesian genetic programming (cgp), crossover operator, embedded cartesian genetic programming (ecgp), module acquisition