James Alexander Sadler Brimer

Anytime analysis looks at how well randomised search heuristics can solve an optimisation problem given a fixed number of objective function evaluations. This contrasts with runtime analysis which looks at placing bounds on the expected runtime, e.g. the amount of time taken for the algorithm to converge on a solution, of a randomised search heuristic on a given optimisation problem. Anytime analysis is of interest to practitioners because it's often more useful to consider how much effort is needed to improve the quality of a solution to within acceptable bounds than it is to find an optimal solution.

There is a large body of work which has used anytime and runtime analysis to characterise the performance of evolutionary algorithms on static and dynamic discrete optimisation problems which are deterministic or noisy, but relatively little work has looked at using anytime analysis to characterise the performance of simpler evolutionary algorithms on discrete optimisation problems which are dynamic, multimodal, and stochastic.

Dynamic, multimodal stochastic optimisation problems are of particular interest because they correspond to real-world problems where an algorithm must operate in an environment which changes over time, perhaps due to actions taken due to the output of the algorithm in the previous time step, where there’s significant uncertainty about how the environment is changing from the algorithm’s point of view.

My research addresses this gap by using anytime analysis and empirical methods to examine the behaviour of simple evolutionary algorithms on discrete, dynamic, multimodal stochastic benchmark problems.

• Advanced Reasoning Group