Hiperheurística

Una hiper-heurí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 seleccionar, combinar, generar o adaptar varias heurísticas más simples (o componentes de tales heurísticas) para resolver eficientemente 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 un solo problema.^[1]^[2]^[3]

Puede haber múltiples heurísticas que se pueden elegir para resolver un problema, y cada heurística tiene su propia fuerza y debilidad. La idea es diseñar automáticamente algoritmos combinando la fuerza y compensando la debilidad de las heurísticas conocidas.^[4] En un marco hiperheurístico típico existe una metodología de alto nivel y un conjunto de heurísticas de bajo nivel (heurísticas constructivas o perturbativas). Dada una instancia de problema, el método de alto nivel selecciona la heurística de bajo nivel que debe aplicarse en un momento dado, dependiendo del estado del problema actual o de la etapa de búsqueda.^[2]

Hiper-heurística contra meta-heurística

La diferencia fundamental entre las metaheurísticas y las hiperheurísticas es que la mayoría de las implementaciones 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 se utiliza hiper-heurística, estamos tratando de encontrar el método correcto o secuencia de heurísticas en una situación dada en lugar de tratar de resolver un problema directamente. Además, estamos buscando una metodología generalmente aplicable en lugar de resolver una sola instancia problemática.

El objetivo de las hiper-heurísticas es ser métodos genéricos, los cuales deben producir soluciones de calidad aceptable, basadas en un conjunto de heurísticas de bajo nivel fáciles de implementar.

Motivación

A pesar de los progresos significativos en la construcción de metodologías de búsqueda para una amplia variedad de áreas de aplicación hasta el momento, tales enfoques todavía requieren especialistas para integrar sus conocimientos en un determinado dominio de problema. Muchos investigadores de la ciencia de la computación, la inteligencia artificial y la investigación operacional 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 la heurística requiere la incorporación de mecanismos de aprendizaje automático en algoritmos para guiar la búsqueda de forma adaptativa. 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, y (idealmente) sería lo suficientemente robusto como para manejar efectivamente un rango de instancias problemáticas de una variedad de dominios. El objetivo es elevar el nivel de generalidad de la metodología de apoyo a la toma de decisiones tal vez a expensas de la calidad de la solución reducida -aunque aceptable- en comparación con los enfoques metaheurísticos hechos a la medida.^[5] Con el fin de reducir la brecha entre los esquemas a medida y las estrategias hiperheurísticas, se han propuesto hiperheurísticas paralelas.^[6]

Orígenes

El término "hiperheurística" fue acuñado por primera vez en una publicación de 2000 de Cowling y Soubeiga, que la utilizó para describir la idea de "heurística para elegir la heurística".^[7] Utilizaron un enfoque de aprendizaje de la "función de elección" que intercambia la explotación y la exploración al elegir la siguiente heurística a utilizar.^[8] Posteriormente Cowling, Soubeiga, Kendall, Han, Ross y otros autores investigaron y ampliaron esta idea en áreas tales como algoritmos evolutivos y heurísticas patológicas de bajo nivel. El primer artículo de la revista para utilizar el término apareció en 2003.^[6] El origen de la idea (aunque no el término) se remonta a principios de 1960^[9]^[10] y fue descubierto y ampliado de forma independiente varias veces durante los años 90.Error en la cita: Error en la cita: existe un código de apertura <ref> sin su código de cierre </ref>^[11]^[12] En el ámbito de Job Shop Scheduling, el trabajo pionero de Fisher y Thompson,^[9]^[10] planteó la hipótesis y probó experimentalmente, utilizando el aprendizaje probabilístico, que la combinación de reglas de programación (también conocida como prioridad o reglas de despacho) era superior a cualquiera de las normas adoptadas por separado. Aunque el término no estaba entonces en uso, 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 eventual enfoque hacia el problema del conocimiento del control del aprendizaje. El llamado sistema COMPOSER, desarrollado por Gratch et al,^[13]^[14] se utilizó para controlar los horarios de comunicaciones por satélite que implican una serie de satélites en órbita terrestre y tres estaciones terrestres. El sistema se puede caracterizar como una búsqueda de escalada en el espacio de posibles estrategias de control.

Clasificación de los enfoques

Hasta ahora, los enfoques hiper-heurísticos pueden clasificarse en dos categorías principales. En la primera clase, capturada por la heurística frase para elegir la heurística,^[7]^[8] el marco hiper-heurístico se proporciona por un conjunto de heurísticas preexistentes, generalmente ampliamente conocidos para resolver el problema objetivo. La tarea es descubrir una buena secuencia de aplicaciones de estas heurísticas para resolver eficazmente el problema. En la segunda clase, la heurística para generar heurística, la idea clave es "desarrollar nuevas heurísticas haciendo uso de los componentes de las heurísticas conocidas".^[15] El proceso requiere, como en la primera clase de hiperheurísticas, la selección de Un conjunto adecuado de heurísticas conocidas por ser útiles para resolver el problema objetivo. Sin embargo, en lugar de suministrarlas directamente al marco, las heurísticas se descomponen primero en sus componentes básicos.

Estos dos tipos amplios principales se pueden categorizar más adelante según si se basan en la búsqueda constructiva o perturbativa. Una clasificación ortogonal adicional de hiperheurísticas considera que la fuente 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).

Metodologías para elegir heurística

Descubra buenas combinaciones de heurísticas de bajo nivel fijas, diseñadas por humanos y bien conocidas.

Basado en la heurística constructiva
Basado en la heurística perturbativa

