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 de manera eficiente problemas de búsqueda computacional. Una de las motivaciones para estudiar la hiperheurística 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 cuales se puede elegir para resolver un problema, y cada una de ellas 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 heurísticas constructivas o perturbativas). Dada una instancia de problema, el método de alto nivel selecciona qué heurística de bajo nivel se debe aplicar 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 las metaheurísticas y las hiperheurísticas es que la mayoría de las implementaciones de las metaheurísticas buscan dentro de un espacio de búsqueda de soluciones de problemas, mientras que las hiperheurísticas siempre buscan dentro de un espacio de búsqueda de heurísticas. Por lo tanto, cuando utilizamos hiperheurísticas, intentamos encontrar el método o la secuencia de heurísticas adecuados en 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 una única instancia de problema.
Las hiperheurísticas pueden considerarse métodos "listos para usar" en lugar de metaheurísticas "hechas 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 de los importantes avances logrados hasta el momento 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 de problemas determinado. Muchos investigadores de las ciencias de la computación , la inteligencia artificial y la investigación operativa ya han reconocido la necesidad de desarrollar sistemas automatizados para reemplazar el papel de un experto humano en tales situaciones. Una de las principales ideas para automatizar el diseño de heurísticas requiere la incorporación de mecanismos de aprendizaje automático en algoritmos para guiar de forma adaptativa la búsqueda. Tanto los procesos de aprendizaje como los de adaptación pueden realizarse en línea o fuera de línea, y basarse en heurísticas constructivas o perturbativas.
Una hiperheurística suele tener como objetivo reducir la cantidad de conocimiento del dominio en la metodología de búsqueda. El enfoque resultante debería ser barato y rápido de implementar, requiriendo menos experiencia en el dominio del problema o en los métodos heurísticos, e idealmente debería ser lo suficientemente robusto como para manejar de manera efectiva una variedad de instancias de problemas de una variedad de dominios. El objetivo es aumentar el nivel de generalidad de la metodología de apoyo a la toma de decisiones, tal vez a expensas de una calidad de solución reducida, pero aún aceptable, en comparación con los enfoques metaheurísticos hechos a medida. [7] Para reducir la brecha entre los esquemas hechos a medida y las estrategias basadas en hiperheurísticas, se han propuesto hiperheurísticas paralelas. [8]
El término "hiperheurística" fue acuñado por primera vez en una publicación del año 2000 por Cowling y Soubeiga, quienes lo utilizaron 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 intercambia 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 ampliaron 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 el término) se remonta a principios de la década de 1960 [12] [13] y fue redescubierto y ampliado de forma independiente varias veces durante la década de 1990. [14] [15] [16] En el campo de la programación de trabajos, el trabajo pionero de Fisher y Thompson, [12] [13] planteó la hipótesis y demostró experimentalmente, utilizando el aprendizaje probabilístico, que la combinación de reglas de programación (también conocidas como reglas de prioridad o de despacho) era superior a cualquiera de las reglas tomadas por separado. Aunque el término no se utilizaba entonces, este fue el primer artículo "hiperheurístico". Otra raíz que inspira el concepto de hiperheurística proviene del campo de la inteligencia artificial . Más específicamente, proviene del trabajo sobre sistemas de planificación automatizados y su enfoque final 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 horarios de comunicación por satélite que involucraban una serie de satélites en órbita terrestre y tres estaciones terrestres. El sistema puede caracterizarse como una búsqueda de escalada en el espacio de posibles estrategias de control.
Los enfoques hiperheurísticos hasta ahora se pueden clasificar en dos categorías principales. En la primera clase, capturada por la frase heurísticas para elegir heurísticas , [9] [10] el marco hiperheurístico se proporciona con un conjunto de heurísticas preexistentes, generalmente conocidas para resolver el problema objetivo. La tarea es descubrir una buena secuencia de aplicaciones de estas heurísticas (también conocidas como heurísticas de bajo nivel dentro del dominio de las hiperheurísticas) para resolver eficientemente el problema. En cada etapa de decisión, se selecciona una heurística a través de un componente llamado mecanismo de selección y se aplica a una solución existente. La nueva solución producida a partir de la aplicación de la heurística seleccionada se acepta/rechaza en función de otro componente llamado criterio de aceptación. El rechazo de una solución significa simplemente descartarla, mientras que la aceptación conduce al reemplazo de la solución existente. En la segunda clase, heurísticas para generar heurísticas , la idea clave es "evolucionar nuevas heurísticas haciendo uso de los componentes de las 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 clasificarse aún más 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 instancia ( aprendizaje en línea ) o muchas instancias del problema subyacente estudiado ( aprendizaje fuera de línea ).
Descubra buenas combinaciones de heurísticas de bajo nivel fijas, diseñadas por humanos y bien conocidas.
Generar nuevos métodos heurísticos utilizando componentes básicos de métodos heurísticos previamente existentes.
El aprendizaje se produce mientras el algoritmo resuelve una instancia de un problema, por lo tanto, las propiedades locales dependientes de la tarea pueden ser utilizadas por la estrategia de alto nivel para determinar la heurística de bajo nivel adecuada que se debe aplicar. Algunos ejemplos de enfoques de aprendizaje en línea dentro de las hiperheurísticas son: el uso del aprendizaje de refuerzo para la selección de heurísticas y, en general, el uso de metaheurísticas como estrategias de búsqueda de alto nivel sobre un espacio de búsqueda de heurísticas.
La idea es reunir conocimientos en forma de reglas o programas, a partir de un conjunto de instancias de entrenamiento, que se espera que se generalicen al proceso de resolución de instancias no vistas. Algunos ejemplos de enfoques de aprendizaje fuera de línea dentro de la hiperheurística son: sistemas de clasificación de aprendizaje , razonamiento basado en casos y programación genética .
En 2020 se proporcionó una clasificación ampliada de las hiperheurísticas de selección [20] para proporcionar una categorización más completa de los métodos hiperheurísticos de selección contemporáneos.
Las hiperheurísticas se han aplicado a muchos problemas diferentes. De hecho, una de las motivaciones de las hiperheurísticas es poder operar en distintos 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:
Las hiperheurísticas no son el único enfoque que se está investigando en la búsqueda de metodologías de búsqueda más generales y aplicables. Muchos investigadores de la informática, la inteligencia artificial y la investigación operativa ya han reconocido la necesidad de desarrollar sistemas automatizados para reemplazar el papel de un 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:
Actualmente, existen varios frameworks disponibles en diferentes lenguajes de programación. Entre ellos se incluyen, entre otros:
HyFlex
ParHyFlex
EvoHyp
Matemáticas