Double-Check Implementation of Ising Model

[thomasWeise]

If I understand correctly, then the Ising model is defined as follows:

We have a graph where the nodes have the names 1 to N.
These nodes are connected by the set of edges E.
The "value" of a node i be its value in the candidate solution x, i.e., x[i] .
The objective value is the number of edges where both involved nodes have the same value.
This gives us a global optimum at the all-zeros string and the all-ones string.

Roughly speaking, we should have pseudo code like this:

f <- 0
for all Edges e do
  i <- start of edge e
  j <- end of edge e
  if x[i] == x[j] then f <- f + 1
end

The maximum objective value should be N and the minimum objective value should be 0.

However, when I look at your implementations of the Ising model, I think -- and I might be wrong, but well, I think -- that you count all edges twice, at least in the 1D version(?)
See, e.g.,

IOHexperimenter/src/Problems/f_ising_1D.hpp

Line 43 in 7b97260

double internal_evaluate(const std::vector<int> &x) {

  double internal_evaluate(const std::vector<int> &x) {
    int result= 0, n = x.size();

    for (int i = 0; i < n; ++i) {
        int first_neig=x[modulo_ising_1D((i+1), n)];
        int second_neig=x[modulo_ising_1D((i -1), n)];

        result += (x[i] *first_neig) + ((1- x[i])*(1- first_neig));
        result += (x[i] *second_neig) + ((1- x[i])*(1- second_neig));
    }
    return (double)result;
  };

For example, if n = 3, then on a 1-D Torus I should have three edges, namely 0-1, 1-2, and 2-0.
The optimal objective value should then probably be 3, I think.
However, if I understand correctly, then the loop will go from i=0 to i=2 and would probably do:

// i = 0
result += (x[0] *x[1]) + ((1- x[0])*(1- x[1]));
result += (x[0] *x[2]) + ((1- x[0])*(1- x[2]));
// i = 1
result += (x[1] *x[2]) + ((1- x[1])*(1- x[2]));
result += (x[1] *x[0]) + ((1- x[1])*(1- x[0]));
// i =2
result += (x[2] *x[0]) + ((1- x[2])*(1- x[0]));
result += (x[2] *x[1]) + ((1- x[2])*(1- x[1]));

This seems to include each index pair twice, and if I have the all-ones string, I should get 6 as result instead of 3.

Again: Maybe I misunderstood something elementary here.
Also: From the optimization perspective, this should not really matter.
But it might matter if someone else implements the Ising model, does own experiments, and then wants to compare the results with the output of the IOHexperimenter.
If we want to compare the expected running times to reach certain objective values, then this may lead to a confusion.

Side note 1: I am not sure whether the compiler allows you to do that, but maybe doing (x[i]==x[j]) & 1 could be a dodgy but fast way to compute x[i]*x[j]+(1-x[i])*(1-x[j]).

Side note 2: IOHprofiler/IOHprofiler.github.io#2

[thomasWeise]

If my thoughts for the 1D-Ising should indeed be true, please double-check also the other Ising model implementations. They might exhibit similar issues.

[FurongYe]

Hi Thomas, Many thanks for reporting the issue. We will look into this and reply as soon as possible.

[FurongYe]

Hi Thomas, many thanks again for reporting this. You are right, all edges are counted twice, so fitness values are doubled. We have revised this and will make notes for the revision with updates.

[thomasWeise]

Hi.

I just took at looked at the updated implementation of the Ising 1D model.
Are you sure it should be result += (x[i] * neig) - ((1 - x[i]) * (1 - neig)); in https://github.com/IOHprofiler/IOHexperimenter/blob/master/src/Problems/PBO/f_ising_ring.hpp#L38?

If both x[i] and neigh are 1, then you add (11)-( (1 - 1) * (1 - 1)) == 1 - 0 == 1, which is right.
However, if both x[i] and neigh are 0, then you will add (00) - ((1 - 0) * (1 - 0)) == 0 - 1 == -1, which I think may not what you want.
I think(?) you might get negative objective values...

Notice that in the old code, you had x[i]*x[j]+(1-x[i])*(1-x[j]), i.e., a + between the two terms, not a -.

Cheers,
Thomas.

[thomasWeise]

I just noticed that you are doing the same (result += (x[i*lattice_size + j] * neighbors[neig]) - ((1 - x[i * lattice_size + j]) * (1 - neighbors[neig]));) in https://github.com/IOHprofiler/IOHexperimenter/blob/master/src/Problems/PBO/f_ising_torus.hpp#L48 and (result += (x[i * lattice_size + j] * neighbors[neig]) - ((1 - x[i * lattice_size + j]) * (1 - neighbors[neig]));) in https://github.com/IOHprofiler/IOHexperimenter/blob/master/src/Problems/PBO/f_ising_triangular.hpp#L48.

Please take a look.
Maybe I misunderstood something ^_^