Local search

Tecniche risolutive viste finora:

backtracking
si modifica una soluzione parziale finchè non si trova una soluzione (o si conclude che non esiste)
propagazione di vincoli (consistenza locale)
si rendono esplicite le conseguenze dei vincoli

Generalizzazione delle due tecniche

Backtracking e propagazione sono tecniche risolutive di queste due classi:

ricerca
ricerca di una soluzione
inferenza
trovare nuovi vincoli (o restringere quelli esistenti) che siano conseguenza di quelli vecchi

La ricerca locale è un algoritmo di ricerca (ossia, è un algoritmo che cerca una soluzione), ma è diverso dal backtracking


Ricerca locale: principio

Sia dato un assegnamento a tutte le variabili
(non un assegnamento parziale come nel backtracking)

Questo assegnamento può soddisfare alcuni vincoli e violarne altri

Idea: modificare il valore di una sola variabile in modo da aumentare i vincoli soddisfatti


Esempio di aumento vincoli soddisfatti

Vincoli x<z y<z z<k e assegnamento x=1, y=1, z=0, k=2

Assegnamento:x=1y=1z=0k=2 
Vincoli:x<zx=1 z=0 NO
y<z y=1z=0 NO
z<k  z=0k=2OK

Se al posto di z=0 si mette z=2:

Assegnamento:x=1y=1z=2k=2 
Vincoli:x<zx=1 z=2 OK
y<z y=1z=2 OK
z<k  z=2k=2NO

Questa modifica rende soddisfatti i primi due vincoli ma violato il terzo

Si passa comunque da un vincolo soddisfatto a due

Se si ripete?


Esempio: raggiungimento soluzione

L'assegnamento precedente non soddisfa il vincolo z<k:

Assegnamento:x=1y=1z=2k=2 
Vincoli:x<zx=1 z=2 OK
y<z y=1z=2 OK
z<k  z=2k=2NO

Cambiando z al valore z=1 si soddisfa il vincolo z<k, ma si perdono di nuovo i primi due vincoli

Cambiando k al valore k=3, tutti i vincoli risultano soddisfatti

Assegnamento:x=1y=1z=2k=3 
Vincoli:x<zx=1 z=2 OK
y<z y=1z=2 OK
z<k  z=2k=3OK

Ricerca locale: generalizzazione

Un assegnamento (totale, non parziale) in generale soddisfa dei vincoli e viola gli altri

Cambiando dei valori, in generale:

Il principio è quello di fare modifiche all'assegnamento in modo da aumentare il numero di vincoli soddisfatti

Quando tutti i vincoli sono soddisfatti, l'assegnamento è una soluzione


Ricerca locale: generalizzazione

Ricerca locale=si modifica iterativamente un assegnamento (totale)

Si guardano solo gli assegnamenti simili a quallo attuale
(quelli che differiscono solo per una variabile)

Rappresentando l'insieme degli assegnementi in modo grafico, si decide come cambiare l'assegnamento guardando solo il suo intorno


Costo

Di solito, si considera il numero di vincoli violati, e si cerca di minimizzarlo

Il costo di un assegnamento è il numero di vincoli violati

Si modifica l'assegnamento per ridurre il suo costo, per arrivare a costo zero (nessun vincolo violato)


Movimento

Spesso si visualizza la ricerca locale come un percorso nello spazio degli assegnamenti

Un cambiamento da una assegnazione a una vicina viene spesso chiamata mossa


Problema della ricerca locale

Anche se una soluzione esiste, non è detto che ci si arrivi

Problema del minimo locale: un assegnamento che non si può migliorare cambiando solo una variabile, ma una soluzione esiste

Esempio: un assegnamento I che:


Minimo locale: esempio

Domini tutti uguali a {0,1,2,3}

Vincoli:

x<zz<kk<r
y<zk<s

Assegnamento:

x=0, y=0, z=1, k=1, s=2, r=2

L'unico vincolo violato è z<k

Quindi, si può diminuire il numero di vincoli violati soltando modificando z oppure k

Due possibilità:

z=0
in questo caso vengono però violati i vincoli x<z ed y<z
k=2 oppure k=3
in questo caso vengono però violati i vincoli k<s ed k<r

Non ci sono modifiche a una singola variabile che diminuscono il numero di vincoli violati

Però una soluzione esiste:

x=0,y=0,z=1,k=2,s=3,r=3

Questa però ha tre variabili diverse!


Hill climbing

Fra tutte le modifiche locali dell'assegnamento, sceglie quella che riduce maggiormente il costo

Nel caso di sopra, non ci sono modifiche che migliorano il costo

Le modifiche migliori sono quelle che mantengono il costo corrente

Quindi, verrebbe cambiato s oppure r a 3

Assegnamento: x=0, y=0, z=1, k=1, s=2, r=2

x<zz<kk<r
y<zk<s

Ci sono però due modifiche che mantengono il costo: s=3 e r=3:

L'assegnamento: x=0, y=0, z=1, k=1, s=3, r=2 ha sempre un solo vincolo violato

Da questo assegnamento, la modifica k=2 porta ancora a costo uno:

L'assegnamento: x=0, y=0, z=1, k=2, s=3, r=2 ha sempre un solo vincolo violato

Ora r=3 porta a costo zero


Hill climbing

Si sceglie la modifica migliore possibile

Si fa questa modifica anche se porta a costo uguale o anche maggiore

Resta il problema dei minimi locali


Minimi locali

Possono esserci condizioni in cui l'algoritmo ripete sempre le stesse scelte

Dominio {0,1,2}

x=zz<kk<mm=r
x=yr=s
y=zm=s

