Artificial evolution with Binary Decision Diagrams: a study in evolvability in neutral spaces

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

  author =       "Richard Mark Downing",
  title =        "Artificial evolution with Binary Decision Diagrams: a
                 study in evolvability in neutral spaces",
  school =       "School of Computer Science, University of Birmingham",
  year =         "2008",
  address =      "UK",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  URL =          "",
  size =         "200 pages",
  abstract =     "This thesis introduces a new approach to artificial
                 evolution employing Binary Decision Diagrams as the
                 genotypic representation, and uses it to study
                 evolvability issues. The approach is referred to as
                 Evolving Binary Decision Diagrams using Inherent
                 Neutrality (EBDDIN). The aims are twofold. Firstly, to
                 develop an evolutionary algorithm with a capability to
                 address many of the issues facing the field of
                 evolutionary computation today. Secondly, to develop a
                 deep understanding of the concepts and mechanisms that
                 facilitate within that context.

                 The issue of evolvability, loosely defined as the
                 capacity to evolve, permeates the field of evolutionary
                 computation. For reasons that are not yet fully
                 understood, current approaches to artificial evolution
                 fail to exhibit a pace and extent of evolutionary
                 change so readily exhibited in nature. In order to
                 resolve this discrepancy, the field of evolutionary
                 computation must characterise, understand and apply
                 evolvability to artificial evolution. If this can be
                 achieved, systems of artificial evolution will become
                 much more capable than they are presently.

                 The approach is developed with the primary practical
                 and theoretical issues regarding evolvability in mind,
                 exploiting inherent properties of the Binary Decision
                 Diagram representation where possible. It is then used
                 as a computational model for studying evolvability
                 issues, giving particular emphasis to the role of
                 neutrality, modularity, gradualism, robustness and
                 population diversity, and the interplay between them.
                 Carefully designed, controlled experiments elucidate
                 the mechanisms and properties that facilitate
                 evolvability and its evolution. The implications are
                 then considered regarding the new understandings
                 developed and the fidelity with the characteristics of
                 biological evolution.

                 Pleiotropic patterns which bias the phenotypic effects
                 of random mutation are found to emerge. These
                 configurations represent the variation component of
                 evolvability and are subject to indirect selection.
                 Higher-level structural configurations (i.e. OBDD
                 variable orderings) that better facilitate such
                 patterns emerge as a logical consequence. Neutrality
                 plays the crucial role of facilitating
                 fitness-conserving exploration and completely
                 alleviating local optima for the domain of Boolean
                 functions. Population diversity allows evolvability
                 traits to compete and evolve, ultimately facilitating
                 the evolution of evolvability. The search is
                 insensitive to the starting point and the absence of
                 initial diversity, requiring only minimal diversity
                 generated from gradual genotypic variation.

                 Gradual evolution in a search space that is free of
                 local optima by way of neutrality can be a viable
                 alternative to problematic evolution on multi-modal
                 landscapes, exhibiting search characteristics that have
                 greater fidelity to natural evolution. This is a
                 fruitful direction for research that is directed at the
                 problem of facilitating evolvability in artificial
                 evolution, and it may lead to evolutionary systems that
                 are open-ended.",
  notes =        "

                 Supervisors: Ata Kaban and Peter Hancox",

Genetic Programming entries for Richard Mark Downing