White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Theoretical and Empirical Evaluation of Diversity-preserving Mechanisms in Evolutionary Algorithms: On the Rigorous Runtime Analysis of Diversity-preserving Mechanisms in Evolutionary Algorithms

Covantes Osuna, Edgar (2018) Theoretical and Empirical Evaluation of Diversity-preserving Mechanisms in Evolutionary Algorithms: On the Rigorous Runtime Analysis of Diversity-preserving Mechanisms in Evolutionary Algorithms. PhD thesis, University of Sheffield.

[img]
Preview
Text (On the Rigorous Runtime Analysis of Diversity-preserving Mechanisms in Evolutionary Algorithms)
ECO Thesis - Theoretical and Empirical Evaluation of Diversity-preserving Mechanisms in Evolutionary Algorithms.pdf
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (2035Kb) | Preview

Abstract

Evolutionary algorithms (EAs) simulate the natural evolution of species by iteratively applying evolutionary operators such as mutation, recombination, and selection to a set of solutions for a given problem. One of the major advantages of these algorithms is that they can be easily implemented when the optimisation problem is not well understood, and the design of problem-specific algorithms cannot be performed due to lack of time, knowledge, or expertise to design problem-specific algorithms. Also, EAs can be used as a first step to get insights when the problem is just a black box to the developer/programmer. In these cases, by evaluating candidate solutions it is possible to gain knowledge on the problem at hand. EAs are well suited to dealing with multimodal problems due to their use of a population. A diverse population can explore several hills in the fitness landscape simultaneously and offer several good solutions to the user, a feature desirable for decision making, multi-objective optimisation and dynamic optimisation. However, a major difficulty when applying EAs is that the population may converge to a sub-optimal individual before the fitness landscape is explored properly. Many diversity-preserving mechanisms have been developed to reduce the risk of such premature convergence and given such a variety of mechanisms to choose from, it is often not clear which mechanism is the best choice for a particular problem. We study the (expected/average) time for such algorithms to find satisfactory solutions for multimodal and multi-objective problems and to extract guidelines for the informed design of efficient and effective EAs. The resulting runtime bounds are used to predict and to judge the performance of algorithms for arbitrary problem sizes, further used to clarify important design issues from a theoretical perspective. We combine theoretical research with empirical applications to test the theoretical recommendations for their practicality, and to engage in rapid knowledge transfer from theory to practice. With this approach, we provide a better understanding of the working principles of EAs with diversity-preserving mechanisms. We provide theoretical foundations and we explain when and why certain diversity mechanisms are effective, and when they are not. It thus contributes to the informed design of better EAs.

Item Type: Thesis (PhD)
Academic Units: The University of Sheffield > Faculty of Engineering (Sheffield) > Computer Science (Sheffield)
The University of Sheffield > Faculty of Science (Sheffield) > Computer Science (Sheffield)
Identification Number/EthosID: uk.bl.ethos.767293
Depositing User: Mr Edgar Covantes Osuna
Date Deposited: 04 Mar 2019 08:50
Last Modified: 25 Sep 2019 20:06
URI: http://etheses.whiterose.ac.uk/id/eprint/23098

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)