Back to search

University of Birmingham

Runtime analyses of univariate estimation of distribution algorithms under linearity, epistasis and deception

Abstract

dc:description.abstract

Estimation of distribution algorithms (EDAs) have been successfully applied to solve many real-world optimisation problems. The algorithms work by building and maintaining probabilistic models over the search space and are widely considered a generalisation of the evolutionary algorithms (EAs). While the theory of EAs has been enriched significantly over the last decades, our understandings of EDAs are sparse and limited. The past few years have seen some progress in this topic, showing competitive performance compared to other EAs on some simple test functions. This thesis studies the so-called univariate EDAs by rigorously analysing their time complexities on different fitness landscapes. Firstly, I show that the algorithms optimise the ONEMAX function as efficiently as the (1+1) EA does. I then investigate the algorithms’ ability to cope with dependencies among decision variables. Despite the independence assumption, the algorithms optimise LEADINGONES – a test function with an epistasis level of (n−1) – using at most O(n2) function evaluations under appropriate parameter settings. I also show that if the selection rate μ/λ is above some constant threshold, an exponential runtime is inevitable to optimise the function. Finally, I confirm the common belief that univariate EDAs have difficulties optimising some objective function when deception occurs. By introducing a new test function with a very mild degree of deception, I show that the UMDA takes an exponential runtime unless the selection rate is chosen extremely high, i.e., μ/λ = O(1/μ). This thesis demonstrates that while univariate EDAs may cope well with independence and epistasis in the environment, the algorithms suffer even at a mild level of deception and that researchers might need to adopt multivariate EDAs when facing deceptive objective functions.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nguyen, Phan Trung Hai
ORCID person:identifier.orcid

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nguyen, Phan Trung Hai. Runtime analyses of univariate estimation of distribution algorithms under linearity, epistasis and deception. d_ph thesis, University of Birmingham, 2021.