Recuita simulada

La recuita simulada (simulated annealing en anglès) és una tècnica de cerca utilitzada en informàtica o aplicacions d'intel·ligència artificial per trobar solucions aproximades a un problema d'optimització. Està basat en una tècnica de la indústria metal·lúrgica que consisteix a escalfar i refredar lentament un material de manera que els àtoms s'alliberen de les seves posicions inicials i es mouen aleatòriament per l'espai donant-los més possibilitats (durant el refredament) a allotjar-se finalment en estats d'energia menors.

L'algorisme consisteix a partir d'una solució inicial i després seleccionar una nova solució aleatòria propera a la solució inicial. Si la nova solució és millor que l'anterior, l'algorisme es mou cap al nou punt (solució), sinó té una certa probabilitat de quedar-se amb la solució anterior i una altra de moure's cap a la nova solució (encara que aquesta sigui pitjor).^[1][2] Aquest procés es repeteix fins que es doni la condició d'acabament que normalment és un temps determinat, un nombre d'iteracions o un cert nivell de qualitat de la solució. La probabilitat de moure's cap a posicions "pitjors" serveix per a evitar que l'algorisme quedi estancat en òptims locals o zones planes i busqui la solució final d'una manera global.

Esquema de l'algorisme

A continuació es mostra un esquema en pseudocodi de la implementació de l'algorisme.

• Inicialitzar:
  • Establir ${\displaystyle \beta =\beta _{0}}$ on ${\displaystyle \beta =1/T}$ on ${\displaystyle T}$ és el paràmetre temperatura.
  • Establir ${\displaystyle k=0}$ (passos de temperatura)
  • Establir ${\displaystyle n_{\beta }=0}$ (nombre d'iteracions per pas de temperatura)

• Generar una configuració aleatòria ${\displaystyle x_{0}^{*}}$ de l'argument de la funció objectiu a minimitzar.

• (GEN_RND) Fer evolucionar la configuració inicial ${\displaystyle x_{0}}$ cap a una configuració pertorbada, ${\displaystyle x^{*}}$ fent una modificació petita: ${\displaystyle x_{0}+\delta x\rightarrow x^{*}}$

• Si ${\displaystyle f(x^{*})<f(x_{0}):}$ accepta ${\displaystyle x^{*}}$. Sinó, accepta ${\displaystyle x^{*}}$ amb probabilitat ${\displaystyle \exp(-\beta \Delta f)}$
  • Fer ${\displaystyle n_{\beta }\leftarrow n_{\beta }+1}$
  • Si ${\displaystyle n_{\beta }\leq n_{\beta }^{MAX}}$ vés a (GEN_RND)
  • Incrementar la temperatura inversa ${\displaystyle \beta \leftarrow \beta +\delta \beta }$
  • Fer ${\displaystyle k\leftarrow k+1}$. Si ${\displaystyle k<k_{MAX}}$ vés a (GEN_RND) sinó (Acaba)
  • Acaba