Evolvability and rate of evolution in evolutionary computation
Thesis (Ph.D.)--Memorial University of Newfoundland, 2010. Computer Science Includes bibliographical references (leaves 137-162) 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...
Main Author: | |
---|---|
Other Authors: | |
Format: | Thesis |
Language: | English |
Published: |
2010
|
Subjects: | |
Online Access: | http://collections.mun.ca/cdm/ref/collection/theses4/id/52802 |
id |
ftmemorialunivdc:oai:collections.mun.ca:theses4/52802 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Memorial University of Newfoundland: Digital Archives Initiative (DAI) |
op_collection_id |
ftmemorialunivdc |
language |
English |
topic |
Evolution (Biology) Evolutionary computation Genetic algorithms |
spellingShingle |
Evolution (Biology) Evolutionary computation Genetic algorithms Hu, Ting, 1981- Evolvability and rate of evolution in evolutionary computation |
topic_facet |
Evolution (Biology) Evolutionary computation Genetic algorithms |
description |
Thesis (Ph.D.)--Memorial University of Newfoundland, 2010. Computer Science Includes bibliographical references (leaves 137-162) 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 dynamics. -- 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 stabilize 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 algorithms. |
author2 |
Memorial University of Newfoundland. Dept. of Computer Science |
format |
Thesis |
author |
Hu, Ting, 1981- |
author_facet |
Hu, Ting, 1981- |
author_sort |
Hu, Ting, 1981- |
title |
Evolvability and rate of evolution in evolutionary computation |
title_short |
Evolvability and rate of evolution in evolutionary computation |
title_full |
Evolvability and rate of evolution in evolutionary computation |
title_fullStr |
Evolvability and rate of evolution in evolutionary computation |
title_full_unstemmed |
Evolvability and rate of evolution in evolutionary computation |
title_sort |
evolvability and rate of evolution in evolutionary computation |
publishDate |
2010 |
url |
http://collections.mun.ca/cdm/ref/collection/theses4/id/52802 |
genre |
Newfoundland studies University of Newfoundland |
genre_facet |
Newfoundland studies University of Newfoundland |
op_source |
Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries |
op_relation |
Electronic Theses and Dissertations (17.45 MB) -- http://collections.mun.ca/PDFs/theses/Hu_Ting.pdf a3312695 http://collections.mun.ca/cdm/ref/collection/theses4/id/52802 |
op_rights |
The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. |
_version_ |
1766113246683594752 |
spelling |
ftmemorialunivdc:oai:collections.mun.ca:theses4/52802 2023-05-15T17:23:33+02:00 Evolvability and rate of evolution in evolutionary computation Hu, Ting, 1981- Memorial University of Newfoundland. Dept. of Computer Science 2010 xi, 162 leaves : ill. Image/jpeg; Application/pdf http://collections.mun.ca/cdm/ref/collection/theses4/id/52802 Eng eng Electronic Theses and Dissertations (17.45 MB) -- http://collections.mun.ca/PDFs/theses/Hu_Ting.pdf a3312695 http://collections.mun.ca/cdm/ref/collection/theses4/id/52802 The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries Evolution (Biology) Evolutionary computation Genetic algorithms Text Electronic thesis or dissertation 2010 ftmemorialunivdc 2015-08-06T19:21:59Z Thesis (Ph.D.)--Memorial University of Newfoundland, 2010. Computer Science Includes bibliographical references (leaves 137-162) 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 dynamics. -- 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 stabilize 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 algorithms. Thesis Newfoundland studies University of Newfoundland Memorial University of Newfoundland: Digital Archives Initiative (DAI) |