Metodologías para generar heurística

Generar nuevos métodos heurísticos utilizando componentes básicos de métodos heurísticos previamente existentes.

Basado en componentes básicos de heurística constructiva
Basado en componentes básicos de heurística perturbativa

Aprendizaje en línea hyperheurística

El aprendizaje tiene lugar mientras el algoritmo está resolviendo 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 apropiada que se aplicará. Ejemplos de enfoques de aprendizaje en línea dentro de la hiperheurística son: el uso del aprendizaje de refuerzo para la selección heurística 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.

Hiper-heurística de aprendizaje fuera de línea

La idea es recopilar conocimientos en forma de reglas o programas, a partir de un conjunto de instancias de formación, que se espera generalizar al proceso de resolver instancias invisibles. Ejemplos de enfoques de aprendizaje fuera de línea en las hiperheurísticas son: aprendizaje de sistemas clasificadores, razonamiento de base de casos y programación genética.

Aplicaciones

Las hiper-heurísticas se han aplicado en muchos problemas diferentes. De hecho, una de las motivaciones de la hiperheurística es poder operar a través de 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 embalaje
Problema de satisfacción booleana
Horarios educativos
Programación de taller
Resolución de problemas multiobjetivo y asignación de espacio
Lista de enfermeras
Programación de personal
Problema del vendedor ambulante
Problema de enrutamiento del vehículo

Áreas relacionadas

Las hiper-heurí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 la informática, la inteligencia artificial y la investigación operacional 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:

Adaptación y autoadaptación de los parámetros del algoritmo
Búsqueda adaptable de un gran vecindario
Configuración del algoritmo
Control de algoritmos
Búsqueda autónoma
Programación genética
Codificaciones indirectas en algoritmos evolutivos
Búsqueda de vecindario variable
Búsqueda reactiva

Véase también

Heurística constructiva
La meta-optimización está estrechamente relacionada con la hiper-heurística.
Programación genética
Algoritmos evolutivos
Búsqueda local (optimización)
aprendizaje automático
Metaheurística
optimización por Enjambre de partículas
Búsqueda reactiva

Notas y referencias

↑ E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg, Hyper-heuristics: An emerging direction in modern search technology, Handbook of Metaheuristics (F. Glover and G. Kochenberger, eds.), Kluwer, 2003, pp. 457–474.
↑ ^a ^b P. Ross, Hyper-heuristics, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (E. K. Burke and G. Kendall, eds.), Springer, 2005, pp. 529-556.
↑ E. Ozcan, B. Bilgin, E. E. Korkmaz, A Comprehensive Analysis of Hyper-heuristics, Intelligent Data Analysis, 12:1, pp. 3-23, 2008.
↑ C. Segura, G. Miranda and C. León: Parallel hyperheuristics for the frequency assignment problem Special issue on nature inspired cooperative strategies for optimization, In Memetic Computing, Special issue on nature inspired cooperative strategies for optimization, (doi 10.1007/s12293-010-0044-5 [1]), 2010.
↑ Cowling P. and Soubeiga E. Neighborhood Structures for Personnel Scheduling: A Summit Meeting Scheduling Problem (abstract), in proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, Burke E.K. and Erben W. (eds), 16-18 Aug 2000, Constance, Germany
↑ ^a ^b Burke E. K., Kendall G., and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics, 9(6):451-470. (doi 10.1023/B:HEUR.0000012446.94732.b6 [2])
↑ ^a ^b Cowling P. and Soubeiga E. Neighborhood Structures for Personnel Scheduling: A Summit Meeting Scheduling Problem (abstract), in proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, Burke E.K. and Erben W. (eds), 16-18 Aug 2000, Constance, Germany
↑ ^a ^b Cowling P., Kendall G. and Soubeiga E., A Hyperheuristic Approach to Scheduling a Sales Summit, 2001, Lecture Notes in Computer Science 2079, Springer-Verlag, pp. 176–190, 2001, ISBN 3540424210, (doi 10.1007/3-540-44629-X
↑ ^a ^b H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, Factory Scheduling Conference (Carnegie Institute of Technology), 1961.
↑ ^a ^b * H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules,Industrial Scheduling (New Jersey) (J. F. Muth and G. L. Thompson, eds.), Prentice-Hall, Inc, 1963, pp. 225–251.
↑ H. L. Fang, P. Ross, and D. Corne, A promising genetic algorithm approach to job shop scheduling, rescheduling, and open-shop scheduling problems, Fifth International Conference on Genetic Algorithms (San Mateo) (S. Forrest, ed.), Morgan Kaufmann, 1993, pp. 375–382.
↑ U. Dorndorf and E. Pesch, Evolution based learning in a job shop scheduling environment, Computers and Operations Research, 22(1), 1995, 25–40.
↑ J. Gratch, S. Chien, and G. DeJong, Learning search control knowledge for deep space network scheduling, Proceedings of the Tenth International Conference on Machine Learning (Amherst, MA), 1993, pp. 135–142.
↑ J. Gratch and S. Chien, Adaptive problem-solving for large-scale scheduling problems: a case study, Journal of Artificial Intelligence Research, 4, 1996, 365–396.
↑ M. Bader-El-Den and R. Poli, Generating sat local-search heuristics using a GP hyper-heuristic framework, Artificial Evolution, 8th International Conference, Evolution Artificielle, EA 2007, Tours, France, October 29–31, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4926 Springer, 2008, pp. 37-49.

Enlaces externos

Hiper-heurística bibliografía