  We develop an Evolutionary Markov Chain Monte Carlo (EMCMC) algorithm for
sampling spatial partitions that lie within a large and complex spatial state
space. Our algorithm combines the advantages of evolutionary algorithms (EAs)
as optimization heuristics for state space traversal and the theoretical
convergence properties of Markov Chain Monte Carlo algorithms for sampling from
unknown distributions. Local optimality information that is identified via a
directed search by our optimization heuristic is used to adaptively update a
Markov chain in a promising direction within the framework of a Multiple-Try
Metropolis Markov Chain model that incorporates a generalized
Metropolis-Hasting ratio. We further expand the reach of our EMCMC algorithm by
harnessing the computational power afforded by massively parallel architecture
through the integration of a parallel EA framework that guides Markov chains
running in parallel.
