Noisy combinatorial optimisation with evolutionary algorithms

., Aishwaryaprajna ORCID: 0000-0003-4386-9745 (2022). Noisy combinatorial optimisation with evolutionary algorithms. University of Birmingham. Ph.D.

Preview

Aishwaryaprajna2022PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (4MB) | Preview

Abstract

The determination of the efficient evolutionary optimisation approaches in solving noisy combinatorial problems is the main focus in this research. Initially, we present an empirical study of a range of evolutionary algorithms applied to various noisy combinatorial optimisation problems. There are four sets of experiments. The first looks at several toy problems, such as OneMax and other linear problems. We find that Univariate Marginal Distribution Algorithm (UMDA) and the Paired-Crossover Evolutionary Algorithm (PCEA) are the only ones able to cope robustly with noise, within a reasonable fixed time budget. In the second stage, UMDA and PCEA are then tested on more complex noisy problems: SubsetSum, Knapsack and SetCover. Both perform well under increasing levels of noise, with UMDA being the better of the two. In the third stage, we consider two noisy multi-objective problems (CountingOnesCountingZeros and a multi-objective formulation of SetCover). We compare several adaptations of UMDA for multi-objective problems with the Simple Evolutionary Multi-objective Optimiser (SEMO) and NSGA-II. In the last stage of empirical analysis, a realistic problem of the path planning for the ground surveillance with Unmanned Aerial Vehicles is considered. We conclude that UMDA, and its variants, can be highly effective on a variety of noisy combinatorial optimisation, outperforming many other evolutionary algorithms.

Next, we study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve OneMax and Jump in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves OneMax with added posterior noise in O(n log n), when the variance of the noise distribution is sigma\(^2\) = O(n) and in O(sigma\(^2\) log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. Building upon this promising performance, we consider other noise models prevalent in optimisation and learning and show that the Voting algorithm has efficient performance in solving OneMax in presence of these noise variants. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LeadingOnes but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):