1/14

Euristiche:algoritmi

costruttivi e di ricerca locale

2/14

Molti problemi reali richiedono soluzioni algoritmiche

I camion devono essere instradati VRP, NP-hard

I depositi o i punti di vendita devono essere localizzatiCPMP, NP-hard

Le reti di comunicazione devono essere disegnateNetwork design, NP-hard

I container devono essere riempiti3D-packing, NP-hard

I collegamenti radio devono avere una frequenza associataFAP, NP-hard

Legno, vetro, pelle devono essere tagliatiNesting, NP-hard

…

3/14

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 SF).

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.

4/14

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.

5/14

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”.

6/14

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.

7/14

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.

8/14

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.

9/14

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.

10/14

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.

11/14

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.

12/14

Ricerca locale: vicinanze

L’insieme di vicinanza (neighborhood) di una soluzione S, N(S), è un sottinsieme di 2C definito da una funzione di vicinanza N: 2C 22c.

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.

13/14

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.

14/14

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].