Argomenti della lezione
- Introduzione
- Caratteristiche della procedura
- I passi della procedura
- Considerazioni generali
Simulated Annealing: Introduzione
In termini generali un problema di ottimizzazione può essere formulato come
z = f (x) Max!
x∈X
con
- X di insieme di soluzioni ammissibili
- z=f(x) funzione obiettivo z=f(x) da massimizzare
Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x);
Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.
Simulated Annealing: Introduzione (segue)
Problema e metodo di risoluzione
Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).
Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.
Un metodo di risoluzione può essere:
- esatto se individua un ottimo globale ammissibile
- euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).
Simulated Annealing: Introduzione (segue)
In presenza di problemi complessi dal punto di vista computazionale (NP-hard) nelle applicazioni è necessario ricorrere a tecniche euristiche di risoluzione.
Le tecniche costruttive sono orientate alla individuazione (costruzione) di una soluzione ammissibile.
Le tecniche migliorative o di ricerca locale partono da una soluzione ammissibile e puntano a migliorarla attraverso la applicazione iterativa di una mossa. Esse convergono in un ottimo locale.
Per migliorare la qualità delle soluzioni individuabili con queste tecniche è possibile ricorrere a tecniche cosiddette metaeuristiche.
Simulated Annealing: Introduzione
Simulated Annealing: Introduzione (segue)
Simulated Annealing: Introduzione (segue)
La qualità della soluzione ottenibile da una tecnica di ricerca locale dipende dalla soluzione di innesto e dalla tipologia di mossa.
Per superare la “trappola” della convergenza in un minimo locale, in corrispondenza di esso, bisognerebbe individuare una procedura che consenta di accettare soluzioni peggiorative.
Simulated Annealing: caratteristiche della procedura
La Simulated Annealing è una tecnica metaeuristica naturale che si basa sull’analogia tra il processo fisico di tempra dei solidi e la risoluzione di problemi di ottimizzazione combinatoria.
La tempra consiste in un processo fisico per il quale un solido, immerso in un bagno caldo, viene progressivamente riscaldato aumentando la temperatura del bagno fino al punto di fusione in corrispondenza del quale le particelle del sistema si distribuiscono in maniera casuale.
Successivamente si provvede al raffreddamento attraverso il lento abbassamento della temperatura del bagno.
In questo modo si raggiunge uno stato di equilibrio termico caratterizzato da un valore dell’energia interna minima.
Simulated Annealing: caratteristiche della procedura (segue)
In particolare, la Simulated Annealing deriva dall’algoritmo di Metropolis, sviluppato per simulare il processo fisico di tempra dei solidi.
A partire dallo stato corrente S, alla temperatura T e con energia E, definito dalle posizioni delle molecole che lo costituiscono, viene applicata una perturbazione consistente nello spostamento di una molecola in una nuova posizione scelta casualmente.
In tal modo il sistema raggiunge un nuovo stato, S’, con un diverso valore di energia E’.
Simulated Annealing: caratteristiche della procedura (segue)
Simulated Annealing: caratteristiche della procedura (segue)
Il nuovo stato viene accettato, come stato corrente, con una probabilità definita dalla seguente espressione:
(vedi formula)
se ΔE=E’-E è la differenza tra l’energia associata al nuovo stato S‘ e quella associata allo stato corrente S e K è la costante di Boltzmann.
Simulated Annealing: caratteristiche della procedura (segue)
Simulated Annealing: caratteristiche della procedura (segue)
Fissato un valore iniziale di T ed individuata una soluzione iniziale come soluzione corrente, l’algoritmo individua, attraverso l’applicazione casuale di una mossa, una soluzione nell’intorno della soluzione corrente.
Se la soluzione esaminata è migliore di quella corrente è sicuramente accettata altrimenti, se peggiore, viene accettata con una probabilità definita da una funzione che dipende dal parametro di controllo.
L’operazione descritta viene eseguita un certo numero di volte al termine delle quali il valore T viene abbassato ed il processo riprende allo stesso modo.
L’algoritmo termina quando il parametro T raggiunge un valore minimo prestabilito.
Simulated Annealing: caratteristiche della procedura (segue)
Simulated Annealing: caratteristiche della procedura (segue)
Se la soluzione è non peggiorativa (Δf≤0) viene accettata;
altrimenti se la soluzione è peggiorativa (Δf>0), si genera un numero casuale a (0≤a≤1): se risulta minore o uguale alla probabilità di accettazione la soluzione generata viene accettata, altrimenti viene rifiutata.
Simulated Annealing: i passi della procedura
1. Inizializzazione
Consiste nell’individuazione di una soluzione iniziale S di innesco.
2. Definizione di una mossa
Definisce l’operazione che permette di individuare casualmente una soluzione S’ nell’intorno della soluzione corrente S.
3. Accettazione della mossa
È l’operazione grazie alla quale si valuta se accettare o meno la soluzione individuata S’ come nuova soluzione corrente S (S’→S) applicando la probabilità di accettazione esposta in precedenza.
4. Definizione della cooling schedules
Rappresenta la definizione di tutti i parametri di controllo dell’algoritmo.
Simulated Annealing: i passi della procedura (segue)
Per cooling schedules si intende l’insieme delle regole che simulano il processo di raffreddamento.
Per definire una cooling schedules, in pratica, bisogna individuare:
- il valore iniziale T0 del parametro di controllo;
- il valore finale Tf del parametro di controllo;
- il numero di transizioni Lk per ciascun valore Tk;
- la legge di decremento di T.
Definizione della cooling schedules
Criteri per la definizione della cooling schedules
Il valore iniziale del parametro di controllo (To) deve essere scelto in modo che, nella fase iniziale dell’algoritmo, tutte le transizioni siano accettate.
Il valore finale del parametro di controllo (Tf ) deve essere tale che, in corrispondenza di Tf, non si possano accettare peggioramenti della soluzione.
Il numero di transizioni per ogni valore di Tk (Lk) e la regola di decremento di T devono essere correlate per assicurare che, ad ogni cambiamento del valore di T, si ristabilisca una condizione di quasi-equilibrio termico.
Definizione della cooling schedules
Scelta di T0
In corrispondenza di T0 quasi tutte le possibili variazioni peggiorative (Δf >0) devono essere accettate. Quindi deve risultare exp(-Δf/T0)≈1 ∀Δf >0 e quindi (-Δf/T0)≈0.
Possibile metodo per la scelta
- si considera il valore della funzione obiettivo f0 della soluzione iniziale;
- si pone un valore di riferimento per la massima variazione della funzione obiettivo (ad esempio Δfmax=|f0/2|);
- si pone T0=10 . Δfmax=10.|f 0 /2|
In questo modo ci si assicura che, per transizioni caratterizzate da un incremento di funzione obiettivo pari al 50% del valore iniziale, la probabilità di accettazione è exp(-Δf/T0)=exp(-1/10)=0,90.
Definizione della cooling schedules (segue)
Scelta di Tf
In corrispondenza di valori prossimi a Tf, la probabilità di accettare soluzioni peggiorative deve essere praticamente nulla, ovvero exp(-Δf/Tf)≈0 ∀Δf >0 ossia (Δf/Tf)→∞ ∀Δf >0.
Possibile metodo per la scelta
- si considera il valore della funzione obiettivo f0 della soluzione iniziale;
- si pone un valore di riferimento per la minima variazione della funzione obiettivo (ad esempio Δfmin= 10-3|f0|);
- si pone Δf =10-1 . Δfmin= 10-4|f0 |
In questo modo ci si assicura che, per transizioni caratterizzate da un incremento di funzione obiettivo pari allo 0,1% del valore iniziale, la probabilità di accettazione è praticamente nulla essendo exp(-Δf/Tf)=exp(-10)=4,54·10-5.
Definizione della cooling schedules (segue)
Scelta della legge di decremento di T e del numero di transizioni per ogni valore di Tk
La regola più frequentemente utilizzata per decrementare il parametro T dalla iterazione generica k alla successiva k+1 è
Tk+1=α·Tk con 0< α <1.
Se α è elevato (es: 0,99) il decremento è più lento e, conseguentemente, Lk può essere basso. Al contrario, se α è più basso (es: 0,9), Lk deve essere più elevato per ripristinare la condizioni di equilibrio termico.
In alternativa si può considerare Lk=L costante e correlato alla dimensione del problema n (es: L=n).
Simulated Annealing: considerazioni generali
Simulated Annealing: considerazioni generali (segue)
La qualità della soluzione ottenibile dipende dai diversi parametri di calibrazione della procedura ovvero:
- Tipo di mossa
- Cooling schedules
Caratteristiche generali della procedura
- Produce soluzioni buone;
- Presenta una elevata flessibilità intesa come capacità di adattamento per la risoluzione di problemi diversi;
- L’implementazione è molto semplice;
- Risulta molto sensibile alla scelta dei parametri di calibrazione;
- I tempi di calcolo dipendono dalla cooling schedules.
Le lezioni del Corso
1. Introduzione al corso di Ricerca operativa II
2. Generalità e classificazione dei sistemi di produzione
3. La logistica dei sistemi di produzione
4. Introduzione all'ottimizzazione combinatoria
5. Fondamenti di teoria della complessità computazionale
6. Algoritmi euristici costruttivi e migliorativi
10. Problemi di Localizzazione
12. Introduzione alla gestione delle scorte
13. Modelli stocastici per la gestione delle scorte
14. Modelli discreti per la gestione delle scorte
15. Introduzione allo scheduling
16. Scheduling su macchina singola
17. Problemi di scheduling su macchina singola e su macchine parall...
