Metaoptimización

En optimización numérica, la metaoptimización consiste en el uso de un método de optimización para poner a punto otro método de optimización. Se ha reportado su uso, desde fecha tan temprana como 1970, por Mercer y Sampson​ para la búsqueda de configuraciones óptimas de parámetros en algoritmos genéticos. La metaoptimización se conoce también en la literatura como: meta-evolución, super-optimización, calibración automática de parámetros, etc. En general, el problema de encontrar un vector de valores (configuración válida) para los parámetros de un algoritmo A, de manera que al aplicar A sobre una instancia del problema P se obtenga el mejor rendimiento, se conoce como: selección de configuraciones, configuración de parámetros u optimización de configuraciones.​ El rendimiento de un algoritmo puede ser medido según los recursos computacionales consumidos (tiempo de ejecución, cantidad de memoria RAM) o la calidad de la solución obtenida, por lo cual dicha medida debe ser definida por el investigador al automatizar el proceso de ajuste de parámetros.

Motivación

Topología de rendimiento para Evolución diferencial.

Los métodos de optimización, como los algoritmos genéticos y la evolución diferencial, tienen diversos parámetros que gobiernan su comportamiento y eficiencia al optimizar un problema dado. Estos parámetros deben ser escogidos por el investigador en pos de alcanzar resultados satisfactorios. La selección de parámetros a mano, es una tarea laboriosa susceptible a errores humanos en lo referente a: qué aspectos provocan un buen rendimiento.

Los parámetros de un algoritmo de optimización pueden ser variados y el rendimiento del proceso de optimización interpretado topológicamente. Esto es computacionalmente factible para algoritmos de pocos parámetros y problemas de optimización que requieren poco tiempo de ejecución, pero cuando el número de parámetros aumenta; el tiempo utilizado para calcular tal topología (paisaje) de rendimiento, incrementa exponencialmente. Esto se conoce como la maldición de la dimensión para un espacio de búsqueda conformado por los parámetros del optimizador(algoritmo). Por ende, se necesita un método eficiente para explorar dicho espacio de búsqueda.

Automatizar la selección de configuraciones adquiere gran importancia en el desarrollo de algoritmos complejos pues el uso de métodos de configuración automáticos disminuye sensiblemente el tiempo dedicado al ajuste de parámetros y mejora, potencialmente, los resultados obtenidos mediante un proceso manual. De manera similar, influye en la comparación y evaluación de algoritmos heurísticos. Las herramientas automáticas permiten mitigar el problema de realizar comparaciones injustas entre dos métodos heurísticos distintos y determinar, en efecto, cual es superior en lugar de cual fue mejor "ajustado" por sus desarrolladores.

Métodos

Meta-optimización en Evolución diferencial.

Una vía simple para buscar parámetros adecuados de un algoritmo de optimización es emplear otro algoritmo de optimización, por encima de este, llamado meta-optimizador. Existen diversas maneras de realizar esto en dependencia del tipo de los parámetros(reales o discretos) y de la medida de rendimiento utilizada.

Diseño Experimental

Varios trabajos han abordado la selección de configuraciones apoyándose en el uso de un diseño experimental de los parámetros, ya sea un diseño factorial completo o fraccionario de acorde el número de parámetros.

En Coy et al​ se propone un procedimiento basado en una combinación de diseño experimental(factorial completo o fraccionario) y descenso de gradiente para encontrar configuraciones efectivas en parámetros de heurísticas. El proceso se divide en dos etapas: Se busca una buena configuración para cada instancia - del problema - del conjunto de entrenamiento usando un diseño experimental y luego se combinan dichas configuraciones tomando el valor promedio de cada parámetro entre todas las configuraciones. Este procedimiento solo es aplicable a parámetros numéricos.

Un enfoque similar es empleado por Adenso-Díaz y Laguna​ en el sistema CALIBRA. Este evalúa cada configuración con un diseño factorial completo de 2 niveles(2 valores por parámetro). A continuación, iterativamente, explora el espacio de las configuraciones en busca de regiones prometedoras usando un diseño experimental fraccionario, basado en los arreglos ortogonales de Taguchi, donde se evalúan 9 configuraciones alrededor de la mejor configuración encontrada hasta el momento. Cuando alcanza un óptimo local, refina el espacio de búsqueda y reinicia el proceso. Este método tiene dos desventajas: es necesario discretizar los parámetros continuos y solo puede optimizar un máximo de 5 parámetros.

F-Race

