Automatic Construction of Programs Using Dynamic Ant Programming
Shinichi Shirakawa, Shintaro Ogino, Tomoharu Nagao · InTech eBooks · 2011
IntroductionAutomatic programming is the research field of generating computer programs automatically.Genetic programming (GP) (Koza, 1992;1994) is a typical example of automatic programming, which was proposed by Koza.GP evolves computer programs with tree structure based on genetic algorithm (GA).GP has, however, the problem of bloating (Langdon & Poli, 1998;Poli, 2003), the growth of the average size of an individual in the population.This chapter introduces a new method for automatic programming using ant colony optimization (ACO) (Dorigo et al., 1999;Dorigo & Stutzle, 2004).ACO is a technique for solving combinatorial optimization problems.ACO algorithm is inspired by the behavior of the ants.Several automatic programming techniques using ACO were investigated (Engelbrecht, 2006).Typical examples are ant programming (AP) (Roux & Fonlupt, 2000), ant colony programming (ACP) (Boryczka & Czech, 2002), AntTAG (Abbass et al., 2002) and generalized ant programming (GAP) (Keber & Schuster, 2002).AP is similar to Probabilistic Incremental Program Evolution (PIPE) (Salustowicz & Schmidhuber, 1997), and it was used to solve the symbolic regression problems.PIPE generates successive populations from a probabilistic prototype tree.ACP was used to solve the symbolic regression problems with two different versions that are the expression approach and the program approach.AntTAG and GAP are grammar-based work.The method proposed in this chapter is named dynamic ant programming (DAP).DAP is based on ACO and generates desired programs using the dynamically changing pheromone table.The nodes (terminal and nonterminal) are selected using the value of the pheromone table.The higher the rate of pheromone, the higher is the probability that it can be chosen.The unnecessary node in DAP is deleted according to pheromone value.Therefore, the average size of programs tends to be small, and it is possible to search desired programs effectively.In order to verify the effectiveness, we applied the proposed method to the symbolic regression problem that is widely used as a test problem for GP systems.We compare the performance of DAP to GP and show the effectiveness of DAP.In order to investigate the influence of several parameters, we compare experimental results obtained using different settings.This chapter consists of five sections.Section 2 is an overview of some related works.Section 3 describes DAP.Several experiments are shown in Section 4. Section 5 is devoted to the conclusions and the discussion of future works.