Program Evolution using Nonparametric Probabilistic Model

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

  author =       "Makoto Tanji",
  title =        "Program Evolution using Nonparametric Probabilistic
  school =       "The University of Tokyo",
  year =         "2011",
  address =      "Japan",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  abstract =     "This paper describes research results of Genetic
                 Programming (GP) which uses nonparametric probabilistic
                 model. Genetic Programming, a method of Evolutionary
                 Computation which uses mechanism of biological
                 evolution for optimization, can generate programs
                 itself and functions by using tree structure data. It
                 can be applied to complex problems which are difficult
                 to solve by human such as the robot routing problem and
                 the regression problem, etc.

                 Conventional Evolutionary Computation methods, GP and
                 GA (Genetic Algorithm), use crossover and mutation
                 which have been inspired by sexual multiplication. In
                 recent years, new approaches called EDA (Estimation of
                 Distribution Algorithm) and PMBGA (Probabilistic Model
                 Building Genetic Algorithm) which uses a probabilistic
                 model from promising have shown promise. EDA and PMBGA
                 can deal with the dependencies of variables and can
                 solve complex problems in GA. Especially, it is widely
                 accepted that EDA and PMBGA are well suited to problems
                 which have dependencies between the variables.

                 In the past decade, EDA-GP and PMBGP (Probabilistic
                 Model Building GP) have been studied. EDA-GP uses PPT
                 (Probabilistic Prototype Tree) or stochastic grammar as
                 probabilistic model. However it is difficult to
                 represent dependencies of solutions because of a
                 variable length tree structure. Furthermore, the number
                 of parameters and the number of promising solutions
                 increase rapidly. As a result, the computational cost,
                 CPU time and memory, will be high. In this research, a
                 comparative experiment of EDA-GP using PPT model is

                 I propose two methods of GP to overcome the problems
                 above: PORTS (Program Optimization by Random Tree
                 Sampling) and PERCE (Program Evolution using Related
                 Clique Extraction). These methods do not need to
                 calculate and store parameters of a probabilistic
                 model. Instead of storing them, PORTS and PERCE use
                 current solutions directly to create new

                 PORTS creates a new solution by sampling and
                 concatenation of fragment of promising trees. The size
                 of the fragments follows a geometric distribution to
                 maintain the diversity of a population. Experimental
                 result shows that PORTS solves GP-easy problems very
                 fast than the conventional GP.

                 PERCE uses a set of sub graphs, called ''related
                 cliques'', that contains a number of PPT nodes relating
                 each other. It does not require explicit calculation
                 and storing of the parameters. Experimental result
                 shows that PERCE solves GP-hard problems such as
                 deceptive problem and multimodal problem.

                 I summarize this research and discuss how to use GP for
                 practical problems. Finally, further topics to be
                 researched are presented and discussed.",

Genetic Programming entries for Makoto Tanji