我正在尝试基于我试图解决的 TSP 在 ruby 上实现模拟退火(我从 java 转换了这段代码)。然而事实证明,退火使我的结果变得最差!(PlayerPath 给了我一条路径,我将在其中进行模拟退火 - 我通过执行贪心算法 1 得到了路径)。有人可以帮我检查代码,看看我是否有问题,或者只是模拟退火并不总是能让事情变得更好?
#BEGIN ANNEALING
for i in 1..k
temp = 10000000
cooling = 0.003
if (playerPath[i].length > 2) # if path is larger than 2
bestPath = playerPath[i]
while temp > 1
newSolution = playerPath[i];
firstPosition = rand(newSolution.length)
secondPosition = rand(newSolution.length)
if(firstPosition == 0 || firstPosition == newSolution.length-1)
next
end
if(secondPosition == 0 || secondPosition == newSolution.length-1 )
next
end
# swap cities
tempStore = newSolution[firstPosition]
newSolution[firstPosition] = newSolution[secondPosition]
newSolution[secondPosition] = tempStore
# Tabulation
currentEnergy = calculate_distance(playerPath[i])
neighbourEnergy = calculate_distance(newSolution)
if(acceptanceProbability(currentEnergy,neighbourEnergy,temp) > rand)
playerPath[i] = newSolution
end
if(calculate_distance(playerPath[i])< calculate_distance(bestPath))
bestPath = playerPath[i];
end
temp *= (1-cooling);
end
end
end
#END ANNEALING
#acceptanceProbability
def acceptanceProbability(energy, newEnergy,temperature)
# If the new solution is better, accept it
if (newEnergy < energy)
return 1.0
end
# If the new solution is worse, calculate an acceptance probability
return Math.exp((energy - newEnergy) / temperature)
end