¿Cuál es la diferencia entre heurística y metaheurística?

Después de algunas investigaciones sobre algoritmos, encontré dos términos que me confunden. He leído al menos 20 artículos y, sin embargo, no hay una definición clara sobre ninguno de ellos. Espero que alguien pueda ayudarme a decir la diferencia entre los algoritmos heurísticos y metaheurísticos. Y si es posible, agregue la fuente de la misma.¿Cuál es la diferencia entre heurística y metaheurística?

ps: Ya sé cuál es el significado de las palabras, pero no sé cuál es la diferencia exacta entre ellos en ciencias de la computación.

gracias de antemano

Fuente

2012-05-04 Nico Liu

Realmente depende del contexto. Las heurísticas son reglas útiles que se aproximan a la respuesta/comportamiento perfecto. Sin contexto, agregarle meta no le da ningún significado especial, solo significa que es meta, es decir, heurística sobre heurística. –

Esto está en el contexto de los algoritmos –

. Todavía depende del contexto, de una manera que significa que nunca obtendrás una respuesta directa, porque no están definidos correctamente. En los círculos de IA, una heurística es una función de "buena adivinanza" que se utiliza como un elemento fundamental de un algoritmo más grande (generalmente de búsqueda). Una metaheurística es una especie de sistema de "buena conjetura" en sí mismo que sigue refinando sus conjeturas. Pero eso es solo mi opinión: estas cosas son tan indefinidas que incluso los documentos que hacen evaluaciones comparativas de heurística versus metaheurística no definen u ofrecen solo definiciones sueltas. Básicamente, sabes uno cuando ves uno. – Novak

Se podría pensar en una heurística como una solución aproximada (no aproximación) a un problema. La diferencia entre aproximación y aproximación es que la primera se trata de obtener una buena estimación de la solución de un problema, pero que realmente no se sabe qué tan buena es. El segundo se trata de obtener una solución para la que pueda demostrar qué tan cerca está de la solución óptima.

Por lo tanto, las heurísticas a menudo dependen del problema, es decir, define una heurística para un problema determinado. Las metaheurísticas son técnicas independientes de los problemas que se pueden aplicar a una amplia gama de problemas. Una heurística es, por ejemplo, elegir un elemento aleatorio para pivotar en Quicksort. Una metaheurística no sabe nada sobre el problema que se aplicará, puede tratar las funciones como cuadros negros.

Se podría decir que una heurística explota la información dependiente del problema para encontrar una solución "suficientemente buena" a un problema específico, mientras que las metaheurísticas son, como patrones de diseño, ideas algorítmicas generales que se pueden aplicar a una amplia gama de problemas.

Fuente

2012-05-07 16:15:46

¿También tiene alguna fuente al respecto? –

Hay un gran libro introductorio sobre metaheurística por [El-Ghazali Talbi] (http://books.google.com/books/about/Metaheuristics.html?id=SIsa6zi5XV8C). Establece más o menos esta misma opinión en la introducción. Echale un vistazo. –

Entonces, desde que dijiste, NSGAII es un algoritmo meta-heurístico ya que podría ser aplicable a muchos problemas incluso con mi propio problema complejo, pero si escribo mi propio algoritmo explotando la información de mi propio problema complejo, significa que es una heurística ¿algoritmo? ¿Tengo el significado y las diferencias? (Lo siento por el mal inglés) – Aerox

Con el fin de darle una cita adecuada, en relación con Alejandro respuesta:

«Un metaheurístico es un marco algorítmico independiente de problemas de alto nivel que proporciona un conjunto de directrices o estrategias para el desarrollo de algoritmos de optimización heurística [ ...] una aplicación específica del problema de un algoritmo de optimización heurística de acuerdo con las directrices expresadas en un marco metaheurístico también se conoce como un metaheurístico »(Sörensen, Glover en http://scholarpedia.org/article/Metaheuristics)

para ser totalmente completa. Deberíamos distinguir entre algoritmos exactos, aproximados y heurísticos. Un algoritmo exacto encuentra una solución exacta. Un algoritmo aproximado debería encontrar una solución aproximada, dentro de un tiempo aceptable, así como también indicar su rango de discrepancia con la supuesta solución óptima. Una heurística simplemente encuentra una solución lo suficientemente buena, dentro de un tiempo aceptable.

Por cierto, el ejemplo de Alejandro quicksort no parece completamente adecuado por dos o tres razones diferentes.

De hecho, la heurística y la metaheurística forman parte del campo de la optimización. El problema que intentan abordar es, por lo tanto, la búsqueda de un óptimo, no de clasificación.
Los heurísticos generalmente se utilizan cuando los problemas que desea abordar son demasiado complejos, en el sentido computacional, que no es el caso del problema de clasificación.
Lo que se señaló a través del ejemplo de quicksort, si lo entiendo bien, es el elemento aleatorio. En principio, puede tener heurística determinística: nunca encontré una metaheurística determinista, pero probablemente podría codificarse. Puede ser un poco "jugar con palabras" pero, el elemento aleatorio caracteriza más adecuadamente "búsqueda estocástica" que (meta) heurística.

Fuente

2015-01-20 21:58:12 Touki

Hum, creo que Una estrella es una posible heurística determinista? – reyman64

@Touki, +1 por sus instructivas adiciones.Solo quiero señalar que, incluso si es un ejemplo de estreñimiento, puede formular la clasificación para encontrar la permutación que minimiza el número de inversiones. Con esa formulación, puede aplicar cualquier metaheurística combinatoria (por ejemplo, GA o SA) para resolverla. Por supuesto, Quicksort funcionaría mucho mejor porque explota la estructura del problema. En este sentido, tal vez Quicksort en sí mismo puede considerarse una heurística para el problema de la clasificación. Lo sé, no es una formulación útil en la práctica, pero sirve para señalar las diferencias. –

Como un lado, ver [Nelder-Mead] (https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method) como un ejemplo de un algoritmo que en mi humilde opinión se puede considerar una meta-heurística (amplia aplicabilidad a una amplia gama de problemas de optimización de caja negra), y es completamente determinista. Es heurístico porque, contrariamente a lo que dicen, [el método simple] (https://en.wikipedia.org/wiki/Simplex_algorithm) no garantiza converger al óptimo global. –

Para una explicación detallada, ver:

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

Un metaheurístico es un marco algorítmico independiente de problemas de alto nivel que proporciona un conjunto de directrices o estrategias para desarrollar optimización heurística algoritmos. El término también se utiliza para referirse a una implementación de problema específico de un algoritmo de optimización heurística de acuerdo con las directrices expresadas en dicho marco (Sörensen, 2015).

Las heurísticas son las directrices, los metaheursticos son el marco que las usa.

Fuente

2016-08-21 19:38:16 dorien

¿Cuál es la diferencia entre heurística y metaheurística?

Respuesta

Cuestiones relacionadas