Metaeuristica

Una metaeuristica è un termine ombrello per quadri algoritmici strategici di alto livello progettati per esplorare lo spazio di ricerca oltre i minimi locali. Il termine è stato coniato da Glover (1986) nel contesto di tabu search e si è standardizzato nella letteratura di RO negli anni 1990. Le principali famiglie di metaeuristiche: (1) tabu search (Glover 1989) — proibisce le mosse recenti di ricerca locale tramite una lista tabù per evitare cicli; (2) simulated annealing (Kirkpatrick, Gelatt e Vecchi 1983) — parametro di temperatura ispirato alla fisica che accetta probabilisticamente mosse peggiorative; (3) algoritmo genetico (Holland 1975) — ricerca evolutiva con popolazione, selezione, crossover e mutazione; (4) variable neighborhood search (Mladenović e Hansen 1997) — transizioni sistematiche tra più strutture di vicinato; (5) GRASP (Feo e Resende 1995) — costruzione randomizzata-greedy più ricerca locale; (6) ottimizzazione tramite colonie di formiche (Dorigo 1992) e sciami di particelle (Kennedy e Eberhart 1995). Le metaeuristiche ibride (matheuristiche) sono cresciute di importanza negli ultimi vent'anni, usando un solver MIP come risolutore di sottoproblemi all'interno del ciclo metaeuristico. La taratura dei parametri (lunghezza della lista tabù, programma di raffreddamento, dimensione della popolazione, tasso di mutazione) determina in larga misura il compromesso qualità-tempo. Riferimenti standard: Glover e Kochenberger (2003), Talbi (2009) e Gendreau e Potvin (2010) Handbook of Metaheuristics.