Simulated annealing doesn't work

Question

I am trying to implement n-queens problems using simulated annealing. I have looked up at all the existing problems and it doesn't solve my problem. The code that I have come up with is this

#Generate random state for Simulated Annealing
def generateRandomState(n):
    rand = [0] * n
    for num in range(0, n):
        pos = random.randint(0, n-1)
        rand[num] = pos
    return rand

#Cost function for Simulated Annealing
def costFunction(solution):
    cost = 0
    for position in range(0, len(solution)):
        for next_position in range(position+1, len(solution)):
            if (solution[position] == solution[next_position]) or abs(position - next_position) == abs(solution[position] - solution[next_position]):
            cost = cost + 1
    return cost

def generateNextState(state):
    for i in range(0, len(state)):
        state[i] = random.randint(0,len(state)-1)
    return state

def simulatedAnnealing(solution, temperature, alpha):
    max_iter = 170000
    size= len(solution)
    current_state = generateRandomState(size)

    for iteration in range(max_iter):
        temperature = temperature * alpha

        next_state = generateNextState(current_state)
        delta_E = costFunction(next_state) - costFunction(current_state)
        exp = decimal.Decimal(decimal.Decimal(math.e) ** (decimal.Decimal(-delta_E) * decimal.Decimal(temperature)))
        if (delta_E>0) or (exp > random.uniform(0,1)):
           current_state = next_state[:]

        if(costFunction(current_state) == 0):
           return current_state

I know that my individual modules like costFunction are working correctly. However the solution is not being generated. My code is based on this link. When I run my code for n=4 all the iterations get over and no solution is generated.
Any help would be appreciated

Answer 1

There are several issues with your code. To start with, your generateNextState function is fundamentally broken. It has both design and implementation issues.

