Asgard - Project Description

Finding spin glass ground states using hierarchical Bayesian optimization algorithm

Researchers

Project Description

Problem definition

The task of finding ground states of spin-glass systems is a well known problem of statistical physics. The physical state of a spin-glass system is defined by

a set of spins (s₀,s₁, ... ,s_n-1), 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 three-dimensional 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 large-scale 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 scale-up 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 zero-mean 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 population-based 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 n-bit 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 low-order 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 spin-glass 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 problem-specific 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 problem-specific 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

C/C++ (gcc, g++,MPI)

Related publications

Pelikan, M., Goldberg, D.E., Ocenasek, J., Trebst, S.: Robust and Scalable Black-Box 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. 1247-1258.
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. 120-125.