Escrito por

Algoritmos que evolucionan

Publicado en la versión papel como: “Computación evolutiva”. Information Technology. Abril de 2013. Nº 187. Nº 187

Es común que la tecnología imite a la naturaleza, que se intente emular la eficiencia que vemos en el vuelo de las aves, en la fotosíntesis de las plantas, en las redes neuronales de nuestro cerebro, y en los mecanismos naturales que formaron todo esto, que son los de la evolución. La investigación en inteligencia artificial es la que más trata de copiar y mejorar la eficiencia de la naturaleza.

image

Una rama de la IA, llamada computación evolutiva, se enfoca en utilizar como mecanismo fundamental el modelo de la evolución biológica, pero más específicamente, la forma en que esta actúa: los mecanismos definidos en 1859 por Charles Darwin, y mejorados en el siglo siguiente por la teoría sintética de la evolución.

La evolución biológica consiste en la acumulación de cambios en los organismos vivos. Esos cambios ocurren al azar, y es la selección natural la que favorece aquellos cambios que resulten ventajosos. Algunos cambios serán buenos o malos dependiendo de si aportan o no son una buena adaptación al medio, que sirva para la reproducción del organismo.

Ya desde los años 1930s, se vio a la evolución como un proceso de aprendizaje. Walter Cannon, lo hace en su libro de 1932, The Wisdom of the Body. En 1950, el célebre matemático Alan Turing, habla de la evolución y el aprendizaje de las máquinas en su clásico artículo sobre inteligencia artificial “Computing Machinery and Intelligence”.

Los inicios, igualmente, podrían buscarse en los trabajos de informática relacionados con la naturaleza realizados por Alexander Fraser a fines de los 1950s, que inspiraron a los inicios de lo que hoy se conoce como computación evolutiva. Fue introducida en los años 1960s como programación evolutiva por el estadounidense Lawrence Fogel. Años después, John Holland propuso un método de programación al que llamó algoritmos genéticos. Para los años 1990s todos los algoritmos inspirados en la naturaleza pasaron a ser sub áreas de lo que se conoció como programación evolutiva.

Algoritmos evolutivos

“Los mecanismos de la evolución biológica son utilizados principalmente para diseñar algoritmos eficientes que permitan resolver problemas de optimización”, dice Guillermo Leguizamon, profesor de la Universidad Nacional de San Luis, y miembro del Laboratorio de Investigación y Desarrollo en Inteligencia Computacional de esta casa. “Lo importante a destacar es que los mecanismos de la evolución biológica pueden ser extremadamente complejos, y en este sentido, la estrategia seguida para diseñar algoritmos de optimización eficientes, es tomar aquellos aspectos más importantes (y en general de una manera simplificada) de los mecanismos de la evolución natural. Así, la supervivencia del más apto (a través de la selección), herencia (mecanismo de crossover o cruzamiento) y variación del material genético (dado por la mutación) son los aspectos principales que se imitan para reflejar desde el punto de vista computacional el proceso evolutivo”.

El de Leguizamon es uno de los grupos más activos en esta temática, dentro de los que se dedican a la inteligencia artificial en el país. Aquí en Argentina también hay grupos de investigación utilizando algoritmos evolutivos en la Universidad de la Patagonia Austral, en la Universidad de La Pampa, en la Universidad de La Plata, en la Universidad Nacional del Litoral y en la Universidad Nacional del Sur.

“El término Computación Evolutiva”, nos cuenta Leguizamon, “representa una rama de la computación que intenta aglutinar a aquellos investigadores que han seguido diferentes enfoques algorítmicos para simular varios aspectos de la evolución. En otras palabras, el campo de la Computación Evolutiva engloba un conjunto de instancias de algoritmos, llamados Algoritmos Evolutivos, cuyo diseño sigue la metáfora de la evolución natural, particularmente la supervivencia del más apto. Estos algoritmos forman una clase de algoritmos adaptativos con operaciones basadas en procesos probabilísticos para crear y mantener individuos en una población de soluciones candidatas para un problema y que a través de un proceso de variación genética y selección, intentan encontrar soluciones cercanas al óptimo”.

