Created by W.Langdon from gp-bibliography.bib Revision:1.8098
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 loops.
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 knowledge.
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