Enrique J. Carmona: " El mundo de los Algoritmos Evolutivos goza de buena salud, como así lo atestigua el gran volumen de publicaciones que aparecen cada año"

16 de abril de 2021

El doctor Carmona Suárez habló hoy de los algoritmos evolutivos y sus aplicaciones. Esta conferencia forma parte del Seminario de IA de la UNED, se emitió desde el Centro de IA de Ourense, en cuya página web podrá seguirse también en diferido. Dicho seminario cuenta con el apoyo económico del Vicerrectorado de Investigación, Transferencia del Conocimiento y Divulgación Científica de la UNED.

OURENSE, 16 de abril.- El 22 de marzo de 2006, la NASA enviaba por vez primera al espacio un hardware diseñado artificialmente. Se trataba de una antena diseñada mediante técnicas evolutivas que operó con éxito durante todo el periodo de la denominada misión Space Technology 5 (ST5). Aunque han pasado unos años desde aquel hito histórico, aún sigue estando vigente algunas de las conclusiones realizadas por los propios desarrolladores de la NASA de aquella época y que están relacionadas con las ventajas del diseño evolutivo frente al diseño convencional. En particular, la ausencia de sesgos de diseño típicamente humanos que favorece la posibilidad de encontrar diseños totalmente novedosos en el campo y la necesidad de ciclos de diseño más rápidos que implican costes de desarrollo menores. Posteriormente (2013-2014), una nueva misión, dedicada a obtener información de la atmósfera lunar, utilizaba también otras antenas obtenidas evolutivamente.

El ponente hizo un recorrido por la perspectiva histórica de los algoritmos evolutivos y así, ya en 1948, Turing propuso lo que denominó “búsqueda genética o evolutiva” como un medio para dotar de inteligencia a una máquina. Posteriormente, en 1962, Bremermann realizaba experimentos en “Optimización a partir de evolución y recombinación” implementados en una computadora.

Sin embargo, es durante los años 60 cuando aparecen, en tres lugares diferentes, sendas implementaciones de lo que hoy en día conocemos como Algoritmo Evolutivo:

Algoritmo Genético: Holland (USA)
Programación Evolutiva: Fogel, Owens y Walsh (USA)
Estrategias Evolutivas: Rechenberg y Schwefel (Alemania)

“Durante los 15 años siguiente estas técnicas se desarrollaron independientemente, pero desde principios de los 90 han sido vistas como diferentes representaciones (dialectos) de una misma disciplina que recibió el nombre de Computación Evolutiva (CE), actualmente, una rama de la inteligencia artificial que aborda problemas de optimización mediante inspiración biológica”, explica el doctor Carmona.

Finalmente, en la década de los 90 emergieron dos nuevas variantes: en 1992, la denominada Programación Genética, liderada por Koza (USA) y, algo más tarde, en 1997, la denominada Evolución Diferencial, presentada por Storn y Price.

“La terminología actual denota todos los algoritmos pertenecientes a la CE como algoritmos evolutivos (AE) y las cinco modalidades mencionadas anteriormente son consideradas como distintas variantes que se engloban bajo el paraguas de la CE. Sin embargo, el mundo de la CE no finaliza en estos cinco tipos de AEs. Existe un amplio repertorio de variantes de cada uno de ellos y, además, abarca otras subramas como son el uso de los AES en problemas de optimización multiobjetivo o en problemas de optimización con restricciones, así como el estudio teórico de la convergencia de este tipo de algoritmos, entre otras”, señala el ponente.

Enrique J. Carmona realizó una introducción a los algoritmos evolutivos, englobándolos en un tipo de algoritmo más amplios denominados metaheurísticas. Si bien puede definirse una heurística como un método de búsqueda que hace uso de la información del domino de un problema particular para utilizar “atajos” en la búsqueda de la solución, una metaheurística es un método de búsqueda que es capaz de generalizar la operativa de una heurística, haciéndola independiente del dominio del problema y, por tanto, alcanzando la propiedad de poder ser usada en un repertorio mucho más amplio de problemas de optimización. Es grande el repertorio de metaheurísticas que existe en la actualidad, todas ellas inspiradas en diferentes procesos naturales o artificiales. No obstante, también es cierto que actualmente hay un debate abierto sobre si las últimas metaheurísticas incorporadas a la colección suponen realmente nuevas aportaciones al campo o son diferentes metáforas en las que subyacen estrategias similares, pero expresadas con una notación diferente.

En cuanto a la comparación entre los AEs y los métodos clásicos, Carmona señala que los primeros son competitivos cuando el uso de estos últimos supone tiempos de ejecución prohibitivos, debido a una explosión combinatoria de posibles soluciones en el espacio de búsqueda (imposible realizar una búsqueda exhaustiva); igualmente, en aquellos casos en que los métodos clásicos son incapaces de dar una solución, los AEs permiten obtener una solución que, aunque no sea la óptima, podría ser mejor que la obtenida hasta el momento para un problema dado o que la que podría producir un humano.

