- 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 = "
http://bds.ul.ie/Publications/murphy-thesis.pdf",
- 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
methodologies.
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.",
