UEGO

UEGO , siglas de “Universal Evolutionary Global Optimizer”,​​ es un algoritmo metaheurístico de optimización global multimodal basado en poblaciones. Es por tanto aplicable a problemas con múltiples óptimos locales. Aspira a ser adaptable a diferentes problemas así como tener una estructura modular y fácilmente paralelizable.​​​​​​

Fundamentos

UEGO surge a partir del algoritmo GAS (“Genetic Algorithm Species based”),​ tratando de mejorar la precisión de sus resultados así como su paralelismo de cara a una implementación de computación de altas prestaciones. Este algoritmo es especialmente apto para resolver problemas de optimización multimodal (con múltiples óptimos locales), pudiendo además descubrir su estructura.

El algoritmo plantea una búsqueda, en distintos niveles de profundidad como se detallará posteriormente, basada en una población dinámica de especies que hacen referencia a distintas regiones del espacio de búsqueda general. Las especies han de verse por consiguiente como “ventanas” de exploración sobre el espacio de búsqueda global​​ sobre las que se lanzarán procesos de optimización local. Estas especies son identificables por un único individuo de referencia o centro (el de mejor valor encontrado en la zona), su valoración de aptitud y un cierto radio (véase la figura 1). Este individuo es el centro de la especie y su radio determina el área de influencia, es decir, un subdominio del espacio de búsqueda dónde se ubican individuos considerados similares.

1.-Representación del concepto de especie de UEGO.

Es importante resaltar que, sobre la base de lo expuesto, se hace necesario contar con una medida de distancia en el espacio de búsqueda. De esta forma, en problemas discretos combinatorios se puede emplear la distancia de Hamming. Por el contrario, para problemas reales se podría emplear la distancia euclídea.​

Además de mantener la búsqueda en múltiples regiones del espacio de soluciones de forma simultánea, UEGO se caracteriza por incluir también un mecanismo de “enfriamiento” como la conocida técnica de "Enfriamiento Simulado". Este mecanismo, que se aplica mediante la creación progresiva de nuevas especies con un menor radio de influencia, permite dirigir la exploración hacia regiones cada vez más pequeñas del espacio de búsqueda . Este enfoque es especialmente eficaz para problemas de tipo radio niche en las que hay varios óptimos locales distribuidos de forma dispar en el espacio de búsqueda. En ese tipo de funciones no se puede determinar el radio niche adecuadamente ya que si es demasiado pequeño la búsqueda no resulta efectiva, y si es demasiado grande aquellos óptimos locales cercanos entre sí no se pueden distinguir.​

El radio de las especies de los distintos niveles no se va simplemente reduciendo de forma arbitraria para aplicar el efecto de enfriamiento. Por el contrario, parte de un radio inicial (con el que se trabaja en el primer nivel de búsqueda) y se reduce hasta un mínimo siguiendo una progresión exponencial. El radio del primer nivel, el que tiene la primera especie creada, es igual al diámetro del dominio de la búsqueda. Esta primera especie se mantendrá durante todo el proceso garantizando así que ninguna región quede inaccesible durante la búsqueda. En lo que respecta al radio mínimo, este se trata de un parámetro a indicar por el usuario. En la figura 2 se incluye una representación ilustrativa de la evolución de los radios según los niveles.

2.- Progresión de los radios según el nivel de búsqueda.

Es importante destacar además que una cierta especie no es estática, sino que puede moverse por el espacio conforme la búsqueda avanza. Este desplazamiento tendrá lugar cuando el valor de aptitud de una nueva solución encontrada en la zona sea mejor que el del centro empleado como referencia. En este caso, el nuevo punto se convertiría en el centro y la ventana definida quedaría entonces desplazada en su dirección (véase la figura 3).

3. Representación del desplazamiento de una especie.

Sobre la base de lo expuesto se puede llegar a la conclusión de que UEGO realiza una búsqueda global basada en especies que, a su vez, son optimizadas internamente. Esto permite descomponerlo en dos componentes fundamentales asociados:

• El primero se encarga de la gestión general de las distintas especies y permite darle carácter global a la solución hallada al cubrirse todo el espacio de búsqueda. Estas especies son entidades dinámicas que en el proceso de búsqueda pueden crearse, combinarse... de hecho, comienza la búsqueda con una única especie.

