Vai al contenuto

Metaeuristica

Da Wikipedia, l'enciclopedia libera.

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.[1][2] 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.[3][4] 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.[5][6] 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.[7]

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.[8] 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.[9][10]

  1. ↑ Metaheuristics for production scheduling, Automation - control and industrial engineering series, ISTE, 2013, ISBN 978-1-84821-497-2.
  2. ↑ (EN) Gupta, Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems, in Expert Systems with Applications, vol. 183, 2021, pp. 115351, DOI:10.1016/j.eswa.2021.115351.
  3. ↑ (EN) Peter Brucker e Sigrid Knust, Complex Scheduling, Springer, 2012, DOI:10.1007/978-3-642-23929-8, ISBN 978-3-642-23928-1.
  4. ↑ Christos H. Papadimitriou e Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publ., corrected, unabridged new edition of the work published by Prentice-Hall in 1982., 1998, ISBN 978-0-486-40258-1.
  5. ↑ (EN) Gad, Particle Swarm Optimization Algorithm and Its Applications: A Systematic Review, in Archives of Computational Methods in Engineering, vol. 29, 2022, pp. 2531–2561, DOI:10.1007/s11831-021-09694-4, ISSN 1134-3060 (WC · ACNP).
  6. ↑ (EN) Li, Evolution strategies for continuous optimization: A survey of the state-of-the-art, in Swarm and Evolutionary Computation, vol. 56, 2020, pp. 100694, DOI:10.1016/j.swevo.2020.100694.
  7. ↑ Glover, Future paths for integer programming and links to artificial intelligence (PDF), in Computers and Operations Research, vol. 13, January 1986, pp. 533–549, DOI:10.1016/0305-0548(86)90048-1, ISSN 0305-0548 (WC · ACNP).
  8. ↑ Rudolph, Self-adaptive mutations may lead to premature convergence, in IEEE Transactions on Evolutionary Computation, vol. 5, 2001, pp. 410–414, DOI:10.1109/4235.942534.
  9. ↑ (EN) Sörensen, Metaheuristics—the metaphor exposed, in International Transactions in Operational Research, vol. 22, 2015, pp. 3–18, DOI:10.1111/itor.12001.
  10. ↑ The Conversation (website), https://theconversation.com/why-we-fell-out-of-love-with-algorithms-inspired-by-nature-42718. URL consultato il 30 agosto 2024.
  • Kenneth Sörensen, Marc Sevaux e Fred Glover, Handbook of Heuristics, Springer, 16 gennaio 2017, ISBN 978-3-319-07123-7.
  • (EN) Ashish Sharma, Nature Inspired Algorithms with Randomized Hypercomputational Perspective, Informated Sciences, 2022, DOI:10.1016/j.ins.2022.05.020.

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]
Estratto da "https://it.wikipedia.org/w/index.php?title=Metaeuristica&oldid=148145954"