Altri progetti
Wikimedia Commons contiene immagini o altri file su Metaeuristica
In informatica ed in ottimizzazione, una metaeuristica è una procedura o euristica di livello superiore progettata per trovare, generare, regolare o selezionare un'euristica (algoritmo di ricerca parziale) che possa fornire una soluzione sufficientemente buona di un problema di ottimizzazione o di un problema di apprendimento automatico, in particolare nel caso di informazioni incomplete o imperfette o di capacità di calcolo limitata. Le metaeuristiche campionano un sottoinsieme di soluzioni che altrimenti sarebbe troppo ampio per essere completamente enumerato o esplorato. Le metaeuristiche richiedono relativamente poche assunzioni sul problema di ottimizzazione da risolvere, quindi possono essere utilizzate per una varietà di problemi. Il loro utilizzo è sempre di interesse allorché metodi esatti o altri metodi (approssimati) non siano disponibili o ritenuti appropriati, a causa di un tempo di calcolo richiesto troppo lungo o perché, ad esempio, la soluzione fornita è troppo imprecisa.
Rispetto agli algoritmi di ottimizzazione e ai metodi iterativi, le metaeuristiche non garantiscono il ritrovamento di una soluzione globalmente ottimale per una data classe di problemi. Molte metaeuristiche implementano una qualche forma di ottimizzazione stocastica, di modo che la soluzione trovata dipenda dall'insieme di variabili casuali generate. Nell'ottimizzazione combinatoria, ci sono molti problemi che appartengono alla classe dei problemi NP-completi e quindi non possono più essere risolti esattamente in un tempo accettabile con un grado di complessità relativamente basso. Le metaeuristiche quindi spesso forniscono buone soluzioni con minor costo computazionale rispetto ai metodi di approssimazione, ai metodi iterativi o alle euristiche semplici. Questo vale anche nel campo dell'ottimizzazione continua o mista-intera. Pertanto, le metaeuristiche costituiscono un approccio utile per problemi di ottimizzazione. Sono stati pubblicati diversi libri e articoli di indagine sull'argomento. Una rassegna della letteratura sull'ottimizzazione metaeuristica, suggerisce che sia stato Fred Glover a coniare il termine metaeuristica.
La maggior parte della letteratura sulle metaeuristiche è di natura sperimentale e descrive risultati empirici basati su esperimenti al computer sugli algoritmi. Sono comunque disponibili anche risultati teorici formali, che tipicamente riguardano la convergenza e la garanzia di trovare l'ottimo globale. Conviene anche menzionare i teoremi no-free-lunch, che affermano che non può esistere una metaeuristica migliore di tutte le altre per un dato problema.
Soprattutto a partire dall'inizio del millennio, sono stati pubblicati molti metodi metaeuristici con pretese di novità ed efficacia pratica. Sebbene il campo sia caratterizzato anche da ricerche di alta qualità, molte delle pubblicazioni più recenti sono caratterizzate da scarsa qualità; i principali difetti comprendono vaghezza, mancanza di elaborazione concettuale, bassa qualità degli esperimenti e scarsa conoscenza della letteratura correlata.
Wikimedia Commons contiene immagini o altri file su Metaeuristica
