Inteligencia artificial: algoritmos genéticos

9 marzo, 2017

Mi investigación gira alrededor del modelado, simulación y optimización. Y en principio, en la universidad, la docencia suele ir alineada con la investigación. Así, pertenezco al equipo docente de Computación e Inteligencia Artificial (IA). Pero curiosamente, una de las asignaturas de las que soy responsable* es Biología Molecular (BM). Realmente es una coincidencia interesante porque si bien es cierto que como informático nunca tendré los conocimientos en Biología Molecular que tiene un biólogo, difícilmente no habré oído hablar de Algoritmos Genéticos (AG). Pero ¿qué son y de dónde vienen?

Uno de los campos más interesantes y estudiados de la BM es la genética. A todos nos suenan científicos como Darwin, Mendel, McClintock y conceptos como genoma, mutación, adaptación, etc. Todos ellos, de manera más o menos directa están relacionados con la genética. Pero ¿por qué nos puede interesar a l@s informátic@s? Pues, por la misma razón que observamos a las hormigas, el cerebro humano, o las abejas: todos ellos son sistemas/procesos/… capaces de solucionar problemas complejos. En el caso concreto de la genética nos fijamos en qué mecanismos utiliza la naturaleza para seleccionar individuos y asegurar la persistencia (o no de las especies que conforman). Dándole la vuelta y simplificando, l@s informátic@s recogemos de ésta una serie de mecanismos que evolucionan un conjunto de soluciones, mejorando iteración tras iteración, hasta encontrar las mejores posibles.

La implementación de la idea de John H. Holland (en los años 70) no es excesivamente compleja: Partimos de una población de individuos, en que cada uno representa una solución factible del problema que se quiere resolver. Cada solución tiene una calidad asociada (fitness) y evidentemente, debe ser factible. En este punto, aplicamos un conjunto de mecanismos evolutivos que producen una nueva generación de individuos. Si todo va bien, tras un cierto número de generaciones, iremos obteniendo individuos (soluciones) que mejoran la solución inicial. Pero ¿cuáles son esos mecanismos? Pues básicamente tres: cruce (simulamos reproducción sexual, por lo que escogeremos parejas de soluciones, las partimos y cruzamos para generar su descendencia), mutación (incluimos mutaciones al azar en los individuos para evitar la convergencia de la población hacia un máximo/mínimo local) y «selección» (eliminamos individuos que representen soluciones no factibles -inviables- y además, en cada generación, nos quedamos con un subconjunto de padres e hijos, normalmente siguiendo el criterio de mejor fitness).  Si como en la realidad este proceso se itera millones de veces (por suerte, los ordenadores nos permiten que los algoritmos genéticos simulen a una velocidad más cercana a la evolución de las bacterias que a la de los primates) nos iremos acercando a una población de soluciones de calidad normalmente muy aceptable.

No debemos olvidar que los Algoritmos Genéticos son metaheurísticas y por lo tanto no hacen una búsqueda completa (exhaustiva) sobre el espacio de soluciones, por lo que no aseguran encontrar la solución óptima. Pero dado que el tipo de problemas a los que se aplican suelen ser de complejidad NP, ya es lo esperado. Estos algoritmos suelen tener pocos parámetros (tamaño de las poblaciones, número de generaciones máximo, probabilidad de mutación, …) pero son extremadamente dependientes del modelado de los individuos (soluciones), ya que es clave facilitar que la producción automática (mediante cruce) de nuevos individuos genere mayoritariamente individuos viables.  También tiene bastante impacto la elección de la población inicial (debido a lo que en BM se llamaría deriva genética, principalmente).

Desde los años 70, los Algoritmos Genéticos han sido una de las «ideas» de la IA más investigadas y utilizadas, dando solución a multitud de problemas combinatorios y siendo utilizadas en aplicaciones reales desde el diseño de los horarios de los JJOO hasta la planificación de rutas logísticas. Y por supuesto, no se han escapado de «sufrir» en sus propios huesos la misma evolución que implementan dando lugar a cientos de aproximaciones y mejoras.

* NOTA: Por suerte, en la UOC, el equipo de las asignaturas no es unipersonal, ya que tenemos colaboradores docentes, que son expert@s en cada asignatura concreta, ya sea por su perfil académico, investigador, o bien su experiencia profesional. En el caso de Biología Molecular, la experta es la Dra. Dorcas Orengo, doctora en Biología y experta en Genética de Poblaciones, Regulación Génica y Genética Molecular Evolutiva.

Daniel Riera es Doctor Ingeniero en Informática por la UAB. Actualmente es el director del Grado de Ingeniería Informática de la UOC y hace investigación dentro del grupo ICSO en temas relacionados con el modelado, simulación y optimización de sistemas combinatorios.

(Visited 258 times, 1 visits today)
Autor / Autora
Daniel Riera Terren
Comentarios
Deja un comentario