Utilising Restricted For-Loops in Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4340

  author =       "Xiang Li",
  title =        "Utilising Restricted For-Loops in Genetic
  school =       "Department of Computer Science, RMIT",
  year =         "2007",
  address =      "Australia",
  month =        "28 " # feb,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://goanna.cs.rmit.edu.au/~vc/papers/li-phd.pdf",
  size =         "223 pages",
  abstract =     "Genetic programming is an approach that uses the power
                 of evolution to allow computers to evolve programs with
                 little human involvement. It has demonstrated its
                 usefulness in solving many experimental problems as
                 well as many real world problems. However, it suffers
                 from weaknesses in using repetitions effectively. While
                 loops are natural components of most programming
                 languages and appear in every reasonably-sized
                 application, they are rarely used in genetic
                 programming. Extending the power of genetic programming
                 by encouraging more use of loops will bridge the gap
                 between the current state-of-the-art in programs
                 evolved with genetic programming and those written by
                 humans, and improve this automatic programming

                 The goal of the work is to investigate a number of
                 restricted looping constructs in which infinite loops
                 are not possible and to determine whether any
                 significant benefits can be obtained with these
                 restricted loops. Possible benefits include: Solving
                 problems which cannot be solved without loops, evolving
                 smaller sized solutions which can be more easily
                 understood by human programmers and solving existing
                 problems quicker by using fewer evaluations.

                 In this thesis, a number of explicit restricted loop
                 formats were formulated and tested on the Santa Fe ant
                 problem, a modified ant problem, a sorting problem, a
                 visit-every-square problem and a difficult object
                 classification problem. A maximum number of iterations
                 based on domain knowledge was used to avoid the
                 infinite iteration problem. The experimental results
                 showed that these explicit loops can be successfully
                 used in genetic programming. The evolutionary process
                 can decide when, where and how to use them. Runs with
                 these loops tended to generate smaller sized solutions
                 in fewer evaluations. Solutions with loops were found
                 to some problems that could not be solved without

                 From these experimental problems, the modified ant
                 problem and the visit-every-square problem were
                 selected to analyse differences between using and not
                 using loops with respect to the search spaces, the
                 patterns captured by genetic programming and the
                 sensitivity to changes in the maximum number of
                 iterations on CPU time. The analysis of the search
                 spaces found that there were more fitter programs
                 within a limited tree depth for programs with loops. To
                 solve the same problem without loops required a larger
                 tree depth and this exponentially increases the number
                 of possible programs and may decrease the chance of
                 finding a good solution. The analysis of the patterns
                 captured found that runs with loops captured repetitive
                 patterns of the problem domain and repeated them to
                 improve the fitness. The analysis of the effect of
                 different values of maximum number of iterations showed
                 that CPU time per evaluation increased as the maximum
                 number of iterations increased. However, solutions were
                 found in fewer evaluations. There was a large range of
                 values for maximum number of iterations for which the
                 overall CPU time was lower. Good choices for maximum
                 number of iterations could be found from domain

                 Overall, the results and analysis have established that
                 there are significant benefits in using loops in
                 genetic programming. Restricted loops can avoid the
                 difficulties of evolving consistent programs and the
                 infinite iterations problem. Researchers and
                 practioners of genetic programming should not be afraid
                 of loops.",

Genetic Programming entries for Xiang Li