Escrito por Alfonso Fernández en Planeta Chatbot.
Tabla de contenidos
Breve historia de los algoritmos genéticos
Los algoritmos genéticos nacieron en los 1970 gracias a John Henry Holland. Son básicamente una estrategia usada para problemas de búsqueda del óptimo basado en una heurística aleatoria. La idea consiste en simular la selección natural. La población inicial irá evolucionando a través de variaciones emergentes de cruces de los más aptos y de mutaciones.
Los pros y contras de estos algoritmos son básicamente:
- Pros: (1) Más rápido que otros algoritmos. (2) Es sencillo. (3) Si la representación vectorial del individuo es correcta podemos encontrar una solución sin un trabajo de análisis muy profundo.
- Contras: (1) Heurística aleatoria, no tiene por qué encontrar el óptimo. (2) No es un algoritmo completo (no siempre encuentra una solución adecuada). (3) En ocasiones puede atascarse con máximos locales. No obstante, la operación cruce/crossover (que veremos más adelante) ayuda a mitigarlo, aunque esto implique más iteraciones.
Principios básicos
Dentro de los algoritmos genéticos existen diferentes tipos e implementaciones. Mostramos dos de los más empleados.
Metodología basada en teoría de la evolución de Darwin:
- Población inicial.
- Evaluación de la capacidad de adaptación.
- Selección y cruce.
- Mutación.
- Reorganización de la población con las nuevas generaciones.
Metodología anterior añadiendo las teorías de Lamarck:
- Población inicial.
- Adaptación Lamarckiana.
- Evaluación de la adaptabilidad.
- Selección y cruce.
- Mutación.
- Reorganización de la población con las nuevas generaciones.
La adaptación cromosómica lamarckiana puede ser llevada a cabo con algoritmos de optimización de búsqueda local, por ejemplo el algoritmo Hill climbing. Esta adaptación afecta a nivel genético y, por lo tanto, es transmitida a siguientes generaciones.
Efecto Baldwin: Es un efecto interesante. Describe el efecto del comportamiento aprendido en la evolución. Básicamente nos dice que, la capacidad de aprender nuevos comportamientos productivos afectará al éxito reproductivo del individuo y, por lo tanto, ayudará a mejorar las oportunidades de reproducción, “maquillando” su carga genética.
Desde un punto de vista práctico, la aplicación de las teorías de Baldwin implica una implementación más pasiva de la adaptación. Esto quiere decir que, aunque una generación pueda sufrir adaptaciones hacia un óptimo, estas, no se trasladarán a las siguientes generaciones. Sin embargo, sí mejorarán los resultados en la evaluación de adaptabilidad.
Una librería que nos puede facilitar la vida, DEAP
A la hora de trabajar con algoritmos genéticos tenemos que tener en consideración qué herramienta software empleamos. Existen diversas opciones, hemos escogido la librería DEAP de Python por su sencillez. A no ser que necesitemos personalizar mucho nuestro algoritmo, escoger una librería testada siempre será un buena idea.
Un caso de uso en el entorno organizacional
Este artículo solamente tiene fines didácticos, por lo que extrapolaremos un ejemplo conocido en la comunidad especializada en este campo, “one max problem”. Crearemos una población de individuos consistentes cada uno en una secuencia aleatoria de 0 y 1. Posteriormente, dejaremos que nuestra población evolucione hasta que alguno de sus miembros alcance el máximo número de 1 posible en su secuencia.
El código base sobre DEAP-Phyton lo tenemos en esta página.
Supongamos que cada individuo está representado por un vector de 0 y 1 de tamaño 100, que representan 100 características de comportamiento. El vector será 1 si el individuo la posee y 0 si no. Organizacionalmente, el comportamiento ideal será cien “1”, y el más pobre cien“0”. Definamos los componentes básicos del algoritmo:
- Representación individuo: I1= [1 1 1 0 0 0 … 0 0 1]
- El óptimo: O= [1 1 1 1 1 1 … 1 1 1]
- Test solución: Daremos una solución por válida si la distancia manhattan al óptimo es de 10 o menos.
- Funciones de variación: Mutación, cruce y adaptación lamarckiana.
- Expondremos dos casos: Uno con adaptación lamarckiana afectando a sólo el 5 % de la población en cada iteración, y modificando el 1% de su genoma; y otro caso sin adaptación lamarckiana.
- Función de aptitud: Emplearemos una métrica sencilla, la distancia Manhattan. dm1 (I1, O)= |Ii1-O1| +|Ii1-O1|+|Ii2-O2|+ …+|Ii100-O100|. En este caso coincide con 100 menos la suma de todos los bits de la secuencia del individuo.
- Tamaño de la población: La organización la componen 10 y 100 individuos.
- Las nuevas generaciones sustituirán a las generaciones anteriores.
Resultados de la simulación
Siguiendo las instrucciones de la librería implementamos el código necesario para hacer correr las simulaciones definidas más arriba.
- Simulación sin algoritmo lamarckiano y población=10
— Generation 1467 —
Min 87.0
Max 90.0
Avg 88.5
Std 0.8062257748296293
- Simulación sin algoritmo lamarckiano y población=100
— Generation 46 —
Min 81.0
Max 90.0
Avg 88.92
Std 0.8084553172560881
- Simulación con algoritmo lamarckiano y población=10:
— Generation 452 —
Min 89.0
Max 90.0
Avg 89.1
Std 0.30000000000175836
- Simulación con algoritmo lamarckiano y población=100:
— Generation 28 —
Min 87.0
Max 90.0
Avg 88.45
Std 0.5361902647376715
Estos datos corresponden solamente a una simulación, por lo que solo se podría sacar alguna conclusión cualitativa evidente:
- Cuando aumentamos la población la convergencia es más rápida.
- La introducción de un factor leve de evolución lamarckiana también favorece la velocidad de convergencia.
Conclusiones
Lo más interesante de este ejercicio es, además de conocer la existencia de esta tipología de algoritmos, ver cómo existen herramientas de optimización que nos permiten, en algunos casos, obtener buenos resultados cuando tenemos una limitación de recursos temporales y económicos.
No obstante, y volviendo a los contras, es un algoritmo que no siempre encontrará el óptimo, incluso no siempre obtendrá una solución factible. Puede atascarse con la problemática de máximos locales, y la representación del problema en genéticas e individuos no es muy sencilla. Además, no es demasiado intuitivo (si no tienes suficiente experiencia) parametrizar datos como la tasa de mutación, tamaño de la población, tasa de restitución …
Referencias
Darwin, Lamarck, or Baldwin: Applying Evolutionary Algorithms to Machine Learning Techniques: http://ieeexplore.ieee.org/document/6927659/
Deap homepage documentation: http://deap.readthedocs.io
Wikipedia reference: https://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico