b'\n_START_ARTICLE_\nMetaoptimizaci\xc3\xb3n\n_START_PARAGRAPH_\nEn optimizaci\xc3\xb3n num\xc3\xa9rica, la metaoptimizaci\xc3\xb3n consiste en el uso de un m\xc3\xa9todo de optimizaci\xc3\xb3n para poner a punto otro m\xc3\xa9todo de optimizaci\xc3\xb3n. Se ha reportado su uso, desde fecha tan temprana como 1970, por Mercer y Sampson\xe2\x80\x8b para la b\xc3\xbasqueda de configuraciones \xc3\xb3ptimas de par\xc3\xa1metros en algoritmos gen\xc3\xa9ticos. La metaoptimizaci\xc3\xb3n se conoce tambi\xc3\xa9n en la literatura como: meta-evoluci\xc3\xb3n, super-optimizaci\xc3\xb3n, calibraci\xc3\xb3n autom\xc3\xa1tica de par\xc3\xa1metros, etc._NEWLINE_En general, el problema de encontrar un vector de valores (configuraci\xc3\xb3n v\xc3\xa1lida) para los par\xc3\xa1metros 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\xc3\xb3n de configuraciones, configuraci\xc3\xb3n de par\xc3\xa1metros u optimizaci\xc3\xb3n de configuraciones.\xe2\x80\x8b El rendimiento de un algoritmo puede ser medido seg\xc3\xban los recursos computacionales consumidos (tiempo de ejecuci\xc3\xb3n, cantidad de memoria RAM) o la calidad de la soluci\xc3\xb3n obtenida, por lo cual dicha medida debe ser definida por el investigador al automatizar el proceso de ajuste de par\xc3\xa1metros.\n_START_SECTION_\nMotivaci\xc3\xb3n\n_START_PARAGRAPH_\nLos m\xc3\xa9todos de optimizaci\xc3\xb3n, como los algoritmos gen\xc3\xa9ticos y la evoluci\xc3\xb3n diferencial, tienen diversos par\xc3\xa1metros que gobiernan su comportamiento y eficiencia al optimizar un problema dado. Estos par\xc3\xa1metros deben ser escogidos por el investigador en pos de alcanzar resultados satisfactorios. La selecci\xc3\xb3n de par\xc3\xa1metros a mano, es una tarea laboriosa susceptible a errores humanos en lo referente a: qu\xc3\xa9 aspectos provocan un buen rendimiento._NEWLINE_Los par\xc3\xa1metros de un algoritmo de optimizaci\xc3\xb3n pueden ser variados y el rendimiento del proceso de optimizaci\xc3\xb3n interpretado topol\xc3\xb3gicamente. Esto es computacionalmente factible para algoritmos de pocos par\xc3\xa1metros y problemas de optimizaci\xc3\xb3n que requieren poco tiempo de ejecuci\xc3\xb3n, pero cuando el n\xc3\xbamero de par\xc3\xa1metros aumenta; el tiempo utilizado para calcular tal topolog\xc3\xada (paisaje) de rendimiento, incrementa exponencialmente. Esto se conoce como la maldici\xc3\xb3n de la dimensi\xc3\xb3n para un espacio de b\xc3\xbasqueda conformado por los par\xc3\xa1metros del optimizador(algoritmo). Por ende, se necesita un m\xc3\xa9todo eficiente para explorar dicho espacio de b\xc3\xbasqueda._NEWLINE_Automatizar la selecci\xc3\xb3n de configuraciones adquiere gran importancia en el desarrollo de algoritmos complejos pues el uso de m\xc3\xa9todos de configuraci\xc3\xb3n autom\xc3\xa1ticos disminuye sensiblemente el tiempo dedicado al ajuste de par\xc3\xa1metros y mejora, potencialmente, los resultados obtenidos mediante un proceso manual. De manera similar, influye en la comparaci\xc3\xb3n y evaluaci\xc3\xb3n de algoritmos heur\xc3\xadsticos. Las herramientas autom\xc3\xa1ticas permiten mitigar el problema de realizar comparaciones injustas entre dos m\xc3\xa9todos heur\xc3\xadsticos distintos y determinar, en efecto, cual es superior en lugar de cual fue mejor "ajustado" por sus desarrolladores.\n_START_SECTION_\nM\xc3\xa9todos\n_START_PARAGRAPH_\nUna v\xc3\xada simple para buscar par\xc3\xa1metros adecuados de un algoritmo de optimizaci\xc3\xb3n es emplear otro algoritmo de optimizaci\xc3\xb3n, por encima de este, llamado meta-optimizador. Existen diversas maneras de realizar esto en dependencia del tipo de los par\xc3\xa1metros(reales o discretos) y de la medida de rendimiento utilizada.\n_START_SECTION_\nDise\xc3\xb1o Experimental\n_START_PARAGRAPH_\nVarios trabajos han abordado la selecci\xc3\xb3n de configuraciones apoy\xc3\xa1ndose en el uso de un dise\xc3\xb1o experimental de los par\xc3\xa1metros, ya sea un dise\xc3\xb1o factorial completo o fraccionario de acorde el n\xc3\xbamero de par\xc3\xa1metros._NEWLINE_En Coy et al\xe2\x80\x8b se propone un procedimiento basado en una combinaci\xc3\xb3n de dise\xc3\xb1o experimental(factorial completo o fraccionario) y descenso de gradiente para encontrar configuraciones efectivas en par\xc3\xa1metros de heur\xc3\xadsticas. El proceso se divide en dos etapas: Se busca una buena configuraci\xc3\xb3n para cada instancia - del problema - del conjunto de entrenamiento usando un dise\xc3\xb1o experimental y luego se combinan dichas configuraciones tomando el valor promedio de cada par\xc3\xa1metro entre todas las configuraciones. Este procedimiento solo es aplicable a par\xc3\xa1metros num\xc3\xa9ricos._NEWLINE_Un enfoque similar es empleado por Adenso-D\xc3\xadaz y Laguna\xe2\x80\x8b en el sistema CALIBRA. Este eval\xc3\xbaa cada configuraci\xc3\xb3n con un dise\xc3\xb1o factorial completo de 2 niveles(2 valores por par\xc3\xa1metro). A continuaci\xc3\xb3n, iterativamente, explora el espacio de las configuraciones en busca de regiones prometedoras usando un dise\xc3\xb1o experimental fraccionario, basado en los arreglos ortogonales de Taguchi, donde se eval\xc3\xbaan 9 configuraciones alrededor de la mejor configuraci\xc3\xb3n encontrada hasta el momento. Cuando alcanza un \xc3\xb3ptimo local, refina el espacio de b\xc3\xbasqueda y reinicia el proceso. Este m\xc3\xa9todo tiene dos desventajas: es necesario discretizar los par\xc3\xa1metros continuos y solo puede optimizar un m\xc3\xa1ximo de 5 par\xc3\xa1metros.\n_START_SECTION_\nF-Race\n_START_PARAGRAPH_\nUna propuesta de Birattari, St\xc3\xbctzle, Paquete, y Varrentrapp,\xe2\x80\x8b bajo el nombre de F-Race, describe un procedimiento basado en algoritmos de carrera para configurar par\xc3\xa1metros de metaheur\xc3\xadsticas. F-Race, inspirado en algoritmos de aprendizaje de m\xc3\xa1quinas, propone la evaluaci\xc3\xb3n de un conjunto de configuraciones candidatas donde se descartan las peores tan pronto como se tenga suficiente evidencia estad\xc3\xadstica en su contra._NEWLINE_A partir de un algoritmo A, un conjunto finito de configuraciones iniciales y una distribuci\xc3\xb3n 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\xc3\xa1s prometedoras que tendr\xc3\xa1n m\xc3\xa1s evaluaciones y por ende un mejor estimado de su comportamiento real. En cada iteraci\xc3\xb3n se selecciona una instancia de I, que se eval\xc3\xbaa(ejecuta A sobre dicha instancia) para todas las configuraciones. A continuaci\xc3\xb3n se efect\xc3\xbaa la prueba de Friedman para comprobar si existen diferencias significativas entre las configuraciones. Esta prueba de hip\xc3\xb3tesis, cumple la funci\xc3\xb3n de un "\xc3\xa1rbitro" que, determina cu\xc3\xa1les corredores(configuraciones) no re\xc3\xbanen las condiciones necesarias para alcanzar buenos resultados, esto es, mejorar el rendimiento ofrecido por las configuraciones restantes. Si la hip\xc3\xb3tesis 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\xc3\xb3n en memoria o se alcanza determinado tiempo l\xc3\xadmite._NEWLINE_Debido a que al inicio todas las configuraciones son evaluadas, el uso de, F-Race est\xc3\xa1 limitado a escenarios donde sea factible enumerar todas las posibles configuraciones de par\xc3\xa1metros. La utilizaci\xc3\xb3n de un dise\xc3\xb1o 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\xc3\xa1metros. Birattari et.al\xe2\x80\x8b proponen como alternativa utilizar un muestreo aleatorio, bajo una distribuci\xc3\xb3n uniforme, de los valores de los par\xc3\xa1metros para obtener las configuraciones iniciales y demuestra la superioridad de dicho m\xc3\xa9todo frente al dise\xc3\xb1o factorial completo. El dise\xc3\xb1o de muestreo aleatorio, en el caso de los par\xc3\xa1metros num\xc3\xa9ricos, evita establecer a priori niveles para los par\xc3\xa1metros y posibilita explorar, en promedio, uniformemente el espacio de las configuraciones con un n\xc3\xbamero arbitrario de candidatos. Con el objetivo de centrar la generaci\xc3\xb3n de candidatos alrededor de los m\xc3\xa1s prometedores, se plantea una nueva variante nombrada Iterated F-Race. Esta propone la aplicaci\xc3\xb3n iterada de F-Race de manera que en cada iteraci\xc3\xb3n las configuraciones candidatas sean muestreadas a partir de un subconjunto de las configuraciones "sobrevivientes" en la iteraci\xc3\xb3n anterior._NEWLINE_F-Race y sus variantes han recibido atenci\xc3\xb3n significativa. Ha sido aplicado en el ajuste de par\xc3\xa1metros de metaheur\xc3\xadsticas en la soluci\xc3\xb3n de problemas de horarios de clases, en la industria como parte de un estudio de viabilidad de una herramienta de soluci\xc3\xb3n de problemas de enrutamiento de veh\xc3\xadculos y problemas de planificaci\xc3\xb3n, as\xc3\xad como en el desarrollo de algoritmos, en particular el dise\xc3\xb1o de una metaheur\xc3\xadstica h\xc3\xadbrida para el problema de horarios de cursos universitarios.\xe2\x80\x8b\n_START_SECTION_\nParamILS\n_START_PARAGRAPH_\nHutter, Hoos y Leyton-Brown\xe2\x80\x8b desarrollaron un framework para resolver el problema de selecci\xc3\xb3n de configuraciones. Bajo el nombre de ParamILS, presentan m\xc3\xa9todos para optimizar el rendimiento de un algoritmo objeto, determinista o estoc\xc3\xa1stico, en una cierta clase de instancias de problemas mediante la variaci\xc3\xb3n de un conjunto de par\xc3\xa1metros ordinales y/o categ\xc3\xb3ricos. Dicha propuesta se basa en un algoritmo de b\xc3\xbasqueda local iterada que utiliza una combinaci\xc3\xb3n de configuraciones escogidas, a priori o aleatoriamente, en su inicializaci\xc3\xb3n; un m\xc3\xa9todo iterativo "Primero el mejor" como b\xc3\xbasqueda local subyacente y cierto n\xc3\xbamero de movimientos aleatorios para perturbar la soluci\xc3\xb3n, en pos de evitar m\xc3\xadnimos locales. Siempre acepta configuraciones que mejoren o igualen el rendimiento de la mejor configuraci\xc3\xb3n encontrada y reinicializa la b\xc3\xbasqueda a partir de una configuraci\xc3\xb3n aleatoria bajo cierta probabilidad. El m\xc3\xa9todo de b\xc3\xbasqueda local se "mueve" por el espacio de b\xc3\xbasqueda modificando 1 par\xc3\xa1metro en cada ocasi\xc3\xb3n._NEWLINE_Un aspecto esencial en ParamILS es dado dos configuraciones determinar cual es la de mejor rendimiento. La alternativa m\xc3\xa1s simple da lugar a una variante conocida como BasicILS, donde se compara la medida estad\xc3\xadstica, asociada a cada configuraci\xc3\xb3n, N veces en ambas configuraciones. Este enfoque, de fijar un N a priori, resulta efectivo cuando las instancias utilizadas son muy hetere\xc3\xb3geneas o es posible identificar un "peque\xc3\xb1o" 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\xc3\xb1o de instancias ocasionar\xc3\xada una pobre generalizaci\xc3\xb3n en las instancias no evaluadas mientras que conjuntos de entrenamiento muy grandes, incrementar\xc3\xadan el tiempo de ejecuci\xc3\xb3n del proceso de b\xc3\xbasqueda. En FocusedILS, una variante de ParamILS, se var\xc3\xada N adaptativamente de una configuraci\xc3\xb3n a otra para estimar la calidad de cada una. Se utiliza un concepto de dominancia entre configuraciones y se asegura la realizaci\xc3\xb3n de muchas evaluaciones sobre las configuraciones buenas._NEWLINE_En la primera publicaci\xc3\xb3n sobre ParamILS se reportaron experimentos sobre: el algoritmo SAPS del Problema de satisfacibilidad booleana, el algoritmo de b\xc3\xbasqueda local GLS+ en el problema de Explicaci\xc3\xb3n M\xc3\xa1s Probable en Redes Bayesianas y el algoritmo SAT4J.\xe2\x80\x8b Se compar\xc3\xb3 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\xc3\xb3 ostensiblemente a CALIBRA en dos de ellos y lo mejor\xc3\xb3 en promedio en un tercero. A su vez ParamILS alcanz\xc3\xb3 mejoras significativas sobre las configuraciones por defecto._NEWLINE_ParamILS fue aplicado para mejorar el rendimiento de la herramienta de optimizaci\xc3\xb3n CPLEX sobre una variada selecci\xc3\xb3n de problemas entre ellos: instancias del problema de asignaci\xc3\xb3n de tareas modelado mediante optimizaci\xc3\xb3n cuadr\xc3\xa1tica en enteros con restricciones, instancias del problema de la mochila modelado con programaci\xc3\xb3n lineal en enteros mixta y problemas cuadr\xc3\xa1ticos asociados a la estimaci\xc3\xb3n de par\xc3\xa1metros de energ\xc3\xada en cadenas de ARN.\xe2\x80\x8b Ambas variantes, BasicILS y FocusedILS, encontraron configuraciones mejores que las configuraciones por defecto de CPLEX, en ocasiones en varios \xc3\xb3rdenes de magnitud. Tambi\xc3\xa9n fue incluido en el framework SATenstein para realizar autom\xc3\xa1ticamente el ajuste de par\xc3\xa1metros, en algoritmos de b\xc3\xbasqueda local estoc\xc3\xa1sticos para SAT.\xe2\x80\x8b En particular, FocusedILS se utiliz\xc3\xb3 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\xc3\xadas de problemas.\n_START_SECTION_\nSACO\n_START_PARAGRAPH_\nLa selecci\xc3\xb3n autom\xc3\xa1tica de configuraciones, definida de manera similar en F-Race y ParamILS, es la base de la herramienta SACO propuesta por Vera en 2011.\xe2\x80\x8b SACO presenta una soluci\xc3\xb3n al problema general de ajuste de par\xc3\xa1metros en algoritmos exactos y estoc\xc3\xa1sticos, bas\xc3\xa1ndose en una variante adaptativa de la metaheur\xc3\xadstica poblacional Harmony Search. Esta propuesta, diferencia el tratamiento de los par\xc3\xa1metros continuos y discretos, o sea, los par\xc3\xa1metros continuos no son discretizados lo cual representa una ventaja respecto a F-Race y ParamILS._NEWLINE_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\xc3\xb3n de configuraciones iniciales en Harmony Search y evaluar posteriormente las nuevas configuraciones encontradas durante la ejecuci\xc3\xb3n del algoritmo. Se sigue el marco definido por Harmony Search, esto es, en cada iteraci\xc3\xb3n se "improvisa" una nueva configuraci\xc3\xb3n, par\xc3\xa1metro a par\xc3\xa1metro, a partir de las configuraciones almacenadas en memoria o del dominio de valores del par\xc3\xa1metro seg\xc3\xban cierta probabilidad definida en Harmony Search. Si el valor del par\xc3\xa1metro es seleccionado de la memoria bajo cierta probabilidad es perturbado. En cada iteraci\xc3\xb3n se busca si existe alguna configuraci\xc3\xb3n en la memoria que ofrezca peor rendimiento que la nueva configuraci\xc3\xb3n 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\xc3\xbamero predeterminado de iteraciones y devuelve la mejor configuraci\xc3\xb3n encontrada._NEWLINE_SACO fue utilizado en el ajuste de par\xc3\xa1metros de algoritmos de Visi\xc3\xb3n de Computadoras, en particular para los problemas de segmentaci\xc3\xb3n de im\xc3\xa1genes en regiones de texturas diferentes y seguimiento de la posici\xc3\xb3n de un brazo en secuencias de video, obteniendo resultados satisfactorios.\xe2\x80\x8b\n_START_SECTION_\nOtros\n_START_PARAGRAPH_\nLa Meta-optimizaci\xc3\xb3n de par\xc3\xa1metros en algoritmos gen\xc3\xa9ticos fue realizada por Grefenstette\xe2\x80\x8b y Keane,\xe2\x80\x8b entre otros, y se han reportado experimentos, por B\xc3\xa4ck,\xe2\x80\x8b donde se optimizaron los par\xc3\xa1metros y los operadores gen\xc3\xa9ticos. Krus y Andersson\xe2\x80\x8b llevaron a cabo meta-optimizaci\xc3\xb3n en el algoritmo COMPLEX-RF e introdujeron el \xc3\xadndice de rendimiento de optimizaci\xc3\xb3n basado en la Teor\xc3\xada de la Informaci\xc3\xb3n. La metaoptimizaci\xc3\xb3n en optimizaci\xc3\xb3n por enjambre de part\xc3\xadculas (PSO) ha sido realizada por Meissner et al.\xe2\x80\x8b as\xc3\xad como por Pedersen y Chipperfield,\xe2\x80\x8b quien adem\xc3\xa1s ha trabajado en la  meta-optimizaci\xc3\xb3n de evoluci\xc3\xb3n diferencial. Tambi\xc3\xa9n han sido utilizados modelos estad\xc3\xadsticos para revelar m\xc3\xa1s informaci\xc3\xb3n sobre la relaci\xc3\xb3n establecida entre la selecci\xc3\xb3n de par\xc3\xa1metros y el rendimiento del proceso de optimizaci\xc3\xb3n, por ejemplo en Francois y Lavergne\xe2\x80\x8b y Nannen y Eiben.\xe2\x80\x8b Por su parte, Smit y Eiben realizaron una comparaci\xc3\xb3n de varias t\xc3\xa9cnicas de meta-optimizaci\xc3\xb3n.\xe2\x80\x8b'