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...
Autores principales: | , |
---|---|
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 |