Cargando…

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

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 populatio...

Descripción completa

Detalles Bibliográficos
Autores principales: Drugan, Madalina M., Thierens, Dirk
Formato: Texto
Lenguaje:English
Publicado: Springer-Verlag 2010
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2987561/
https://www.ncbi.nlm.nih.gov/pubmed/21151488
http://dx.doi.org/10.1007/s12065-010-0040-1
_version_ 1782192142221836288
author Drugan, Madalina M.
Thierens, Dirk
author_facet Drugan, Madalina M.
Thierens, Dirk
author_sort Drugan, Madalina M.
collection PubMed
description 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.
format Text
id pubmed-2987561
institution National Center for Biotechnology Information
language English
publishDate 2010
publisher Springer-Verlag
record_format MEDLINE/PubMed
spelling pubmed-29875612010-12-08 Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms Drugan, Madalina M. Thierens, Dirk Evol Intell Research Paper 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. Springer-Verlag 2010-07-21 2010 /pmc/articles/PMC2987561/ /pubmed/21151488 http://dx.doi.org/10.1007/s12065-010-0040-1 Text en © The Author(s) 2010 https://creativecommons.org/licenses/by-nc/4.0/ This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
spellingShingle Research Paper
Drugan, Madalina M.
Thierens, Dirk
Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title_full Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title_fullStr Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title_full_unstemmed Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title_short Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms
title_sort recombination operators and selection strategies for evolutionary markov chain monte carlo algorithms
topic Research Paper
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2987561/
https://www.ncbi.nlm.nih.gov/pubmed/21151488
http://dx.doi.org/10.1007/s12065-010-0040-1
work_keys_str_mv AT druganmadalinam recombinationoperatorsandselectionstrategiesforevolutionarymarkovchainmontecarloalgorithms
AT thierensdirk recombinationoperatorsandselectionstrategiesforevolutionarymarkovchainmontecarloalgorithms