Universidad Simón Bolívar Laboratorio de Algoritmos y Estructuras I CI2691
Trimestre Enero-Marzo 2021
Profesora: Carolina Chang
Alumno: Miguel Cordero
Carnet: 15-10326
Proyecto I
Introducción a los Algoritmos Genéticos¶
¿Qué son los Algoritmos Géneticos?¶
Los Algoritmos Genéticos son métodos que pueden usarse para resolver problemas de búsqueda, y optimización del resultado. Su nombre deriva de la similitud con el proceso evolutivo de los seres vivos donde las poblaciones evolucionan según los principios de Selección Natural y Supervivencia del más Fuerte como estableció Charles Darwin.
Estos algoritmos genéticos necesitan una población inicial de posibles soluciones al problema que irán evolucionando hacia valores más próximos al óptimo dependiendo de cuál sea el problema planteado y la programación respectiva.
Ese es el objetivo principal de implementar los Algoritmos Genéticos, obtener la mejor solución a un problema que por otros métodos pudiera resultar más complicado
¿Cómo funcionan?¶
Fase de Codificación¶
Al igual que en la evolución de los seres vivos, lo primero que se necesita es representar cual sería una posible solución al problema. Es decir, establecer como serán los Individuos con los cuales se trabajaran.
Para ello, según el problema que se vaya a resolver se define el Cromosoma, en nuestro caso la representación en forma computacional de cada individuo para que el algoritmo lo puede interpretar, generalmente se trata de una matriz, una lista, tuplas etc. (si en la película The Matrix éramos 0s y 1s no es muy distinto a lo que se hace con los algoritmos genéticos).
Por su parte, cada entrada de nuestro cromosoma va a representar lo que a nivel biológico se conoce como Gen y al conjunto de genes se le conoce como Genotipo mientras que su representación visual es el Fenotipo de dicho individuo.
Definidos a los individuos se necesita crear una Población Inicial o conjunto al azar de individuos, cada uno de los cuales representa una posible solución al problema dado.
Fase de Evaluación¶
Asi como en la naturaleza las características de cada individuo determinan que tan buena será su adaptación a las condiciones del ambiente en el que se desarrolla. En los algoritmos genéticos también es posible determinar que tan bueno es cada individuo como solución al problema y se realiza mediante un función llamada Fitness que permite cuantificar cuan optima es la solución generalmente en comparación con una referencia dada. Es ¡La clave! del algoritmo génetico porque es la base en la toma de decisiones de las siguientes fases.
Dependiendo de como se programe, lo que hace es asignar un rango de valores a cada individuo y que por ejemplo puede estar entre 0 y 1, en porcentaje de 0 a 100 etc, tal que que si el valor del Fitness es cercano a 0 mejor es la solución y mientras mas cercano a 1 menos optima es (o viceversa).
Lo importante es que una vez definido la función fitness podemos ver si deseamos Maximizar o Miniminzar nuestra función, es decir, si buscaremos aquellas soluciones cuyo fitness sea el mas alto o aquellas que tengan el fitness mas bajo, respectivamente. Ejemplo de gráfico de minimización:
Cabe destacar que todos los problemas tienen una función fitness propia y que depende de lo complejo de la solución o del problema a resolve.
Fase de Selección¶
El siguiente paso es el proceso de Selección, durante esta fase se realiza la evaluación de cada individuo para determinar cuales son los más aptos para Reproducirse y generar nuevos individuos. Esto lo determina el fitness que cada individuo presenta, como bien ocurre en la naturaleza el mejor adaptado tiene más posibilidades de reproducirse.
En los algoritmos genéticos hay varios métodos de selección que permiten imitar este comportamiento de selección “aleatoria”, se conocen como Roulette Wheel o Rueda de la Ruleta, Tournament Selection o Selección por Torneo, Elitism o Elitismo, entre otros.
Como este proyecto es una versión "simple" de un algoritmo genético implementaremos sólo dos métodos selección por Torneo y Elitismo
Selección por Torneo¶
Como su nombre lo indica se trata de elegir al azar una cantidad finita de individuos de la población, entre los seleccionados se compara su fitness y el que mayor fitness tenga es el que resulta seleccionado para reproducir una nueva generación, es una especie de competencia.
Este proceso se repite hasta tener o bien un conjunto variado de individuos seleccionados o hasta tener un par de individuos que serán los que representen a los padres de la nueva generación.
Elitismo¶
El elitismo, se basa en la teoría de la Supervivencia del Más Fuerte, en este técnica sólo los mejores individuos de la población sobreviven hasta la próxima generación y sin sufrir ningún tipo de cambio.
La utilidad de esta técnica es que permite que las mejores soluciones (la élite) no se pierdan durante el proceso de Cruce y Mutación pero aún tienen la posibilidad de ser elegidos para reproducirse, sin embargo, es importante que la elite no sea muy grande para garantizar la diversidad de la población.
Fase de Reproducción, Cruce o Crossover¶
Durante la fase de Cruce los padres seleccionados combinan su características genéticas para producir una Descendencia que conformorá una nueva población de soluciones que en promedio será mejor que la anterior generación porque obtiene las mejores características de cada padre.
Las técnicas para realizar Cruce en algoritmos genéticos son variadas al menos nueve (9), algunas son Cruce por un Único Punto o Single Point Crossover, Cruce por dos puntos o Two Points Crossover, entre otros. Pero el método puede variar de acuerdo al problema y la especificación del individuo, lo importante es garantizar que la descendencia sea variada para asegurar que se cubra todas las posibles soluciones al problema.
A diferencia de la reproducción natural, el cruce no se aplica a todos los pares de individuos que han sido seleccionados para emparejarse, sino que se aplica de manera aleatoria con un alta probabilidad de que ocurra, pero en caso de no ocurrir, la descendencia se obtiene simplemente duplicando los dos padres seleccionados en ese momento en la siguiente generación.
En este proyecto se aplicará el Cruce por dos puntos, que consiste en seleccionar dos puntos al azar en el cromosoma del padre dividiéndolo asi en tres secciones. Luego, se copia una seccion de sus genes en las respectivas posiciones de uno de los dos hijos que se generan y de forma intercalada (una seccion es del primer padre, la segunda seccion es del segundo padre, y asi hasta completar todos los genes).
Fase de Mutación¶
Teniendo a la nueva descendencia, se realiza el proceso de Mutación.
La mutación no es mas que alterar uno o varios de los genes del individuo de forma aleatoria y con una muy baja probabilidad de que ocurra, en la naturaleza suele ocurrir en el momento de la reproducción por lo que sólo afecta a la descendencia y el cambio producido puede ser o no beneficioso para el individuo, no hay forma de garantizarlo pero siempre se espera que sea un cambio favorable porque el cambio busca mejorar su adaptabilidad al ambiente que lo rodea.
En los algoritmos genéticos el procedimiento no es muy diferente, sin embargo, se realiza luego de tener a la descendencia, y no necesariamente se mejora al individuo luego de la mutación.
Fase de creación de una nueva generación¶
Finalmente, la combinación de la elite en caso de existir y la descendencia luego de la mutación, conforma un nueva población de posibles soluciones que debe ser igual en tamaño a la población inicial.
Esta nueva generación reemplaza la población anterior y se repite el ciclo desde la evaluación del fitness en adelante y si el proceso ha sido ejecutado de manera adecuada la nueva población presentará mejores características en comparación con la anterior.
Y esto se debe a que con cada generación las buenas características se propagan a traves de la descendencia y la elite asegurando que cada generación se acerque más y más a la solución optima es lo que se conoce como Convergencia del Algoritmo.
Este ciclo se repite o bien hasta alcanzar un determinado número de generaciones o hasta llegar a la solución óptima.
Aplicacion del Algoritmo Genético en la Reconstrucción de Imágenes¶
Problema a resolver¶
El objetivo es el siguiente: recrear por medio de polígonos, formas o figuras, una imagen dada por el usuario.
Si bien existen programas desarrollados en otros lenguajes de programación, e incluso librerías especificamente diseñadas para resolver este tipo de problemas utilizando algoritmos genéticos, se quiere en esta ocasion desarrollar las funciones desde cero, siguiendo la teoría previamente dada y limitando el uso de las librerías a lo estrictamente necesario.
En este caso al procesamiento de imágenes, matrices, gráficas y números aleatorios que es lo que manejaremos durante el proyecto.
Adicionalmente, se aplicaran tecnicas de análisis descendente, correctitud de las funciones y procedimientos, y la documentación adecuada. Temas vistos y evaluados en el desarrollo del curso de Algoritmos y Estructuras I CI2691 de la Universidad Simón Bolívar.
Las imágen que se quiere reconstruir es:
La Mona Lisa, que sirvió de ejemplo inicial y motivación.
Y estás dos son de amigos que ofrecieron sus trabajos para la prueba de este algoritmo:
Imagen, por Castellano, Pedro.
Imagen, por Pinto, Luis.
Librerías utilizadas¶
Numpy y Copy permiten manipular las matrices, como ordernar sus elementos o copiar por completo toda una matriz en otra variable
import numpy as np
import copy
La librería Random permite generar números o listas con relativa aleatoriedad será útil para incluir cierto grado de probabilidad en el algoritmo
import random
Librerías especializadas en el manejo de imágenes y gráficos
Matplolib, Ipython y Time permite generar gráficas de los datos generados y se vayan actualizando conforme avancen las generaciones
import matplotlib.pyplot as plt
from matplotlib import colors
%matplotlib inline
from IPython.display import clear_output
from time import sleep
Skimage nos permitirá leer imágenes desde una URL guardar esa imagen como una matriz de números reales, junto con Pil podremos ver las gráficas de cada individuo o su fenotipo. Skimage nos ofrece dos funciones esenciales para el algoritmo: Structural Similarity y Mean Squared Error que serán dos opciones para evaluar como se diferencia una imagen de la otra, es decir,nos dará nuestra función fitness.
Imageio nos permitirá guardar las imágenes como gif.
from skimage.metrics import structural_similarity as ssim, mean_squared_error as mse
from skimage import io , color, img_as_float
from skimage.transform import resize
from PIL import Image, ImageDraw
import imageio
Os es una librería opcional, que se implementa por las limitaciones de Google Colaboratory (COLAB) para almacenar la informacion, con mkdir se creará una carpeta local donde se guardaran las imágenes temporalmente mientra dura la sesión.
import os
from os import mkdir
Aplicación y sus respectivas fases¶
Codificacion¶
Genes, Genotipo e Individuo¶
Como buscamos recrear una imagen utilizando triángulos de diferentes tamaños, colores y transparencias.
Los individuos o posibles soluciones serán imágenes de 200x200 pixeles conformadas por un número finito de triángulos.
En esta representación el Individuo tendrá por cromosoma una lista de triángulos creados de manera aleatoria. Siendo los Genes, cada uno de los triángulos.
Y como para representar visualmente a un triángulo se necesita de tres vértices y un color con transparencia, es decir, en formato RGBA, cada triángulo será a su vez una lista de 10 elementos a saber:
$$ triángulo=[x_1, x_2 , y_1, y_2, z_1 ,z_2, R, G, B, A]$$Donde:
$x_i,y_i$ con $0\leq x_i, y_i\leq200$ representan las coordenadas de un vértice del triángulo en un cuadro de 200x200 unidades. $R,G,B,A$ representan un color y su respectiva intesidad de colores Rojo (Red), Verde (Green), Azúl (Blue), Transparencia (Alpha)
El Genotipo en este caso será la lista completa de todos los triángulos en forma matricial.
#Demostración del genotipo de un individuo con 10 triángulos aleatorios
#Correr varias veces esta celda para obtener diversos resultados
individuo_de_prueba=genes(10)
#Para visualizar mejor al individuo se utiliza numpy
individuo_de_prueba=np.asarray(individuo_de_prueba)
print(individuo_de_prueba)
Fenotipo¶
Para representar visualmente a un individuo es necesario leer la información del cromosoma triángulo por triángulo para ir contruyendo la imagen final que representa al individuo. Esto es, pasar de una matriz a un gráfico que permita luego la comparación entre la imágen original y la población.
Cabe destacar que estos triangulos se grafican sobre un fondo negro para facilitar el contraste de los colores pero no es determinante para el resultado del algoritmo ya que los triangulos adoptadoran los colores de la imagen de referencia (si el algoritmo es correcto).
# Demostración del fenotipo del individuo de prueba obtenido anteriormente
fenotipo_de_prueba=fenotipo_transparencia(individuo_de_prueba)
plt.axis('off')
plt.imshow(fenotipo_de_prueba)
Población Inicial¶
La población incial dependerá del numero de individuos o posibles soluciones con las que cuales el algoritmo iniciará la búsqueda de la imagen mas óptima.
Como se sugiere contar con poblaciones realtivamente grandes, se inicia por defecto con 200 individuos para asegurar que se cubra una buena cantidad de soluciones. Cada individuo contará con un número entre 20 y 100 triángulos, ya que si son muy pocos se puede perder un poco la definición de la imagen e incluso llegar muy rápido a un mínimo o máximo local (ya no se consegueriran mejores individuos en las próximas generaciones), pero si son muchos el algoritmo puede tardar en alcanzar una solución aceptable.
La población inicial será por defecto una lista de 200 individuos, cada uno con 50 triángulos para evitar que converga aceleradamente y le tome menos tiempo modificar a la población.
# Demostración de una población de 10 individuos y 10 triangulos
poblacion_de_prueba=crear_poblacion(10,10)
#Para visualizar mejor el genotipo de la población (lista de individuos)
poblacion_de_prueba=np.asarray(poblacion_de_prueba)
print(poblacion_de_prueba)
#Para visualizar el fenotipo de la poblacion (lista de imágenes, una por individuo)
mostrar_poblacion(poblacion_de_prueba)
Evaluación¶
Para la evaluación del fitness de cada individuo necesitamos comparar dos imagenes, la de referencia y el fenotipo del individuo.
Existen varias formas y/o fórmulas que permiten comparar dos imágenes. Dos de ellas, las mas comunes son, Error de la Media Cuadrática-MSE por sus siglas en ingles de Mean Squared Error y Similitud Estructural-SSIM por sus siglas en ingles de Structural Similarity.
El MSE mide la diferencia entre dos imágenes pixel por pixel, por lo que requiere que ambas imágenes sean de las mismas dimensiones. Si ambas imágenes son identicas su valor será $0.0$, y será $1.0$ si son totalmente diferentes. La fórmula está definada por la siguiente expresión: $$MSE=1/n \sum\ (x-\bar{x})^2$$ Donde $x$ representa los valores $(R,G,B)$ de la imágen original para un pixel, $\bar{x}$ los valores del pixel correspondiente del individuo, y $n$ es el número de pixeles a comparar.
Está será la función que se implementará para medir el fitness de los individuos. Que nos permitirá minimzar los valores del fitness hasta llegar a 0.
En cambio, el SSIM considera los cambios en la información estructural de cada imagen, junto con el contraste y el brillo, entre porciones de igual tamaño entre las imágenes a comparar. El SSIM asigna valores entre $[-1,1]$ siendo 1 si ambas imágenes son iguales. Y su fórmula está dada por: $$SSIM(x,\bar{x})=\frac{(2 \mu_{x}\mu_{\bar{x}}+c_{1})(2\sigma_{x\bar{x}}+c_{2})}{(2 \mu_{x}^2+\mu_{\bar{x}}^2+c_{1})(\sigma_{x}^2+\sigma_{\bar{x}}^2+ c_{2})}$$
Donde:
$\mu_{i}$ es el valor promedio para $x$ y $\bar{x}$;
$\sigma_{i}^2$ es la varianza respecto de $x$ y $\bar{x}$;
$\sigma_{x\bar{x}}$ es la covarianza de $x$ y $\bar{x}$;
$c_{i}$ son constantes que dependen de los pixeles en las imágenes.
Fitnes Poblacional y por Individuo¶
# Se escoge como demostración la imagen del primer individuo
imagen_a_comparar=fenotipo_transparencia(poblacion_de_prueba[0])
# La funcion fitness debe retornar 0.0 cuando se compara una imagen consigo misma
fitness_de_prueba=fitness(imagen_a_comparar,imagen_a_comparar)
print(f'La comparación de una imágen consigo misma dio como fitnes: {fitness_de_prueba}')
# Se comparan los individuos de la población anterior con el seleccion:
fitness_de_la_poblacion_de_prueba=fitness_poblacion(imagen_a_comparar,poblacion_de_prueba)
# Para visualizar mejor los resultados, note que el primer valor es 0. por comparse
# el primer individuo consigo mismo. El resto de los valores está entre 0.0 y 1.0
fitness_de_la_poblacion_de_prueba=np.asarray(fitness_de_la_poblacion_de_prueba)
print(fitness_de_la_poblacion_de_prueba)
Selección¶
Para selección se utilizaran las técnicas de Elitismo y Selección por Torneo.
Con el elitismo se busca garantizar que las mejores soluciones de cada generación se mantengan en la siguiente, para garantizar que siempre se mejore el fitness y el algoritmo converga. Por defecto el valor escogido es de un $20\%$ de la poblacion, para dejar paso a una descendencia variada.
Con la selección por torneo, se busca que individuos al azar puedan ser elegidos para el cruce. El tamaño del torneo es 3, para mejorar el tiempo de ejecución del algoritmo ya que es un método lento de selección pero que se compensa con la variedad génetica que produce.
Elite y Torneo¶
# Obtenemos a los mejores 3 fitness de la población anterior
elite_de_prueba, fitness_obtenido =orden_elite(poblacion_de_prueba,fitness_de_la_poblacion_de_prueba,3)
elite_de_prueba=np.asarray(elite_de_prueba)
print(elite_de_prueba)
print(f'\n Y sus fitness fueron: {fitness_obtenido}')
# Para demostrar la selección por torneo puede correr esta celda varias veces
padre_1_de_prueba=seleccion_torneo(poblacion_de_prueba,fitness_de_la_poblacion_de_prueba)
print(padre_1_de_prueba)
Cruce¶
El cruce para cada generación se realiza por medio de Cruce por dos Puntos, estos puntos son seleccionados al azar en un rango que va desde $1/3$ a un $2/3$ de la longitud del cromosoma de cada individuo. Los puntos seleccionados no pueden ser los mismo porque se trataría del cruce por un punto. Y tampoco pueden coincidir con los entremos del cromosoma para evitar que se copie por completo a uno de los padres.
Se fija una probabilidad por defecto de $0.9$ o $90\%$, donde si un valor arbitrario entre $0.0$ y $1.0$ es menor que $0.9$ el cruce ocurre, en caso contrario, los padres son copiados directamente a la nueva generación, siguiendo la teoría dada anteriormente.
Los individuos que se combinaran en cada cruce son seleccionados cada uno por torneo, para aumentar la variación génetica de cada generación.
El cruce se realiza hasta alcanzar el tamaño maximo de la población.
Cruce por dos puntos¶
# Para probar esta función el radio de cruce está fijo 0.99 de probabilidad
# Como la descendencia complementa a la elite debe obtenerse 6 nuevos individuos
# Para completar los 10 que conforman a cada población.
descendencia_de_prueba=cruce(poblacion_de_prueba,elite_de_prueba,fitness_de_la_poblacion_de_prueba,0.99)
descendencia_de_prueba=np.asarray(descendencia_de_prueba)
print(f'Se obtuvieron {len(descendencia_de_prueba)} descendientes.')
print(descendencia_de_prueba)
Mutación¶
En la mutación generalmente los cambios son pequeños pero significativos. Sin embargo, debido a la complejidad del problema los pequeños cambios alargan la convergencia del algoritmo y prolonga la duración del proceso para alcanzar una optima solución.
Por esta razón, la mutación evalua a cada uno de los genes (triágulos) de la descendencia y modifica una de sus características dependiendo de un número aleatorio entre $0.0$ y $1.0$ y un valor por defecto del $2\%$ de radio de mutación, es decir, si el número aleatorio es menor a $0.02$, la mutación ocurre.
Para evitar el estancamiento de las generaciones, producto de haber alcanzado el mayor grado de diversidad genética, el radio de mutación irá disminuyendo en $0.000001\%$ o $0.00000001$ por cada generación, esta pequeña variación asegura que el redio de mutación siga siendo una probalidad pequeña pero que asegure que el cambio ocurra cada vez con menor frecuencia.
# Esta funcion genera pequeños cambios en la descendencia, a fines de la demostracion
# se considerá una población de dos individuos como descendencia y un radio de mutación
# fijo en 0.02, se incluye la intruccion print('Ha ocurrido una mutación') para
# representar que hubo un cambio
mutacion(descendencia_de_prueba[0:1],0.02)
print(descendencia_de_prueba[0:1])
Complemento¶
Una parte importante del proceso pero que no forma parte de los algoritmos genéticos es la visualización del avance desde la población inicial hasta la solución más óptima, y que a su vez permita llevar un registro de la convergencia del algoritmo.
La función de complemento Plot permitirá representar, la imagen de referencia a la izquierda, el mejor individuo en el centro y la gráfica de los mejores fitness generación por generación (en este caso por ser un problema de minimización de la funcón fitness deberá decrecer poco a poco hasta 0.0).
Por otra parte, leer_imagen() permitirá escoger imágenes de internet escogidas por el usuario.
Las sentencias try-except se implementan como parte de la programación robusta con el objetivo de facilitar la interacción con el usuario final.
# Para demostrar esta función se utilizan ejes vacios
plot_(imagen_a_comparar,imagen_a_comparar,eje_x=[],eje_y=[],i=1,imagenes=[])
# Para probar esta función utilice la URL de una imagen en linea
# O use la imagen de la Mona Lisa por defecto copie y pegue el siguiente Link
# https://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Mona_Lisa_headcrop.jpg/481px-Mona_Lisa_headcrop.jpg
image_a_procesar=leer_imagen()
Algoritmo Principal¶
La prueba de este algoritmo está en la sección de implementación
# Función that implement Genetics Algorithm to recreate images using triangles
# in an interactive way to the user.
# Generate a final gif with the process and save pictures every 50th generation.
def algoritmo_genetico():
'''
Genetic algorithm to reconstruct an online picture input by the user.
This use polygons of three side to recreate the image.
Implement: MSE as Evaluation Fitness
Selection by tournament
Two Points Crossover
Random Mutation
return: A gif with the process and save the pictures in a folder called
AlgoritmoGenetico.
'''
x_data=[]
y_data=[]
imagenes=[]
answer='n'
######this avoid that user input wrong values to the algorithm#####
#Read the reference image to compare
while answer=='n':
try:
imagen_referencia=leer_imagen()
sleep(2)
#clear_output(wait=True)
answer=input('¿Desea inciar el Algoritmo Genético con esta imagen? y/n: ')
# Give the chance to user to interrupt the process
print('El Algoritmo Genético va a iniciar si desea detenerlo utilice la combinación ctrl+M+I\n')
except KeyboardInterrupt:
print('Ha detenido el programa')
return
# Read the number of initial solutions to evaluate
while True:
try:
num_individuos=int(input('Ingrese el número de individuos con los que desea iniciar \n (Sugerencia 200 individuos): '))
assert (num_individuos>0)
break
except KeyboardInterrupt:
print('Ha detenido el programa')
return
else:
print('El valor ingresado no es un entero')
print('Vuelva a intentarlo')
# Read the number of triangles for every individual in population
while True:
try:
num_genes=int(input('Ingrese el número de genes (triángulos) que desea para cada individuo\n (Sugerencia 75 triángulos o más): '))
assert (num_genes>0)
break
except KeyboardInterrupt:
print('Ha detenido el programa')
return
else:
print('El valor ingresado no es un entero')
print('Vuelva a intentarlo')
# Read the number of generations or iterations for the algorithm
while True:
try:
num_generaciones=int(input('Ingrese el número de generaciones que desea evaluar\n (Sugerencia 5000 0 6000 Generaciones): '))
assert (num_generaciones>0)
break
except KeyboardInterrupt:
print('Ha detenido el programa')
return
else:
print('El valor ingresado no es un entero')
print('Vuelva a intentarlo')
# Read the probability to mutate a gen in individual
while True:
try:
mutacion_rate=float(input('Ingrese un valor entre 0.0 y 1.0 para la probabilidad con la que desea que ocurran las mutaciones\n (Sugerencia 0.01): '))
assert (0.0<=mutacion_rate<=1.0)
break
except KeyboardInterrupt:
print('Ha detenido el programa')
return
else:
print('El valor ingresado no es un número real entre 0.0 y 1.0')
print('Vuelva a intentarlo')
# Read the probability to crossover two individual
while True:
try:
cruce_rate=float(input('Ingrese un valor entre 0.5 y 1.0 para la probabilidad con la que desea que ocurran los cruces\n (Sugerencia 0.9): '))
assert (0.0<=cruce_rate<=1.0)
break
except KeyboardInterrupt:
print('Ha detenido el programa')
return
else:
print('El valor ingresado no es un número real entre 0.0 y 1.0')
print('Vuelva a intentarlo')
##########
### Genetic Algorithm
try:
# Create the first generation acording to the user input
generacion=crear_poblacion(num_individuos,num_genes)
i=0
while i <= num_generaciones:
# Evaluation of population
fit=fitness_poblacion(imagen_referencia, generacion)
# Selection by elitism
elite=orden_elite(generacion,fit,int(0.2*num_individuos))
# Show the fitness individual and fitness by generations
ejemplo=fenotipo_transparencia(elite[0])
if i%50=0:
plot_(imagen_referencia,ejemplo,x_data,y_data,i,imagenes)
# Crossover the population
descendencia=cruce(generacion,elite,fit,cruce_rate)
# Mutate the offspring
mutacion(descendencia,mutacion_rate-(i*0.00000001))
# Create a new generation
elite.extend(descendencia)
generacion=elite
# Repeat the process
i=i+1
# Save the process as a gif
imageio.mimwrite(f'/content/AlgoritmoGenetico/algoritmo_prueba{i}.gif', imagenes, fps=1)
return generacion,imagen_referencia
except KeyboardInterrupt:
print('Ha detenido el programa')
return
Implementación¶
# Test del algoritmo génetico. Corra la celda anterior aunque haya corrido las celdas anteriores
# El algoritmo retorna la última generación creada y por las limitaciones de colab trabaje con generaciones
# menores a 1000 y luego con el resultado corra la celda siguiente si desea continuar evaluando generaciones.
# Puede utilizar la Mona Lisa como ejemplo:
# https://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Mona_Lisa_headcrop.jpg/481px-Mona_Lisa_headcrop.jpg
# Puede utilizar la imagen de Castellano Pedro:
# https://pbs.twimg.com/media/EyVab7zXMAACokK?format=jpg&name=medium
# Puede utilizar la imagen de Pinto Luis:
# https://pbs.twimg.com/media/EzN-wDIUcAIi_C8?format=jpg&name=small
mejor_poblacion_encontrada, imagen_de_referencia=algoritmo_genetico()
# Test del algoritmo génetico. Corra la celda anterior aunque haya corrido las celdas anteriores
# El algoritmo retorna la última generación creada y por las limitaciones de colab trabaje con generaciones
# menores a 1000 y luego con el resultado corra la celda siguiente si desea continuar evaluando generaciones.
# Puede utilizar la Mona Lisa como ejemplo:
# https://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Mona_Lisa_headcrop.jpg/481px-Mona_Lisa_headcrop.jpg
# Puede utilizar la imagen de Castellano Pedro:
# https://pbs.twimg.com/media/EyVab7zXMAACokK?format=jpg&name=medium
# Puede utilizar la imagen de Pinto Luis:
# https://pbs.twimg.com/media/EzN-wDIUcAIi_C8?format=jpg&name=small
mejor_poblacion_encontrada, imagen_de_referencia=algoritmo_genetico_anvil()
Imágenes de la implementación¶
Todas las imágenes y gif se encuentran disponibles en la cuenta de twitter del proyecto EDUGAP_USB por las siglas en ingles de Evolutionary Development Using Genetics Algorithms in Python (Desarrollo Evolutivo Usando Algoritmos Genéticos en Python)
IMAGEN DE LA MONA LISA
Algoritmo Genético Mejor Individuo de la Generación 0
Algoritmo Genético Mejor Individuo de la Generación 500
Algoritmo Genético Imágenes del Proceso desde la Generación 0 a la Generación 500
IMAGEN DE LUIS PINTO
Algoritmo Genético Mejor Individuo Generación 0
Algoritmo Genético Mejor Individuo Generación 10000
Algoritmo Genético Imágenes del Proceso desde la Generación 0 a la Generación 10000
Pruebas implementadas para definir la modificación¶
Para las pruebas de mutación se eligión la imagen de Pedro Castellano, por se la más sencilla en cuanto a colores y forma, pero con una cantidad de detalle considerable para evaluar la actuación del algoritmo para detalles como: el color de la la oreja, los rasgos faciales y las líneas del contorno.
Las condiciones de cada prueba fueron las siguientes:
Población: 200 individuos
Triángulos: 75 triangulos
Probabilidad de mutación: 0.01 o 1%
Probabilidad de cruce: 0.9 o 90%
Constante de mutación a disminuir (propia del algoritmo): 0.00000001
RESULTADOS:
Prueba utilizando la versión original de la función Mutación y aumentando generación a generación la probabilidad de que un gen mute:
Gif del proceso de esta prueba
Prueba utilizando la versión original de la función Mutación y disminuyendo generación a generación la probabilidad de que un gen mute:
Gif del proceso de esta prueba
Prueba utilizando la versión original de la función Mutación SIN disminuir generación a generación la probabilidad de que un gen mute:.
Gif del proceso de esta prueba
En el desarrollo de estas pruebas se optó por implementar una nueva función de mutación que en lugar de generar valores aleatorios en el rango completo del gen, es decir, $[0, 200]$ para los vértices y $[0,256]$ para los colores, se generara un valor al azar dependiendo del valor de cada gen en el rango de $[gen-25,gen+25]$. Esta función de mutación tiene por nombre $mutacion\_suave$.
Como en ese rango existe la posibilidad que el valor generado se salga de los limites, se aplicó la condición de que si es superior a 200 el nuevo valor del gen será 200, y de ser menor a 0, el nuevo valor del gen será 0.
A excepción de que el valor original del gen a mutar fuera 200 y 0 respectivamente.
Se realizaron las mismas pruebas que la versión original y estos fueron los resultados:
Prueba utilizando la versión "suave" de la función Mutación y disminuyendo generación a generación la probabilidad de que un gen mute
Gif del proceso de esta prueba
Prueba utilizando la versión "suave" de la función Mutación SIN disminuir generación a generación la probabilidad de que un gen mute:
Gif del proceso de esta prueba
Una última prueba se realizó utilizando un rango de $[gen-5,gen+5]$ y disminuyendo la probabilidad de mutación. Con las mismas condiciones descritas anteriormente.
Gif del proceso de esta prueba
CONCLUSIÓN
En vista de los resultados obtenidos para unas 10 mil generaciones, parece que la versión original del algoritmo arrojó el resultado óptimo del fitness $0.01453$ con un semejanza bastante cercana en cuanto a forma y color con el original.
Por su parte, la versiones original y "suave" disminuyendo por una constante arrojaron valores de fitness de $0.01492$ y $0.01473$ respectivamente, pero el mejor individuo para la generación 10 mil en cuanto a forma y color no llegó a imitar o mejorar al de la versión inicial.
Sin embargo, por calidad de detalle del rostro y por el fenómeno de estancamiento, se eligió la versión original disminuyendo la probabilidad de mutación. Y continuar las pruebas variando la probabilidad de mutación hasta obtener mejores resultados.
Referencias y fuentes consultadas¶
- Portada, imagen de referencia: https://bs-uploads.toptal.io/blackfish-uploads/blog/post/seo/og_image_file/og_image/14111/0901-Genetic_Algorithms-Search_and_Optimization_by_Natural_Selection_Dan_Social-c593a24c34612eaba65058efa44e7980.png
- Evaluacion, imagen de referencia: http://robologs.net/wp-content/uploads/2015/08/ejemplo_fitness.png
- Gráfica de fitness, imagen de referencia: https://cdn-images-1.medium.com/max/800/1*5G7NUBHMeFM_Zfa8obwilQ.png
- Torneo, imagen de referencia: https://www.hebergementwebs.com/image/19/19c2800a4e16bba5aa99413bd1b1c35f.jpg/algoritmos-geneticos---guia-rapidaalgoritmos-geneticos-guia-rapida-49.jpg
- Cruce, imagen de referencia: https://slideplayer.es/slide/4319708/14/images/19/Cruce+de+dos+puntos+padre+1+madre+hijo+1+hijo+2.jpg
- Mutación, imagen de referencia: http://docplayer.es/docs-images/55/35841184/images/30-0.png
Teoría:
- TemasGeneticos, pdf on-line: http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/temageneticos.pdf
- Algoritmos Geneticos, Sancho Fernando: http://www.cs.us.es/~fsancho/?e=65
- Pdf dado en clase sobre algoritmos genéticos.