- 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 = "
http://etheses.bham.ac.uk/862/",
-
URL = "
http://etheses.bham.ac.uk/862/1/Downing08PhD.pdf",
-
URL = "http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.521944",
- 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 = "oai:etheses.bham.ac.uk:862
Supervisors: Ata Kaban and Peter Hancox",
