Statistica Sinica 10(2000), 317-342

EVOLUTIONARY MONTE CARLO: APPLICATIONS TO

MODEL SAMPLING AND CHANGE POINT PROBLEM

Faming Liang and Wing Hung Wong

The National University of Singapore and UCLA, 8118 Math Sciences

Abstract: Motivated by the success of genetic algorithms and simulated annealing in hard optimization problems, the authors propose a new Markov chain Monte Carlo (MCMC) algorithm called an evolutionary Monte Carlo algorithm. This algorithm has incorporated several attractive features of genetic algorithms and simulated annealing into the framework of MCMC. It works by simulating a population of Markov chains in parallel, where a different temperature is attached to each chain. The population is updated by mutation (Metropolis update), crossover (partial state swapping) and exchange operators (full state swapping). The algorithm is illustrated through examples of -based model selection and change-point identification. The numerical results and the extensive comparisons show that evolutionary Monte Carlo is a promising approach for simulation and optimization.

Key words and phrases: Change-point identification, crossover, exchange, genetic algorithm, Markov chain Monte Carlo, metropolis algorithm, mutation, parallel tempering, regression variable selection, simulated annealing.