シミュレーテッドアニーリングが機能しない

Question

simulated annealingを使用してn-queensの問題を実装しようとしています。私はすべての既存の問題を見上げて、それは私の問題を解決しません。私が出ているコードは、私がcostFunctionように私の個々のモジュールが正しく機能していることを知っているこの

#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 

です。ただし、解決策は生成されていません。私のコードはこの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から作成した場合（各値が正確に1回存在するため）、2つの列の間で行をスワップしてランダムな順列を生成できます。このアプローチは、置換の状態空間が繰り返し値を許容する状態空間よりも小さいので、より効率的であり得る。

その他の問題は、生成した新しい状態を使用するかどうかを選択する方法と関連しています。あなたの現在のロジックには、逆のものがたくさんあります。

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 

ここで私がプレーしてきたコードのフルバージョンがあります：もっとこのような何かに

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

：私はあなたがこれらの行を変更したいと思います。私は、コードを作業するために必要ではないいくつかのより多くのものを変更したが、彼らは診断の問題を簡単にする：

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]