Euristiche:
algoritmi
costruttivi e di
ricerca locale
Molti problemi reali richiedono
soluzioni algoritmiche
I camion devono essere instradati
VRP, NP-hard
I depositi o i punti di vendita devono essere localizzati
Le reti di comunicazione devono essere disegnate
I conteiner devono essere riempiti
CPMP, NP-hard
Network design, NP-hard
3D-packing, NP-hard
I collegamenti radio devono avere una frequenza associata
Legno, vetro, pelle devono essere tagliati
…
FAP, NP-hard
Nesting, NP-hard
Notazione
Un problema di ottimizzazione combinatoria è definito su di un
insieme C = {c1 , … , cn} di componenti di base.
Una soluzione del problema è un sottinsieme S  C;
F  2C è il sottinsieme delle soluzioni ammissibili, (una soluzione S è
ammissibile sse SF).
z: 2C   è la funzione di costo,
L’obiettivo è trovare una soluzione ammissibile di costo minimo S°,
cioè trovare S° F tale che z(S°)  z(S), S  F.
In subordine, l’algoritmo ritorna la miglior soluzione ammissibile
trovata, S*  F.
Esempio: TSP
Esempio di problema: il Traveling Salesman Problem (TSP).
Il TSP è definito su un grafo completo pesato e non diretto
G=(V,E,D), dove V è l’insieme dei vertici, E è l’insieme degli
archi e D è l’insieme dei pesi associati agli archi.
• L’insieme dei componenti corrisponde a E (C=E),
• F corrisponde all’insieme dei cicli Hamiltoniani in G
• z(S) è la somma dei pesi associati agli archi nella
soluzione S.
Considerazioni computazionali
La dimensione delle istanze dei problemi reali
impedisce di risolverle all’ottimo in un tempo
accettabile.
Però questi problemi devono essere risolti.
Da qui la necessità di trovare soluzioni subottime, che
però siano di “qualità accettabile” e che siano trovate
in un “tempo accettabile”.
Come gestire l’NP-completezza
• Istanze piccole;
• Casi speciali polinomiali;
• Algoritmi approssimati: garantiscono di trovare una
soluzione di errore massimo noto;
• Algoritmi probabilistici garantiscono che per istanze
sufficientemente grandi la probabilità di ottenere una
cattiva soluzione è molto picccola;
• Algoritmi euristici: nessuna garanzia, ma storicamente, in
media, questi algoritmi hanno il miglior rapporto
qualità/tempo per il problema in esame.
Euristiche: tre classi
Tre classi principali di algoritmi euristici.
La prima si concentra sugli aspetti strutturali del
problema da risolvere per definire algoritmi
costruttivi o di ricerca locale.
La seconda, denotata come "metaeuristica" (Glover,
1986), si concentra sulla guida di algoritmi costruttivi
o di ricerca locale per superare situazioni critiche.
Infine, un trend recente cerca di incorporare
risultati forti della programmazione matematica nelle
strutture euristiche.
Euristiche: nessuna dominanza
Gli algoritmi delle tre classi sono stati
presentati successivamente in letteratura,
ma questo non implica nulla sulla loro
efficacia relativa.
Specifici problemi possono essere risolti al
meglio da un algoritmo di una qualsiasi classe.
Euristiche di tipo 1: importanza
della struttura della soluzione
Le euristiche di tipo 1 sfruttano le proprietà
strutturali delle soluzioni ammissibili per
ottenere rapidamente una buona soluzione.
Di solito si tratta di euristiche costruttive o di
euristiche di ricerca locale.
Euristiche costruttive
1. Ordina i componenti in C per costi crescenti.
2. Set S*= e i=1.
3. Repeat
If (S*ci è una soluz. parziale ammissibile)
then S*=S*ci.
i=i+1.
Until S* F.
Euristiche costruttive
Un approccio costruttivo può generare soluzioni
ottime per certi tipi di problemi, es. il MST.
In altri casi però potrebbe essere incapace di
costruire una soluzione ammissibile.
TSP: ordina gli archi per costi crescenti, prendi
quello di costo minore e aggiungi archi di costo
crescente, purchè non chiudano sottocicli, finchè non
si completa un circuito Hamiltoniano.
Strategie costruttive più complesse generano
notissime euristiche per il TSP, quali la Farthest
Insertion, la Nearest Neighbor o la Sweep.
Ricerca locale: vicinanze
L’insieme di vicinanza (neighborhood) di una
soluzione S, N(S), è un sottinsieme dic 2C definito da
una funzione di vicinanza N: 2C  22 .
Spesso si considerano solo soluzioni ammissibili,
quindi funzioni di vicinanza N: F  2F.
La specifica funzione utilizzata ha un profondo
impatto sulla performance dell’algoritmo. La sua
scelta è lasciata al progettista dell’algoritmo.
Ricerca locale
1.Genera una soluzione iniziale ammissibile S.
2. Trova S'N(S), tale che z(S')=min z(S^),
S^ N(S).
3. If z(S') < z(S) then S=S'
goto step 2.
4. S* = S.
L’aggiornamento della soluzione al passo 3 è detto mossa da S
a S'.
Può essere fatta verso la prima soluzione migliorante trovata.
Ricerca locale
Ci sono problemi per cui la ricerca locale garantisce di
trovare una soluzione ottima (es. l’algoritmo del
simplesso).
Per il TSP, due note LS sono la 2-opt e la 3-opt, che
prendono una soluzione (una lista di n vertici) e
scambiano esaustivamente gli elementi di ogni coppia o
tripletta di vertici.
Vicinanze più sofisticate originano euristiche più
efficaci, fra cui Lin and Kernighan [LK73].