Linear multi-objective drift analysis

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
203 Downloads (Pure)

Abstract

The tools of drift analysis enable bounds on run-times (or first hitting times) of stochastic processes, such as randomised algorithms, based on bounds on the expected progress at each time step in terms of a distance measure. In this paper, we generalise the multiplicative drift theorem to apply to processes which are best described by more than one distance function. We provide four examples to illustrate the application of this method: the run-time analysis of an evolutionary algorithm on a multi-objective optimisation problem; the analysis of a variant of the voter model on a network; a parallel evolutionary algorithm taking place on islands with limited migration; a synchronous network epidemiology model. In the latter example, we show that populations with limited neighbourhoods (such as the ring topology) are able to resist epidemics much more effectively than well-mixed populations.
Original languageEnglish
Number of pages16
JournalTheoretical Computer Science
Early online date2 Apr 2018
DOIs
Publication statusE-pub ahead of print - 2 Apr 2018

Fingerprint

Dive into the research topics of 'Linear multi-objective drift analysis'. Together they form a unique fingerprint.

Cite this