Simulated annealing

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Simulated Annealing)

Il Simulated Annealing (in italiano ricottura simulata) è una strategia che viene utilizzata per risolvere problemi di ottimizzazione.

Questo processo mira a trovare un minimo globale quando si è in presenza di più minimi locali.

Il concetto di annealing ("ricottura") deriva dalla scienza dei metalli, dov'è usato per descrivere il processo di eliminazione di difetti reticolari dai cristalli tramite una procedura di riscaldamento seguita da un lento raffreddamento. In questo caso un difetto reticolare corrisponde ad una combinazione errata di due oggetti (ad esempio una connessione errata di due neuroni all'interno di una rete neurale).

Procedimento di utilizzo[modifica | modifica wikitesto]

  1. Viene scelta una temperatura iniziale arbitraria:
    1. Si sonda il problema in modo da individuarne le possibili soluzioni (da 50 a 100 soluzioni);
    2. Per ogni possibile soluzione se ne calcola il costo;
    3. Si prende il \Delta E_{max};
    4. A questo punto si prende una temperatura iniziale maggiore della variazione di energia (T_{iniziale} > \Delta E_{max}) ma dello stesso ordine di grandezza;
  2. Viene abbassata la temperatura fino a raggiungere un valore prossimo allo 0;
  3. In prossimità del minimo valore di T si troverà un minimo (di energia) abbastanza forte;
  4. Ripetendo questo ciclo la possibilità di trovare la stessa soluzione è tendente a 0. Se vengono trovate due soluzioni uguali per due prove diverse dello stesso problema significa che, molto probabilmente, qualcosa non funziona correttamente.

La temperatura della rete viene definita in modo che:

  1. Se T è elevata: Ci si può permettere di fare salti alti e quando si trova un minimo si può provare a proseguire per scoprire se si trattava solamente di un minimo locale;
  2. Se T è bassa: Si possono ancora fare dei salti alti ma con minore probabilità quindi si procede a passi più corti;
  3. Riduzione veloce di T: Implica il congelamento di alcune fluttuazioni termiche;
  4. Riduzione molto lenta di T: Può implicare il non raggiungimento della conclusione del calcolo e quindi il non trovare un minimo globale.


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica