Recuita simulada

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 en 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 en 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[modifica | modifica el codi]

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

  • Inicialitzar:
    • Establir  \beta = \beta_0  on \beta = 1/T  on T és el paràmetre temperatura.
    • Establir  k = 0 (passos de temperatura)
    • Establir  n_{\beta} = 0  (nombre d'iteracions per pas de temperatura)
  • Generar una configuració aleatòria  x_{0}^{*} de l'argument de la funció objectiu a minimitzar.
  • (GEN_RND) Fer evolucionar la configuració inicial  x_{0} cap a una configuració pertorbada,  x^{*} fent una modificació petita:  x_{0} + \delta x  \rightarrow   x^{*}
  • Si  f( x^{*}) < f( x_{0}): accepta  x^{*} . Sinó, accepta  x^{*} amb probabilitat  \exp(-\beta \Delta f)
    • Fer  n_{\beta} \leftarrow n_{\beta}+1
    • Si  n_{\beta} \leq n_{\beta}^{MAX} vés a (GEN_RND)
    • Incrementar la temperatura inversa  \beta  \leftarrow \beta + \delta \beta
    • Fer  k \leftarrow k + 1 . Si  k < k_{MAX} vés a (GEN_RND) sinó (Acaba)
    • Acaba


Referències[modifica | modifica el codi]

  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[modifica | modifica el codi]