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 β = β 0 {\displaystyle \beta =\beta _{0}} on β = 1 / T {\displaystyle \beta =1/T} on T {\displaystyle T} és el paràmetre temperatura.
    • Establir k = 0 {\displaystyle k=0} (passos de temperatura)
    • Establir n β = 0 {\displaystyle n_{\beta }=0} (nombre d'iteracions per pas de temperatura)
  • Generar una configuració aleatòria x 0 ∗ {\displaystyle x_{0}^{*}} de l'argument de la funció objectiu a minimitzar.
  • (GEN_RND) Fer evolucionar la configuració inicial x 0 {\displaystyle x_{0}} cap a una configuració pertorbada, x ∗ {\displaystyle x^{*}} fent una modificació petita: x 0 + δ x → x ∗ {\displaystyle x_{0}+\delta x\rightarrow x^{*}}
  • Si f ( x ∗ ) < f ( x 0 ) : {\displaystyle f(x^{*})<f(x_{0}):} accepta x ∗ {\displaystyle x^{*}} . Sinó, accepta x ∗ {\displaystyle x^{*}} amb probabilitat exp ⁡ ( − β Δ f ) {\displaystyle \exp(-\beta \Delta f)}
    • Fer n β ← n β + 1 {\displaystyle n_{\beta }\leftarrow n_{\beta }+1}
    • Si n β ≤ n β M A X {\displaystyle n_{\beta }\leq n_{\beta }^{MAX}} vés a (GEN_RND)
    • Incrementar la temperatura inversa β ← β + δ β {\displaystyle \beta \leftarrow \beta +\delta \beta }
    • Fer k ← k + 1 {\displaystyle k\leftarrow k+1} . Si k < k M A X {\displaystyle k<k_{MAX}} vés a (GEN_RND) sinó (Acaba)
    • Acaba

Referències

  1. ↑ Torrent-Fontbona, F. Decision support methods for global optimization. M.Sc. Thesis of the University of Girona (2012)
  2. ↑ F. Torrent, V. Muñoz, B. López. Solving large immobile location-allocation by affinity propagation and simulated annealing. Application to select which sporting event to watch Expert Systems with Applications, Volume 40, Issue 11, pages 4593-4599, ISSN 0957-4174, doi:10.1016/j.eswa.2013.01.065(2013)

Enllaços externs

  • http://yuval.bar-or.org/index.php?item=9 Arxivat 2009-08-30 a Wayback Machine.
  • http://biomath.ugent.be/~brecht/downloads.html Arxivat 2009-03-19 a Wayback Machine.
  • http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10548&objectType=file Arxivat 2008-09-23 a Wayback Machine.
  • http://en.wikiversity.org/wiki/Simulated_Annealing_Project