Significado de los métodos (meta) heurísticos

10

  1. Para la optimización, de Wikipedia :

    En informática, la metaheurística designa un método computacional que optimiza un problema al intentar iterativamente mejorar una solución candidata con respecto a una medida de calidad dada. Las metaheurísticas hacen pocas o ninguna suposición sobre el problema que se está optimizando y pueden buscar espacios muy grandes de soluciones candidatas. Sin embargo, las metaheurísticas no garantizan que se encuentre una solución óptima. Muchas metaheurísticas implementan alguna forma de optimización estocástica.

    Otros términos que tienen un significado similar a metaheurístico son: sin derivación, búsqueda directa, recuadro negro o, de hecho, solo optimizador heurístico. Se han publicado varios libros y encuestas sobre el tema.

    • Me pregunto cómo saber si un método de optimización es metaheurístico o no. Por ejemplo,

      (1) ¿El método simplex para programación lineal es metaheurístico?

      (2) ¿La mayoría de los métodos de programación no lineal como el descenso de gradiente, el método multiplicador lagrangiano, los métodos de penalización, los métodos de punto interior (métodos de barrera), son metaheurísticos?

      (3) ¿Todos los métodos sin gradiente, como el método de Nelder-Mead o el método simplex de descenso, son metaheurísticos?

    • ¿Cuáles son algunos métodos de optimización que no son metaheurísticos?

  2. Más generalmente (más allá de la optimización) para técnicas de resolución de problemas, de Wikipedia :

    La heurística se refiere a técnicas basadas en la experiencia para la resolución de problemas, el aprendizaje y el descubrimiento . Cuando una búsqueda exhaustiva no es práctica, se utilizan métodos heurísticos para acelerar el proceso de encontrar una solución satisfactoria. Los ejemplos de este método incluyen el uso de una regla general, una suposición educada, un juicio intuitivo o sentido común.

    En términos más precisos, las heurísticas son estrategias que utilizan información fácilmente accesible, aunque poco aplicable, para controlar la resolución de problemas en seres humanos y máquinas.

    Me pregunto cómo entender el significado de "heurístico".

    • ¿Cómo puedo saber si una técnica de "resolución de problemas, aprendizaje y descubrimiento" es heurística o no?

    • ¿Cuáles son algunas técnicas de "resolución de problemas, aprendizaje y descubrimiento" que no son heurísticas?

¡Gracias y saludos!

optimization heuristics Tim
fuente

Respuestas:

7

La heurística es algo que funciona en muchos casos en la práctica, aunque no existe un argumento detallado de por qué debería funcionar bien.

La metaheurística no es un algoritmo sino un esquema o idea heurística general que puede usarse dentro de algoritmos específicos.

Por ejemplo, el algoritmo simplex para programación lineal no es ni heurística ni metaheurística, ya que tiene una teoría de convergencia bien establecida. El sqame es válido para la programación cuadrática secuencial o los métodos de punto interior. (Los métodos de puntos interiores son un esquema general, pero no heurístico y, por lo tanto, no son metaheurísticos, ya que existe una teoría bastante fuerte asociada con él).

