Los algoritmos genéticos forman parte fundamental de las técnicas de inteligencia artificial e intentan replicar computacionalmente comportamientos biológicos. Fueron impulsados en los años 60 por John Holland, aunque no fue hasta finales de los 80 cuando alcanzaron una masa crítica en los círculos académicos. Son el máximo exponente de lo que se considera la computación evolutiva.
Estos algoritmos intentan encontrar soluciones óptimas a problemas. Para saber si una solución es mejor que otra se utiliza una función de fitness, de manera que se puede pensar en ellos como mecanismos para resolver problemas de optimización de funciones (por ejemplo, ¿cuál es el valor de x que minimiza la función f(x)=x²?).
Su funcionamiento es sencillo. Parten de una población de posibles soluciones al azar y, en cada iteración, cruzan a sus individuos para generar una nueva población con sus descendientes. Los progenitores se escogen en función de lo buenos que son respecto a la función de fitness: cuanto mejor sea un individuo (más apto), más probable es que sea escogido. Típicamente dos progenitores generan dos descendientes. Muy de vez en cuando se introducen mutaciones en los descendientes para acelerar la convergencia e intentar alcanzar la solución óptima.
La forma más simple de algoritmo genético puede describirse así:
Por tanto, un algoritmo genético realiza tres tipos de operaciones: selección, cruce y mutación.
- Selección: escoge individuos (también llamados cromosomas) entre la población para la reproducción. Cuanto más capaz sea el cromosoma (tenga mejor fitness), más veces será seleccionado para reproducirse.
- Cruce: su labor es elegir un lugar y cambiar las secuencias antes y después de esa posición entre dos cromosomas para crear nueva descendencia.
- Mutación: produce variaciones de modo aleatorio en un cromosoma.
Una importante cualidad de los algoritmos genéticos es que son capaces de realizar búsquedas masivas en paralelo. Esto, junto al hecho de que muchos problemas se pueden expresar en términos de optimizar una función, hace de ellos una buena opción cuando no hay algoritmos eficientes específicos para el problema o es suficiente con encontrar una buena solución aunque no sea la óptima. Por ello, tienen aplicación en muchísimos ámbitos, como el aprendizaje automático de robots, la desambiguación de términos en procesamiento de lenguaje natural, la construcción de horarios en centros de estudio para evitar conflictos o la generación de composiciones musicales automáticas (creatividad artificial). La NASA ha diseñado algunas antenas de sus naves espaciales con técnicas de computación evolutiva.
Veamos un ejemplo: imaginad que elegís una frase cualquiera y que el algoritmo genético tiene que adivinarla. Comienza con una población de frases (cadenas de caracteres) al azar, de la misma longitud que la frase objetivo. Dada una cadena, lo que recibe el algoritmo es información acerca de lo parecida que es a la frase objetivo (es decir: su fitness). La elección de la función de fitness es crucial. Una medida sencilla para saber lo ajustada que está una cadena a la frase objetivo es medir el número de letras correctas que tiene. Esta medida funciona mal con cadenas muy largas porque las diferencias se hacen excesivamente pequeñas. La manera de resolverlo es tomar la potencia de 2 de dicha medida. Es decir, nuestra función de fitness es la siguiente:
Por ejemplo, si nuestra frase objetivo fuera HOLA MUNDO, la frase HALA MANDO tendría un fitness de 256 al tener ocho letras correctas.
Una vez seleccionados dos progenitores según su fitness, lo siguiente es cruzarlos para generar dos descendientes. Esta operación (llamada crossover) es muy sencilla: basta con elegir aleatoriamente un punto de cruce e intercambiar las subcadenas como muestra el siguiente diagrama:
Los hijos generados se pueden mutar, lo que consistiría en cambiar alguno de sus caracteres por otro al azar. Tanto el cruce como la mutación no se hacen siempre: típicamente se utiliza una probabilidad muy alta para la operación de cruce y muy baja para la mutación. Si no se realizan ni el cruce ni la mutación, los dos progenitores pasan a la siguiente generación intactos.
Lo mejor es verlo con un ejemplo. Supongamos que la frase elegida es EN BOCA CERRADA NO ENTRAN MOSCAS, que tiene una longitud de 32 caracteres. Para crear una frase en nuestro idioma vamos a utilizar 28 caracteres: nuestras 27 letras junto con el espacio (no tenemos en cuentas las minúsculas). Con ellos se podrían generar 28³² frases distintas de longitud 32, cuyo valor es igual a:
20.373.094.654.699.866.980.264.680.600.446.288.486.804.686.204
Para entender lo grande que es este número, supongamos que pudiéramos trabajar con el Sunway TaihuLight, uno de los superordenadores más potentes del mundo. Este ordenador hace 93.000 billones de operaciones por segundo. Evaluar a esa velocidad el fitness de todas las frases posibles le llevaría 6.946.522.511.463.216.578.460 años: más de 500.000 millones de veces la edad estimada del universo. La fuerza bruta queda completamente descartada.
Un algoritmo genético lo consigue en unas cuantas iteraciones. Con una población de 500 frases, una probabilidad de cruce del 75% y una probabilidad de mutación del 1% conseguimos los siguientes resultados (tabla resumida):
Nuestro algoritmo consigue llegar a la solución óptima en 42 iteraciones, lo que tarda apenas diez segundos en un portátil convencional. Las mejores frases introducen innovaciones que provocan incrementos en el fitness medio de toda la población. Esto se traduce también en incrementos sucesivos de su valor máximo.
Es muy importante elegir bien los parámetros del algoritmo, que en nuestro caso son el tamaño de la población y las probabilidades de cruce y de mutación. La siguiente tabla muestra el número medio de iteraciones hasta conseguir el óptimo para diversos valores de esos parámetros (en amarillo los valores que elegimos previamente):
Éste es un ejemplo ilustrativo, inspirado en The Computational Beauty of Nature, un maravilloso libro de Gary William Flake que recomiendo encarecidamente. Aunque en la vida real los problemas son mucho más complejos, sirve perfectamente para describir las características y funcionamiento de un algoritmo genético. He programado el experimento en R y, como siempre, compartiré el código con todo aquel que me lo pida.
Imagen: special for you/shutterstock
Soluciones y Sectores
Te puede interesar
-
Edificios sostenibles para un turismo más inteligente y competitivo
El sector turístico representó el año pasado el 12,2% del PIB en España. Se trata, por tanto, de un ...
-
La capacitación en industria 4.0, condición sine qua non para su transformación
Recientemente leía un artículo sobre “Desafíos de la industria europea en la nueva coyuntura socioeconómica”. En él se apuntaba, ...
-
Hospitalización domiciliaria: un nuevo paradigma en la gestión de pacientes crónicos
Como explicaba en un post anterior, asistimos a la transformación de la atención médica para mejorar la calidad de ...
