Efficient Sampling with Small Populations: a Genetic Algorithm Satisfying Detailed Balance

Christopher Watkins; Yvonne Buttkewitz

doi:10.1145/2739482.2764708

Efficient Sampling with Small Populations: a Genetic Algorithm Satisfying Detailed Balance

Christopher Watkins
, Yvonne Buttkewitz

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a population genetic algorithm which satisfies detailed balance, and which has a stationary distribution that factorises into an explicit form for arbitrary fitness functions. For a population size of 1, it is the Metropolis algorithm with a ‘breeder’ proposal distribution; it extends to larger populations in a natural way, and the stationary (that is, the mutation-selection equilibrium) distribution is exactly known in a simple form for any population size. We term this algorithm exchangeable breeding tuple product sampling (EBT).
EBT is closely related to some non-parametric Bayesian Markov-chain Monte Carlo sampling algorithms. EBT can also be viewed as a generalisation of the Moran process.

Original language	English
Title of host publication	Gecco Companion '15
Subtitle of host publication	Proceedings of the Companion Publication of the 2015 Genetic and Evolutionary Computation Conference
Pages	1517-1518
Number of pages	2
ISBN (Electronic)	978-1-4503-3488-4
DOIs	https://doi.org/10.1145/2739482.2764708
Publication status	Published - 11 Jul 2015

Access to Document

10.1145/2739482.2764708

Cite this

@inproceedings{5dd80ac171dd427c81f9cda511565d33,

title = "Efficient Sampling with Small Populations: a Genetic Algorithm Satisfying Detailed Balance",

abstract = "We present a population genetic algorithm which satisfies detailed balance, and which has a stationary distribution that factorises into an explicit form for arbitrary fitness functions. For a population size of 1, it is the Metropolis algorithm with a {\textquoteleft}breeder{\textquoteright} proposal distribution; it extends to larger populations in a natural way, and the stationary (that is, the mutation-selection equilibrium) distribution is exactly known in a simple form for any population size. We term this algorithm exchangeable breeding tuple product sampling (EBT). EBT is closely related to some non-parametric Bayesian Markov-chain Monte Carlo sampling algorithms. EBT can also be viewed as a generalisation of the Moran process.",

author = "Christopher Watkins and Yvonne Buttkewitz",

year = "2015",

month = jul,

day = "11",

doi = "10.1145/2739482.2764708",

language = "English",

pages = "1517--1518",

booktitle = "Gecco Companion '15",

}

TY - GEN

T1 - Efficient Sampling with Small Populations

T2 - a Genetic Algorithm Satisfying Detailed Balance

AU - Watkins, Christopher

AU - Buttkewitz, Yvonne

PY - 2015/7/11

Y1 - 2015/7/11

N2 - We present a population genetic algorithm which satisfies detailed balance, and which has a stationary distribution that factorises into an explicit form for arbitrary fitness functions. For a population size of 1, it is the Metropolis algorithm with a ‘breeder’ proposal distribution; it extends to larger populations in a natural way, and the stationary (that is, the mutation-selection equilibrium) distribution is exactly known in a simple form for any population size. We term this algorithm exchangeable breeding tuple product sampling (EBT). EBT is closely related to some non-parametric Bayesian Markov-chain Monte Carlo sampling algorithms. EBT can also be viewed as a generalisation of the Moran process.

AB - We present a population genetic algorithm which satisfies detailed balance, and which has a stationary distribution that factorises into an explicit form for arbitrary fitness functions. For a population size of 1, it is the Metropolis algorithm with a ‘breeder’ proposal distribution; it extends to larger populations in a natural way, and the stationary (that is, the mutation-selection equilibrium) distribution is exactly known in a simple form for any population size. We term this algorithm exchangeable breeding tuple product sampling (EBT). EBT is closely related to some non-parametric Bayesian Markov-chain Monte Carlo sampling algorithms. EBT can also be viewed as a generalisation of the Moran process.

U2 - 10.1145/2739482.2764708

DO - 10.1145/2739482.2764708

M3 - Conference contribution

SP - 1517

EP - 1518

BT - Gecco Companion '15

ER -