• El segundo es un optimizador local independiente que se aplica sobre las distintas especies para dirigirlas, de forma independiente, hacia los óptimos de su entorno o “ventana”. Esta modularidad hace al algoritmo especialmente adaptable a gran variedad de problemas mediante la selección de un optimizador local especializado.

Durante su ejecución, UEGO mantiene la lista de individuos que definen cada especie activa. Sin embargo, no se tiene en cuenta ningún tipo de relación de parentesco entre ellas. Por lo tanto, los individuos que definen las especies son autosuficientes tanto para generar nuevas especies como para desplazarse en el espacio de búsqueda. Esta autosuficiencia característica es una de las claves del paralelismo implícito del algoritmo.

Algoritmo

La estructura esquematizada de UEGO, derivada directamente del que se muestra en,​ se muestra a continuación en el algoritmo 1. Posteriormente se hablará sobre las funciones que lo forman y los parámetros con los que opera.

• Función AlgoritmoUEGO(N, max_spec_num, levels, min_r):
  • Init_species_list ()
  • Optimize_species(n[1])
  • Repetir desde i = 2 hasta levels hacer:
    • Establish(r[i], new[i], n[i])
    • Create_species(new[i]/ length(species_list))
    • Fuse_species(r[i])
    • Shorten_species_list(max_spec_num)
    • Optimize_species_list(n[i]/max_spec_num)
    • Fuse_species(r[i])
  • Fin Repetir
• Fin AlgoritmoUEGO

Algoritmo 1.- Esquema general del algoritmo UEGO.

Parámetros

En lo que respecta a los parámetros de configuración de UEGO que recibe del usuario, como se puede ver en el algoritmo 1, son cuatro:

• Límite de evaluaciones (N): Es el número máximo de evaluaciones de la función objetivo que el usuario permite para todo el proceso. Se trata de una cota superior por lo que la búsqueda puede concluir con un número inferior de llamadas a dicha función. No obstante este valor debe permitir el adecuado desarrollo de cada especie estudiada para alcanzar unos resultados de calidad.

• Número de niveles (levels): Es el nivel máximo a alcanzar, es decir, el que tendrá el mínimo radio. Al determinar el número de niveles, este valor especifica también el número de etapas o generaciones (véase el algoritmo 1). Si bien es cierto que un valor alto proporcionará mayor fiabilidad a la búsqueda, su incremento desproporcionado hará la convergencia del algoritmo muy lenta.

• Máximo de especies (max_spec_num): Determina la longitud máxima de la lista de especies, es decir, el número de especies que pueden existir y optimizarse de forma simultánea. Por lo tanto, es necesario contar con un número adecuado de subespecies para el tipo de función de forma que se pueda realizar una búsqueda en anchura a una escala considerable.

• Radio mínimo (min_r): Es el radio asociado con el nivel máximo (por lo tanto, el mínimo radio (véase la figura 3.30)). Este valor puede verse como la “resolución” de la búsqueda a la hora de mantener independientes las ventanas de búsqueda. Por consiguiente, es normalmente interesante que se trate de un valor pequeño para que se mantengan independientes las especies y se conserven los distintos óptimos locales próximos entre sí.

Es importante destacar que, en realidad, la configuración del algoritmo puede apoyarse además en otro parámetro de usuario. Este quinto parámetro posible es el “umbral de estabilidad” o “treshold” como se explica en.​​ Para poder definir una ejecución de UEGO bastaría con escoger y proporcionar cuatro parámetros del conjunto formado por los cuatro descritos previamente y este quinto parámetro. El algoritmo es capaz, por tanto, de obtener toda la información necesaria a partir de un subconjunto de cuatro sobre la base de los principios y relaciones descritas en.​​ En cualquier caso, este quinto parámetro es mucho menos intuitivo y fácil de comprender que los otros por lo que puede incluso llegar a ignorarse en términos de configuración como se hace en.​

Una vez recibe UEGO los parámetros de entrada por parte del usuario procede a calcular toda la información que necesita para llevar a cabo la exploración. Es necesario por ejemplo calcular la distribución de los radios y almacenarla en el vector “r[i]” que se muestra en el algoritmo 1 así como los presupuestos para creación y optimización de especies por nivel (los vectores “new[i]” y “n[i]” respectivamente). En​​​​ y​ se detallan de relación y formulación concerniente a estos cálculos.

Nótese finalmente que no se incluyen parámetros relativos al optimizador local escogido. Como es de suponer, éstos habrían de ser considerados también según el algoritmo escogido.

