Manipulating Convergence In Evolutionary Systems

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

  author =       "Gearoid Patrick Murphy",
  title =        "Manipulating Convergence In Evolutionary Systems",
  school =       "University of Limerick",
  year =         "2009",
  address =      "Ireland",
  month =        "19 " # may,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  size =         "149 pages",
  abstract =     "The central question of this thesis is how to prevent
                 the catastrophic loss of diversity in evolutionary
                 algorithms, referred to as premature convergence. This
                 is not a new question for the field as premature
                 convergence has long been recognised to be a negative
                 influence on the effectiveness of evolutionary search

                 A number of hypothetical solutions to this problem are
                 proposed and the validity of these conjectures is
                 experimentally evaluated. Given that a loss of
                 diversity causes premature convergence, our first
                 approach to this problem is to saturate the population
                 with domain-relevant functionality. By maintaining an
                 external representation of the useful functionality we
                 conjecture that the diversity needed to solve an
                 evolutionary search problem will be protected from
                 premature convergence.

                 We propose the Run Transferable Libraries (RTL)
                 algorithm to this end. A set of strategies for
                 discovering and exploiting useful functionality are
                 proposed and evaluated. The applicability of RTL is
                 tested by applying it to a number of arbitrary real
                 world problems.

                 Our analysis of the RTL experiments indicates that the
                 internal evolutionary dynamics of the population
                 presents a better target for algorithms attempting to
                 inhibit premature convergence. Consequently we
                 hypothesise a number of techniques to manipulate the
                 evolutionary dynamics of the population inspired from
                 popular strategies in the literature. These hypotheses
                 employ a life cycle (age) model, an island model and a
                 hill-climbing model. We present an analysis of their
                 performance based on the phenotypic diversity of the
                 population on a popular benchmark problem.

                 Of these hypothetical assertions, we show that the
                 hill-climbing crossover model consistently produces
                 high quality results on the benchmark problem. Further
                 to this finding, we hypothesise that the bloat
                 regulation properties we observe in the hill-climbing
                 crossover model may improve generalisation in contrast
                 to benchmark algorithms and present an experimental
                 evaluation of this conjecture.

                 Finally, we examine the use of backtracking to prevent
                 premature convergence. Backtracking strategies allow an
                 algorithm to recognise when it has run into a local
                 optimum or dead end and provide a means of redirecting
                 the algorithm to other areas of the search space. We
                 propose and implement a backtracking algorithm for
                 evolutionary algorithms called the Adaptive Effort
                 algorithm and experimentally evaluate its ability to
                 avoid premature convergence.",

Genetic Programming entries for Gearoid Murphy