Molti problemi di ottimizzazione reali sono troppo grandi o troppo complicati per un metodo esatto: orari scolastici con decine di vincoli, giri di consegna con finestre orarie, disposizione di macchinari in uno stabilimento. Le metaeuristiche sono strategie generali per cercare buone soluzioni in questi casi. Non garantiscono l'ottimo, ma in tempi ragionevoli trovano spesso soluzioni molto buone, e si adattano a problemi diversi cambiando pochi ingredienti.
Il punto di partenza: la ricerca locale
Quasi tutte le metaeuristiche partono dalla ricerca locale. Servono tre cose:
- una rappresentazione della soluzione (per il commesso viaggiatore, l'ordine delle città);
- una funzione di costo da minimizzare (la lunghezza del giro, più eventuali penalità per vincoli violati);
- un vicinato: le soluzioni raggiungibili con una piccola modifica (per esempio una mossa 2-opt, o lo scambio di due elementi).
La ricerca locale più semplice, detta discesa, parte da una soluzione e si sposta a un vicino migliore finché ne esiste uno. Il limite è evidente: si ferma al primo ottimo locale, una soluzione migliore di tutti i suoi vicini ma potenzialmente molto peggiore dell'ottimo globale. È come un escursionista nella nebbia che scende sempre e si ferma nella prima conca, senza sapere che più in là c'è una valle molto più profonda.
Le metaeuristiche sono, in sostanza, modi diversi di uscire da quelle conche.
Simulated annealing
Il simulated annealing (ricottura simulata) prende l'idea dalla metallurgia: un metallo raffreddato lentamente forma una struttura più ordinata di uno raffreddato in fretta. L'algoritmo:
- sceglie un vicino a caso;
- se è migliore, lo accetta;
- se è peggiore di una quantità Δ, lo accetta comunque con probabilità e^(−Δ/T), dove T è la «temperatura»;
- abbassa gradualmente T.
import math, random
def annealing(sol, costo, vicino, T=100.0, alfa=0.995, passi=100000):
migliore = attuale = sol
for _ in range(passi):
cand = vicino(attuale)
delta = costo(cand) - costo(attuale)
if delta < 0 or random.random() < math.exp(-delta / T):
attuale = cand
if costo(attuale) < costo(migliore):
migliore = attuale
T *= alfa
return migliore
All'inizio, con T alta, si accettano spesso peggioramenti e la ricerca esplora liberamente. Man mano che T scende, i peggioramenti vengono accettati sempre meno e la ricerca si stabilizza. La scelta più delicata è lo schema di raffreddamento: troppo veloce e ci si blocca in un ottimo locale, troppo lento e si spreca tempo.
Tabu search
La tabu search è deterministica e usa la memoria. A ogni passo si sposta al miglior vicino, anche se è peggiore della soluzione attuale. Per evitare di tornare subito indietro e girare in tondo, tiene una lista tabu delle mosse recenti, che restano vietate per un certo numero di iterazioni.
Elementi tipici:
- durata tabu: quante iterazioni una mossa resta vietata; valori piccoli rischiano cicli, valori grandi limitano troppo la ricerca;
- criterio di aspirazione: una mossa tabu è comunque permessa se porta a una soluzione migliore di tutte quelle viste finora;
- diversificazione: se la ricerca ristagna, si favoriscono mosse poco usate per spostarsi in zone nuove.
La tabu search è molto efficace in problemi di scheduling e assegnamento, dove valutare tutti i vicini è abbastanza rapido.
Algoritmi genetici
Gli algoritmi genetici lavorano su una popolazione di soluzioni invece che su una sola, imitando in modo astratto la selezione naturale:
- selezione: le soluzioni migliori hanno più probabilità di essere scelte come «genitori»;
- incrocio: due genitori si combinano per produrre figli che ereditano parti di entrambi;
- mutazione: piccole modifiche casuali mantengono la diversità;
- sostituzione: i figli prendono il posto di parte della popolazione.
Il punto critico è l'incrocio. Per molti problemi combinare due soluzioni valide in modo ingenuo produce soluzioni non valide: unendo metà di un giro del commesso viaggiatore con metà di un altro si ottengono città ripetute e città mancanti. Servono operatori progettati per il problema, come l'incrocio ordinato per le permutazioni. In pratica, gli algoritmi genetici funzionano meglio quando ogni figlio viene anche migliorato con una ricerca locale: si parla allora di algoritmi memetici.
Confronto
| Metodo | Soluzioni attive | Come esce dagli ottimi locali | Punto delicato |
|---|---|---|---|
| Simulated annealing | una | accetta peggioramenti con probabilità decrescente | schema di raffreddamento |
| Tabu search | una | vieta le mosse recenti | durata tabu e vicinato |
| Algoritmi genetici | molte | ricombina soluzioni diverse | operatori di incrocio |
Consigli pratici
- Il vicinato conta più della metaeuristica: un buon insieme di mosse, valutate in modo incrementale (calcolando solo la variazione di costo), vale più di qualunque parametro ben scelto.
- Vincoli come penalità: spesso conviene permettere soluzioni che violano alcuni vincoli, aggiungendo una penalità al costo, invece di vietarle. La ricerca si muove più liberamente.
- Confrontate con una base semplice: un greedy seguito da discesa con riavvii casuali è un riferimento onesto. Se la metaeuristica non lo batte, qualcosa va rivisto.
- Più esecuzioni: i metodi casuali danno risultati diversi a ogni esecuzione; si confrontano medie e dispersione su più prove, non un singolo risultato fortunato.
- Limiti inferiori: quando possibile, un rilassamento lineare o un limite combinatorio dice quanto si è lontani dall'ottimo.
In sintesi
- La ricerca locale migliora una soluzione con piccole mosse ma si ferma al primo ottimo locale.
- Il simulated annealing accetta peggioramenti con una probabilità che cala con la temperatura.
- La tabu search si sposta sempre al miglior vicino e vieta temporaneamente le mosse recenti.
- Gli algoritmi genetici fanno evolvere una popolazione e rendono meglio se combinati con la ricerca locale.
- Vicinato ben progettato, penalità sui vincoli e confronti onesti contano più dei parametri.
