Sia F l' insieme delle soluzioni ammissibili s di un generico problema di ottimizzazione combinatoria e c(s) la sua funzione costo e supponiamo, senza perdere in generalità, che si tratti di un problema di minimo:

min

1-INTORNI

Un intorno N(s) associa ad ogni soluzione ammissibile s un sottoinsieme di soluzioni ammissibili "vicine" (cioè uno degli elementi dell' insieme potenza 2^F di F). Si suppone che N sia "esplorabile" efficientemente. Ciò equivale a supporre l' esistenza di un algoritmo che chiamiamo IMPR(s) (per "improvement") e che fornisce efficientemente (ciò equivale il più delle volte, come sappiamo, a dire che IMPR è polinomiale) una soluzione t in N(s) tale che c(t) è minore di c(s), se tale soluzione esiste, mentre fornisce 0 se ciò non è possibile. Spesso t è una soluzione di N(s) diversa da s con valore più  basso possibile della funzione obbiettivo.

GENERAL_LOCAL_SEARCH(N):

begin

generare una soluzione ammissibile s in F ;

while IMPR(s) 0 do s := IMPR(s) ;

return s

end

COSE DA DECIDERE:

• come generare il primo s
• come scegliere un "buon" intorno N
• se vale la pena di ripetere la procedura magari partendo da soluzioni ammissibili generate a caso in F

ALCUNE EURISTICHE MOLTO NOTE

• Randomised Repeated Trials (Prove Ripetute Casualizzate)
• Greedy Randomised Adaptive Search Procedure (GRASP)
• Simulated Annealing (SA)
• Algoritmi Genetici (GA)
• Ricerca con Tabu (Tabu Search, TS)
• Sampling-and-Clustering (SC)
• Metodi di Soglia (Threshold Method, TM)
• Exploring Tabu Search (X-TS)
• Ant System (AS)
• Ant Colony Optimisation (ACO)
• Granular Tabu Search (GTS)

Si distinguono euristiche a molti agenti (ad esempio GA, AS, ACO) e ad agente singolo (GRASP, SA, TS).

Vedremo brevemente solo alcune delle più famose.

2-SIMULATED ANNEALING SEMPLIFICATO

SIMANN :

M := 0 ;

q := temperatura iniziale ;

genera soluzione iniziale i ;

x := i ;

repeat

repeat

GENERA (a caso) j in N(i) ;

if D = c(j) - c(i) 0 then i := j else

if exp(-D q) > RANDOM(0,1) then i := j ;

if c(i) < c(x) then x := i

until in EQUILIBRIO ;

AGGIORNA q

M := M+1 ;

until q q-finale v M=K

return x

N.B. In maiuscolo le subroutine che è necessario assegnare.

ESEMPIO DI SEMPLICE STRATEGIA

temperatura iniziale = avg (Dc⁺) / ln (1/c_o

q-finale tra 6 e 50

aggiornamento di q: f(q) := 0.95 q

ORIGINE  Metodi Monte-Carlo per simulare il processo di formazione di cristalli a partire da un prodotto fuso abbassando molto lentamente la temperatura al fine di ottenere lo stato cristallino ad energia più bassa (Metropolis et al. 1953)

Se associamo ad ogni soluzione s ammissibile di F un vertice di un grafo e lo connettiamo ai vertici rappresentanti soluzioni di N(s) otteniamo un grafo H (talmente grande da essere solo immaginato). Indichiamo con d(x) il grado di un vertice di H e con D una stima per eccesso del suo grado massimo.

Il seguente algoritmo genera una passeggiata casuale su H partendo da un generico vertice x:

1. con probabilità ½ resta nel vertice x ;

2. seleziona y in F casualmente secondo la distribuzione seguente

Pr(y) =

3. con probabilità min x := y ;

4. go to 1

N.B. a 1 è un parametro: l' algoritmo sopra riportato è per un problema di minimo, mentre nel caso di massimo invece di a bisogna usare 1/a

Sia MC (a) la catena di Markof ottenuta con questo algoritmo: si noti che tale processo accetta di spostarsi in una soluzione migliorante con probabilità 1, mentre si sposta su soluzioni peggioranti con probabilità che dipende da a

decrescente di c(x), e quindi favorisce le soluzioni migliori (per problemi di massimo sarebbe monotona crescente dato che a è sostituito da 1/a

Algoritmo di Metropolis: simulare MC(a) per T iterazioni partendo da una soluzione ammissibile arbitraria e fornire in uscita la miglior soluzione trovata durante la simulazione.

L' algoritmo di Simulated Annealing si può considerare come un algoritmo di Metropolis dove a viene fatto variare secondo uno schema assegnato durante la simulazione, ottenendo una catena di Markof non-omogenea MC(a(t)). Ciò che abbiamo chiamato "temperatura" e indicato con q in SIMANN non è altro che 1/a

N.B. A quanto si sa non esiste prova che SIMANN sia migliore del più semplice algoritmo di Metropolis se a è scelto in maniera ottimale.

2-ALGORITMO GENETICO (Holland 1975)

GENALG:

t := 1 ;

inizializza una popolazione POP(t) con N soluzioni P_i(t) ;

while condizione di fine non soddisfatta do

for i := 1 to N do calcola la fitness f_i = f(P_i(t)) ;

for i := 1 to N do

P_i(t+1) := una soluzione P_j(t) scelta a caso in POP(t) con probabilità p_j = f_j/S_k=1,.,nf_k ;

CROSS(POP(t+1))

MUT(POP(t+1)) ;

t := t+1

end while

3-RICERCA CON TABU (Glover 1989)

IDEA: esplorare in N(s) escludendo alcuni movimenti dichiarati "tabu" per evitare di ciclare e guidare la ricerca verso regioni non ancora esplorate dell' insieme F. Un precursore di questo metodo può ritenersi quello di Kernigham-Lin. I metodi basati sulla ricerca con tabu sono risultati spesso tra i più efficaci.

Sia T la lista di mosse tabu e l la sua lunghezza, detta tabu tenure, spesso variabile dinamicamente intorno ad un valore centrale preferenziale.

Le restrizioni dettate da T possono essere violate quando un movimento che sarebbe tabu fornisce una soluzione migliore della migliore soluzione fin ora trovata (criterio di aspirazione).  

Caratteristiche importanti delle mosse utilizzate per esplorare un intorno N(s) tenendo conto della lista di mosse tabu T:

Efficienza: (importante in tutti i metodi di ricerca locale) la miglior soluzione in N(s) raggiungibile deve essere trovata rapidamente e deve essere semplice memorizzare la mossa corrispondente in T

Recentezza: quante iterazioni fa si è richiesto di usare la stessa mossa; su questa caratteristica si basa la possibilità di variare dinamicamente l

Frequenza: la frequenza con la quale una certa mossa viene richiesta è indicazione della sua "appetibilità" ed è utilizzata per intensificare la ricerca in zone promettenti di F

Qualità: il miglioramento della funzione obbiettivo ottenuto