模拟退火不起作用

Question

我想用simulated annealing来实现n皇后问题。我已经查看了所有存在的问题，并没有解决我的问题。我想出的代码是这样的

#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 

我知道我喜欢costFunction各个模块正常工作。但是解决方案没有生成。我的代码是基于这个link。当我运行代码n=4时，所有迭代都会结束，并且不会生成解决方案。
任何帮助，将不胜感激

Answer 1

您的代码有几个问题。首先，你的generateNextState功能基本上被打破。它有设计和实现问题。

让我们先处理执行问题。该功能修改state到位，之前也返回它。这不是很好，因为你将当前状态传入，然后再将新状态与旧状态进行比较（如果它们是同一个对象，则不是很有用）。该函数可能应该创建一个输入的副本。

设计问题是它创建一个完全随机的新状态。新国家与以前的国家没有任何关系。这很糟糕，因为这意味着您的搜索只是随机选取值并查看您是否最终猜出了解决方案。你应该选择一个与旧状态密切相关的新状态。举例来说，你可以尝试移动随机女王排随机：

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 

有很多其他的方式来产生新的状态，这只是一个来到我的脑海的想法。其他选项可能是将部分或全部皇后移动到邻近位置。或者，如果您从range创建初始状态（因此每个值只出现一次），则可以交换两列之间的行，生成随机排列。这种方法可能更有效率，因为排列的状态空间小于允许重复值的状态空间。

其他问题与如何选择是否使用您生成的新状态有关。你目前的逻辑有一堆东西倒退。我想你想改变这些行：

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

要更多的东西是这样的：

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 

这是我一直在玩代码的完整版本。我已经改变了一些事情，是没有必要的工作代码，但他们使诊断问题变得更加容易：

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 

一个例子运行：

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]