Enhanced generalized ant programming (EGAP)

ABSTRACT

This paper begins by reviewing different methods of automatic programming while emphasizing the technique of Ant Programming (AP). AP uses an ant foraging metaphor in which ants generate a program by moving through a graph. Generalized Ant Programming (GAP) uses a context-free grammar and an Ant Colony System (ACS) to guide the program generation search process. There are two enhancements to GAP that are proposed in this paper. These are: providing a heuristic for path termination inspired by building construction and a novel pheromone placement algorithm. Three well-known problems -- Quartic symbolic regression, multiplexer, and an ant trail problem -- are experimentally compared using enhanced GAP (EGAP) and GAP. The results of the experiments show the statistically significant advantage of using this heuristic function and pheromone placement algorithm of EGAP over GAP.

REFERENCES

• 1: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 2: Boryczka, M. and Wiezorek, W.: Solving approximation problems using ant colony programming. In Proceedings of AI-METH 2003, pages 55--60, 2003.
• 3: Mariusz Boryczka, Ant Colony Programming for Approximation Problems, Proceedings of the IIS'2002 Symposium on Intelligent Information Systems, p.147-156, June 03-06, 2002
• 4: Mariusz Boryczka , Zbigniew J. Czech, Solving Approximation Problems By Ant Colony Programming, Proceedings of the Genetic and Evolutionary Computation Conference, p.133, July 09-13, 2002
• 5: Mariusz Boryczka , Zbigniew J. Czech, Solving Approximation Problems By Ant Colony Programming, Proceedings of the Genetic and Evolutionary Computation Conference, p.133, July 09-13, 2002
• 6: Boryczka, M., Czech, Z. J. and Wieczorek, W.: Ant Colony Programming for Approximation Problems, Genetic and Evolutionary Computation GECCO-2003, Lecture Notes in Computer Science 2723--2724 (E. Cantu-Paz, al., Eds.), Springer-Verlag, Berlin Heidelberg, 2003. Fundamenta Informaticae 68 (2005) 1--191.
• 7: Mariusz Boryczka, Eliminating Introns in Ant Colony Programming, Fundamenta Informaticae, v.68 n.1-2, p.1-19, April 2005
• 8: Christian Keber , Matthias G. Schuster, Option Valuation With Generalized Ant Programming, Proceedings of the Genetic and Evolutionary Computation Conference, p.74-81, July 09-13, 2002
• 9: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 10: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 11: John R. Koza , David Andre , Forrest H. Bennett , Martin A. Keane, Genetic Programming III: Darwinian Invention & Problem Solving, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 12: O'Neill M., and Brabazon A.: Grammatical Swarm. In: LNCS 3102 Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2004. Seattle, WA, USA, pp. 163--174, Springer, Berlin, 2004.
• 13: Michael O'Neill , Anthony Brabazon, Grammatical Swarm: The generation of programs by social programming, Natural Computing: an international journal, v.5 n.4, p.443-462, November 2006 [doi>10.1007/s11047-006-9007-7]
• 14: Michael O'Neill , Conor Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, Kluwer Academic Publishers, Norwell, MA, 2003
• 15: Roux, O., and Fonlupt, C., 2000, Ant Programming: Or How to Use Ants for Automatic Programming, in Proceedings of ANTS' 2000, ed. By M. Dorigo et al. pp. 121--129.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Design, Performance

Keywords:
ant programming, automatic programming, enhanced generalized ant programming, generalized ant programming, heuristic