Hiperheurística

Una hiperheurística es un método de búsqueda heurística que busca automatizar, a menudo mediante la incorporación de técnicas de aprendizaje automático , el proceso de selección, combinación, generación o adaptación de varias heurísticas más simples (o componentes de dichas heurísticas) para resolver eficientemente problemas de búsqueda computacional. Una de las motivaciones para estudiar las hiperheurísticas es construir sistemas que puedan manejar clases de problemas en lugar de resolver solo un problema. ^{[ 1 ] [ 2 ] [ 3 ]}

Puede haber múltiples heurísticas entre las que elegir para resolver un problema, y ​​cada heurística tiene sus propias fortalezas y debilidades. La idea es diseñar automáticamente algoritmos combinando las fortalezas y compensando las debilidades de las heurísticas conocidas. ^{[ 4 ]} En un marco hiperheurístico típico, hay una metodología de alto nivel y un conjunto de heurísticas de bajo nivel (ya sean constructivas o perturbativas). Dada una instancia del problema, el método de alto nivel selecciona qué heurística de bajo nivel debe aplicarse en un momento dado, dependiendo del estado actual del problema (o etapa de búsqueda) determinado por las características. ^{[ 2 ] [ 5 ] [ 6 ]}

La diferencia fundamental entre metaheurísticas e hiperheurísticas radica en que la mayoría de las implementaciones de metaheurísticas buscan dentro de un espacio de búsqueda de soluciones a problemas, mientras que las hiperheurísticas siempre buscan dentro de un espacio de búsqueda de heurísticas. Por lo tanto, al usar hiperheurísticas, buscamos el método o la secuencia de heurísticas adecuados para una situación dada, en lugar de intentar resolver un problema directamente. Además, buscamos una metodología de aplicación general, en lugar de resolver un único caso.

Las hiperheurísticas podrían considerarse métodos "listos para usar", en contraposición a las metaheurísticas "a medida". Su objetivo es ser métodos genéricos que produzcan soluciones de calidad aceptable, basadas en un conjunto de heurísticas de bajo nivel fáciles de implementar.

A pesar del notable progreso alcanzado hasta ahora en la creación de metodologías de búsqueda para una amplia variedad de áreas de aplicación, estos enfoques aún requieren que los especialistas integren su experiencia en un dominio específico. Muchos investigadores de informática , inteligencia artificial e investigación operativa ya han reconocido la necesidad de desarrollar sistemas automatizados que reemplacen el rol del experto humano en estas situaciones. Una de las ideas principales para automatizar el diseño de heurísticas requiere la incorporación de mecanismos de aprendizaje automático en los algoritmos para guiar la búsqueda de forma adaptativa. Tanto los procesos de aprendizaje como de adaptación pueden realizarse en línea o fuera de línea, y basarse en heurísticas constructivas o perturbativas.

Una hiperheurística generalmente busca reducir la cantidad de conocimiento del dominio en la metodología de búsqueda. El enfoque resultante debería ser económico y rápido de implementar, requiriendo menos experiencia tanto en el dominio del problema como en los métodos heurísticos, e idealmente, debería ser lo suficientemente robusto como para manejar eficazmente una variedad de instancias de problemas de diversos dominios. El objetivo es elevar el nivel de generalidad de la metodología de apoyo a la decisión, quizás a costa de una calidad de solución reducida, pero aún aceptable, en comparación con los enfoques metaheurísticos personalizados. ^{[ 7 ]} Para reducir la brecha entre los esquemas personalizados y las estrategias basadas en hiperheurísticas, se han propuesto hiperheurísticas paralelas. ^{[ 8 ]}

El término "hiperheurísticas" fue acuñado por primera vez en una publicación de 2000 por Cowling y Soubeiga, quienes lo usaron para describir la idea de "heurísticas para elegir heurísticas". ^{[ 9 ]} Utilizaron un enfoque de aprendizaje automático de "función de elección" que equilibra la explotación y la exploración al elegir la siguiente heurística a utilizar. ^{[ 10 ]} Posteriormente, Cowling, Soubeiga, Kendall, Han, Ross y otros autores investigaron y extendieron esta idea en áreas como algoritmos evolutivos y heurísticas patológicas de bajo nivel. El primer artículo de revista que utilizó el término apareció en 2003. ^{[ 11 ]} El origen de la idea (aunque no del término) se remonta a principios de la década de 1960 ^{[ 12 ] [ 13 ]} y fue redescubierto y extendido de forma independiente varias veces durante la década de 1990. ^{[ 14 ] [ 15 ] [ 16 ]} En el dominio de la programación de talleres de trabajo , el trabajo pionero de Fisher y Thompson, ^{[ 12 ] [ 13 ]} hipotetizó y demostró experimentalmente, utilizando aprendizaje probabilístico, que la combinación de reglas de programación (también conocidas como reglas de prioridad o despacho) era superior a cualquiera de las reglas tomadas por separado. Aunque el término no se usaba entonces, este fue el primer artículo "hiperheurístico". Otra raíz que inspira el concepto de hiperheurísticas proviene del campo de la inteligencia artificial . Más específicamente, proviene del trabajo en sistemas de planificación automatizados y su eventual enfoque hacia el problema del aprendizaje del conocimiento de control. El llamado sistema COMPOSER, desarrollado por Gratch et al., ^{[ 17 ] [ 18 ]} se utilizó para controlar los cronogramas de comunicación satelital que involucran una serie de satélites en órbita terrestre y tres estaciones terrestres. El sistema puede caracterizarse como una búsqueda de ascenso de colina en el espacio de posibles estrategias de control.