Un ejemplo de algoritmos evolutivos podrían ser los llamados algoritmos genéticos, las estrategias evolutivas, programación evolutiva y programación genética, como los más difundidos. Estos pueden aplicarse a optimización combinatoria y numérica, aprendizaje de máquina, control, problemas clásicos de investigación operativa, diseño ingenieril, robótica, procesamiento de señales, entre muchos otros.

En la evolución biológica los mecanismos principales son las mutaciones que aparecen al azar en los organismos vivos, que son filtradas por la selección natural, si alguna de estas confiere una ventaja que le permita estar mejor adaptado a su entorno, entonces podrá dejar una mayor descendencia, y esa ventaja se esparcirá por la población. En computación evolutiva hacen lo mismo.

“Obviamente estos modelos son abstracciones de muy alto nivel del proceso evolutivo (incluso a veces se los considera modelos de juguete o toy models)”, nos cuenta Ricardo Di Pasquale, que acaba de defender su doctorado en la Universidad Nacional de General Sarmiento, sobre algoritmos genéticos paralelos. Su intención es aplicarlos al procesamiento masivo de datos, especialmente en su trabajo en CAMMESA, apuntando optimizar el manejo de las redes de energía eléctrica.

Según Di Pasquale, los algoritmos genéticos se utilizan “en problemas de optimización combinatoria que son de una clase de problemas (NP) considerados “intratables”, o que no admiten soluciones factibles en tiempos humanamente razonables. De modo que si tenemos un problema intratable para enfoques como la programación lineal u otros métodos de optimización, es válido ir hacia estos modelos evolutivos (que muchas veces son híbridos y utilizan salidas de los otros enfoques como entrada), que terminan haciendo lo que se llama un “random walk” (caminata aleatoria) en un espacio de estado de soluciones posibles”.

“El campo de aplicación de los algoritmos evolutivos es enorme”, dice Di Pasquale. “Incluso más abarcativo que el de la optimización combinatoria. Hay que tener en cuenta que la aplicación básica de algoritmos evolutivos no requiere una heurística específica sobre el campo a explorar (la conceptualización del modelo sí lo requiere, pero el mecanismo evolutivo en sí, no), por lo que las aplicaciones son literalmente infinitas. Entre los campos de aplicación más destacados están el aprendizaje automatizado, pudiendo ser usados en la construcción y entrenamiento de otras estructuras como es el caso de las redes neuronales. El ámbito del data mining también es propicio para la aplicación de algoritmos genéticos. Han sido utilizados, en otro orden de cosas, para evolucionar música y arte. En cuanto a la biología, se ha utilizado con éxito algoritmos genéticos para buscar formas de moléculas de proteínas. Otras áreas de interés son la predicción de sistemas dinámicos no lineales, la planificación de trayectorias de robots, planeamiento estratégico, diseño de aeroplanos, optimización de redes de comunicación. Incluso en la industria del software son utilizados para generar juegos de pruebas unitarias automatizadas”.

“Los algoritmos evolutivos”, nos cuenta Leguizamon, desde San Luis, “conforman un subconjunto de lo que se denomina técnicas metaheurísticas o simplemente metaheurísticas que incluyen a técnicas de optimización capaces de encontrar soluciones de alta calidad para un problema determinado en un tiempo razonable desde el punto de vista práctico. Sin embargo, existen metaheurísticas basadas en otro tipo de metáforas, muchas de ellas inspiradas en la naturaleza. Por ejemplo, el principio de la inteligencia colectiva, observada en ciertas especies como las hormigas, abejas, bandadas, cardúmenes, etc. Entre las más conocidas en encuentran Ant Colony Optimization (Optimización basada en el comportamiento de las colonias de hormigas), Particle Swarm Optimization (Optimización Basada en Enjambre), Sistemas Inmunes (Basado en la dinámica de un sistema inmune de un organismo vivo) entre otros”.

Computación evolutiva en Argentina

