Program Search with a Hierarchical Variable Length Representation: Genetic Programming, Simulated Annealing and Hill Climbing

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

  author =       "Una-May O'Reilly and Franz Oppacher",
  title =        "Program Search with a Hierarchical Variable Length
                 Representation: Genetic Programming, Simulated
                 Annealing and Hill Climbing",
  institution =  "Santa Fe Institute",
  year =         "1994",
  number =       "94-04-021",
  address =      "1399 Hyde Park Road Santa Fe, New Mexico 87501-8943

  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  abstract =     "This paper presents a comparison of Genetic
                 Programming(GP) with Simulated Annealing (SA) and
                 Stochastic Iterated Hill Climbing (SIRC) based on a
                 suite of program discovery problems which have been
                 previously tackled only with GP. All three search
                 algorithms employ the hierarchical variable length
                 representation for programs brought into recent
                 prominence with the GP paradigm [K-92]. We experiment
                 with three GP crossover operators and a new
                 hierarchical variable length mutation operator
                 developed for use in SA and SIRC. The paper provides a
                 comparison among GP, SA and SIRC in terms of likelihood
                 of success, required evaluations and program
                 characteristics. This is the first reported
                 experimentation with the goal of program discovery
                 using SA and SIRC. We feel it is not intuitively
                 obvious that mutation-based adaptive search can handle
                 program discovery yet, to date, for each GP problem we
                 have tried, SA or SIRC also work.

                 One important conclusion from the experimentation is to
                 recognise the general value_ of a hierarchical variable
                 length representation for program induction as it is
                 distinct from different search strategies and operators
                 complementary to both the strategy and representation.
                 Based upon comparable results among GP, SA and SIRC,
                 the results emphasise that a search strategy should be
                 chosen according to the characteristics of the
                 landscape (which is determined by fitness function and
                 representation) and with regard to factors such as
                 algorithmic simplicity and computational complexity.

  notes =        "Hard copy sent from SFI by (Patricia
                 Brunello) Second revision dated 6/6/94

                 This paper was co-authored with Franz Oppacher of
                 Carleton University. An abridged version appears in the
                 Proceedings of the Third Conference on Parallel Problem
                 Solving from Nature, Springer Verlag, 1994
                 \cite{OReilly:1994:GPSAHC}. A longer version is SFI
                 Technical Report 94-04-021",
  size =         "13 pages, 2nd edition 18 pages",

Genetic Programming entries for Una-May O'Reilly Franz Oppacher