3
$\begingroup$

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:

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)
$\endgroup$
  • $\begingroup$ Can you share a ISIN paper for GA? $\endgroup$ – Carlos Mougan Jan 16 at 7:59
  • $\begingroup$ Haven't seen one. People only write ising spin glass when referring to the benchmark, without stating particular model. $\endgroup$ – Piotr Rarus - Reinstate Monica Jan 16 at 17:13
  • 1
    $\begingroup$ @CarlosMougan I've found some papers. Definitions are little intuitive, models differ, but maybe you can find something interesting there. $\endgroup$ – Piotr Rarus - Reinstate Monica Jan 17 at 13:31
  • $\begingroup$ @CarlosMougan I updated post with problem instances and a method. I'll publish python lib with benchmarks in next 1-2 weeks. $\endgroup$ – Piotr Rarus - Reinstate Monica Jan 21 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.