Efficient program generation by genetic programming

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

  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

                 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

                 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",

Genetic Programming entries for Takuya Ito