Monday, September 6, 2010

Genetic Madness: Hide & Seek

Hace un tiempo vengo desarrollando (de gusto, no es que el mundo lo necesite) un framework de Algoritmos Genéticos (GA, por sus siglas en inglés) en Python. Si mal no recuerdo, lo empecé a armar estando en India, ya que lo necesitaba para el trabajo que estaba haciendo allá.

Para los que no sepan qué corno son los GA (y no fueron lo suficientemente curiosos para abrir el link a wikipedia que puse antes), la idea básica es que es un método de optimización algorítmico basado en la selección natural darwiniana. Uno opera sobre una población de soluciones a un problema, selecciona los más aptos (usando una función de fitness que nos dice qué tan buena es una solución), y los combina para obtener una nueva población, agregando alguna que otra mutación cada tanto para hacerlo más divertido :P. Con el correr de las generaciones simuladas, los individuos tienden a aumentar su aptitud (esto es, son mejores soluciones para nuestro problema!).

Hace aproximadamente un mes leí un gran libro referido al tema, escrito por David Goldberg, lo cual me dio un mejor fundamento teórico para mejorar el framework. Tuve ganas de hacer algo así como un juego, muy simple, que use los conceptos de GA, para poder enseñarle a alguien que no tiene idea de programación cómo opera un algoritmo genético. No se me ocurrieron muchas aplicaciones divertidas de GA como para llegar a llamarlas juego, pero uno de los experimentos que hice me pareció interesante como para compartirlo en el blog. La idea básica del programa es la siguiente:

Usando pygame, crea mini ventanitas de distintos colores (sin bordes ni "header", solo cuadraditos de colores). Al clickearlas, se cierran, y es como si el usuario "matara" esa ventanita. Un algoritmo genetico evoluciona la posicion y el color de las ventanitas, donde una ventanita se considera más apta que otra si  perduró más tiempo en el desktop sin ser clickeada. Cada generación dura hasta que no quedan más ventanitas vivas, tras lo cual se reinicia el ciclo (la nueva población de ventanitas se obtiene usando los métodos de selección, mutación y crossover típicos en los algoritmos genéticos).

El resultado: el comportamiento emergente es que las ventanitas se esconden en los iconos del escritorio y se mimetizan con tu desktop (tienden a tener los colores de tu background). Esto quiere decir que mientras más jugás los colores más tienden a ser los de tu background, por evolución artificial... no sé si me expliqué bien pero en este screenshot se ve: (acá está la versión grande)
Probé con varios tipos de fondos de pantalla, pero usando un color simple se ve más claramente. Fue divertido ver como, partiendo de una población inicial de ventanas ubicadas al azar y con colores totalmente aleatorios, de a poco se tendía a que las ventanas imiten el color wallpaper (haciéndolas más difíciles de ver) y se ubiquen en los bordes (llamando menos la atención).

El experimento es muy simple y podría ser refinado de infinitas maneras, pero me pareció una linda forma de mostrar cómo actúa la selección "natural" en cualquier ambiente en el que haya variación y presión sobre los individuos.


Por si a alguno le interesa, acá está el proyecto open-source del framework, actualmente en un muy temprano estado de desarrollo. Pueden bajarse el código de ahí y correrlo en sus máquinas... Y si alguno quiere colaborar con el proyecto no dude en contactarme!

Saludos,
Manuel