Lets handle the implementation issue first. The function modifies state in place, before also returning it. That's not good since you're passing the current state in, and then later comparing the new state with the old one (which is not very useful if they're the same object). The function should probably make a copy of the input.

The design issue is that it creates a new state that is completely random. The new state has no relation to the previous state. That's bad since it means your search is just picking values at random and seeing if you eventually guess a solution. You should pick a new state that is closely related to the old state. For instance, you could try moving a random queen to a random row:

def generateNextState(state):
    new_state = state[:] # copy the state, so we don't modify the original
    new_state[random.randint(0, len(state)-1)] = random.randint(0,len(state)-1)
    return new_state

There are lots of other ways to generate the new states, this is just one idea that came to my mind. Other options might be to move some or all of the queens to a neighboring position. Or, if you created your initial state from a range (so each value is present exactly once), you could swap the rows between two columns, generating a random permutation. That approach may be more efficient, since the state space of permutations is smaller than a state space that allows repeated values.

The other issues have to do with how you pick whether or not to use the new state you've generated. Your current logic has a bunch of stuff backwards. I think you want to change these lines:

    exp = decimal.Decimal(decimal.Decimal(math.e) ** (decimal.Decimal(-delta_E) * decimal.Decimal(temperature)))
    if (delta_E>0) or (exp > random.uniform(0,1)):

To something more like this:

    exp = math.exp(-delta_E / temperature)       # divide by temp, no need for decimals
    if delta_E < 0 or exp > random.uniform(0,1): # first condition needs the operator flipped

Here's the full version of the code I've been playing with. I've changed some more things that aren't necessary for working code, but they make diagnosing issues easier:

import random
import math

#Generate random state for Simulated Annealing
def generateRandomState(n):
    return list(range(n)) # in python 2 you don't need the `list` call here

#Cost function for Simulated Annealing
def costFunction(solution):
    cost = 0
    for position in range(0, len(solution)):
        for next_position in range(position+1, len(solution)):
            if (solution[position] == solution[next_position]) or abs(position - next_position) == abs(solution[position] - solution[next_position]):
                cost = cost + 1
    return cost

def generateNextState(state): # randomly swap two values
    state = state[:]
    i, j = random.sample(range(len(state)), 2)
    state[i], state[j] = state[j], state[i]
    return state

def simulatedAnnealing(size, temperature, alpha):
    max_iter = 170000
    current_state = generateRandomState(size)
    current_cost = costFunction(current_state)

    for iteration in range(max_iter):
        print(current_state, current_cost, temperature)
        temperature = temperature * alpha

        next_state = generateNextState(current_state)
        next_cost = costFunction(next_state)
        delta_E = next_cost - current_cost
        if delta_E<0 or math.exp(-delta_E / temperature) > random.uniform(0,1):
           current_state = next_state
           current_cost = next_cost
           if current_cost == 0:
              return current_state

    return None

An example run:

In [342]: simulatedAnnealing(8, 2, 0.99)
[0, 1, 2, 3, 4, 5, 6, 7] 28 2
[6, 1, 2, 3, 4, 5, 0, 7] 18 1.98
[6, 1, 2, 4, 3, 5, 0, 7] 8 1.9602
[6, 1, 2, 5, 3, 4, 0, 7] 5 1.9405979999999998
[6, 4, 2, 5, 3, 1, 0, 7] 4 1.92119202
[6, 4, 2, 5, 3, 1, 0, 7] 4 1.9019800997999998
[3, 4, 2, 5, 6, 1, 0, 7] 4 1.8829602988019998
[3, 4, 2, 5, 6, 1, 0, 7] 4 1.8641306958139798
[6, 4, 2, 5, 3, 1, 0, 7] 4 1.84548938885584
[6, 4, 2, 5, 1, 3, 0, 7] 4 1.8270344949672814
[6, 4, 3, 5, 1, 2, 0, 7] 5 1.8087641500176086
[6, 4, 3, 5, 1, 2, 0, 7] 5 1.7906765085174325
[6, 4, 3, 5, 1, 2, 0, 7] 5 1.7727697434322582
[6, 4, 3, 5, 1, 2, 7, 0] 6 1.7550420459979357
[6, 7, 3, 5, 1, 2, 4, 0] 5 1.7374916255379562
[3, 7, 6, 5, 1, 2, 4, 0] 5 1.7201167092825767
[3, 7, 6, 5, 1, 2, 4, 0] 5 1.7029155421897508
[3, 7, 0, 5, 1, 2, 4, 6] 3 1.6858863867678533
[3, 7, 0, 1, 5, 2, 4, 6] 3 1.6690275229001748
[3, 5, 0, 1, 7, 2, 4, 6] 4 1.652337247671173
[3, 5, 0, 1, 7, 2, 4, 6] 4 1.6358138751944613
[1, 5, 0, 3, 7, 2, 4, 6] 2 1.6194557364425166
[1, 5, 0, 3, 7, 2, 4, 6] 2 1.6032611790780915
[1, 5, 0, 3, 7, 4, 2, 6] 2 1.5872285672873105
[1, 5, 0, 3, 7, 4, 2, 6] 2 1.5713562816144375
[1, 5, 0, 2, 7, 4, 3, 6] 4 1.555642718798293
[1, 5, 0, 2, 7, 4, 3, 6] 4 1.5400862916103102
[1, 5, 2, 0, 7, 4, 3, 6] 3 1.524685428694207
[4, 5, 2, 0, 7, 1, 3, 6] 4 1.509438574407265
[4, 5, 2, 0, 7, 1, 3, 6] 4 1.4943441886631923
[7, 5, 2, 0, 4, 1, 3, 6] 3 1.4794007467765604
[7, 5, 2, 0, 4, 6, 3, 1] 3 1.4646067393087947
[7, 5, 2, 4, 0, 6, 3, 1] 3 1.4499606719157068
[7, 5, 2, 4, 0, 6, 3, 1] 3 1.4354610651965496
[7, 5, 2, 4, 0, 6, 3, 1] 3 1.4211064545445842
[7, 5, 2, 4, 6, 0, 3, 1] 1 1.4068953899991383
[7, 5, 2, 4, 6, 0, 3, 1] 1 1.392826436099147
[7, 5, 2, 4, 6, 0, 3, 1] 1 1.3788981717381554
[7, 5, 2, 4, 6, 0, 3, 1] 1 1.365109190020774
[6, 5, 2, 4, 7, 0, 3, 1] 1 1.3514580981205662
[6, 1, 2, 4, 7, 0, 3, 5] 1 1.3379435171393605
[6, 1, 2, 4, 7, 0, 3, 5] 1 1.324564081967967
[6, 1, 2, 4, 7, 0, 3, 5] 1 1.3113184411482872
[6, 1, 2, 4, 7, 0, 3, 5] 1 1.2982052567368043
[4, 1, 2, 6, 7, 0, 3, 5] 4 1.2852232041694363
[3, 1, 2, 6, 7, 0, 4, 5] 5 1.2723709721277419
[3, 1, 2, 6, 0, 7, 4, 5] 5 1.2596472624064645
[3, 1, 2, 5, 0, 7, 4, 6] 3 1.2470507897824
[3, 1, 2, 5, 0, 7, 4, 6] 3 1.234580281884576
[3, 1, 4, 5, 0, 7, 2, 6] 5 1.2222344790657302
[3, 1, 4, 5, 7, 0, 2, 6] 3 1.210012134275073
[3, 2, 4, 5, 7, 0, 1, 6] 4 1.1979120129323222
[2, 3, 4, 5, 7, 0, 1, 6] 7 1.1859328928029989
[2, 6, 4, 5, 7, 0, 1, 3] 5 1.1740735638749689
[2, 6, 4, 5, 7, 0, 1, 3] 5 1.162332828236219
[2, 6, 4, 5, 7, 0, 1, 3] 5 1.150709499953857
[4, 6, 2, 5, 7, 0, 1, 3] 3 1.1392024049543183
[4, 6, 2, 5, 1, 0, 7, 3] 2 1.1278103809047753
[4, 6, 2, 5, 1, 0, 7, 3] 2 1.1165322770957276
[0, 6, 2, 5, 1, 4, 7, 3] 1 1.1053669543247702
[0, 4, 2, 5, 1, 6, 7, 3] 3 1.0943132847815225
[0, 4, 2, 5, 1, 6, 7, 3] 3 1.0833701519337071
[0, 4, 2, 5, 7, 6, 1, 3] 3 1.07253645041437
[6, 4, 2, 5, 7, 0, 1, 3] 3 1.0618110859102263
[1, 4, 2, 5, 7, 0, 6, 3] 3 1.051192975051124
[1, 4, 2, 5, 7, 6, 0, 3] 3 1.0406810453006128
[6, 4, 2, 5, 7, 1, 0, 3] 5 1.0302742348476066
[6, 1, 2, 5, 7, 4, 0, 3] 2 1.0199714924991305
[6, 1, 2, 5, 7, 4, 0, 3] 2 1.0097717775741393
[6, 1, 2, 5, 7, 4, 0, 3] 2 0.9996740597983979
[6, 1, 2, 5, 7, 4, 0, 3] 2 0.9896773192004139
[6, 1, 2, 5, 7, 4, 0, 3] 2 0.9797805460084098
[6, 1, 2, 5, 7, 4, 0, 3] 2 0.9699827405483257
[6, 1, 2, 5, 7, 4, 3, 0] 2 0.9602829131428424
[6, 1, 2, 5, 7, 4, 3, 0] 2 0.950680084011414
[6, 1, 2, 5, 7, 4, 3, 0] 2 0.9411732831712999
[6, 1, 3, 5, 7, 4, 2, 0] 1 0.9317615503395869
[6, 1, 3, 5, 7, 4, 2, 0] 1 0.922443934836191
[6, 1, 3, 5, 7, 4, 2, 0] 1 0.9132194954878291
[6, 1, 3, 5, 7, 4, 2, 0] 1 0.9040873005329508
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8950464275276213
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8860959632523451
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8772350036198217
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8684626535836234
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8597780270477872
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8511802467773093
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8426684443095362
[6, 5, 3, 1, 7, 4, 2, 0] 1 0.8342417598664409
[6, 1, 3, 5, 7, 4, 2, 0] 1 0.8258993422677765
[6, 1, 3, 5, 7, 2, 4, 0] 1 0.8176403488450987
[6, 0, 3, 5, 7, 2, 4, 1] 1 0.8094639453566478
[6, 0, 3, 5, 7, 1, 4, 2] 1 0.8013693059030813
[6, 0, 3, 5, 7, 1, 4, 2] 1 0.7933556128440505
[6, 0, 3, 5, 7, 1, 4, 2] 1 0.78542205671561
[6, 0, 3, 5, 7, 1, 4, 2] 1 0.7775678361484539
[6, 0, 3, 5, 7, 1, 4, 2] 1 0.7697921577869694
Out[342]: [4, 0, 3, 5, 7, 1, 6, 2]