El algoritmo Nelder-Mead = downhill simplex para minimizar una función es la heurística (en realidad puede fallar en problemas bastante simples en dimensiones superiores), y la búsqueda tabú es metaheurística (ya que se pueden escribir muchos algoritmos diversos que emplean la búsqueda tabú, pero son de otra manera de calidad bastante diferente.

Arnold Neumaier
fuente
¡Gracias! (1) Entonces, para saber si un método es metaheurístico, ¿es para ver si tiene una teoría sobre cuándo converge con el verdadero optimizador? Si un método aún no tiene esa teoría, entonces ¿es menesterista? Si algún día hay una teoría para ello, ¿pasará de ser metaheurístico a no metaheurístico? (2) "Otros términos que tienen un significado similar a metaheurístico son: sin derivación, búsqueda directa, recuadro negro o, de hecho, simplemente optimizador heurístico". Me pregunto si la metaheurística solo hace uso de valores de función y es libre de derivadas. ¿Es el método de "búsqueda" en su respuesta a mi otra pregunta?
Tim
@Tim: metaheurístico significa: (i) ninguna teoría de convergencia, y (ii) ninguna receta definitiva para proceder, sino principios generales. - sin derivadas (= búsqueda directa = recuadro negro; diferentes nombres para el mismo de diferentes raíces históricas) pueden ser heurísticas o no; solo informa sobre la entrada que el usuario debe proporcionar.
Arnold Neumaier
¡Gracias! Me pregunto si la metaheurística solo hace uso de valores de función y es libre de derivadas.
Tim
@Tim: Probablemente sí; No conozco nada realmente llamado metaheurístico que use gradientes.
Arnold Neumaier
7

No repetiré sobre simplex y Nelder-Mead ya que @ArnoldNeumaier ya dio una muy buena explicación, pero quería agregar mis 2 centavos.

Una de las mejores citas que he escuchado hace algún tiempo para describir la diferencia entre heurística y metaheurística: una heurística es una regla bastante buena. Una metaheurística es una regla bastante buena para encontrar reglas bastante buenas.

Debería verlo como una forma de encontrar buenas heurísticas para problemas específicos; Básicamente, si te haces una de las siguientes preguntas, estás hablando de una metaheurística:

  • ¿Cómo debo ajustar los parámetros de esta heurística para mejorar el rendimiento en ese problema?
  • ¿Es esto heurístico mejor que heurístico?

Hay un montón de metaheurísticas que puede usar para resolver problemas, aprender y descubrir , a saber:

Me parece que la mayoría de las metaheurísticas están inspiradas en fenómenos naturales, que son difíciles de explicar rigurosamente, pero que tienen buenas propiedades de convergencia.

Aquí hay un buen enlace si desea leer más sobre otras técnicas metaheurísticas.

Charles Menguy
fuente
¡Gracias! No estoy seguro de entender "Una heurística es una regla bastante buena. Una metaheurística es una regla bastante buena para encontrar reglas bastante buenas". Por ejemplo, ¿el recocido simulado, el enjambre de partículas, la colonia de hormigas y la búsqueda tabú son heurísticos o metaheurísticos? Si son uno de los dos, ¿cuáles son sus contrapartes para el otro?
Tim
Lo que debe entender de esta cita es que tanto la heurística como la metaheurística no son exactas ni probadas, por lo tanto, "regla bastante buena". Un metaheurístico está en un nivel más alto que un heurístico, y es a través de varias iteraciones sucesivas que puede encontrar un conjunto de parámetros que resolverán un problema correctamente. Si supiera cuál es este conjunto de parámetros desde el principio, solo tendría que escribir una heurística para resolver el problema. Pero como no lo sabe, debe usar un algoritmo para encontrar estos parámetros para su heurística: una metaheurística. Espero que eso aclare.
Charles Menguy
Y los algoritmos que proporcioné aquí son todos metaheurísticos, y puede encontrar más detalles en el enlace que proporcioné. No estoy seguro de lo que quieres decir exactamente para las contrapartes.
Charles Menguy
Por contrapartes, quiero decir, por ejemplo, si los algoritmos son todos metaheurísticos, entonces las heurísticas en las que operan deben ser ellos mismos más valores específicos para sus parámetros ajustables.
Tim
Tomemos, por ejemplo, el recocido simulado. Lo que hace al final es una búsqueda en una cadena de Markov. La "regla" de la heurística sería asumir que un estado en la cadena de Markov es la solución. Lo que hace el metaheurístico es buscar convergencia en la cadena de Markov para encontrar el estado óptimo que describe la solución. En general, creo que no debería esforzarse demasiado para hacer la distinción: use la heurística cuando haya una solución "relativamente" simple que pueda calcularse fácilmente, y use la metaheurística cuando el espacio de la solución sea demasiado grande y necesite ser más inteligente sobre resolviendo el problema.
Charles Menguy