Tecniche risolutive viste finora:
Backtracking e propagazione sono tecniche risolutive di queste due classi:
La ricerca locale è un algoritmo di ricerca (ossia, è un algoritmo che cerca una soluzione), ma è diverso dal backtracking
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
Vincoli x<z y<z z<k e assegnamento x=1, y=1, z=0, k=2
Assegnamento: | x=1 | y=1 | z=0 | k=2 |   | |
---|---|---|---|---|---|---|
Vincoli: | x<z | x=1 | z=0 |   | NO | |
y<z | y=1 | z=0 | NO | |||
z<k | z=0 | k=2 | OK |
Se al posto di z=0 si mette z=2:
Assegnamento: | x=1 | y=1 | z=2 | k=2 |   | |
---|---|---|---|---|---|---|
Vincoli: | x<z | x=1 | z=2 |   | OK | |
y<z | y=1 | z=2 | OK | |||
z<k | z=2 | k=2 | NO |
Questa modifica rende soddisfatti i primi due vincoli ma violato il terzo
Si passa comunque da un vincolo soddisfatto a due
Se si ripete?
L'assegnamento precedente non soddisfa il vincolo z<k:
Assegnamento: | x=1 | y=1 | z=2 | k=2 |   | |
---|---|---|---|---|---|---|
Vincoli: | x<z | x=1 | z=2 |   | OK | |
y<z | y=1 | z=2 | OK | |||
z<k | z=2 | k=2 | NO |
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=1 | y=1 | z=2 | k=3 |   | |
---|---|---|---|---|---|---|
Vincoli: | x<z | x=1 | z=2 |   | OK | |
y<z | y=1 | z=2 | OK | |||
z<k | z=2 | k=3 | OK |
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=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
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)
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
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:
Domini tutti uguali a {0,1,2,3}
Vincoli:
x<z | z<k | k<r |
y<z | k<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à:
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!
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<z | z<k | k<r |
y<z | k<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
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
Possono esserci condizioni in cui l'algoritmo ripete sempre le stesse scelte
Dominio {0,1,2}
x=z | z<k | k<m | m=r |
x=y | r=s | ||
y=z | m=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
Nell'esempio, il problema si può vedere in due modi:
Esistono algoritmi creati per risolvere il problema
Il problema dell'esempio si può riformulare cosí:
La soluzione dei vincoli pesati è:
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
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
Serve sempre ad evitare di andare in ciclo su degli assegnamenti
Basato su un principio diverso: evitare di rifare sempre le stesse scelte
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
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
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
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
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
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:
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
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
Idea:
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