- author = "Takuya Ito",
- title = "Efficient program generation by genetic programming",
- school = "School of Information Science, Japan Advanced Instutute of Science and Technology",
- year = "1999",
- address = "Ishikawa, Japan",
- month = mar,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://hdl.handle.net/10119/876",
-
URL = "
https://dspace.jaist.ac.jp/dspace/bitstream/10119/876/3/608paper.pdf",
- size = "79 pages",
-
abstract = "Genetic Programming (GP) can generate computer
programs automatically without any explicit knowledge
for target programs (solution programs). The solution
programs are generated by means of selection and some
genetic operators. However, GP has a difficulty, which
it often takes too much time to generate solution
programs. This may be a critical problem when GP
generates large scale programs.
The goal of this work is to generate computer programs efficiently by means of the framework of GP. 'Efficient' means to reduce the number of generations which is necessary to generate solution programs. To realise this goal, this work improves a genetic operator of GP. There are three genetic operators for GP, crossover, mutation and reproduction. Among these genetic operators, crossover mainly contributes to searching for solution programs. Therefore, this work improves crossover. The normal crossover selects a crossover point randomly so that it breaks building blocks (i.e., effective small program which contributes to improving fitness performance) due to its blind application. To solve this problem, this work proposes four new crossovers
The first crossover is a 'depth-dependent crossover' and the second crossover is a 'revised depth-dependent crossover'. 'Depth-dependent' means that node selection probability is determined by the depth of the tree structure. On these crossovers, shallower nodes are more often selected, and deeper nodes are selected rarely. The building blocks can be protected by swapping shallower nodes.
The third crossover is a 'non-destructive depth-dependent crossover', which is a combination of the depth-dependent crossover and a 'non-destructive crossover'. 'Nondestructive' means that offsprings of crossover are kept only if their fitness are better than fitness of their parents. This crossover is proposed to solve the program size problem of the depth-dependent crossover.
The fourth crossover is a 'self-tuning depth-dependent crossover'. On this crossover, each individual of the population has a different depth selection probability and depth selection probability of a selected individual is copied to the next generation. This crossover is proposed to enhance the applicability of the depth-dependent crossover for various GP problems.
This work compares GP performances (i.e., fitness value and the size of generated programs) of the normal crossover with performances of these four crossovers using standard GP problems and an original robot problem. These experimental results clarify that the superiority of the proposed crossovers to the normal crossover.
Furthermore, this work discusses the building block hypothesis, which explains how crossover searches solution programs with a survey of previous works and these experimental results.",
- notes = "Supervisor Satoshi Sato",
