Scaling of Program Functionality

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

@Article{langdon:2007:gpem,
  author =       "W. B. Langdon",
  title =        "Scaling of Program Functionality",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2009",
  volume =       "10",
  number =       "1",
  pages =        "5--36",
  month =        mar,
  keywords =     "genetic algorithms, genetic programming, search
                 landscapes, evolutionary computation",
  ISSN =         "1389-2576",
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/wbl_scale_prog_func.pdf",
  doi =          "doi:10.1007/s10710-008-9065-y",
  size =         "32 pages",
  abstract =     "The distribution of fitness values (landscapes) of
                 programs tends to a limit as the programs get bigger.
                 We use Markov chain convergence theorems to give
                 general upper bounds on the length of programs needed
                 for convergence. How big programs need to be to
                 approach the limit depends on the type of the computer
                 they run on. We give bounds (exponential in $N$, $N\log
                 N$ and smaller) for five computer models: any, average
                 or amorphous or random, cyclic, bit flip and 4
                 functions (AND, NAND, OR and NOR).

                 Programs can be treated as lookup tables which map
                 between their inputs and their outputs. Using this we
                 prove similar convergence results for the distribution
                 of functions implemented by linear computer programs.
                 We show most functions are constants and the remainder
                 are mostly parsimonious.

                 The effect of ad-hoc rules on genetic programming (GP)
                 are described and new heuristics are proposed.

                 We give bounds on how long programs need to be before
                 the distribution of their functionality is close to its
                 limiting distribution, both in general and for average
                 computers. The computational importance of destroying
                 information is discussed with respect to reversible and
                 quantum computers.

                 Mutation randomizes a genetic algorithm population in
                 \frac{1}{4}(l+1)(\log(l)+4) generations.

                 Results for average computers and a model like genetic
                 programming are confirmed experimentally.",
}

Genetic Programming entries for William B Langdon