Giuseppe Bruno » 6.Algoritmi euristici costruttivi e migliorativi

Argomenti della lezione

• Alcune definizioni fondamentali
• Algoritmi costruttivi
• Algoritmi migliorativi
• Conclusioni

Alcune definizioni fondamentali

In termini generali un problema di ottimizzazione può essere formulato come

z = f (x)    Max!

x∈X

con

• X di insieme di soluzioni ammissibili
• z=f(x) funzione obiettivo z=f(x) da massimizzare

Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x);

Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.

Alcune definizioni fondamentali (segue)

Problema e metodo di risoluzione

Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).

Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.

Un metodo di risoluzione può essere:

• esatto se individua un ottimo globale ammissibile
• euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).

Alcune definizioni fondamentali (segue)

Alcune definizioni fondamentali (segue)

Alcune definizioni fondamentali (segue)

Classificazione tecniche euristiche

I metodi di risoluzione euristici si distinguono in:

metodi costruttivi, orientati alla individuazione (costruzione) di una soluzione ammissibile;

metodi migliorativi o di ricerca locale, che, partendo da una soluzione ammissibile, puntano a migliorarla;

metodi metaeuristici che utilizzano diversi meccanismi per migliorare le soluzioni ottenibili con un metodo migliorativo.

Metodi o algoritmi costruttivi

Metodi costruttivi
Metodi orientati alla costruzione di una soluzione ammissibile.
Passi fondamentali di un algoritmo costruttivo:

1. Inizializzazione
Si sceglie un elemento di partenza per la costruzione della soluzione parziale S.

2. Selezione di un nuovo elemento da aggiungere alla soluzione parziale
Si individua il criterio di selezione di un nuovo elemento da aggiungere alla soluzione parziale S.

3. Criterio di arresto
Se S è completa e, quindi, ammissibile la procedura si interrompe altrimenti si ritorna al passo 2.

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi costruttivi (segue)

Metodi o algoritmi migliorativi

Metodi migliorativi
Metodi orientati al miglioramento di una soluzione ammissibile

Passi fondamentali di un algoritmo migliorativo

1. Inizializzazione
Si sceglie una soluzione iniziale S di innesco del processo di ricerca.

2. Individuazione dell’intorno
Si definisce una “mossa” ovvero una operazione che consente di individuare un intorno N(S) della soluzione corrente.

3. Scelta di una nuova soluzione
Si individua la soluzione S‘∈N(S) migliore dell’intorno.

4. Criterio di arresto
Se S’ è migliore di S si sostituisce si pone S=S’ e si torna al passo 2; altrimenti la procedura si arresta.

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi (segue)

Metodi o algoritmi migliorativi

Dal punto di vista matematico il processo di ricerca analizza, ad ogni iterazione, un intorno della soluzione corrente. Per questa ragione gli algoritmi migliorativi sono detti anche algoritmi o tecniche di ricerca locale.
Le soluzioni individuate da algoritmi di ricerca locale rappresentano ottimi (minimi o massimi) locali e dipendono dalla

• Scelta della soluzione di partenza;
• Scelta della mossa.

Conclusioni

In presenza di problemi complessi dal punto di vista computazionale (NP-hard) nelle applicazioni è necessario ricorrere a tecniche euristiche di risoluzione.

Le tecniche costruttive sono orientate alla individuazione (costruzione) di una soluzione ammissibile.

Le tecniche migliorative o di ricerca locale partono da una soluzione ammissibile e puntano a migliorarla attraverso la applicazione iterativa di una mossa. Esse convergono in un ottimo locale.

Per migliorare la qualità delle soluzioni individuabili con queste tecniche è possibile ricorrere a tecniche cosiddette metaeuristiche.