Hierarchical BOA Solves Ising Spin Glasses and MAXSAT

Martin Pelikan^1,2 and David E. Goldberg²

¹Computational Laboratory (Colab)
Swiss Federal Institute of Technology (ETH)
Hirschengraben 84
8092 Zürich, Switzerland

²Illinois Genetic Algorithms Laboratory (IlliGAL)
University of Illinois at Urbana-Champaign
104 S. Mathews Ave.
Urbana, IL 61801
{pelikan,deg}@illigal.ge.uiuc.edu

Abstract. Theoretical and empirical evidence exists that the hierarchical Bayesian optimization algorithm (hBOA) can solve challenging hierarchical problems and anything easier. This paper applies hBOA to two important classes of real-world problems: Ising spin-glass systems and maximum satisfiability (MAXSAT). The paper shows how easy it is to apply hBOA to real-world optimization problems--in most cases hBOA can be applied without any prior problem analysis, it can acquire enough problem-specific knowledge automatically. The results indicate that hBOA is capable of solving enormously difficult problems that cannot be solved by other optimizers and still provide competitive or better performance than problem-specific approaches on other problems. The results thus confirm that hBOA is a practical, robust, and scalable technique for solving challenging real-world problems.

LNCS 2724, p. 1271 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003