Procedimientos

En el algoritmo 1 se hace referencia a una serie de funciones que conformarían la lógica de UEGO. La explicación de la lógica de dichas funciones se hace a continuación, siguiendo el orden de aparición:

• Init_species_list(): Este procedimiento crea una nueva lista de especies que consta inicialmente de un único individuo. Esto se hace escogiendo aleatoriamente un punto del espacio de búsqueda y asociándole el primer radio. Este radio coincide con el diámetro del dominio de búsqueda de la función o problema a optimizar. La especie inicial, por la propia lógica del algoritmo, se mantendrá durante todo el proceso como se introdujo.

• Establish( r[i], new[i], n[i] ): Este procedimiento asocia, para cada nivel alcanzado hasta el máximo “levels”, el valor de un radio r[i] correspondiente y dos números que indican máximo de evaluaciones de la función objetivo. Concretamente, new[i] indica el número máximo de evaluaciones que se pueden realizar en un cierto nivel para crear especies, mientras que n[i] delimita el número máximo de evaluaciones que se pueden realizar en un nivel dado durante el proceso de optimización de todas las especies.

• Create_species( evals ): Para cada una de las especies se crea una sub-lista de soluciones escogidas aleatoriamente en su zona. Se van formando entonces parejas de soluciones de modo que se puedan combinar cada una de ellas con el resto (véase la figura 4). Cada vez que se selecciona una pareja, se calcula el punto medio de la línea que las conecta, y se obtiene el valor de la función en dicho punto medio. Si este valor es peor que los valores de las soluciones que forman la pareja, entonces significa que el punto medio está en un valle mientras que las soluciones pertenecen a dos colinas diferentes. En esta situación se opta por incluir las dos soluciones en la lista de especies original como centros de dos nuevas especies. Cada una de estas nuevas especies recién insertadas tienen como radio aquel correspondiente al nivel en el que esté ejecutándose el algoritmo en ese momento. Es importante insistir en que el parámetro “evals” del procedimiento es un límite superior del número de evaluaciones que se pueden realizar en la creación de las especies. De este modo, no tiene porqué consumirse completamente. En​ se explica con detenimiento el cálculo de presupuestos.

• Fuse_species( radius ): En este procedimiento, si los centros de cualquier par de especies están a una distancia inferior al radio dado, las dos especies se funden en una sola (véase la figura 4). La especie resultante tendrá como centro aquel de las dos que tenga el mejor valor, y se le asociara como nivel (y por tanto como radio) el menor de las dos especies. De esta forma recibirá el mayor radio de las dos originales.

4. Ejemplo de fusión de dos especies.

• Shorten_species_list( max_spec_num ): Este procedimiento se encarga de eliminar especies en caso de que la lista general sea más extensa que el máximo permitido (el parámetro “max_spec_num”). Las especies de mayor nivel son eliminadas antes, por lo que se van guardando las especies con radio mayor. De este modo, la especie raíz de nivel 1, cuyo radio es el diámetro del espacio de búsqueda, siempre se mantiene. Se conserva de esta forma el ámbito global de la búsqueda como se anticipó.

• Optimize_species_list( evals ): Este procedimiento es el encargado de optimizar cada una de las especies de forma independiente. La optimización de cada especie tiene asociado un número máximo de evaluaciones de la función objetivo, y toma como punto de partida el centro de la misma, moviéndose en la región definida por su radio. Si el proceso de optimización encuentra un punto solución mejor que el centro, entonces este nuevo punto pasa a ser el centro de la especie, de modo que la ventana, y por tanto la región de búsqueda, se desplazan (véase la figura 3). El radio de la especie, no obstante, se mantiene siempre constante. En este procedimiento es donde se efectúan las mutaciones de los individuos para intentar producir descendientes con un mejor valor. El criterio de reemplazo que se aplica es determinista: se van guardando las mejores soluciones directamente (los centros de las especies).

Aplicaciones

El algoritmo UEGO se ha aplicado a una serie de problemas distintos como el alineamiento de imágenes, problemas de localización continua y la optimización del diseño de campos de helióstatos. Se puede destacar además la existencia del algoritmo GASUB,​ que aplica las ideas de UEGO al ámbito de los problemas de localización discreta.

Enlaces externos

• Página oficial de UEGO, donde puede encontrarse una implementación del algoritmo en C++.