Una propuesta de Birattari, Stützle, Paquete, y Varrentrapp,​ bajo el nombre de F-Race, describe un procedimiento basado en algoritmos de carrera para configurar parámetros de metaheurísticas. F-Race, inspirado en algoritmos de aprendizaje de máquinas, propone la evaluación de un conjunto de configuraciones candidatas donde se descartan las peores tan pronto como se tenga suficiente evidencia estadística en su contra. A partir de un algoritmo A, un conjunto finito de configuraciones iniciales y una distribución I de instancias del problema se realiza un proceso iterativo. Dicho proceso iterativo puede verse como una "carrera" donde las peores configuraciones abandonan la competencia a medida que esta avanza, favoreciendo a las configuraciones más prometedoras que tendrán más evaluaciones y por ende un mejor estimado de su comportamiento real. En cada iteración se selecciona una instancia de I, que se evalúa(ejecuta A sobre dicha instancia) para todas las configuraciones. A continuación se efectúa la prueba de Friedman para comprobar si existen diferencias significativas entre las configuraciones. Esta prueba de hipótesis, cumple la función de un "árbitro" que, determina cuáles corredores(configuraciones) no reúnen las condiciones necesarias para alcanzar buenos resultados, esto es, mejorar el rendimiento ofrecido por las configuraciones restantes. Si la hipótesis nula es rechazada, se realizan comparaciones dos a dos entre todas las configuraciones y la de mejor rendimiento, eliminando aquellas que son significativamente peor. Este proceso continua hasta que queda una sola configuración en memoria o se alcanza determinado tiempo límite.

Debido a que al inicio todas las configuraciones son evaluadas, el uso de, F-Race está limitado a escenarios donde sea factible enumerar todas las posibles configuraciones de parámetros. La utilización de un diseño factorial completo, sobre el espacio de las configuraciones, para escoger las configuraciones iniciales presupone una desventaja en F-Race pues el conjunto de configuraciones candidatas crece exponencialmente respecto a la cantidad de parámetros. Birattari et.al​ proponen como alternativa utilizar un muestreo aleatorio, bajo una distribución uniforme, de los valores de los parámetros para obtener las configuraciones iniciales y demuestra la superioridad de dicho método frente al diseño factorial completo. El diseño de muestreo aleatorio, en el caso de los parámetros numéricos, evita establecer a priori niveles para los parámetros y posibilita explorar, en promedio, uniformemente el espacio de las configuraciones con un número arbitrario de candidatos. Con el objetivo de centrar la generación de candidatos alrededor de los más prometedores, se plantea una nueva variante nombrada Iterated F-Race. Esta propone la aplicación iterada de F-Race de manera que en cada iteración las configuraciones candidatas sean muestreadas a partir de un subconjunto de las configuraciones "sobrevivientes" en la iteración anterior.

F-Race y sus variantes han recibido atención significativa. Ha sido aplicado en el ajuste de parámetros de metaheurísticas en la solución de problemas de horarios de clases, en la industria como parte de un estudio de viabilidad de una herramienta de solución de problemas de enrutamiento de vehículos y problemas de planificación, así como en el desarrollo de algoritmos, en particular el diseño de una metaheurística híbrida para el problema de horarios de cursos universitarios.​

ParamILS

Hutter, Hoos y Leyton-Brown​ desarrollaron un framework para resolver el problema de selección de configuraciones. Bajo el nombre de ParamILS, presentan métodos para optimizar el rendimiento de un algoritmo objeto, determinista o estocástico, en una cierta clase de instancias de problemas mediante la variación de un conjunto de parámetros ordinales y/o categóricos. Dicha propuesta se basa en un algoritmo de búsqueda local iterada que utiliza una combinación de configuraciones escogidas, a priori o aleatoriamente, en su inicialización; un método iterativo "Primero el mejor" como búsqueda local subyacente y cierto número de movimientos aleatorios para perturbar la solución, en pos de evitar mínimos locales. Siempre acepta configuraciones que mejoren o igualen el rendimiento de la mejor configuración encontrada y reinicializa la búsqueda a partir de una configuración aleatoria bajo cierta probabilidad. El método de búsqueda local se "mueve" por el espacio de búsqueda modificando 1 parámetro en cada ocasión.

Un aspecto esencial en ParamILS es dado dos configuraciones determinar cual es la de mejor rendimiento. La alternativa más simple da lugar a una variante conocida como BasicILS, donde se compara la medida estadística, asociada a cada configuración, N veces en ambas configuraciones. Este enfoque, de fijar un N a priori, resulta efectivo cuando las instancias utilizadas son muy hetereógeneas o es posible identificar un "pequeño" subconjunto de instancias que sea representativo pues permite obtener buenas configuraciones con poco esfuerzo computacional. Escoger un N apropiado es, por lo general, un problema complicado ya que un conjunto muy pequeño de instancias ocasionaría una pobre generalización en las instancias no evaluadas mientras que conjuntos de entrenamiento muy grandes, incrementarían el tiempo de ejecución del proceso de búsqueda. En FocusedILS, una variante de ParamILS, se varía N adaptativamente de una configuración a otra para estimar la calidad de cada una. Se utiliza un concepto de dominancia entre configuraciones y se asegura la realización de muchas evaluaciones sobre las configuraciones buenas.

