metaheuristici

Le metaheuristiche sono metodi generali per guidare la ricerca di soluzioni vicine all’ottimo in problemi di ottimizzazione complessi, in particolare di tipo combinatorio. Si tratta di framework di ricerca indipendenti dal problema specifico che combinano euristiche diverse per bilanciare esplorazione del dominio e sfruttamento delle regioni promettenti. A differenza degli algoritmi esatti, non garantiscono l’ottimalità globale, ma forniscono soluzioni di buona qualità entro limiti di tempo ragionevoli.

Operano su una o più soluzioni con meccanismi di ricerca locale, diversificazione e intensificazione, includendo una componente stocastica per evitare ottimi locali. Tra le principali famiglie figurano: algoritmi di ricerca locale con strategie di diversificazione e intensificazione; algoritmi evolutivi, tra cui i memetici; l’annealing simulato; la tabu search; e metodi basati su sciami quali l’ottimizzazione tramite sciami di particelle e l’ottimizzazione tramite colonie di formiche. Esistono anche metaheuristiche ibride, come i memetic algorithms, che combinano ricerca globale e locale, e hyper-heuristics che selezionano tra diverse euristiche.

Le metaheuristiche trovano impiego in problemi di ottimizzazione combinatoria, come il problema del commesso viaggiatore, i problemi di scheduling e di assegnazione, nonché in routing logistico, progettazione di reti, design di progettazione ingegneristica, bioinformatica e finanza.

Tra i limiti vi sono la dipendenza dal modello di encoding del problema, la sensibilità ai parametri di controllo, i costi computazionali e l’assenza di garanzie di ottimalità globale. Nonostante ciò, le metaheuristiche offrono strumenti flessibili ed efficaci per problemi grandi e complessi e continuano a evolversi con nuove tecniche e ibridi.

Le metaheuristiche hanno assunto rilievo dagli anni Ottanta e Novanta del XX secolo e rimangono ampiamente usate in ricerca operativa, ingegneria e scienze applicate.