En el equipo de la Universidad Nacional de San Luis la investigación en computación evolutiva es la más desarrollada de las aplicadas a inteligencia artificial. “La investigación actual que se realiza en el LIDIC”, dice Leguizamon, “ incluye la investigación, desarrollo y aplicación de Algoritmos Evolutivos y otras metaheurístcas a problemas de optimización académicos y del mundo real. Ejemplos de problemas estudiados incluyen a: problemas de planificación, bioinformática (microarrays y problemas de ensamblado), problemas numéricos de optimización, problemas de optimización dinámica, etc. Más recientemente el grupo se está orientando a la resolución de problemas de distribución de turbinas de viento en campos eólicos para optimizar la energía producida”.

Si bien recién están comenzando con esta aplicación de los algoritmos evolutivos a las energías renovables, la idea es ir hacia aplicaciones más reales. Han comenzado con simuladores de parques eólicos para poder medir el desempeño de las soluciones propuestas.

“Uno de los simuladores que pensamos usar es el OpenWind que está disponible para aplicaciones académicas. En una etapa posterior, pretendemos aplicar los algoritmos desarrollados en un entorno de un parque eólico real para lo cual se necesitará establecer los contactos necesarios y trabajar de manera integrada con alguna institución nacional o privada”, dice Leguizamon, quien también es organizador del IEEE Congress on Evolutionary Computation 2013 (www.cec2013.org).

En el Centro de investigación en señales, sistemas e inteligencia computacional, de la Facultad de Ingeniería y Ciencias Hídricas, perteneciente a la Universidad Nacional del Litoral, también están trabajando con computación evolutiva, y en inteligencia artificial desde hace unos 15 años. Allí funcionan cinco grupos que han encarado diferentes enfoques para la investigación en computación evolutiva. Georgina Stegmayer, investigadora del CONICET, está a cargo del grupo que se vale de la informática para la naturaleza, es decir, al revés de la computación evolutiva. En su grupo de trabajo estudian aplicaciones para la bioinformática, actualmente centrados en poder analizar las reacciones y relaciones químicas mediante computación evolutiva.

Diego Milone, también del CONICET, está a cargo de los otros grupos de la facultad. Nos cuenta que “son muchas las aplicaciones que tenemos en marcha, en su mayoría con la participaciones de becarios de doctorado o posdoctorado”. Una de las más interesantes, relacionada con la que están comenzando en San Luis, es la que se enfoca en aplicaciones en la energía solar, específicamente en centrales fotovoltaicas.

“El objetivo”, dice Milone, “es encontrar cómo conectar los módulos fotovoltaicos, inversores y demás componentes de una central, de forma de maximizar el rendimiento en situaciones reales, donde pasan nubes, hay cambios de temperatura, humedad, etc.”. Una aplicación muy útil en un momento clave del país que está desarrollando la tecnología y la aplicación solar en provincias como Santa Fe y en especial en San Juan.

Otras aplicaciones que están investigando en la UNL, se relacionan con el reconocimiento de rostros y del habla. Aquí Milone tiene la ayuda del becario posdoctoral Leando Vignolo, y buscan poder aplicar esta investigación a las interfaces hombre-máquina de seguridad. La idea es poder determinar automáticamente cuáles son las características de un rostro, y del habla, que hacen que se maximice la tasa de aciertos en un sistema de reconocimiento.

También están aplicando la computación evolutiva a la salud humana, en especial al diagnósticos de autismo a partir de la voz. “Este es el más reciente, consiste en determinar también en la voz, cuáles son las características que definen ciertos diagnósticos asociados con el autismo”, cuenta Milone.

La evolución biológica no consiste en la búsqueda de soluciones, en la forma de conseguir buenos resultados valiéndose de mecanismos como la selección natural. Las mutaciones que ocurren durante la reproducción de los organismos no son dirigidas, ni son racionales, sólo ocurren al azar. Y será mediante la selección natural que se filtrarán aquellos cambios o mutaciones que no resulten una ventaja adaptativa para el organismo. En computación, ocurre todo lo contrario, la evolución y sus mecanismos de selección son dirigidos a la búsqueda del más apto, a la búsqueda de la solución más óptima, no es el resultado del azar. El sueño de los creacionistas.

Artículos relacionados

Lo más interesante
Top 6
artículos
Síguenos