Evolvability and Rate of Evolution in Evolutionary Computation

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

  author =       "Ting Hu",
  title =        "Evolvability and Rate of Evolution in Evolutionary
  school =       "Department of Computer Science, Memorial University of
  year =         "2010",
  address =      "ST. John's, Newfoundland, Canada",
  month =        May,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://www.mun.ca/computerscience/graduate/thesis_TingHU.pdf",
  size =         "173 pages",
  abstract =     "Evolvability has emerged as a research topic in both
                 natural and computational evolution. It is a notion put
                 forward to investigate the fundamental mechanisms that
                 enable a system to evolve. A number of hypotheses have
                 been proposed in modern biological research based on
                 the examination of various mechanisms in the biosphere
                 for their contribution to evolvability. Therefore, it
                 is intriguing to try to transfer new discoveries from
                 Biology to and test them in Evolutionary Computation
                 (EC) systems, so that computational models would be
                 improved and a better understanding of general
                 evolutional mechanisms is achieved.

                 Rate of evolution comes in different flavors in natural
                 and computational evolution. Specifically, we
                 distinguish the rate of fitness progression from that
                 of genetic substitutions. The former is a common
                 concept in EC since the ability to explicitly quantify
                 the fitness of an evolutionary individual is one of the
                 most important differences between computational
                 systems and natural systems. Within the biological
                 research community, the definition of rate of evolution
                 varies, depending on the objects being examined such as
                 gene sequences, proteins, tissues, etc. For instance,
                 molecular biologists tend to use the rate of genetic
                 substitutions to quantify how fast evolution proceeds
                 at the genetic level. This concept of rate of evolution
                 focuses on the evolutionary dynamics underlying fitness
                 development, due to the inability to mathematically
                 define fitness in a natural system. In EC, the rate of
                 genetic substitutions suggests an unconventional and
                 potentially powerful method to measure the rate of
                 evolution by accessing lower levels of evolutionary

                 Central to this thesis is our new definition of rate of
                 evolution in EC. We transfer the method of measurement
                 of the rate of genetic substitutions from molecular
                 biology to EC. The implementation in a Genetic
                 Programming (GP) system shows that such measurements
                 can indeed be performed and reflect well how evolution
                 proceeds. Below the level of fitness development it
                 provides observables at the genetic level of a GP
                 population during evolution. We apply this measurement
                 method to investigate the effects of four major
                 configuration parameters in EC, i.e., mutation rate,
                 crossover rate, tournament selection size, and
                 population size, and show that some insights can be
                 gained into the effectiveness of these parameters with
                 respect to evolution acceleration. Further, we observe
                 that population size plays an important role in
                 determining the rate of evolution. We formulate a new
                 indicator based on this rate of evolution measurement
                 to adjust population size dynamically during evolution.
                 Such a strategy can stabilise the rate of genetic
                 substitutions and effectively improve the performance
                 of a GP system over fixed-size populations. This rate
                 of evolution measure also provides an avenue to study
                 evolvability, since it captures how the two sides of
                 evolvability, i.e., variability and neutrality,
                 interact and cooperate with each other during
                 evolution. We show that evolvability can be better
                 understood in the light of this interplay and how this
                 can be used to generate adaptive phenotypic variation
                 via harnessing random genetic variation. The rate of
                 evolution measure and the adaptive population size
                 scheme are further transferred to a Genetic Algorithm
                 (GA) to solve a real world application problem - the
                 wireless network planning problem. Computer simulation
                 of such an application proves that the adaptive
                 population size scheme is able to improve a GA's
                 performance against conventional fixed population size
  notes =        "http://www.mun.ca/computerscience/graduate/grad_thesis.php",

Genetic Programming entries for Ting Hu