Python中模拟退火的基础知识
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19757551/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Basics of Simulated Annealing in Python
提问by user2916473
I have to use simulated annealing for a certain optimization problem. To get a 'feel' of the technique, I wrote a small python code and tried to run it. However, it doesn't seem to be giving satisfactory results.
对于某个优化问题，我必须使用模拟退火。为了“感受”该技术，我编写了一个小的 Python 代码并尝试运行它。然而，它似乎并没有给出令人满意的结果。
import random;
import math;
from math import *;
LIMIT=100000;
def update_temperature(T,k):
T1=T/log(k+1);
# print "temp now is " + str(T1);
return T1;
def get_neighbors(i,l):
if(l>1):
if(0<=i and i<l):
if(i==0):
return [1];
if(i==l-1):
return [l-2];
return [i-1,i+1];
return [];
def make_move(x,A,T):
nhbs=get_neighbors(x,len(A));
nhb=nhbs[random.choice(range(0,len(nhbs)))];
delta=A[nhb]-A[x];
if(delta < 0):
return nhb;
else:
r=random.random();
if(r <= (e**(-1*delta)/(T*1.0))):
return nhb;
return x;
def simulated_annealing(A):
l=len(A);
init_pos=random.choice(xrange(0,l));
T=10000**30;
k=1;
x_best=init_pos;
x=x_best;
while(T>0.0000001 ):
x=make_move(x,A,T);
if(A[x] < A[x_best]):
x_best=x;
T=update_temperature(T,k);
k+=1;
return [x,x_best,init_pos];
def isminima_local(p,A):
l=len(A);
if(l==1 and p==0):
return True;
if(l>1):
if(p==0):
if(A[0] <=A[1]):
return True;
if(p==l-1):
if(A[p-1] >=A[p]):
return True;
if(0<=p and p<l and A[p-1]>=A[p] and A[p]<=A[p+1]):
return True;
return False;
def func(x):
F=sin(x);
return F;
def initialize(l):
A=[0]*l;
for i in xrange(0,l):
A[i]=func(i);
return A;
def main():
A=initialize(LIMIT);
local_minima=[];
for i in xrange(0,LIMIT):
if( isminima_local(i,A)):
local_minima.append([i,A[i]]);
sols=simulated_annealing(A);
m,p=A[0],0;
for i in xrange(1,LIMIT):
if(m>A[i]):
m=A[i];
p=i;
print "Global Minima at \n";
print p,m;
print "After annealing\n";
print "Solution is " + str(sols[0]) + " " + str(A[sols[0]]);
print "Best Solution is " + str(sols[1]) + " " + str(A[sols[1]]);
print "Start Solution is " + str(sols[2]) + " " + str(A[sols[2]]);
for i in xrange(0,len(local_minima)):
if([sols[0],A[sols[0]]]==local_minima[i]):
print "Solution in local Minima";
if([sols[1],A[sols[1]]]==local_minima[i]):
print "Best Solution in local Minima";
for i in local_minima:
print i;
main();
I am unable to understand where I am going wrong. Is there something wrong with the implementation or is there something wrong in my understanding about simulated annealing ? Please point out the error..
我无法理解我哪里出错了。实现有问题还是我对模拟退火的理解有问题？请指出错误..
My rough idea about SA: Pick a random neighbor If neighbor improves your condition, move there, Else, move there with certain probability. The probability is such that initially bad moves are 'allowed' but they are 'prohibited' later on. Finally you will converge to your solution.
我对 SA 的粗略想法：选择一个随机邻居 如果邻居改善了你的状况，就搬到那里，否则，以一定的概率搬到那里。概率是这样的，最初的坏举动是“允许”的，但后来被“禁止”了。最后，您将收敛到您的解决方案。
I have found the set of local minima and global minima using brute force. Then I run SA. I was expecting that SA will atleast converge to a local minima but that doesn't seem to be the case always. Also, I am not sure if at every step I choose a neighbor randomly and then try to move or I choose the bestneighbor ( even if none of the neighbors improve my condition) and then try to move there.
我使用蛮力找到了局部最小值和全局最小值的集合。然后我运行SA。我原以为 SA 至少会收敛到局部最小值，但情况似乎并非总是如此。此外，我不确定是否在每一步我都随机选择一个邻居然后尝试移动，或者我选择最好的邻居（即使没有邻居改善我的状况）然后尝试移动到那里。
回答by hunse
For the most part, your code seems to work well. The main reason that it's slow to converge is that you only look at the two neighbors on either side of your current point: if you expand your search to include any point in A, or even just a wider neighborhood around your current point, you'll be able to move around the search space much more quickly.
在大多数情况下，您的代码似乎运行良好。收敛缓慢的主要原因是您只查看当前点两侧的两个邻居：如果您扩展搜索以包括 A 中的任何点，或者甚至只是当前点周围更广泛的邻域，您将能够更快地在搜索空间中移动。
Another trick with simulated annealing is determining how to adjust the temperature. You started with a very high temperature, where basically the optimizer would always move to the neighbor, no matter what the difference in the objective function value between the two points. This kind of random movement doesn't get you to a better point on average. The trick is finding a low enough starting temperature value such that the optimizer will move to better points significantly more often than it moves to worse points, but at the same time having a starting temperature that is high enough to allow the optimizer to explore the search space. As I mentioned in my first point, if the neighborhood that you select points from is too limited, then you'll never be able to properly explore the search space even if you have a good temperature schedule.
模拟退火的另一个技巧是确定如何调节温度。你从一个非常高的温度开始，基本上优化器总是会移动到邻居，无论两点之间的目标函数值有什么差异。平均而言，这种随机运动不会让您达到更好的水平。诀窍是找到一个足够低的起始温度值，以便优化器移动到更好点的频率明显高于移动到更差点的频率，但同时具有足够高的起始温度以允许优化器探索搜索空间。正如我在第一点中提到的，如果您从中选择点的社区太有限，那么即使您有良好的温度计划，您也永远无法正确探索搜索空间。
Your original code was somewhat hard to read, both because you used a lot of conventions that Python programmers try to avoid (e.g., semicolons at ends of lines), and because you did a few things that programmers in general try to avoid (e.g., using lowercase L as a variable name, which looks very similar to the numeral 1). I rewrote your code to make it both more readable and more Pythonic (with the help of autopep8). Check out the pep8 standardfor more information.
你的原始代码有点难以阅读，因为你使用了很多 Python 程序员试图避免的约定（例如，行尾的分号），而且因为你做了一些程序员通常试图避免的事情（例如，使用小写的 L 作为变量名，看起来与数字非常相似1）。我重写了您的代码，使其更具可读性和 Pythonic（在 的帮助下autopep8）。查看pep8 标准了解更多信息。
In make_move, my rewrite picks one random neighbor from across the whole search space. You can try rewriting it to look in an expanded local neighborhood of the current point, if you're interested in seeing how well that works (something between what you had done above and what I've done here).
在 中make_move，我的重写从整个搜索空间中随机选择一个邻居。您可以尝试重写它以查看当前点的扩展本地邻域，如果您有兴趣了解它的工作情况（介于您上面所做的和我在这里所做的之间）。
import random
import math
LIMIT = 100000
def update_temperature(T, k):
return T - 0.001
def get_neighbors(i, L):
assert L > 1 and i >= 0 and i < L
if i == 0:
return [1]
elif i == L - 1:
return [L - 2]
else:
return [i - 1, i + 1]
def make_move(x, A, T):
# nhbs = get_neighbors(x, len(A))
# nhb = nhbs[random.choice(range(0, len(nhbs)))]
nhb = random.choice(xrange(0, len(A))) # choose from all points
delta = A[nhb] - A[x]
if delta < 0:
return nhb
else:
p = math.exp(-delta / T)
return nhb if random.random() < p else x
def simulated_annealing(A):
L = len(A)
x0 = random.choice(xrange(0, L))
T = 1.
k = 1
x = x0
x_best = x0
while T > 1e-3:
x = make_move(x, A, T)
if(A[x] < A[x_best]):
x_best = x
T = update_temperature(T, k)
k += 1
print "iterations:", k
return x, x_best, x0
def isminima_local(p, A):
return all(A[p] < A[i] for i in get_neighbors(p, len(A)))
def func(x):
return math.sin((2 * math.pi / LIMIT) * x) + 0.001 * random.random()
def initialize(L):
return map(func, xrange(0, L))
def main():
A = initialize(LIMIT)
local_minima = []
for i in xrange(0, LIMIT):
if(isminima_local(i, A)):
local_minima.append([i, A[i]])
x = 0
y = A[x]
for xi, yi in enumerate(A):
if yi < y:
x = xi
y = yi
global_minumum = x
print "number of local minima: %d" % (len(local_minima))
print "global minimum @%d = %0.3f" % (global_minumum, A[global_minumum])
x, x_best, x0 = simulated_annealing(A)
print "Solution is @%d = %0.3f" % (x, A[x])
print "Best solution is @%d = %0.3f" % (x_best, A[x_best])
print "Start solution is @%d = %0.3f" % (x0, A[x0])
main()