Assegnamento: x=0,y=0,z=0,k=1,m=1,k=1,s=1

C'è un solo vincolo violato: k<m

Ogni modifica a una variabile fra x,y,z oppure m,r,s porta alla violazione di (almeno) due uguaglianze

L'unica variabile che si può modificare senza aumentare il costo è k

Unica modifica a costo zero: k=0

Assegnamento: x=0,y=0,z=0,k=0,m=1,k=1,s=1

Ora però z<k è violato

L'unica modifica a costo zero è k=0

Questo riporta alla soluzione di partenza


Problemi dell'hill climbing

Nell'esempio, il problema si può vedere in due modi:

Esistono algoritmi creati per risolvere il problema


Peso dei vincoli

Il problema dell'esempio si può riformulare cosí:

La soluzione dei vincoli pesati è:


Pesatura vincoli sull'esempio

Incremento di peso 1 ogni volta che un vincolo è violato

Grafica con assegnamenti e peso (freccia=<, linea=uguaglianza)

I vincoli violati hanno una croce per indicare l'aumento di peso di uno (zero croci=peso 1, una croce=peso 2, ...)

La scelta migliore ora è k=0

Questo diminuisce il peso, dato che soddisfare il vincolo con la croce vale due (mentre gli altri vincoli valgono uno):

Il vincolo k<m, che prima era violato, è ora soddisfatto; il peso aggiuntivo però non viene tolto

Viene aggiunto un peso al vincolo z<k, che ora è violato

Cambiare k=1 è ancora la scelta migliore

Ora, cambiare k=0 oppure m=2 ha lo stesso costo

Infatti, il vincolo z<k ha costo due, che è lo stesso costo di violare m=r ed m=2

Supponiamo anche di fare la scelta sbagliata k=0

Questo porta ancora a:

Ora però violare z<k ha costo tre, mentre violare m=r ed m=s ha solo costo due

Quindi, viene scelto m=2

La modifica m=1 ha costo 4, mentre r=1 ha costo 3 (anche s=1)

Ora si cambia s=2 e si ottiene una soluzione


Pesi dei vincoli: principio

Il problema dell'hill climbing è che si può verificare che:

Con i pesi, questi vincoli tendono a contare sempre meno, fino a che si arriva al punto che è permesso violarli


Tabu search

Serve sempre ad evitare di andare in ciclo su degli assegnamenti

Basato su un principio diverso: evitare di rifare sempre le stesse scelte


Tabu list

Il tabu search è basato sul mantenere una lista degli ultimi cambiamenti che sono stati fatti

Questa lista si chiama tabu list

Quando si deve scegliere una cambiamento, si esclude uno che sia nella lista


Tabu list: definizione

La tabu list è in effetti una coda

La tabu list contiene coppie variabile=valore

La sua lunghezza viene scelta a priori

Quando la coda è piena, ogni volta che viene inserita una coppia variabile=valore, viene eliminata quella più vecchia


Tabu search: definizione

Dato un assegnamento, si considerano tutti quelli che differiscono da essi per il valore di una variabile (come nell'hill climbing)

Si escludono però le modifiche di una variabile x al valore v se la coppia x=v sta nella tabu list (questo non c'è nell'hill climbing)

Tra tutte le modifiche, si sceglie quella che porta a un costo minore


Tabu search, sull'esempio

Fissiamo lunghezza 4 della tabu list

Inizialmente, la lista è vuota

Come prima, la scelta migliore è k=0 (mantiene lo stesso costo)

La scelta fatta viene aggiunta alla coda

Ora k=1 è ancora la scelta migliore (mantiene il costo)

Ora però non si può più scegliere k=0, perchè questa è una modifica che sta nella lista

Un'altra scelta che mantiene il costo è k=2

Ora k non può più venire cambiata

Una delle scelte migliori (meno peggio) è m=2

È quindi possibile uscire dal ciclo

In questo caso, è anche possibile fare una scelta sbagliata (z=1, per esempio)

Se la lista fosse stata più lunga, prima o poi si sarebbe dovuto per forza cambiare m=2

In generale, più la lista è lunga e meno è probabile che si cicli sugli assegnamenti

D'altra parte, allungare la lista può allungare dei percorsi


Restart

Le tecniche viste prima sono deterministiche

L'unico grado di libertà è il caso in cui ci sono più scelte a costo minimo

Questo significa che se c'è un algoritmo attraversa un ciclo di assegnamenti (senza scelte multiple) una volta, allora lo continua ad attraversare per sempre

Soluzione tipica: si fissa un numero di iterazioni; se si supera, si parte con un nuovo assegnamento casuale


Percorsi casuali

Anche se non si incontrano cicli, si potrebbe restare in "zone" di assegnamenti in cui non ci sono soluzioni

Facendo movimenti casuali, questo si può risolvere

Vediamo due metodi:


WalkSAT

Deriva da SAT, ma si può usare anche per CSP

Idea: si procede come al solito, ma ogni tanto si fa un movimento a caso


WalkSAT

Si fissa all'inizio una probabilità p

Ad ogni passo, con probabilità p si fa la mossa solita

Con probabilità 1-p si sceglie una variabile a caso in un vincolo violato, e si sceglie un valore casuale per questa variabile


Congelamento simulato

Idea:


Congelamento simulato

Sia d la differenza di costo di un cambiamento

Si esegue il cambiamento con probabilità e-dT, dove T è una parametero chiamato temperatura

All'inizio, si usa T alto, e quindi la probabilità di un cambiamento casuale è alta

Si diminusce la temperatura con il tempo

Più si va avanti, più le mosse diventano sempre meno casuali