Por otro lado, si comparamos los AEs con otras metaheurísticas, la principal ventaja de los primeros, comparados con aquellas metaheurísticas que hacen uso de una única solución, transformándola en pasos sucesivos (metaheurísticas basadas en trayectoria), es que la búsqueda de la solución en los AEs está basada en población, lo que disminuye la posibilidad de éstos queden atrapados en un óptimo local. No obstante, también existen otro tipo de metaheurísticas, como las basadas en inteligencia de enjambre, que hacen uso de este tipo de búsqueda. Por el contrario, el inconveniente de las metaheurísticas que hacen uso de búsqueda basada en población es un mayor coste computacional. Sin embargo, esto último puede paliarse paralelizando la ejecución del algoritmo. Adicionalmente, la existencia de una gran variedad de AEs facilita el uso de la variante más adecuada en función de las características del problema a resolver.

Existe un amplio repertorio de problemas en donde los AEs pueden ser competitivos:

problemas en los que se quiere optimizar tanto los parámetros de un modelo como en aquellos otros donde se requiere la optimización del propio modelo y sus parámetros simultáneamente
problemas de optimización tanto en espacios discretos/continuos
problemas de optimización multiobjetivo
problemas de optimización con restricciones

Carmona indica que dos mecanismos forman la base de los sistemas evolutivos:

Los operadores de variación (recombinación y mutación), que tienden a aumentar la variedad genética de la población y, por tanto, permiten crear la diversidad necesaria para poder alcanzar la solución a partir de una población inicial obtenida aleatoriamente. Se dice que este tipo de operadores favorecen la EXPLORACIÓN del espacio de búsqueda
El proceso de selección de supervivientes, que tiende a disminuir la variedad genética, pero actúa como una fuerza que empuja la convergencia hacia una solución

Se dice que este mecanismo favorece la EXPLOTACIÓN del espacio de búsqueda.

Otra propiedad importante los AEs es su naturaleza estocástica, es decir, no son deterministas. Esto implica que el subsiguiente estado del sistema está determinado tanto por las acciones predecibles del proceso como por mecanismos aleatorios. Esta aleatoriedad se manifiesta principalmente en la toma de decisiones probabilista que subyace en la operativa de los operadores de variación. La principal consecuencia de esta propiedad se traduce en que la ejecución de un mismo AE, configurado con los mismos valores de parámetros, no tiene por qué dar resultados idénticos.

Al estudiar la evolución de la población en una AE, al inicio, los individuos están diseminados aleatoriamente sobre todo el espacio de búsqueda. Después de unas pocas generaciones, los individuos de la población abandonan las regiones de alto valor de adaptación y empiezan a “descender las colinas”, asumiendo un problema de minimización. Durante las generaciones intermedias, el mecanismo de exploración del AE visitará diferentes regiones del espacio de búsqueda, seleccionando aquellos valles más prometedores. Cercanos al final del proceso de búsqueda, toda la población estará concentrada alrededor de pocos valles. Entonces, alguno de ellos debería corresponder al valle del óptimo global, donde el mecanismo de explotación del AE acabará encontrando finalmente la mejor solución. No obstante, es posible que la población no llegue a explorar el “valle adecuado”, quedando así los individuos atrapados en óptimos locales. Normalmente, las causas de quedar atrapado en un óptimo local pueden ser debidas a una mala configuración del AE o a una mala elección del tipo de AE utilizado para resolver el problema.

El profesor Carmona señala que, en todo problema de optimización abordado mediante un AE, hay dos puntos clave: cómo representar las soluciones potenciales (individuos) y cómo evaluar el grado de bondad de cada una de ellas. En el primer caso, además, hay que establecer el procedimiento que nos permita pasar de la representación en el espacio de búsqueda (representación genotípica) a la representación perteneciente al dominio del problema (representación fenotípica). Con relación a cómo evaluar cada posible solución, hay que definir una función matemática, denominada función de evaluación o función fitness, que nos permita medir objetivamente cómo de buena es una solución y, adicionalmente, nos permita comparar el grado de adaptación de las diferentes soluciones contenidas en la población actual. Por ejemplo, si se quisiera encontrar el máximo de la función potencia al cuadrado en un intervalo de los números enteros, podríamos, por ejemplo, representar cada individuo por una cadena binaria (genotipo); la forma de decodificar cada individuo podría consistir entonces en transformar el número binario en su correspondiente número expresado en base 10 (fenotipo); y, finalmente, la forma de evaluar dicho individuo podría ser la de calcular el cuadrado de su valor fenotípico. Por ejemplo, el individuo representado por la cadena binaria 10010, se decodificaría como el entero, 18 y el valor de adaptación de dicho individuo sería 18x18=324”.

La curva que muestra la evolución del mejor individuo de la población a lo largo del tiempo tiene una forma característica: rápido progreso al principio, un progreso moderado a lo largo de lo que podría denominarse fase intermedia, y la tendencia a una asíntota en las generaciones finales. Durante la primera fase predomina la exploración del espacio de búsqueda y, durante la última, la explotación de las regiones más prometedoras. El éxito de la ejecución dependerá en gran medida del equilibrio entre exploración y explotación llevado a cabo durante la fase intermedia.

Algoritmos anytime