Los enfoques hiperheurísticos se pueden clasificar en dos categorías principales. En la primera, denominada heurísticas para elegir heurísticas , ^{[ 9 ] [ 10 ]} el marco hiperheurístico se basa en un conjunto de heurísticas preexistentes y ampliamente conocidas para resolver el problema objetivo. La tarea consiste en descubrir una buena secuencia de aplicaciones de estas heurísticas (también conocidas como heurísticas de bajo nivel dentro del ámbito de las hiperheurísticas) para resolver el problema de manera eficiente. En cada etapa de decisión, se selecciona una heurística mediante un mecanismo de selección y se aplica a una solución existente. La nueva solución resultante de la aplicación de la heurística seleccionada se acepta o rechaza según un criterio de aceptación. El rechazo de una solución implica su descarte, mientras que su aceptación conlleva el reemplazo de la solución existente. En la segunda clase, heurísticas para generar heurísticas , la idea clave es "desarrollar nuevas heurísticas utilizando los componentes de heurísticas conocidas". ^{[ 19 ]} El proceso requiere, como en la primera clase de hiperheurísticas, la selección de un conjunto adecuado de heurísticas que se sabe que son útiles para resolver el problema objetivo. Sin embargo, en lugar de proporcionarlas directamente al marco, las heurísticas se descomponen primero en sus componentes básicos.

Estos dos tipos principales pueden subdividirse según se basen en una búsqueda constructiva o perturbativa. Una clasificación ortogonal adicional de las hiperheurísticas considera la fuente que proporciona retroalimentación durante el proceso de aprendizaje, que puede ser una sola instancia ( aprendizaje en línea ) o varias instancias del problema subyacente estudiado ( aprendizaje fuera de línea ).

Las hiperheurísticas se han aplicado a una gran variedad de problemas. De hecho, una de las motivaciones de las hiperheurísticas es su versatilidad para operar en diferentes tipos de problemas. La siguiente lista es una selección no exhaustiva de algunos de los problemas y campos en los que se han explorado las hiperheurísticas:

• problema de empaquetamiento de contenedores
• problema de satisfacibilidad booleana
• horarios educativos
• programación de talleres de trabajo
• resolución de problemas multiobjetivo y asignación de espacio
• planificación de turnos de enfermeras
• programación de personal
• problema del viajante
• problema de enrutamiento de vehículos
• problema de la mochila multidimensional
• Problema de la mochila 0-1
• problema de corte máximo
• problema de asignación cuadrática
• problema de diseño de instalaciones
• Diseño del parque eólico

Las hiperheurísticas no son el único enfoque que se investiga en la búsqueda de metodologías de búsqueda más generales y aplicables. Muchos investigadores de informática, inteligencia artificial e investigación operativa ya han reconocido la necesidad de desarrollar sistemas automatizados que reemplacen el rol del experto humano en el proceso de ajuste y adaptación de las metodologías de búsqueda. La siguiente lista describe algunas áreas de investigación relacionadas:

• Adaptación y autoadaptación de los parámetros del algoritmo
• algoritmo memético adaptativo
• búsqueda adaptativa en vecindarios grandes
• configuración del algoritmo
• control de algoritmos
• carteras de algoritmos
• búsqueda autónoma
• programación genética
• Codificaciones indirectas en algoritmos evolutivos
• búsqueda de vecindario variable
• búsqueda reactiva

Actualmente, existen varios frameworks disponibles en diferentes lenguajes de programación. Estos incluyen, entre otros:

HyFlex

ParHyFlex

Hiperactividad evolutiva

MatHH

• Heurística constructiva
• La metaoptimización está estrechamente relacionada con las hiperheurísticas.
• algoritmos genéticos
• programación genética
• algoritmos evolutivos
• búsqueda local (optimización)
• aprendizaje automático
• algoritmos meméticos
• metaheurísticas
• En búsqueda y optimización no hay nada gratis
• optimización por enjambre de partículas
• búsqueda reactiva