Python中模拟退火的基础知识

Question

我必须使用模拟退火来解决某个优化问题.为了获得该技术的"感觉",我编写了一个小的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();

我无法理解我哪里出错了.实现是否有问题,或者我对模拟退火的理解是否有问题？请指出错误..

关于SA的粗略想法:选择一个随机的邻居如果邻居改善了你的状况,那么移动到那里,其他的,以一定的概率移动到那里.概率是这样的,即最初的不良行动是"允许的",但后来被"禁止".最后,您将收敛到您的解决方案.

我使用蛮力找到了一组局部最小值和全局最小值.然后我运行SA.我期待SA至少会收敛到局部最小值,但这似乎并非总是如此.此外,我不确定在每一步我是否随机选择邻居然后尝试移动或我选择最好的邻居(即使没有邻居改善我的条件)然后尝试移动到那里.

Answer 1

在大多数情况下,您的代码似乎运行良好.收敛缓慢的主要原因是你只看你当前点两边的两个邻居:如果你扩大你的搜索以包括A中的任何一个点,或者甚至只是你当前点附近的一个更宽的邻域,你'能够更快地在搜索空间中移动.

模拟退火的另一个技巧是确定如何调整温度.你从非常高的温度开始,无论两点之间的目标函数值有什么不同,基本上优化器总会移动到邻居.这种随机运动并不能让你平均得到更好的结果.诀窍是找到一个足够低的起始温度值,这样优化器将比移动到更差点更频繁地移动到更好的点,但同时具有足够高的起始温度以允许优化器探索搜索空间.正如我在第一点中提到的,如果您选择的邻域太有限,那么即使您有一个良好的温度计划,您也永远无法正确探索搜索空间.

您的原始代码有点难以阅读,因为您使用了许多Python程序员试图避免的约定(例如,行末端的分号),并且因为您做了一些程序员通常试图避免的事情(例如,使用小写L作为变量名,看起来非常类似于数字1).我重写了你的代码,使它更具可读性和Pythonic(借助于它autopep8).查看pep8标准了解更多信息.

在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()