I experimented a bit with Carlo's code, and had to fix several issues in order to get your annealing to work. They are:
- your temperatures are way too high; they must be chosen in such a way that the exponential function initially returns small numbers so they depend on the range of your energy function;
- and they are rather critical to reaching the solution anyway, and doing so in a reasonable number of steps. I ended up with 10000, 1, and 0.03
- when you reject a swap, it makes little sense to iterate 250 times, unless you also lower the temperature.
- the energy function does not need the "refinements"; they were not symmetric, and redundant; I simply use d*d.
- the method Random.Next(min,max) returns a number in the range [min,max) i.e. it never returns max, so you'd be better of using
int r = rnd.Next(-2, 3);
As a result it took some 300K steps to find the solution.
How did I work this out? The first step was to drastically increase observability: I added current_gp_index, new_gp_index, and probability parameters to your dump method, and called that at every try (for the first 1000), just to see what was actually going on. And then it all became clear step by step.