¿Qué son las hiperheurísticas?

Quería saber cuáles son las diferencias entre la hiperheurística y la metaheurística, y cuáles son sus principales aplicaciones. ¿Qué problemas son adecuados para ser resueltos por Hyper-heuristics?

TL: DR : Las hiperheurísticas son metaheurísticas, adecuadas para resolver el mismo tipo de problemas de optimización, pero (en principio) ofrecen un enfoque de "creación rápida de prototipos" para profesionales no expertos. En la práctica, existen problemas con el enfoque predominante, que motivan una perspectiva emergente sobre la hiperheurística de la 'caja blanca' .

Con más detalle:

Las metaheurísticas son métodos para buscar en un espacio intratablemente grande de posibles soluciones para encontrar una solución de "alta calidad". Las metaheurísticas populares incluyen recocido simulado, búsqueda tabú, algoritmos genéticos, etc.

La diferencia esencial entre metaheurística e hiperheurística es la adición de un nivel de búsqueda indirecta: informalmente, la hiperheurística se puede describir como 'heurística para buscar el espacio de la heurística'. Por lo tanto, se puede usar cualquier metaheurístico como hiperheurístico, siempre que la naturaleza del 'espacio de heurística' a buscar se defina adecuadamente.

El área de aplicación de la hiperheurística es, por lo tanto, la misma que la metaheurística. Su aplicabilidad (en relación con la metaheurística) es como una 'herramienta de creación rápida de prototipos': la motivación original era permitir a los profesionales no expertos aplicar la metaheurística a su problema específico de optimización (por ejemplo, "Vendedor-viajero (TSP) más ventanas de tiempo más bin- embalaje ") sin requerir experiencia en el dominio del problema altamente específico. La idea era que esto podría hacerse mediante:

1. Permitir a los profesionales implementar solo heurísticas muy simples (efectivamente, aleatorizadas) para transformar soluciones potenciales. Por ejemplo, para el TSP: "intercambiar dos ciudades aleatorias" en lugar de (por ejemplo) la heurística más compleja de Lin-Kernighan .
2. Logre resultados efectivos (a pesar de utilizar estas heurísticas simples) combinándolas / secuenciando de manera inteligente, generalmente empleando alguna forma de mecanismo de aprendizaje.

La hiperheurística se puede describir como 'selectiva' o 'generativa' dependiendo de si las heurísticas son (respectivamente) secuenciadas o combinadas. Por lo tanto, la hiperheurística generativa a menudo usa métodos como la Programación Genética para combinar heurísticas primitivas y, por lo tanto, el profesional generalmente las personaliza para resolver un problema específico. Por ejemplo, el documento original sobre hiperheurística generativa utilizó un sistema de clasificación de aprendizaje para combinar la heurística para el empaquetado de contenedores. Debido a que los enfoques generativos son específicos del problema, los comentarios a continuación no se aplican a ellos.

Por el contrario, el motivador original para la hiperheurística selectiva fue que los investigadores podrían crear un solucionador hiperheurístico que probablemente funcionaría bien en un dominio de problema invisible, utilizando solo heurísticas aleatorias simples.

La forma en que esto se ha implementado tradicionalmente fue a través de la introducción de la 'barrera del dominio hiperheurístico' (véase la figura a continuación), mediante la cual se afirma que la generalidad a través de los dominios problemáticos es posible al evitar que el solucionador tenga conocimiento del dominio en el que Está funcionando. En cambio, resolvería el problema operando solo en índices enteros opacos en una lista de heurísticas disponibles (por ejemplo, en la forma del 'Problema de Bandidos Multi-armados' ).

En la práctica, este enfoque de "dominio ciego" no ha dado como resultado soluciones de calidad suficiente. Para lograr resultados en cualquier lugar comparable a la metaheurística específica del problema, los investigadores hiperheurísticos han tenido que implementar heurísticas complejas específicas del problema, fracasando en el objetivo de la creación rápida de prototipos.

En principio, todavía es posible crear un solucionador selectivo hiperheurístico que sea capaz de generalizar a nuevos dominios problemáticos, pero esto se ha hecho más difícil ya que la noción anterior de barrera de dominio significa que solo un conjunto de características muy limitado está disponible para el cruce -dominio de aprendizaje (por ejemplo, como lo ejemplifica un popular marco hiperheurístico selectivo ).

Una perspectiva de investigación más reciente hacia la hiperheurística de la 'caja blanca' aboga por un enfoque declarativo y rico en características para describir dominios problemáticos. Este enfoque tiene una serie de ventajas reclamadas:

1. Los profesionales ahora ya no necesitan implementar la heurística, sino que simplemente especifican el dominio del problema.
2. Elimina la barrera del dominio, colocando a las hiperheurísticas en el mismo estado 'informado' sobre el problema que la metaheurística específica del problema.
3. Con una descripción del problema de la caja blanca, el infame teorema 'No Free Lunch' (que esencialmente establece que, considerado en el espacio de todos los problemas de la caja negra , el recocido simulado con un programa de recocido infinito es, en promedio, tan bueno como cualquier otro enfoque) no ya se aplica

DESCARGO DE RESPONSABILIDAD: Trabajo en esta área de investigación y, por lo tanto, es imposible eliminar todo sesgo personal de la respuesta.