BRODERICK CRAWFORD LABRIN
Encontrar la mejor configuración de parámetros para que trabaje adecuadamente un algoritmo, está fuertemente relacionado con la reciente definición de Hiperheurística.
Una definición
Las hiperheurísticas son métodos que apuntan a automatizar el proceso de selección, combinación, generación o adaptación de algoritmos, o sus componentes, para una resolución más eficiente, por ejemplo, de problemas de optimización.
Una heurística se puede definir como una técnica o procedimiento para resolver un problema, y una hiperheurística se define como una "heurística para elegir las heurísticas" o una "heurística que genera heurísticas".
Edmund Kieran Burke propuso una clasificación completa de hiperheurísticas teniendo en cuenta dos dimensiones: la naturaleza de la heurística y la fuente de su retroalimentación para aprender. La primera dimensión, distingue entre dos tipos de hiperheurística: las que seleccionan heurísticas desde un conjunto preexistente y las hiperheurísticas que generan nuevas heurísticas a partir de componentes básicos. En relación a la retroalimentación, identifican tres categorías: aprendizaje en línea, aprendizaje fuera de línea y sin aprendizaje.
La distinción entre los procesos en línea (online) y fuera de línea (offline) se propuso previamente para clasificar la configuración de parámetros en algoritmos evolutivos, diferenciando entre el ajuste de parámetros (offline) y el control de parámetros (online), este último esquema permite la modificación de los parámetros del algoritmo mientras éste se ejecuta, a diferencia del ajuste de parámetros que realiza una asignación fija antes de su ejecución.
El ajuste de parámetros en algoritmos evolutivos ha sido investigado desde hace varios años. Otra comunidad de investigación importante, que se centra en problemas muy relacionados, ha sido establecida bajo el nombre de Búsqueda Reactiva. Roberto Battiti ha centrado su investigación en Metaheurísticas Reactivas.
Aunque estos enfoques se han desarrollado en paralelo por diferentes comunidades, parece que tienen principios y propósitos comunes y responden a necesidades similares. Recientemente, Youssef Hamadi, Eric Monfroy y Frédéric Saubion han propuesto integrar las principales motivaciones y el objetivo de estos enfoques bajo el concepto más general de Búsqueda Autónoma.
Búsqueda autónoma
Durante el año recién pasado, el Proyecto Fondecyt: "Un Sistema de búsqueda autónoma para la configuración de Metaheurísticas de variable continua para la resolución de problemas combinatoriales", ha dado continuidad a una línea de investigación que se comenzó a desarrollar en la Pontificia Universidad Católica de Valparaíso hace más de una década.
Esta línea de investigación inicialmente tuvo el propósito de estudiar y aplicar técnicas clásicas de optimización para la resolución de problemas de Optimización Combinatoria, técnicas de la Investigación de Operaciones y Programación con Restricciones. Pero, la profundización del tema y la propia evolución de las técnicas internacionalmente, han llevado a extender nuestro estudio a Metaheurísticas que se auto-ajusten, es decir, que puedan adecuar su comportamiento y/o componentes durante su ejecución. En general, estas Metaheurísticas son inspiradas en la Naturaleza, comportamiento de insectos, aves u otros organismos.
La Búsqueda Autónoma es un caso particular de sistemas adaptativos capaces de mejorar su rendimiento, ya sea por auto-adaptación o adaptación supervisada. Un sistema de búsqueda autónoma debería poder cambiar sus componentes internos, cuando se expone a fuerzas y oportunidades externas cambiantes, para obtener mejores resultados.
Por ejemplo, un algoritmo de optimización puede mejorar su rendimiento con la adaptación on-line de sus componentes implicados en el proceso de búsqueda: heurísticas, mecanismos de inferencia, operadores de movimientos y otros. Las fuerzas externas corresponden a la información recopilada durante la ejecución del algoritmo: calidad de las soluciones, diversidad de las soluciones, número de veces que se evalúa la función objetivo y otros.
Esta información se extrae directamente del problema o indirectamente observando la eficiencia de los componentes del algoritmo.
