15,607,737 members
1.00/5 (1 vote)
See more: , +
I did my best to solve the task, but the code fails.
My code is located here: GitHub - nikolayresh/Simulated-Annealing-Search: An example of how Simulated Annealing search works[^]
The sense of this task is that initially you have a sequence: [B1, B2, B3, B4, 0, W1, W2, W3] where B1, B2, B3, B4 - black balls on the board, 0 - gap on the board, W1, W2, W3 - white balls on the board. And the final state should be: [W1, W2, W3, 0, B1, B2, B3, B4]
Rules for the gap - the closest ball to gap can swap places with it OR the second closest ball can swap places with gap by jumping over the first closest ball.
For example, such states are valid: [B1, B2, B3, 0, B4, W1, W2, W3],
[B1, B2, 0, B4, B3, W1, W2, W3] or [B1, B2, B3, B4, W2, W1, 0, W3].
Black balls can only be moved to the right, white balls only to the left.
What function to use with simulated annealing to get to solution?

What I have tried:

Tried to build the optimizing function that calculates sum of squares of distances between goal state and each successive state, but the function is stuck.
Posted
Updated 13-Jan-21 13:50pm
Richard MacCutchan 10-Jan-21 13:29pm
"but the function is stuck."
Then unstick it. Seriously, you can not expect anyone here to guess what your code is doing. Please use the Improve question link above and provide some proper details.

## Solution 1

The `energy` function is pretty straightforward: just the sum of the squared difference between current ball (and gap) indices and the target ones.

[update]
It looks that simulated annealing have hard time with this problem (well, at least, I had hard time trying to find a good energy function...).
The following just takes long time in order to compute suboptimal solutions.
I'm not happy with it, but, nevertheless I post it here hoping it could somehow help.

C#
```using System;

namespace SA
{

class Ball
{
public Ball(string id, int targetIndex)
{
this.id = id;
this.targetIndex = targetIndex;
}

public int energy( int index)
{
int d = (targetIndex-index)*2;

int e = d*d; // 'basic' enrgy: squared distance from target index

if ( targetIndex < 3 )
{
if ( index >= 3)
e += 1000;  // sum a noticeable energy when 'on the wrong side'
}
else if ( targetIndex == 3)
{
e += d*d*d*d*1000; // sum big energy if the gap is in wrong position
}
else
{
if ( index <= 3)
e += 1000; // sum a noticeable energy when 'on the wrong side'
}
return e;
}
}

class Test
{

static int energy( Ball [] ball)
{
int e = 0;
for (int n=0; n< ball.Length; ++n)
{
e += ball[n].energy(n);
}
return e;
}

static double probability(int energy, double temperature)
{
if (energy <=0) return 1.0;
double p = Math.Exp(-(double)energy/temperature);
return p;
}

static void dump( Ball [] ball, int energy, double temperature)
{
foreach (var b in ball)
{
Console.Write("{0} ", b.id);
}
Console.WriteLine("{0} {1}", energy, temperature);
}

// Driver method
public static void Main()
{
const double THot=300000;
const double TCold=30000;
const double TSub=2.0;
double t = THot;
Random rnd = new Random();

Ball [] ball = new Ball[8];
ball[0] = new Ball("B1", 4);
ball[1] = new Ball("B2", 5);
ball[2] = new Ball("B3", 6);
ball[3] = new Ball("B4", 7);
ball[4] = new Ball("GP", 3);
ball[5] = new Ball("W1", 0);
ball[6] = new Ball("W2", 1);
ball[7] = new Ball("W3", 2);

int cur_gp_index = 4;
int cur_energy = energy(ball);

while ( t > TCold)
{
const int Iterations = 250;
for (int n=0; n<Iterations; ++n)
{
int new_gp_index;
int new_energy;
for (;;)
{
int r = rnd.Next(-2,3); // <- Fixed a blunder, thanks to Luc Pattyn
new_gp_index = cur_gp_index + r;
if ( new_gp_index != cur_gp_index && new_gp_index >=0 && new_gp_index<=7)
break;
}
// swap
Ball temp = ball[new_gp_index];
ball[new_gp_index] = ball[cur_gp_index];
ball[cur_gp_index] = temp;
new_energy = energy(ball);
if ( probability( new_energy - cur_energy, t) > .95)
{
//dump (ball, new_energy, t);
cur_energy=new_energy;
cur_gp_index = new_gp_index;
}
else
{
temp = ball[new_gp_index];
ball[new_gp_index] = ball[cur_gp_index];
ball[cur_gp_index] = temp;
}
}
t-=TSub;
}
dump (ball, cur_energy, t);
Console.WriteLine("done.");
}
}
}```

[/update]

v3
NickResh777 10-Jan-21 17:38pm
I did exactly that in my code and it didn't help. Local search cannot give out another correct state without knowing previous states. I think that this task has no solution, as any incorrect relocation of a ball will lead to deadend
CPallini 11-Jan-21 2:53am
I've made a test and my program was actually unable to find the global minimum. I suppose the energy function, after all, it is not so 'straightforward'.
CPallini 12-Jan-21 16:46pm
I've updated my solution. Actually, it isn't a 'solution'...
NickResh777 12-Jan-21 17:10pm
Thanks. I will try your code

## Solution 2

Hi,

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.

:)

CPallini 14-Jan-21 4:44am
Hi Luc, than you for trying my code (and fixing it :-) )
The rnd.Next was really a blunder.
Still I think the energy refinements are not bad.
Thanks again.
Luc Pattyn 14-Jan-21 6:04am
Prego