Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms

M.M. Drugan, D. Thierens

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

9 Citaten (Scopus)
84 Downloads (Pure)

Samenvatting

Markov Chain Monte Carlo (MCMC) methods are often used to sample from intractable target distributions. Some MCMC variants aim to improve the performance by running a population of MCMC chains. In this paper, we investigate the use of techniques from Evolutionary Computation (EC) to design population-based MCMC algorithms that exchange useful information between the individual chains. We investigate how one can ensure that the resulting class of algorithms, called Evolutionary MCMC (EMCMC), samples from the target distribution as expected from any MCMC algorithm. We analytically and experimentally show-using examples from discrete search spaces-that the proposed EMCMCs can outperform standard MCMCs by exploiting common partial structures between the more likely individual states. The MCMC chains in the population interact through recombination and selection. We analyze the required properties of recombination operators and acceptance (or selection) rules in EMCMCs. An important issue is how to preserve the detailed balance property which is a sufficient condition for an irreducible and aperiodic EMCMC to converge to a given target distribution. Transferring EC techniques to population-based MCMCs should be done with care. For instance, we prove that EMCMC algorithms with an elitist acceptance rule do not sample the target distribution correctly.

Originele taal-2Engels
Pagina's (van-tot)79-101
Aantal pagina's23
TijdschriftEvolutionary Intelligence
Volume3
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - aug 2010

Vingerafdruk

Duik in de onderzoeksthema's van 'Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms'. Samen vormen ze een unieke vingerafdruk.

Citeer dit