Principi di ricottura simulata in Python

Question

Devo utilizzare la ricottura simulata per un determinato problema di ottimizzazione. Per avere un'idea della tecnica, ho scritto un piccolo codice Python e ho provato ad eseguirlo. Tuttavia, non sembra dare risultati soddisfacenti.

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

Non riesco a capire dove sto andando male. C'è qualcosa di sbagliato nell'implementazione o c'è qualcosa di sbagliato nella mia comprensione della ricottura simulata? Si prega di segnalare l'errore ..

La mia idea di massima su SA: Scegli un vicino casuale Se vicino di casa migliora la sua condizione, spostare lì, Else, spostare lì con certa probabilità. La probabilità è tale che le mosse iniziali siano "consentite" ma in seguito "vietate". Finalmente convergerai nella tua soluzione.

Ho trovato l'insieme di minimi locali e minimi globali utilizzando la forza bruta. Quindi eseguo SA. Mi aspettavo che SA si convergerebbe almeno in un minimo locale, ma non sembra sempre il caso. Inoltre, non sono sicuro se ad ogni passo scelgo un vicino a caso e poi provo a spostarmi o scelgo il migliore vicino (anche se nessuno dei vicini migliora la mia condizione) e poi provo a trasferirmi.

Answer 1

Per la maggior parte, il codice sembra funzionare correttamente. Il motivo principale per cui converge lentamente è che guardi solo i due vicini su entrambi i lati del tuo attuale punto: se espandi la ricerca per includere qualsiasi punto in A, o anche solo un intorno più ampio intorno al tuo punto corrente, tu Sarò in grado di spostarmi molto più rapidamente nello spazio di ricerca.

Un altro trucco con ricottura simulata è determinare come regolare la temperatura. Hai iniziato con una temperatura molto elevata, in cui sostanzialmente l'ottimizzatore si spostava sempre al vicino, indipendentemente dalla differenza nel valore della funzione obiettivo tra i due punti. Questo tipo di movimento casuale non ti porta in media ad un punto migliore. Il trucco sta nel trovare un valore di temperatura iniziale sufficientemente basso tale che l'ottimizzatore si muoverà in punti migliori significativamente più spesso di quanto si muova in punti peggiori, ma allo stesso tempo abbia una temperatura iniziale abbastanza alta da permettere all'ottimizzatore di esplorare la ricerca spazio. Come ho accennato nel mio primo punto, se il quartiere da cui selezioni i punti è troppo limitato, non sarai mai in grado di esplorare correttamente lo spazio di ricerca anche se hai un buon programma di temperatura.

Il codice originale era un po 'difficile da leggere, sia perché si utilizzavano molte convenzioni che i programmatori Python tentano di evitare (ad esempio, punto e virgola alle estremità delle righe), e perché si è fatto un paio di cose che i programmatori in generale cercano di evitare (ad esempio, utilizzare L minuscole come nome di variabile, che sembra molto simile al numero 1). Ho riscritto il tuo codice per renderlo più leggibile e più Pythonic (con l'aiuto di autopep8). Controlla il pep8 standard per ulteriori informazioni.

In make_move, la mia riscrittura seleziona un vicino casuale da tutto lo spazio di ricerca. Puoi provare a riscriverlo per cercare in un quartiere locale espanso del punto corrente, se sei interessato a vedere come funziona (qualcosa tra ciò che hai fatto sopra e ciò che ho fatto qui).

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