Finding spin glass ground states using hierarchical Bayesian optimization algorithm
Researchers
Project Description
Problem definition
The task of finding ground states of spinglass systems is a well known problem of statistical physics.
The physical state of a spinglass system is defined by
 a set of spins (s_{0},s_{1}, ... ,s_{n1}), where each spin
s_{i} can obtain a value from {+1, 1}, and
 a set of coupling constants J_{ij} relating pairs of spins.
A Hamiltonian specifies the energy of the system as H(s)=S s_{i} J_{ij }
s_{j}. The task is to find a state of
spins called the ground state for given coupling constants J_{ij} that
minimizes the energy of the system. We
consider a special case, where the spins are arranged on a two or
threedimensional grid and each spin interacts with only its nearest neighbors
in the grid (4 neighbors in 2D, 6 neighbors in 3D). Periodic boundary conditions
are used to approximate the behavior of a largescale system.
Goals
The goals of this project
are
 Development of efficient methods for
finding the ground states of 2D/3D spin glass systems.
 Parallelization of proposed methods,
investigation of scaleup and efficiency of parallel methods.
 Utilization of proposed methods for the
more general task of finding the distribution of configurations for
different energy levels.
The experiments are not restricted only to
the spin glass systems with the
discrete coupling constants J_{ij}Î{+1,1}.
We also use spin glass instances where the coupling constants are generated
according to a zeromean Gaussian distribution with unit variance or
according to a sum of two symmetrically located Gaussian distributions.
Methods
We investigate the usage of a hierarchical Bayesian optimization algorithm (hBOA) for solving spin glass instances. hBOA
combines techniques and concepts from
genetic and evolutionary computation, machine learning, and statistics. From
genetic and evolutionary computation, hBOA borrows the concepts of
populationbased search based on selection and recombination, the creation of
a number of artificial niches for diversity preservation, and the facetwise
theory and design. From machine learning and statistics, hBOA borrows the
techniques for learning and sampling probabilistic graphical models.

Figure 1: The evolutionary cycle of hierarchical Bayesian optimization algorithm.


In hBOA each state of the system is represented by an nbit binary
string, where n is the total number of spins. Each bit in a solution
string determines the state of the corresponding spin: 0 denotes the state 1, 1
denotes the state +1. The general procedure of hBOA is similar to that of
classical genetic algorithm, but the recombination operators are replaced by
probability estimation followed by probabilistic sampling. First, the initial
population of hBOA is generated randomly. In each generation, solutions
with low energy are selected from the current population of N candidate
solutions and the true probability distribution of these selected solutions is
estimated (statistical scoring functions are used to discover correlations
between the spin values among the selected solutions and incorporate this
information into the Bayesian network). New candidate solutions are generated by
sampling the estimated Bayesian network. The new solutions are then incorporated
into the original population, replacing some of the old ones or all of them. The
process is repeated until the ground state is met.
The performance of hBOA is improved by enhancing the initial population of
candidate solutions using a simple heuristic based on a random walk through the
grid. In each solution of the initial population, a random spin is first
selected as a starting point for the random walk. Then, a random unvisited
neighbor of the current spin is visited, setting its value to increase the
fitness of the solution the most. The walk continues until all spins have been
visited. If all neighbors of the current spin have already been visited, the
walk continues in a randomly selected unvisited spin.
The performance of hBOA is also improved by combining hBOA with a local
searcher referred to as the discrete hill climber (DHC). DHC is applied
prior to the evaluation of each solution by flipping a bit that improves the
solution the most; this is repeated until no more improvement is possible. For
most constraint satisfaction problems including Ising spin glasses, DHC
increases the computational cost of each evaluation by at most n
log n time steps; in practice, the increase in computational
complexity is still significantly lower because only a few bits are flipped on
average. Here, for instance, DHC does not increase the asymptotic computational
complexity at all, while it decreases the required number of evaluations
approximately tenfold.
Parallel
processing
Original hBOA works sequentially. Even in the case of problems solvable
with loworder polynomial complexity the size of tractable instances is
limited. That is why we proposed the parallel Mixed Bayesian Optimization
Algorithm (MBOA). In discrete domain MBOA performs similarly to hBOA,
but it is able to utilize the cluster of workstations to perform the construction of
Bayesian network in parallel, using MPI
library.

Figure 2: The architecture of parallel MBOA.


Preliminary results
To estimate the scalability of hBOA on
2D Ising spinglass systems, we tested hBOA on random instances for problems
ranging from n = 6 x 6 = 36 to n = 20 x 20 = 400 spins, 1000
random instances for each problem size. To ensure that a correct ground
state was found for each system, we verified the results using the
Spin Glass Ground State Server. The
results indicate that hBOA performs similarly as the best problemspecific
approach; the time complexity of hBOA can be estimated as O(n^{3.51}
log n), whereas the time complexity of the method of Galluccio and
Loebl is O(n^{3.5}). Despite that hBOA does not use any
problemspecific knowledge except for the evaluation of suggested states of
the system and the method of Galluccio and Loebl fully relies on the
knowledge of the problem structure and its properties, hBOA is capable of
providing almost the same asymptotic complexity.

Figure 3: The number of evaluations for hBOA on 2D Isin spin glasses
(1000 random instances for each problem size). Preprint from IlliGAL
report #2003019. 

Currently, we perform experiments to estimate
the scalability of hBOA for 3D Ising spin glass systems.
Languages
Related publications
 Pelikan, M., Goldberg, D.E., Ocenasek, J., Trebst, S.:
Robust and Scalable BlackBox Optimization, Hierarchy, and Ising Spin Glasses .
IlliGAL report #2003019, 2003.
 Ocenasek, J., Schwarz, J., Pelikan, M.:
Design of Multithreaded Estimation of Distribution Algorithms.
In: CantúPaz et al. (Eds.): Genetic and Evolutionary Computation Conference  GECCO 2003. Springer Verlag: Berlin, 2003, pp. 12471258.
 Ocenasek, J., Pelikan, M.:
Parallel spin glass solving in hierarchical Bayesian optimization algorithm.
In: Proceedings of the 9th International Conference on Soft Computing, Mendel 2003,
Brno University of Technology, Brno, Czech Rep., 2003, pp. 120125.
