Algoritmos genéticos e imágenes

3 08 2013

Hace ya bastante tiempo vi la película Tron: The legacy, y escuché que decían algo sobre algoritmos genéticos. Le pregunté a mi hermano, que entonces seguía viviendo aquí y me explicó que son bastante simples y sirven para encontrar algo así como una solución a cierto problema, tal vez no óptima pero intentando serlo, con un método un poco más simple que el que implicaría encontrar una solución óptima.

La idea era la siguiente: Se crea una población inicial random y se evalúa con el objetivo al que se quiere llegar, se toma el mejor o un conjunto de los mejores elementos de la población y se mezclan para generar una nueva generación, poniendo partes de uno y de otro aleatoriamente y añadiendo un pequeño cambio aleatorio también, que es lo que le permite evolucionar, y se sigue el proceso una y otra vez.

Después de eso decidí hacer un programa simple, que de un conjunto de series de letras aleatorias, llegara por medio de un algoritmo genético a mi nombre. En realidad no siempre llegaba porque a veces faltaba alguna letra, pero llegaba a algo bastante parecido.

El programa genera una población inicial de 50 000 cadenas de caracteres y elije las 2 que más se parecen a mi nombre y las combina, haciendo 400 nuevas cadenas de caracteres, y esas cifras hacen que converga muy rápidamente, pero también que le hagan falta letras para formar la palabra final. Un ejemplo:

$ python ejemplo1.py
GENERACION 0
Padre: elbtwro (8)    Madre: aeborkt (8)
GENERACION 1
Padre: albtrko (10)    Madre: albelro (10)
GENERACION 2
Padre: alberko (11)    Madre: alberro (11)
GENERACION 3
Padre: alberko (11)    Madre: alberro (11)

A la tercera generación llega al resultado final, pero no es la solución óptima. Con eso aprendí que el diseño de la función de evaluación y la función de apareamiento es muy importante para que el algoritmo converja.

Después de ese primer programa ya tenía una idea de cómo funcionaban los algoritmos genéticos y decidí hacer otro que generara una imagen que diera la misma sensación luminosa que una imagen dada. Es decir, que si se transformara a escala de grises fuera igual que la original transformada a escala de grises también, sólo que la nueva imagen hecha con colores aleatorios.

Usando una imagen de 20×20 pixeles, después de más de 700 generaciones y N horas de procesamiento, el resultado es el siguiente:

Imagen Introducida                                       Resultado

imagen-original   geneticos

 

 

 

 

 

 

Como reflexión sobre el proceso, creo que podría mejorar si se evalúa cada siguiente generación conforme van “naciendo” los hijos, y si es mejor que los padres pasar a la siguiente generación, lo que generaría generaciones de diferentes tamaños cada vez, y lo que podría agilizar el programa. También podría ser que se evolucione la imagen pixel por pixel, y quizá podría ser más rápido, pues tal vez sea más rápido alcanzar 400 combinaciones de 3 números que una combinación de 1200 números. Cosa de probar…


Acciones

Information

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




A %d blogueros les gusta esto: