computer-science - método - heuristica

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

Question

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 los dos. Espero que alguien pueda ayudarme a distinguir la diferencia entre los algoritmos heurísticos y metaheurísticos. Y si es posible, agregue la fuente de ello.

pd: ya sé cuál es el significado de las palabras, pero no sé cuál es la diferencia exacta entre ellas en informática.

gracias por adelantado

Answer 1

Para dar una cotización adecuada, en relación a la respuesta de Alejandro:

«Una metaheurística es un marco algorítmico independiente de problemas de alto nivel que proporciona un conjunto de pautas o estrategias para desarrollar algoritmos de optimización heurística [...] Una implementación específica de un algoritmo de optimización heurística según las pautas expresadas en un marco metaheurístico también se conoce como metaheurística »(Sörensen, Glover en http://scholarpedia.org/article/Metaheuristics )

Para estar completamente completo. Debemos distinguir entre algoritmos exactos, aproximados y heurísticos. Un algoritmo exacto encuentra una solución exacta. Un algoritmo aproximado debe encontrar una solución aproximada, dentro de un tiempo aceptable, así como 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.

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

Answer 2

Para una explicación detallada, ver:

Sörensen, K. (2015). Metaheurística: la metáfora expuesta. Transacciones internacionales en investigación operativa, 22 (1), 3-18.

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

Las heurísticas son las pautas, la metaheúrgica es el marco que las utiliza.

Answer 3

Se podría pensar en una solución heurística como una solución aproximada (no aproximada) a un problema. La diferencia entre aproximación y aproximación es que la primera consiste en obtener una buena idea de la solución de un problema, pero en realidad no se sabe qué tan bueno es. El segundo es sobre 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, se define una heurística para un problema dado. Las metaheurísticas son técnicas independientes de problemas que pueden aplicarse 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 cajas negras.

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