Además, la curva de progreso de un AE revela una característica interesante: la de permitir obtener una solución durante cualquier instante del proceso de ejecución (algoritmos anytime). Este comportamiento es opuesto al de otro tipo de algoritmos que necesitan la realización de un número de pasos fijos antes de poder proporcionar una solución.

El nombre “anytime” viene de la propiedad de que la búsqueda puede ser parada en cualquier momento y el algoritmo siempre producirá alguna solución, aunque sea subóptima. Sin embargo, esta propiedad puede ser interesante en aquellos casos en que se disponga de poco tiempo para poder obtener una solución, de tal manera que, aunque la solución proporcionada no sea óptima, puede ser mejor a la obtenida por cualquier otro método o por el propio humano.

El ponente estableció algunas pautas para determinar cómo elegir un tipo de AE en función de las características del problema abordado. Igualmente, para ejemplificar la mecánica de este tipo de algoritmos, presentó un ejemplo de uso del paradigma basado en programación genética aplicado al problema de la regresión simbólica.

Otro punto curioso presentado por el doctor Carmona es la competición que todos los años, desde 2004, se celebra anualmente en la Conferencia sobre Computación Genética y Evolutiva (GECCO por su acrónimo en inglés). Se trata de un certamen de premios pagados en efectivo, denominados "Humies", que se conceden a aquellos resultados que fueron producidos por cualquier forma de computación evolutiva y que resultan ser competitivos con los que pudiera producir un humano. En particular, el concepto de "competitividad humana" fue definido por John Koza, el padre de la programación genética, quien estableció que un resultado creado automáticamente se considera "competitivo humano" si satisface al menos uno de los ocho criterios existentes.

La última parte de la presentación estuvo dedicada a algunas de las aplicaciones de los AEs llevadas a cabo en diferentes trabajos y proyectos de investigación realizados en el Departamento de Inteligencia Artificial de la UNED y, más concretamente, en el seno del grupo SIMDA. Los dominios de aplicación abarcan campos tan diversos como las Matemáticas, la Electrónica, la Medicina y la Industria. El ponente resumió así los diferentes pasos a seguir para abordar un problema mediante computación evolutiva:

Definir el problema original
Transformar el problema original en un problema de optimización
Establecer cómo codificar y decodificar las soluciones
Definir cómo evaluar las soluciones (función fitness)
Seleccionar el tipo de AE y sintonizar adecuadamente su configuración

Concretamente, en el caso de las Matemáticas, se mostró cómo abordar el problema de la resolución de ecuaciones diferenciales, incluyendo tanto ecuaciones diferenciales lineales como no lineales, sistemas de ecuaciones diferenciales y ecuaciones diferenciales en derivadas parciales. En Electrónica, se ejemplificó el uso de los AEs para abordar el problema del diseño automático de circuitos electrónicos analógicos. En Medicina, los AEs fueron utilizados para la detección de estructuras anatómicas en imágenes de fondo de ojo. Y, finalmente, en el caso de la Industria, para aplicaciones tales como la optimización de la eficiencia energética de una turbina de gas aeronáutica o para la optimización de diagramas de flujo de instalaciones de canteras.

Para finalizar, Enrique J. Carmona explica que, a pesar de que los algoritmos genéticos son los AEs más conocidos, hay vida más allá de este tipo concreto de algoritmos, dado el amplio repertorio de AEs existentes. Adicionalmente, hay que tener en cuenta que no todos los problemas de optimización se resuelven mediante AEs. Así, en algunos casos, pueden existir métodos clásicos que resuelvan el problema de manera óptima. En caso contrario, los AEs sí deberían ser tenidos en cuenta en aquellos problemas de optimización donde la dimensionalidad y el número de óptimos locales es alto, el número de objetivos a optimizar es mayor de dos (problemas multiobjetivo) y cuando el problema de optimización está sujeto a un número elevado de restricciones. Estos últimos problemas mencionados forman parte del mundo real y aparecen frecuentemente en el ámbito de la ingeniería.

No obstante, el uso de AEs para problemas reales representa un elevado coste computacional (tanto en la ejecución del AE como en el proceso de configuración de sus parámetros). Sin embargo, “con el incremento de la potencia de cómputo, esto debería ser hoy en día un problema cada vez menor, máxime si, además, por su propia naturaleza, los AEs son fácilmente paralelizables”. En el caso del diseño industrial, el uso de este tipo de algoritmos suele requerir de potentes simuladores para poder evaluar automáticamente las diferentes soluciones propuestas a lo largo del proceso evolutivo. Adicionalmente, en algunos casos, se requiere la necesidad de poder explicar el diseño obtenido evolutivamente, imprescindible para ser aceptado y usado industrialmente, tal y como podría requerir, por ejemplo, con la propuesta de un nuevo circuito electrónico obtenido evolutivamente.

En cualquier caso, a pesar de sus inconvenientes y gracias a sus ventajas, el mundo de los AEs, en particular, y el de las metaheurísticas, en general, gozan de muy buena salud, tal y como así lo atestigua el gran volumen de publicaciones que cada año aparecen en torno a este tipo de algoritmos.

Puedes ver la conferencia aquí.

UNED Ourense