Qual è la differenza tra euristica e metaheuristica?

Question

Dopo alcune ricerche sugli algoritmi ho trovato due termini che mi confondono. Ho letto almeno 20 documenti e ancora non ci sono definizioni chiare su entrambi. Spero che qualcuno possa aiutarmi a capire la differenza tra l'euristica e gli algoritmi di metaeuristica. E se possibile, aggiungine la fonte.

ps: so già qual è il significato delle parole, ma non so quale sia l'esatta differenza tra loro in informatica.

grazie in anticipo

Answer 1

Si potrebbe pensare ad un'euristica come una soluzione approssimata (non approssimazione) ad un problema. La differenza tra approssimazione e approssimazione è che il primo riguarda la possibilità di ottenere una buona ipotesi sulla soluzione di un problema, ma che non sai davvero quanto sia bello. Il secondo riguarda l'ottenimento di una soluzione per la quale è possibile dimostrare quanto è vicino alla soluzione ottimale.

Quindi, l'euristica è spesso dipendente dal problema, ovvero, si definisce un'euristica per un determinato problema. Le meta-euristiche sono tecniche indipendenti dal problema che possono essere applicate a una vasta gamma di problemi. Un'euristica è, ad esempio, la scelta di un elemento casuale per la rotazione in Quicksort. Un meta-euristico non sa nulla del problema che verrà applicato, può trattare le funzioni come scatole nere.

Si potrebbe dire che un euristico sfrutta le informazioni dipendenti dal problema per trovare una soluzione "abbastanza buona" per un problema specifico, mentre le meta-euristiche sono, come i modelli di progettazione, idee algoritmiche generali che possono essere applicate a una vasta gamma di i problemi.

Answer 2

Al fine di dare una citazione corretta, rispetto a Alejandro risposta:

«Un metaeuristica è un quadro algoritmico problema indipendente di alto livello che fornisce una serie di linee guida o strategie per sviluppare algoritmi di ottimizzazione euristici [ ...] una specifica implementazione-problema di un algoritmo di ottimizzazione euristica secondo le linee guida espresse in un quadro metaeuristica è indicato anche come un metaeuristica »(Sörensen, Glover su http://scholarpedia.org/article/Metaheuristics)

per essere del tutto completa. Dovremmo distinguere tra algoritmi esatti, approssimativi ed euristici. Un algoritmo esatto trova una soluzione esatta. Un algoritmo approssimativo dovrebbe trovare una soluzione approssimativa, entro un tempo accettabile, oltre a indicare il suo intervallo di discrepanza con la presunta soluzione ottimale. Un'euristica trova semplicemente una soluzione abbastanza buona, entro un tempo accettabile.

A proposito, l'esempio di Alejandro quicksort non sembra del tutto adeguato per due o tre motivi diversi.

1. In effetti, l'euristica e la metaeuristica fanno parte del campo dell'ottimizzazione. Il problema che cercano di affrontare è quindi di cercare un ottimo, non di smistamento.
2. Le euristiche sono generalmente utilizzate quando i problemi che si vogliono affrontare sono troppo complessi, in senso computazionale, il che non è il caso del problema di classificazione.
3. Ciò che è stato indicato tramite l'esempio quicksort, se lo capisco bene, è l'elemento casuale. In linea di principio, è possibile avere euristiche deterministiche - non ho mai incontrato una metaeuristica deterministica, ma probabilmente si potrebbe codificarla. Potrebbe essere un po '"giocare con le parole", ma l'elemento casuale caratterizza più propriamente la "ricerca stocastica" rispetto all'euristica (meta).

Answer 3

Per una spiegazione dettagliata, vedere:

Sörensen, K. (2015). Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1), 3-18.

Un metaeuristica è un algoritmico quadro problema indipendente di alto livello che fornisce una serie di linee guida o strategie per sviluppare ottimizzazione euristica algoritmi. Il termine viene anche utilizzato per fare riferimento a un'implementazione specifica del problema di un algoritmo di ottimizzazione euristica secondo le linee guida espresse in tale framework (Sörensen, 2015).

Le euristiche sono le linee guida, metaheurstics è la struttura che utilizza quelle.