- author = "Xiang Li",
- title = "Utilising Restricted For-Loops in Genetic Programming",
- 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",
-
URL = "
https://researchrepository.rmit.edu.au/discovery/fulldisplay?docid=alma9921861226701341&context=L&vid=61RMIT_INST:ResearchRepository&lang=en&search_scope=ResearchETD&adaptor=Local%20Search%20Engine&tab=Research&query=any,contains,An%20Analysis%20of%20Explicit%20Loops%20in%20Genetic%20Programming&offset=0",
-
URL = "http://researchbank.rmit.edu.au/view/rmit:6317",
- 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
method.
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.",
- notes = "Jan 2021 http://researchbank.rmit.edu.au/view/rmit:6317 broken, given replacement (researchrepository.rmit.edu.au/) flaky",
