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

ほとんどの場合、コードはうまく機能しているようです。収束が遅い主な理由は、現在の点の両側にある 2 つの近傍しか見ていないためです。A 内の任意の点を含めるように検索を拡張したり、現在の点の周囲のより広い近傍を含めたりすると、検索スペース内をより迅速に移動できるようになります。

シミュレートされたアニーリングのもう 1 つのトリックは、温度を調整する方法を決定することです。あなたは非常に高い温度から始めました.2点間の目的関数値の違いに関係なく、基本的にオプティマイザーは常に隣に移動します. この種のランダムな動きでは、平均してより良いポイントに到達することはありません. トリックは、オプティマイザが悪い点に移動するよりもはるかに頻繁に良い点に移動するように、十分に低い開始温度値を見つけることですが、同時に、オプティマイザが検索を探索できるように十分に高い開始温度を設定することです。スペース。最初のポイントで述べたように、ポイントを選択する近隣が限定的すぎると、適切な温度スケジュールを持っていても検索スペースを適切に探索することができなくなります。

元のコードは、Python プログラマーが回避しようとする多くの規則 (行末のセミコロンなど) を使用したことと、プログラマーが一般的に回避しようとするいくつかのこと (たとえば、変数名として小文字の L を使用すると、数字に非常によく似ています1)。コードを書き直して、より読みやすく、より Pythonic にしました ( の助けを借りてautopep8)。詳細については、 pep8 標準を確認してください。

ではmake_move、私の書き直しにより、探索空間全体から 1 つのランダムな近傍が選択されます。それがどの程度うまく機能するかを確認したい場合は、現在のポイントの拡張されたローカル ネイバーフッドを参照するように書き直すことができます (上記で行ったことと、ここで行ったことの間の何か)。

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 に答える