Classi di Problemi
Università degli Studi di Milano
Marco Frasca
●
Classi di problemi (decisionali, di ricerca, di ottimizzazione)
●
Definizioni basate sul concetto di soluzione ammissibile:
➢
●
Diverse esigenze
➢
Decidere se esiste una soluzione o se una data istanza è una soluzione
(problemi di decisione)
➢
Costruire tutte le soluzioni ammissibili (problema di enumerazione)
➢
Trovare una soluzione ammissibile (problema di ricerca)
➢
●
una soluzione che soddisfa un certo insiemi di criteri
Trovare le soluzioni “migliori” rispetto ai criteri fissati dal problema
(problema di ottimizzazione)
Esempio: Elencare tutti i sottoinsiemi di k elementi di un insieme S
Problemi di ottimizzazione
Università degli Studi di Milano
Marco Frasca
●
Trovare le soluzioni ottimali
●
Le soluzioni ammissibili che ottimizzano una funzione obiettivo
●
Dove possibile uso di tecniche “efficienti”:
- Programmazione dinamica, greedy, etc.
➢
Si costruiscono tutte le soluzioni e si valuta una funzione di costo
(“forza bruta”)
- Lo spazio delle soluzioni deve essere finito
- Fattibile solo con spazi delle soluzioni discreti
- Solo se è l'unica strada possibile e lo spazio delle soluzioni è finito
Soluzioni Ottimali
Università degli Studi di Milano
Marco Frasca
Inoltre esistono problemi inerentemente “complessi”,
trattabili in maniera esatta solo per taglie piccole:
➢
Problema del Commesso viaggiatore (TSP)
●
➢
Un commesso viaggiatore che deve visitare n città ritornando poi a
quella iniziale. Lo scopo è quello di minimizzare la distanza
percorsa (e quindi il costo). Quale ordine di visita scegliamo?
Problema del circuito hamiltoniano = problema del commesso
viaggiatore in cui le distanze sono unitarie
Problemi di ottimizzazione
Università degli Studi di Milano
Marco Frasca
Nel campo dell’ottimizzazione si distingue tra problemi
monodimensionali e problemi multidimensionali.
• Nel primo caso si cerca l’ottimo di una funzione obiettivo
dipendente da una sola variabile (un grado di libertà).
• Nel secondo caso si cerca l’ottimo di una funzione obiettivo
dipendente da più variabili (più gradi di libertà)
●
Spazio delle soluzioni S: insieme di tutte le soluzioni
ammissibili
- Continuo : massimizzare f(x) = arctg(x) + sen(x), S = R
- Discreto : massimizzare f(x), x in S = {0,1}n
Problemi di ottimizzazione
Università degli Studi di Milano
Marco Frasca
●
●
Determinare x = argmaxx f(x)
Massimizzazione e minimizzazione sono
assolutamente equivalenti. Infatti è sufficiente
cambiare di segno alla funzione obiettivo per
passare da un problema di minimo ad uno di
massimo e viceversa:
x = argminx -f(x)
Ottimi globali vs ottimi
locali
Università degli Studi di Milano
Marco Frasca
●
Molti algoritmi di minimizzazione “discendono” lungo la
superficie della funzione e quindi riescono a localizzare il
minimo più vicino al punto d’inizio (quindi un minimo locale).
➢
Esempio: Metodo del gradiente
➢
●
●
La funzione deve essere derivabile
Gli ottimi locali possono essere di qualità molto bassa
Per localizzare più di un minimo o per localizzare un minimo
globale sono richiesti metodi che permettano di partire da
differenti condizioni iniziali
➢
➢
È quindi molto costoso
Spesso si adottano algoritmi che approssimano una soluzione ottima ma
mantengono l'efficienza
PSO
Università degli Studi di Milano
Marco Frasca
Per ovviare questo problema talvolta si usano algoritmi che non
scelgono sempre la soluzione ottima. Questi algoritmi sono in
genere probabilistici e/o approssimati
● Una semplice tecnica algoritmica per la soluzione di problemi di
minimo (o massimo) è il cosiddetto “Particle Swarm
Optimization” (PSO)
●
➢
➢
➢
➢
➢
Tecnica che non richiede la derivabilità della funzione
può essere utilizzata con successo in problemi di ottimizzazione irregolari,
rumorosi, variabili nel tempo, eccetera
Informalmente, una serie di agenti esplorano lo spazio delle soluzioni in
maniera tale da comportarsi come stormi di uccelli
nessuno degli agenti ha la capacità individuale di affrontare il problema
l’interazione collettiva è la base della soluzione
PSO
Università degli Studi di Milano
Marco Frasca
●
●
●
●
Ogni particella (punto nello spazio, soluzione ammissibile) che nel
suo movimento trova una valore migliore della funzione, si trova
di fronte a due alternative:
➢ allontanarsi dal gruppo per raggiungerlo (individualismo)
➢ rimanere nel gruppo (socialità)
Se più individui si dirigono verso la soluzione migliore, anche altri
membri possono cambiare la loro direzione per sfruttare lo
stesso miglioramento
Il gruppo cambia gradualmente direzione verso le zone più
promettenti, ovvero l’informazione gradualmente si propaga a
tutti
la strategia di ricerca si esprime come bilanciamento tra i due
aspetti, individuale e collettivo
PSO
Università degli Studi di Milano
Marco Frasca
●
●
●
●
Ogni agente è caratterizzato da una posizione, ed una velocità (che
determina come l'agente si muove nello spazio delle soluzioni).
La velocità dipende da parametri fra cui la migliore soluzione trovata
finora dall’agente e la migliore soluzione globalmente individuata
Gli agenti si muoveranno in tutte le tutte le direzioni cercando la
soluzione migliore. In genere è preferibile limitare la velocità massima
per evitare che gli agenti si disperdano troppo
Ad ogni posizione viene associata una fitness, cioè un valore che
misura la bontà di quella posizione (in genere il valore assunto dalla
funzione in quel punto)
- Esempio: se ottimiziamo la funzione f(x), ogni x in S è una possibile
posizione che una particella può occupare, e f(x) è la sua fitness
PSO
Università degli Studi di Milano
Marco Frasca
●
➢
●
L’algoritmo procede per intervalli di tempo discreti. L’agente i al
tempo t mantiene
➢
La sua posizione pi,j (t), per ogni dimensione j
➢
La sua velocità vi,j (t), per ogni dimensione j
➢
la posizione bi,· con fitness massima dell’agente i trovata fino al tempo corrente
➢
la posizione g con fitness massima fra tutti gli agenti al tempo corrente .
Velocità e posizione dell’agente i vengono aggiornati al tempo t + 1
come segue per ogni dimensione j
➢
vi,j (t + 1) = w · vi,j (t) + c1 · rand() · (bi,j − pi,j (t)) + c2 · rand() · (gj − pi,j (t))
➢
pi,j (t + 1) = pi,j (t) + vi,j (t + 1)
Si noti che i valori casuali sono in genere diversi. Il valore w è detto inerzia,
ed è buona norma che lo si riduca iterazione dopo iterazione. Le costanti
c1 e c2 sono in genere settate ad un valore tra 1 e 2.
PSO
Università degli Studi di Milano
Marco Frasca
●
Algoritmo PSO (f, n, c1, c2, dim, w, n_iter) % dim =dimensione dello spazio
Inizializza i parametri e gli n agenti
Inizializza le posizioni e velocità degli n agenti in maniera casuale
t=1
while t < n_iter do
calcola fitness posizioni attuali
aggiorna migliori posizioni individuali
aggiorna migliore posizione globale
for i = 1 to n do
for j = 1 to dim do % aggiorno posizioni e velocità
vi,j (t + 1) = w ·vi,j (t)+c1 ·rand()·(bi,j (t)−pi,j (t))+c2 ·rand()·((gj (t))−pi,j (t))
pi,j (t + 1) = pi,j (t) + vi,j (t + 1)
end for
end for
t ←t +1
Riduci w
end while
Esercizi
Università degli Studi di Milano
Marco Frasca
●
1. Scrivere un programma in MATLAB che utilizzi l'algoritmo PSO descritto
per trovare il minimo della funzione
f (x, y) = (1 − x)2 + 100 · (y − x2 )2
●
●
Disegnate l’evoluzione della configurazione degli agenti (usate plot).
2. Scrivere un programma in MATLAB che utilizzi l'algoritmo PSO
descritto per trovare il minimo della funzione
3
1
2
(−0.2sqrt ∑ x i )
3 i=1
f ( x 1, x 2, x 3)=−20⋅e
●
3
1
( ∑ cos (2πxi ))
3 i=1
−e
Disegnate l’evoluzione della configurazione degli agenti (usate plot3).
Approccio di forza bruta
Università degli Studi di Milano
Marco Frasca
●
●
Se si utilizza un approccio di “forza bruta”, quello che cioè
prova tutte le soluzioni ammissibili fino a trovare quella
ottima, alcuni programmi potrebbero non terminare!
Da usare se non si conoscono altri metodi
La potenza dei computer moderni rende “affrontabili” problemi
di discrete dimensioni, ma non molto
● 10!
= 3.63 · 106
permutazioni di 10 elementi
●
●
220 = 1.05 · 106
sottoinsiemi di 20 elementi
Backtracking
Università degli Studi di Milano
Marco Frasca
●
L'algoritmo di backtracking è un algoritmo di forza bruta che esplora
tutto lo spazio delle soluzioni per trovare una soluzione ammissibile
o per cercare quella ottima
- Lo spazio deve essere finito
●
●
Ciononostante, talvolta si può evitare di tentare tutte le possibili
soluzioni in base a criteri per capire in anticipo che delle soluzioni
non possono migliorare quella attualmente calcolata
Ogni soluzione ammissibile è un assegnamento delle variabili che
deve rispettare (laddove ci siano) i vincoli del problema
Backtracking
Università degli Studi di Milano
Marco Frasca
●
●
●
Sia S[v1..vk] è una soluzione ammissibile sulle prime k
variabili (sotto-soluzione)
Ogni variabile può assumere un numero finito di valori
Si prova un assegnamento non ancora provato per la
variabile vk+1
➢
➢
Se la sottosoluzione è ammissibile allora continua con la variabile
successiva
Altrimenti torna indietro e prova un altro valore per la variabile vk+1
Backtracking
Università degli Studi di Milano
Marco Frasca
●
●
●
●
L'algoritmo di backtracking è inerentemente ricorsivo, ma esiste
versione iterativa
L’intero processo di ricerca in molti casi può essere descritto come la
visita di un albero in cui ogni nodo rappresenta una sotto-soluzione
e vi è un cammino da una sotto-soluzione A ad una sotto-soluzione
B, se B è ottenibile da A.
I figli del nodo A sono tutte e sole le sotto-soluzioni ottenibili
direttamente (cioè cambiando il valore di una sola variabile) da A.
In genere ogni livello dell'albero corrisponde all'assegnamento di una
variabile
Albero di decisione
Università degli Studi di Milano
Marco Frasca
Soluzioni ≡ foglie in un albero di decisione
Soluzioni parziali ≡ nodi interni dell'albero di decisione
Radice ≡ sotto-soluzione vuota
Variabili: v1 , v2 , …..., vn ∊ {a1 , a2 , …, am}
m=2
v2=a1
a1a1
v1=a1
a1
v2=a2
a1a2
v1=a2
v2=a1
a2
a2a1
v2=a2
a2a2
Esempio: sottoinsiemi
possibili
Università degli Studi di Milano
Marco Frasca
Esempio :possibili sottoinsiemi di un
insieme S = {s1, s2, ..., sm}
vi := variabile binaria associata a si , per
i ∊ {1, 2, …, m}.
Vi = 1 se si è inserito nel sottoinsieme, 0
altrimenti.
- Sottoinsieme := stringa binaria di
lunghezza m
- I sottoinsiemi possibili sono tutte le
possibili stringhe binarie di lunghezza
m, cioè 2m.
Soluzioni ≡ foglie in un albero di
decisione
v1=1
1
v2=1
11
v3=1
101
Livello v1
v1=0
0
v2=0
10
v3=0
100
Livello v2
v2=a1
v3=1
011
v2=a2
01
00
v3=0
010
Esempio: Circuito
Hamiltoniano
Università degli Studi di Milano
Marco Frasca
v1=a1
v1=am
Esempio: Circuito Hamiltoniano
vi := variabile che indica la i-ma
città visitata;
v i∈{a1, a 2, , am }
Nelle foglie trovo tutti i modi di
visitare m+1 città, anche con
ripetizione
A noi ne interessano solo alcune,
quelle in cui ogni città
compare 1 volta, eccetto la
prima, due volte.
a1
v2=a1
............
a1a1
................
v2=a2
a1am
............
v2=a1
am
............
ama1
............
v2=a2
amam
Backtracking: potatura
Università degli Studi di Milano
Marco Frasca
Spesso l’albero di ricerca può essere potato: l’algoritmo usa dei criteri
(euristiche) per riconoscere in anticipo alcune sotto-soluzioni che non
portano ad alcuna soluzione ammissibile;
- Tale cammino nodo (e quindi il sotto-albero) viene escluso dalla
ricerca.
Non appena si giunge a un nodo tale che ogni ramo figlio viene
riconosciuto come ”vicolo cieco” (le foglie nel sotto-albero non sono
soluzioni ammissibili), tale nodo viene abbandonato e si risale
(backtrack) fino al nodo (più viciono) che ammette mosse non
ancora esplorate
- da qui la ricerca riprende scegliendo un nuovo cammino attraverso
una di queste mosse.
Potatura: circuito
Hamiltoniano
Università degli Studi di Milano
Marco Frasca
I nodi a1a1 e amam sono gìà vicoli ciechi perché ogni soluzione ammissibile
deve passare per ogni città una sola volta
v1=a1
v2=a1
a1
............
a1a1
v1=am
................
v2=a2
a1am
............
v2=a1
am
............
ama1
............
v2=a2
amam
Esercizio
Università degli Studi di Milano
Marco Frasca
●
Scrivere un programma in MATLAB che utilizzando l'algoritmo
backtracking risolva il problema del commesso viaggiatore
semplificato,in cui cioè non bisogna tornare nella città di
partenza. Provare per n= 3, 5, 10 città. Il programma deve
restituire uno dei cammino ottimali ed il suo costo
- Rappresentare le strade tra le città come matrice delle connessioni
W. W simmetrica, ovviamente.
➢
Wij := lunghezza della strada che collega direttamente la città i e la città j
➢
Wij := -1 se non esiste collegamento diretto tra città i e j
© Copyright 2024 ExpyDoc
