MEDAL Report 2006002
Hierarchical BOA, Cluster Exact Approximation, and Ising Spin Glasses
Martin Pelikan and Alexander K. Hartmann  (2006)

Abstract. This paper analyzes the hierarchical Bayesian optimization algorithm (hBOA) on the problem of finding ground states of Ising spin glasses with $\pm J$ couplings in two and three dimensions. The performance of hBOA is compared to that of the simple genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA). The performance of all tested algorithms is improved by incorporating a deterministic hill climber based on single-bit flips and cluster exact approximation (CEA). The results show that hBOA significantly outperforms GA and UMDA on a broad spectrum of spin-glass instances and that CEA enables all tested algorithms to solve larger spin-glass instances. Using advanced hybrid methods created by combining competent genetic and evolutionary algorithms with advanced local searchers thus proves advantageous in this challenging class of problems.

Download PDF

Download PS

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan