14

对于某个优化问题，我必须使用模拟退火。为了“感受”这项技术，我编写了一个小的 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 至少会收敛到局部最小值，但情况似乎并非总是如此。另外，我不确定我是在每一步随机选择一个邻居然后尝试移动还是选择最好的邻居（即使没有邻居改善我的状况）然后尝试移动到那里。

4

1 回答 1

18

在大多数情况下，您的代码似乎运行良好。收敛缓慢的主要原因是您只查看当前点两侧的两个邻居：如果您扩展搜索以包括 A 中的任何点，甚至只是当前点周围更广泛的邻域，您将能够更快地在搜索空间中移动。

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

你的原始代码有点难以阅读，既因为你使用了很多 Python 程序员试图避免的约定（例如，行尾的分号），也因为你做了一些程序员通常试图避免的事情（例如，使用小写 L 作为变量名，看起来与数字非常相似1）。我重写了您的代码，使其更具可读性和 Python 风格（在 的帮助下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()
于 2013-11-03T22:43:24.910 回答