Robust and Scalable Black-Box Optimization, Hierarchy and Ising Spin Glasses

One of the most important challenges in computational optimization is the design of advanced black-box optimization techniques that would enable automated, robust, and scalable solution to challenging optimization problems. This paper describes an advanced black-box optimizer—the hierarchical Bayesian optimization algorithm (hBOA)—that combines techniques of genetic and evolutionary computation, machine learning, and statistics to create a widely applicable tool for solving real-world opti-mization problems. The paper motivates hBOA, describes its basic procedure, and provides an in-depth empirical analysis of hBOA on the class of random 2D and 3D Ising spin glass problems. The results on Ising spin glasses indicate that even without much problem-specific knowledge, hBOA can provide competitive or better results than techniques specialized in solving the particular problem or class of problems. Further-more, hBOA can solve a large class of nearly decomposable and hierarchical problems for which there exists no other scalable solution.