Algoritme de recocido simulat

Simulated annealing (SA), també cridat temple simulat, recocido simulat, cristalisació simulada o refredat simulat, és un algoritme de busca metaheurística per a problemes d'optimisació global; l'objectiu general d'este tipo d'algoritmes és trobar una bona aproximació al valor òptim d'una funció en un espai de busca gran. Dit "òptim global" correspon a la solució del problema d'interés per al que no existix un millor valor. En el cas de que tal problema siga de minimisació, l'òptim global serà aquell per al qual la funció objectiu tinga el més chicotet possible de tots els de el seu (espai de busca) Pel contrari, per a un problema de maxización, l'òptim global és aquell en el valor més alt possible.

El nom i inspiració de SA ve del procés de recocido de l'acer i ceràmiques, una tècnica que consistix en calfar i després gelar llentament el material per a variar les seues propietats físiques. La calor causa que els àtoms aumenten la seua energia i que puguen aixina desplaçar-se de les seues posicions inicials (un mínim local d'energia); el refredat llent els dona majors provabilitats de recristalizar en configuracions en menor energia que l'inicial (mínim global).

El método va ser descrit independentment per: 1) Scott Kirkpatrick, C. Daniel Gelatt i Mario P. Vecchi en 1983, i 2) per un atre costat per Vlado Černý en 1985. El método SA és una adaptació de l'algoritme Metropolis-Hastings, un método de Montecarlo utilisat per a generar mostres d'estats d'un sistema termodinàmic.

Iteración bàsica

En cada iteración, el método de recocido simulat evalua alguns veïns de l'estat actual s i probabilísticamente decidix entre efectuar una transició a un nou estat s' o quedar-se en l'estat s. En l'eixemple de recocido de metals descrit dalt, l'estat s es podria definir en funció de la posició de tots els àtoms del material en el moment actual; el desplaçament d'un àtom es consideraria com un estat veí del primer en este eixemple.

Típicament la comparació entre estats veïns es repetix fins que es trobe un estat òptim que minimise l'energia del sistema o fins que es complixca cert temps computacional o atres condicions.

Veïnat d'un estat

El veïnat d'un estat s està compost per tots els estats als que es puga aplegar a partir de s per mig d'un canvi en la conformació del sistema. Els estats veïns són generats per mig de métodos de Montecarlo.

El método d'evaluació d'estats veïns és fonamental per a trobar una solució òptima global al problema donat. Els algoritmes heurístics, basats en buscar sempre un estat veí millor (en energia més baixa) que l'actual es detenen en el moment que troben un mínim local d'energia. El problema en este método és que no pot assegurar que la solució trobada siga un òptim global, puix l'espai de busca explorat no comprén totes les possibles variacions del sistema.

Provabilitat de transició

La provabilitat de fer la transició al nou estat s és una funció P(δ I, T) de la diferència d'energia δI=I(s')-I(s) entre els dos estats, i de la variable T, cridada temperatura per analogia en el concepte físic de temperatura.

Si δI és negatiu, és dir, la transició disminuïx l'energia, el moviment és acceptat en provabilitat P=1. És important remarcar que la condició de que el sistema sempre passe a un sistema de menor energia quan es troba una no és en absolut necessària per a l'èxit del método. Quan δI és positiu la provabilitat de transició P és sempre distinta de zero, encara , és dir, el sistema pot passar a un estat de major energia (pijor solució) que l'estat actual. Esta propietat impedix que el sistema es quede atrapat en un òptim local.

A mida que la temperatura tendix al mínim, la provabilitat de transició a un estat de major energia tendix a zero asintóticamente. Quan T aplega a zero, l'algoritme solament acceptarà canvis a estats en menor energia. Per esta propietat, la temperatura juga un paper molt important en el control de l'evolució del sistema. A temperatures altes, el sistema tendirà a bots d'energia grans entre els estats, mentres que a temperatures més baixes, els canvis en energia seran menors.

Aixina, en cada iteración l'algoritme tendix a trobar estats en menor energia total. Hi ha moltes maneres de disminuir la temperatura, sent la més usual l'exponencial, a on T disminuïx per un factor α<1 en cada pas.

Protocol de recocido

Com el nom de l'algoritme sugerix, la variació de la temperatura durant la computació és una característica distintiva d'este método. L'algoritme comença en un valor de T molt alt, que va decreixent en cada iteración seguint un cert protocol de recocido, que pot ser diferent per a cada problema, pero que sempre deu terminar en T=0. Aixina el sistema serà lliure inicialment d'explorar una gran porció de l'espai de busca, ignorant chicotetes variacions de l'energia entre els estats veïns evaluats, per a més tarde centrar-se en regions en estats de baixa energia i, al final, canviar solament a estats en energia menor que l'inicial, fins a alcançar un mínim.

Erro al crear miniatura:

Eixemple ilustrant l'importància del protocol de refredat: El problema consistix en dispondre els píxelés en l'image de tal manera que es minimise una funció d'energia potencial que causa que els colors similars s'atraguen a distàncies curtes i es repelixquen a distàncies llargues. En cada iteración s'intercanvien les posicions de dos píxels adjacents. L'image de l'esquerra és obtinguda en un protocol de gelat ràpit, en el que la temperatura descendix ràpidament, i la de la dreta, en un protocol llent, equiparables als processos de formació de sòlits amorfos i cristalinos respectivament.

La provabilitat de que l'algoritme acabe trobant el mínim global per a un problema donat s'aproxima a 1 a mida que el protocol de recocido s'estén.

Pseudocódigo

Escomença en un estat s₀ i seguix fins a un màxim de k_max passos o fins que es troba un estat en energia menor o igual que i_min. La funció veí(s) genera aleatoriamente un veí d'un estat donat s; la funció encert(0, 1) torna un valor aleatori uniformemente distribuït en l'interval [0, 1]; vore Distribució uniforme. El procés de recocido (gelat) s'expressa per mig de temperatura(r), que dona la temperatura en funció de la fracció r del temps que ya ha transcorregut.

• Siga s = s₀
• Per a k = 0 fins a k_max (exclusive):
  • T ← temperatura(k ∕ k_max)
  • s_nue ← veí(s)
  • Si P(I(s), I(s_nue), T) ≥ encert(0, 1):
    • s ← s_nue
• Eixida: estat final s

La provabilitat d'acceptació originalment proposta és

• si $e^{\prime }<e$, llavors $P(e,e^{\prime },T)=1$
• si $e^{\prime }>e$, llavors $P(e,e^{\prime },T)=\exp (-(e^{\prime }-e)/T)$