En la primera publicación sobre ParamILS se reportaron experimentos sobre: el algoritmo SAPS del Problema de satisfacibilidad booleana, el algoritmo de búsqueda local GLS+ en el problema de Explicación Más Probable en Redes Bayesianas y el algoritmo SAT4J.​ Se comparó el rendimiento de las configuraciones por defecto de cada algoritmo, las obtenidas por la herramienta CALIBRA y las dadas por ParamILS en sus dos variantes. Entre los cuatro escenarios estudiados, FocusedILS superó ostensiblemente a CALIBRA en dos de ellos y lo mejoró en promedio en un tercero. A su vez ParamILS alcanzó mejoras significativas sobre las configuraciones por defecto. ParamILS fue aplicado para mejorar el rendimiento de la herramienta de optimización CPLEX sobre una variada selección de problemas entre ellos: instancias del problema de asignación de tareas modelado mediante optimización cuadrática en enteros con restricciones, instancias del problema de la mochila modelado con programación lineal en enteros mixta y problemas cuadráticos asociados a la estimación de parámetros de energía en cadenas de ARN.​ Ambas variantes, BasicILS y FocusedILS, encontraron configuraciones mejores que las configuraciones por defecto de CPLEX, en ocasiones en varios órdenes de magnitud. También fue incluido en el framework SATenstein para realizar automáticamente el ajuste de parámetros, en algoritmos de búsqueda local estocásticos para SAT.​ En particular, FocusedILS se utilizó para configurar SATenstein ante 6 distribuciones distintas de problemas, obteniendo mejores resultados que 11 algoritmos del estado del arte de SAT, en las 6 categorías de problemas.

SACO

La selección automática de configuraciones, definida de manera similar en F-Race y ParamILS, es la base de la herramienta SACO propuesta por Vera en 2011.​ SACO presenta una solución al problema general de ajuste de parámetros en algoritmos exactos y estocásticos, basándose en una variante adaptativa de la metaheurística poblacional Harmony Search. Esta propuesta, diferencia el tratamiento de los parámetros continuos y discretos, o sea, los parámetros continuos no son discretizados lo cual representa una ventaja respecto a F-Race y ParamILS. En SACO se utiliza un conjunto de instancias, que se asume finito y representativo de las posible instancias del problema, como conjunto de entrenamiento para inicializar la población de configuraciones iniciales en Harmony Search y evaluar posteriormente las nuevas configuraciones encontradas durante la ejecución del algoritmo. Se sigue el marco definido por Harmony Search, esto es, en cada iteración se "improvisa" una nueva configuración, parámetro a parámetro, a partir de las configuraciones almacenadas en memoria o del dominio de valores del parámetro según cierta probabilidad definida en Harmony Search. Si el valor del parámetro es seleccionado de la memoria bajo cierta probabilidad es perturbado. En cada iteración se busca si existe alguna configuración en la memoria que ofrezca peor rendimiento que la nueva configuración construida, y en caso afirmativo se reemplaza por esta. Para ello se define un criterio de dominancia entre configuraciones. El algoritmo termina al alcanzar un número predeterminado de iteraciones y devuelve la mejor configuración encontrada. SACO fue utilizado en el ajuste de parámetros de algoritmos de Visión de Computadoras, en particular para los problemas de segmentación de imágenes en regiones de texturas diferentes y seguimiento de la posición de un brazo en secuencias de video, obteniendo resultados satisfactorios.​

Otros

La Meta-optimización de parámetros en algoritmos genéticos fue realizada por Grefenstette​ y Keane,​ entre otros, y se han reportado experimentos, por Bäck,​ donde se optimizaron los parámetros y los operadores genéticos. Krus y Andersson​ llevaron a cabo meta-optimización en el algoritmo COMPLEX-RF e introdujeron el índice de rendimiento de optimización basado en la Teoría de la Información. La metaoptimización en optimización por enjambre de partículas (PSO) ha sido realizada por Meissner et al.​ así como por Pedersen y Chipperfield,​ quien además ha trabajado en la meta-optimización de evolución diferencial. También han sido utilizados modelos estadísticos para revelar más información sobre la relación establecida entre la selección de parámetros y el rendimiento del proceso de optimización, por ejemplo en Francois y Lavergne​ y Nannen y Eiben.​ Por su parte, Smit y Eiben realizaron una comparación de varias técnicas de meta-optimización.​

Referencias

• Datos: Q6822261