Ising Spin Glass - Optimization

I'm a newbie researcher working on model-based genetic algorithms, mainly linkage learning in both discrete and continuous spaces, using data modeling. I would like to ask you about Ising Spin Glass (ISG) problem in the context of optimization. I've seen a lot of papers running benchmarks on this particular problem. I've googled it, checked wiki but eventually understood nothing :/

1. What is an intuitive definition of this problem, making it well suited for optimization?
2. When referring to ISG problem in papers, which specific model researchers have in mind?
3. How to formulate this problem in the context of optimization? (encoding, fitness evaluation)

I don't ask nor expect a ready solution, some general direction would suffice as I feel kinda lost.

Update 1

I've found some python repo on github. It calculates energy in a following way:

import numpy as np

def totalEnergy(J, configuration):
    """
    calculate the energy for a given configuration.
    Parameters:
         J: 
        nSpin*nSpin matrix, J[i,j] is the interation between spin i and j.
         configuration: 
        1*nSpin vector, configuration[i] stores the spin at site i.
    Returns:
        the total energy of this configuration.
    """
    # 0.5 for double counting
    return 0.5*np.dot(configuration,np.dot(J,configuration))

Update 2

Found some papers:

• Pál, K. F. (1996). The ground state energy of the Edwards-Anderson Ising spin glass with a hybrid genetic algorithm. Physica A: Statistical Mechanics and Its Applications, 223(3-4), 283–292. doi:10.1016/0378-4371(95)00348-7
• Prügel-Bennett, A., Shapiro, J. L. (1997). The dynamics of a Genetic Algorithm for simple random Ising systems. Physica D: Nonlinear Phenomena, 104(1), 75–114. doi:10.1016/s0167-2789(96)00163-7
• Finding Ground States of Sherrington-Kirkpatrick Spin Glasses with Hierarchical BOAand Genetic Algorithms
• The role of crossover operator in the genetic optimization ofmagnetic models
• Searching Ground States of Ising Spin Glasses with a Tree Bond-Based Representation

Once I get through them, I'll code it into my benchmarks package. I'm going to release it on pypi in a few weeks, if anyone's interested.

Answer

There's a list of ISG instances at Parameterless Population Pyramid (P3) repository.

-140 1110100000000101010100001011011001010010111011010111000110101010111010101111100010101010100001101010
200
0 1 1
1 2 1
2 3 -1
3 4 -1

It works like this:

-140 - global optimum

111010... - best genome

200 - number of dependencies

From record 3 onwards you got specified dependencies.

Example

Let's take genome 1 0 1 1 1 0 1. Values 0 must be substituted to -1. As problem is binary that is just convention in repo associated with data types underneath.

After transformation we have following genome: 1 -1 1 1 1 -1 1. Let's assume following dependencies:

0 1 1
1 2 1
2 3 -1

We iterate over each row. We take first row 0 1 1. First 2 values are indices. You take gene values at that positions. In genome 1 -1 1 1 1 -1 1 values at these indices (0, 1) are 1 and -1. We multiply those values. We get -1. Third value in this tuple (0 1 1) denotes multiply factor. You take your previous score -1 and multiply it by that factor 1. We get -1. You repeat that process for every dependency. To get overall fitness you just sum up all the subscores.

genome: 1 -1 1 1 1 -1 1

dependencies:

0 1 1 = 1 * -1 * 1 = -1
1 2 1 = -1 * 1 * 1 = -1
2 3 -1 = 1 * 1 * -1 = -1

fitness = sum(-1, -1, -1)