Investigating the performance of module acquisition in cartesian genetic programming

ABSTRACT

Embedded Cartesian Genetic Programming (ECGP) is a form of the graph based Cartesian Genetic Programming (CGP) in which modules are automatically acquired and evolved. In this paper we compare the efficiencies of the ECGP and CGP techniques on three classes of problem: digital adders, digital multipliers and digital comparators. We show that in most cases ECGP shows a substantial improvement in performance over CGP and that the computational speedup is more pronounced on larger problems.

REFERENCES

• 1: Angeline, P. J. Pollack, J. (1993) Evolutionary Module Acquisition, Proceedings of the 2nd Annual Conference on Evolutionary Programming, pp. 154--163, MIT Press, Cambridge.
• 2: Dessi, A. Giani, A. Starita, A. (1999) An Analysis of Automatic Subroutine Discovery in Genetic Programming, GECCO 1999: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 996--1001, Morgan-Kaufmann, San Francisco.
• 3: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 4: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 5: Miller, J. F. , Thomson, P., and Fogarty T. C. (1997) Designing Electronic Circuits Using Evolutionary Algorithms. Arithmetic Circuits: A Case Study, Genetic Algorithms and Evolution Strategies in Engineering and Computer Science: Recent Advancements and Industrial Applications. Editors: D. Quagliarella, J. Periaux, C. Poloni and G. Winter, Wiley.
• 6: Miller, J. F. (1999) An Empirical Study of the Efficiency of Learning Boolean Functions using a Cartesian Genetic Programming Approach, GECCO 1999: Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida, pp 1135--1142, Morgan Kaufmann, San Francisco.
• 7: Julian F. Miller , Peter Thomson, Cartesian Genetic Programming, Proceedings of the European Conference on Genetic Programming, p.121-132, April 15-16, 2000
• 8: Poli, R. (1996), Parallel Distributed Genetic Programming, Technical Report, CSRP-96-15, University of Birmingham, UK.
• 9: Rosca, J. P. (1995) Genetic Programming Exploratory Power and the Discovery of Functions, Proceedings of the 4th Annual Conference of Evolutionary Programming, San Diego, pp 719--736, MIT Press, Cambridge.
• 10: Lee Spector, Simultaneous evolution of programs and their control structures, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
• 11: Spector, L. (2001) Autoconstructive Evolution: Push, PushGP, and Pushpop, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp. 137--146. San Francisco, CA: Morgan Kaufmann Publishers
• 12: Terry Van Belle , David H. Ackley, Code Factoring And The Evolution Of Evolvability, Proceedings of the Genetic and Evolutionary Computation Conference, p.1383-1390, July 09-13, 2002
• 13: Vesselin K. Vassilev , Julian F. Miller, The Advantages of Landscape Neutrality in Digital Circuit Evolution, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.252-263, April 17-19, 2000
• 14: Vesselin K. Vassilev , Julian F. Miller, Scalability Problems of Digital Circuit Evolution: Evolvability and Efficient Designs, Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware, p.55, July 13-15, 2000
• 15: Walker, J. A. Miller, J. F. (2004) Evolution and Acquisition of Modules in Cartesian Genetic Programming, Proc. of the 7th European Conference on Genetic Programming, Lecture Notes in Computer Science, Vol. 3003, pp 187--197, Springer-Verlag, Berlin.
• 16: Woodward, J. R. (2003) Modularity in Genetic Programming, Proceedings of the Fifth European Conference on Genetic Programming, Lecture Notes in Computer Science, Vol. 2610, pp. 258--267, Springer-Verlag, Berlin.
• 17: 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, Performance

Keywords:
cartesian genetic programming, computational effort, digital adders, digital comparators, digital multipliers, modularity, module acquisition