Charla: Algoritmos genéticos

El pasado viernes 29 de mayo tuvo lugar una charla titulada «Resolviendo problemas complejos. Una introducción a los Algoritmos Genéticos”, impartida por la Dr.ª Ángela Ribeiro Seijas, Directora del Grupo de Percepción Artificial del Centro de Automática y Robótica (CSIC-UPM). La charla fue en el contexto de la asignatura «Inteligencia Artificial II» (modalidad Executive del Grado en Ingeniería Informática), cuyo profesor es Pedro Javier Herrera, si bien estuvo abierta toda la comunidad universitaria.

Breve resumen de la conferencia:

Desde que en 1975 fueran propuestos por John Henry Holland basándose en la evolución natural de Darwin, los Algoritmos Genéticos se han convertido en un método de Inteligencia Artificial muy potente y usado en la resolución de problemas de todo tipo.

El punto de partida es elegir una codificación o representación del problema lo más adecuada posible para garantizar una rápida solución. Se construye así una «población», formada por individuos. La codificación puede ser muy diversa, pues puede estar basada en cadenas binarias, vectores de números reales, redes neuronales, grafos, árboles de decisión, etc. Sea cual sea la codificación, lo importante es que debe constituir un alfabeto de baja cardinalidad, es decir, que el número de elementos que la componen debe ser pequeño. Es por ello que habitualmente se utiliza el código binario, formado por 2 elementos exclusivamente: 0 y 1. A esta representación de un individuo se la denomina cromosoma, imitando el nombre que se utiliza en Biología para el material genético de un ser vivo, donde cada uno de los bits constituye un gen.

Una vez que hemos representado la población del problema siguiendo esta codificación, el siguiente paso es definir una función de «fitness», de aptitud, de mejor ajuste o de mérito. Se trata de una función que, en base a los valores de los genes de un individuo de la población, devuelve un valor numérico que indica lo bueno o no tan bueno que es ese individuo y su capacidad de supervivencia y de dejar descendencia. Esta función hay que intentar maximizarla. Normalmente su valor está normalizado entre 0 y 1, de tal forma que interesa que se aproxime lo más posible al valor 1. La definición concreta de la función dependerá del problema en cuestión.

La población inicial o primera generación es producida aleatoriamente, es decir, sus cromosomas son secuencias binarias de 0 y 1 elegidos al azar. Dicha primera generación es evaluada según la función de «fitness» para comprobar si hemos alcanzado ya un umbral o criterio de finalización del algoritmo (normalmente esto no se logra con la población inicial). Entramos entonces en un proceso iterativo en el cual se producen cambios en el material genético de la población mediante los denominados operadores genéticos con el objetivo de lograr la maximización de la función de «fitness» y por tanto de alcanzar el umbral de finalización del proceso. Se distinguen las siguientes 4 etapas:

• Selección: se eligen aleatoriamente parejas de individuos de la población, que harán las veces de progenitores o padres de la siguiente generación. Existen diversos métodos de selección, si bien se suele fomentar que un individuo podrá ser seleccionado con mayor probabilidad cuanto mayor sea su función de «fitness», ya que en este caso el individuo será muy bueno y estará mejor adaptado que el resto para dejar descendencia.
• Una vez elegidos quiénes serán los padres de la siguiente generación, se produce el cruce de genes, recombinación o intercambio genético y que corresponde a la reproducción sexual. En este caso, el cromosoma de un progenitor se mezcla con el del otro progenitor. Se produce el cruce basándonos en una probabilidad de cruce (bastante alta), que nos dice cómo es de probable que se produzca este intercambio genético. En algunos casos especiales habrá que tener en cuenta si el cruce produce una representación válida o no de un nuevo individuo de la población (cruce especializado).
• Luego se produce la mutación, o modificación aleatoria de algunos genes del cromosoma (de 0 pasan a 1, o viceversa), basándose en una probabilidad de mutación que suele ser muy baja. La mutación es un mecanismo para generar y garantizar la diversidad genética. Por tanto permite sortear los máximos locales de la función de «fitness», que no conforman la solución óptima del problema. Así se logra acceder a zonas diferentes del espacio de búsqueda de soluciones que de otra manera no serían exploradas. Hay que tener en cuenta, eso sí, que en ocasiones la mutación de un solo gen del cromosoma puede corresponder a un individuo muy parecido al del individuo no mutado, mientras que otras veces se trata de un individuo muy diferente al original.
• Por último tiene lugar el reemplazo de una generación por otra, es decir, se decide qué individuos intervendrán en la siguiente iteración del algoritmo. Habitualmente la generación de progenitores muere y continúa viva la generación de hijos surgidos de los pasos anteriores. Sin embargo, a veces se introduce un nuevo operador genético llamado selección elistista, según el cual una vez generada la nueva generación, ordenamos todos los individuos de la generación de progenitores y de la  generación de hijos según la función de «fitness» y permitimos que pasen a la siguiente iteración los n mejores del total. De esta manera se garantiza que los individuos mejor adaptados al entorno son los que sobreviven a futuras etapas del algoritmo.

Para todos aquellos interesados en estos temas también pueden consultar un tutorial sobre Algoritmos Genéticos realizado por Marek Obitko de la Universidad Técnica de la República Checa de Praga.

La segunda parte de la charla se centró en un par de aplicaciones de los Algoritmos Genéticos a lo que se denomina Agricultura de precisión. Se trata de dos proyectos de investigación realizados por el grupo que dirige, dentro del Centro de Automática y Robótica (CAR) dependiente del Consejo Superior de Investigaciones Científicas (CSIC) y la Universidad Politécnica de Madrid (UPM).

El primero de ellos, el denominado Proyecto RHEA, consistía en un proyecto europeo liderado por el grupo de investigación de Ángela Ribeiro sobre la detección de malas hierbas en cultivos. Se trata de encontrar automáticamente las zonas donde han surgido plantas perjudiciales para los cultivos, donde deberemos aplicar productos agroquímicos adecuados para su eliminación, minimizando a su vez la contaminación de las zonas no invadidas por malas hierbas así como minimizando los costes económicos.

Se trata de un proyecto muy interesante que combina técnicas Robótica, Procesamiento de Imágenes, Visión Artificial e Inteligencia Artificial: manejo de drones, captura de fotografías de zonas de cultivo desde los drones, mosaicado o unificación de las fotografías para generar un único mapa del campo, detección automática de las plantas perjudiciales tanto por su posición, color, tamaño y forma de las hojas, etc. Los Algoritmos Genéticos fueron utilizados en este proyecto para la búsqueda de los parámetros óptimos del procesado de imágenes para facilitar la detección de las líneas de cultivo, el realzado del color de la imagen, las operaciones morfológicas en la imagen (erosión, dilatación y agrupación) y la segmentación de las zonas de interés (malas hierbas).

También se mencionó un segundo proyecto sobre el cálculo aproximado de la zona cubierta por rastrojos en cultivos también mediante procesamiento de imágenes, incluyendo también los Algoritmos Genéticos en su realización.

Desde la Escuela Politécnica Superior de la Universidad Francisco de Vitoria, queremos agradecer la presencia de Ángela Ribeiro por esta charla tan interesante.

 

Fuente de la imagen principal de este post: http://www.genetic-programming.org/