¿Qué son los algoritmos genéticos?

Un algoritmo es una serie de pasos que describen el proceso de búsqueda de una solución a un problema concreto. Y un algoritmo genético es cuando se usan mecanismos que simulan los de la evolución de las especies de la biología para formular esos pasos. Es una técnica de inteligencia artificial inspirada en la idea de que el que sobrevive es el que está mejor adaptado al medio, es decir la misma que subyace a la teoría de la evolución que formuló Charles Darwin y que combina esa idea de la evolución con la genética.

Pero claro, ¿cómo se implementa esto con fórmulas matemáticas? Pues lo que haces es transformar la resolución de cualquier problema en un conjunto de soluciones en el que cada una de ellas funciona como si fuera un individuo. Abordas los problemas de manera que puedas decir, este conjunto de soluciones es como una población, una población de soluciones. Imagina que tu problema a resolver es que quieres saber cuál es el camino más corto para ir de Madrid a San Petersburgo y tienes miles de soluciones. Cada camino que encuentres podría ser una opción, si le aplicas un algoritmo genético, cada camino que encuentres sería un individuo. Para poder aplicar algoritmos genéticos debes ser capaz de convertir las soluciones a tu problema en vectores matemáticos, entonces, un vector para ir de aquí a San Petersburgo puede ser uno que enumere las ciudades por las que vas pasando. Puede haber muchos recorridos: unos más largos y otros más cortos, unos tendrán más tráfico, otros tendrán menos tráfico…

Los algoritmos genéticos tienen como punto de partida un conjunto de soluciones aleatorio. Si continuamos con el ejemplo de San Petersburgo, puedo ir poniendo ciudades y puedo pasar hasta por Australia para ir a Rusia. Obviamente esa combinación no va a ser muy eficiente pero el procedimiento acabará descartándola. Una vez que tengo ese conjunto de soluciones inicial aleatorio aplico lo que se llama una función de ajuste o función objetivo, que en este caso es llegar en el menor tiempo posible a San Petersburgo. Mi función objetivo sería el tiempo que tardo teniendo en cuenta el tráfico y teniendo en cuenta los kilómetros que recorro. Esa función objetivo sirve para clasificar las soluciones aleatorias: las que duran menos tiempo son mejores y las que duran más tiempo son peores. Una vez que las tengo clasificadas lo que hago, y aquí entra la genética, es reproducirlas. Reproduzco las soluciones, como se reproducen los individuos en una población, e implemento los tres mecanismos que intervienen en la selección de las especies: la reproducción en sí, el cruzamiento y la mutación.

Para imitar la reproducción hay diferentes mecanismos matemáticos, uno de ellos es a partir de la función objetivo, es decir que se reproduzcan más aquellas soluciones que son mejores y por lo tanto las que son peores desaparecerán; al aplicar el cruzamiento combinas unas soluciones con otras. Por ejemplo, cojo la mitad de una solución que pasaba por Australia y la combino con otra solución que pasaba por China… Las vas combinando garantizando que son lógicas y luego, finalmente, aplicas un procedimiento de mutación de forma matemática, pues si antes pasaba por Sídney yo implemento matemáticamente que me cambie Sídney por ejemplo por cualquier otra ciudad australiana y ya no pasa por Sídney, pasa por Melbourne o por dónde sea. Eso sería un poco como aplicar las tres dinámicas que existen en el mundo biológico cuando se reproducen las especies.

Una vez que he aplicado todo esto, de nuevo hay que calcular la función objetivo de la nueva población. Veré que algunas soluciones habrán mejorado y otras habrán empeorado. Quizá me dé soluciones que tardan menos de Madrid a San Petersburgo y otras al revés, que tardan muchísimo más. Como vuelvo a aplicar el mecanismo de la reproducción que está basado en la función objetivo, lo que ocurre es que va a reproducir en mayor número las soluciones que tardan menos y va a eliminar aquellas que tarden muchísimo. Y de nuevo vuelvo a aplicar el cruzamiento y las mutaciones entre las mejores soluciones. Así funcionan los algoritmos genéticos. Cuando estás buscando resolver problemas en un campo enorme no es viable el procedimiento enumerativo de ir de una en una porque puedes tener millones y millones de posibles soluciones. Estos algoritmos genéticos combinan la aleatoriedad porque se inician con un conjunto de soluciones totalmente aleatorio pero luego también están dirigidas porque buscan el resultado más óptimo. Y gracias a ello encuentras soluciones muy eficientes en muy poco tiempo de computación. 

Laura Núñez es doctora en Economía, profesora de Finanzas en el IE Business School, IE University.

Pregunta realizada vía email por Myriam García Sánchez

Nosotras respondemos es un consultorio científico semanal, patrocinado por la Fundación Dr. Antoni Esteve, que contesta a las dudas de los lectores sobre ciencia y tecnología. Son científicas y tecnólogas, socias de AMIT (Asociación de Mujeres Investigadoras y Tecnólogas), las que responden a esas dudas. Envía tus preguntas a nosotrasrespondemos@gmail.com o por Twitter #nosotrasrespondemos.

Coordinación y redacción: Victoria Toro