Algoritmo Genético Sencillo en Python

Algoritmo Genético

En la Inteligencia Artificial, los primeros trabajos para introducir los concpetos  de la Genetica Biológica a la Computación se los debemos a Jhon Holland (Adaptation in Natural Systems, 1975)  quien  hizo los  avances teóricos pioneros.Recomiendo leer esta breve introducción es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico, para  entender los concpetos y tener una idea de los tipos de problemas en que son mas utiles estas tecnicas
 La idea basica de los Algoritmos Genéticos es  aplicar conceptos como selección natural y mutación  para obtener a los mejores individuos que solucionan un problema en cada generacion, usando técnicas de computación . Los procedimientos evolutivos son aleatorios y probabilistas ( estocásticos) La forma en que se mide esta mejor adaptación de los individuos, es por el grado que se ajustan  al objetivo o resolución del problema.
Las aplicaciones de los Algoritmos Genéticos solo dependen de nuestra creatividad y se los utiliza en búsquedas de soluciones en entornos alta complejidad, aun en presencia de ruido y distorsión, en Telecomunicaciones ( selección de frecuencias) Autoamtizacion y Robotica, Procesamiento de Imágenes,Información (Bases de Datos, Cronogramas, Asignación de Recursos,etc), Finanzas, Economía,Genética ,Biología, Optimizacion de Operaciones y  Productos,  etc

Cabe mencionar que los algoritmos evolutivos se pueden combinar con facilidad con otras heuristicas y técnicas que recopilan mayor información para determinar la población inicial, las operaciones evolutivas,  o tomar decisiones para reiniciar las búsquedas de solución desde otros puntos cuando no se logran objetivos satisfactorios. Se pueden combinar con técnicas de satisfacción de restricciones CSP, logica difusa, etc

Pseudocodigo General de los Algoritmos Genéticos o Evolutivos

# Las letras en cursiva representan las diversas funciones que se deben crear
1: g←0; # generación inicial aleatoria
2: Inicializar la poblacion Pb(g);
3: Evaluar la poblacion Pb(g) con la funcion de adecuacion f(Pb) ;
 # La funcion de  Evaluar  f(P) debe coincidir con la Solucion del problema que se quiere resolver
4: Mientras (no se cumpla la condición de finalizar) Hacer
5:  Seleccionar padres de la poblacion Pb(g);
6:  Combinar padres de la poblacion Pb(g)
7:  Mutar padres de la poblacion Pb(g)
# Los pasos 5,6 y 7 producen una nueva poblacion Np(g)
8:  Evaluar  la poblacion Np(g) con  la funcion de adecuacion f(Np);
9:  Escoger mejores descendientes del conjunto Pb(g) Union Np(g)⇒P(g+1); # Reemplazo Generacional
10: g←g+1; # siguiente generación
11: fin Mientras

Representaciones de los Algoritmos Genéticos usando cadenas de bits

Cada Solución o Cromosoma es  normalmente una cadena de bits  Ej.(0,1,0,1,0,0,1). La cantidad de bits  que tiene este vector esta relacionada al numero de variables existentes en la solucion pedida, la precision exigida en la solución, y los bits que se requieren para representar estas condiciones 

Cada bit del cromosoma representa a un gen, que puede tomar valor 1 o 0. El valor especifico de un gen se le denomina alelo, a la posición del alelo se le llama locus. En el Ej. ((0,1,0,1,0,0,1) en el tercer locus desde la izquierda, el alelo es 0 

Al paquete genetico completo se lo llama genotipo  o polacion (En el pseudocodigo el genotipo es la Poblacion Pb(g)).

La interaccion del genotipo con su entorno por medio de los operadores evolutivos( representados en en el pseudocodigo por los pasos Seleccionar, Combinar, Mutar)da lugar a una nueva  poblacion  denominada fenotipo  (En el pseudocodigo el fenotipo se representa por la nueva poblacion Np(g))

Un individuo  es cada cromosoma o solución que incluye la información de la terna fenotipo-genotipo-adecuacion (En el pseudocodigo los individuos son los cromosomas mejores descendientes que forman el reemplazo generacional en la poblacion P(g+1))

 
Ejemplo de Algoritmo Evolutivo con Python: 

Algoritmo Genético para Seleccionar Individuo con mejor Aptitud Musical

Paso 1 : Generar Individuos de una Población Inicial  aleatoriamente
Mientras (No sea la ultima Generación) Hacer
Paso 2: Evaluar la Población con la función de ajuste
Paso 3:  Función de Selección por medio de Torneo
Paso 4:  Función de Mutación
Paso 5:  Función de Cruce
Paso 6:  Conformar la Próxima Generación
Fin 

Lógica y Pasos del Problema

El funcionamiento y comportamiento de este sencillo Algortimo Evolutivo  se entiende perfectamente a partir de los Pasos y el Resultado que arrojan
No se asusten si al ejecutar el codigo los resultados son otros, lo cual es natural por la generacion aleatoria de las poblaciones y de los elementos de los operadores geneticos, pero si estudian bien los Resultados veran que sigue la Logica mostrada aqui. 

Paso 1:Generar Individuos de una Población Inicial  aleatoriamente

Se construye una matriz llamada poblacion donde cada una de las 7  filas es un individuo cuyo crmosoma tiene 6 genes o bits . Luego se utiliza la funcion random.randint para cargar aleatoriamente cada posicion de cada fila con 1 o 0, por ello se importo la libreria random.
Los operadores evolutivos se aplicaran durante tres generaciones
En un caso real los 1 y O pueden obtenerse por mediciones o ponderaciones hechas a individuos reales sometidos a estimulos musicales, o luego de una audicion de sus habilidades musicales 

Código del Paso 1 

Resultado del Paso 1 

Paso 2:  Evaluar la Población  con la función de Evaluación o Ajuste

La función de Evaluación  para medir la Aptitud  Musical es simplemente un Vector que permite asignar un valor o peso a cada bit de cada cromosoma o fila de la población. El primer bit desde la izquierda es el  de Signo, seguido por potencias de 2.Se imprime este vector. Luego se procede a multiplicar el vector Aptitud por la matriz Población. A continuación se imprime el valor resultante de cada fila o cromosoma, que incluye el Signo y la suma de las potencias de 2 de sus genes. Por ultimo se imprime la suma total de las Aptitudes de cada individuo de la población

Código del Paso 2

Resultado del Paso 2 para la primera Población 

 Paso 3:  Función de Selección por medio de Torneo

El cual simplemente elige entre dos individuos aquel que tiene mejor aptitud por medio de la función Torneo que es una simple comparación  Se van haciendo las comparaciones entre pares de individuos y se elige el que tiene mayor valor absoluto

Código del Paso 3

Resultado del Paso 3  Selección  para la primera Población 

Paso 4 Función de Mutación

La función de Mutación simplemente cambia de 1 a 0 un bit elegido aleatoriamente en un individuo. En este caso se aplica al segundo individuo con mejor Aptitud en la Poblacion

Código del Paso 4  Función de Mutación 

Resultado del Paso 4  Mutación para la primera Población 

Paso 5 Función de Cruce

Se utiliza para que dos individuos intercambien sus bits en una posición elegida al azar Da lugar a dos nuevos cromosomas denominados Descendencia

Código del Paso 5 Función de Cruce 

Resultado del Paso 5   Función de Cruce

Paso 6 Formación de la  Siguiente Generación 

La primera fila corresponde al mejor cromosoma de la Generación Inicial,  que en este caso es el de la fila 0
La segunda fila corresponde al segundo mejor cromosma de la Generación Inicial, pero mutado que es el de la fila 1
La tercera y cuarta filas corresponden a las descendencias obtenidas por cruce entre el mejor cromosoma  y la mutación del segundo mejor cromsoma
La quinta y sexta filas corresponden a las descendencias obtenidas por cruce entre el tercer y cuarto mejor cromosoma

Código del Paso 6 Formación de la Siguiente Generación

Resultado del Paso  6  Para la Generación Inicial que formo la Generación 1

Resultado Final: Comparación del mejor Individuo de la Población  Final  respecto a la Población Inicial

Se observa que se obtiene un individuo con mayor Actitud Musical ( en valor absoluto)  en la Ultima Generación ( 15,5) -fila 5  respecto al mejor individuo de la  Poblacion Inicial ( 11,5) - fila 0

Aquí tienen el Vídeo Relacionado 

Código Completo 

Para copiarlo directamente en un compilador o IDE online de Python tal como
este  onlinegdb.com
Atiende que no le añadas ningun punto ni nada al copiar, o que lo haga el compilador que para que les funcione corretamente. Recuerdense de tener seleccionado el lenguaje Python 3 si el IDE es para múltiples lenguajes como este

# Comienza el codigo

import random

individuos = 7
cromosomas = 6
generaciones = 3

#Creando un arreglo de 6 x 7
poblacion = [[0 for x in range(cromosomas)] for x in range(individuos)]

print("POBLACION INICIAL")

#Llenando la población aleatoriamente
for individuo in range(individuos):
    for cromosoma in range(cromosomas):
        poblacion[individuo][cromosoma] = random.randint(0, 1)


#Función para medir aptitud
def medir_aptitud(poblacion):
    aptitud = [0 for i in range(individuos)]
    valores = ["Signo", 2 ** 3, 2 ** 2, 2 ** 1, 2 ** 0, 2 ** -1, 2 ** -2]
    print("")
    print("VALORES PARA DETERMIANR APTITUD MUSICAL")
    print(valores)

# Multiplicndo el Vector de Aptitud por el cromosoma ( fila) de cada individuo de la Poblacion.
    for individuo in range(individuos):
        for cromosoma in range(1, cromosomas):
            aptitud[individuo] += poblacion[individuo][cromosoma] * valores[cromosoma]
        #Cambiando el signo según valor 
        if poblacion[individuo][0] == 1:
            aptitud[individuo] *= -1

    #Imprimiendo valores de aptitud de cada  fila o cromosoma
    print("")
    print("APTITUD")
    for individuo in range(individuos):
        print(str(individuo) + " - [" + ", ".join(str(f) for f in poblacion[individuo]) + "] = " + "{:.9}".format(aptitud[individuo]))
 
# Imprimiendo la Aptitud Total de la Poblacion ( Sumas de las Aptitudes de sus individuos)
    total_aptitud = 0
    for x in range(individuos):
        total_aptitud += abs(aptitud[x])
    print("TOTAL APTITUD " + str(total_aptitud))
    print("")
    return aptitud


#Función para realizar torneo entre cada par de individuos (elige el individuo con mayor aptitud)
def torneo(indice_individuo1, indice_individuo2):
    print("TORNEO")
    print(str(indice_individuo1) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo1]) + "] = " + "{:.9}".format(aptitud[indice_individuo1]))
    print(str(indice_individuo2) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo2]) + "] = " + "{:.9}".format(aptitud[indice_individuo2]))

    if abs(aptitud[indice_individuo1]) > abs(aptitud[indice_individuo2]):
        indice_ganador = indice_individuo1
    else:
        indice_ganador = indice_individuo2

    print("GANADOR")
    print(str(indice_ganador) + " - [" + ", ".join(str(f) for f in poblacion[indice_ganador]) + "] = " + "{:.9}".format(aptitud[indice_ganador]))
    print("")
 
    return indice_ganador


#Función de mutación que cambia de 1 a 0 un bit elegido al azar en un individuo
def mutacion(indice_individuo):
    print("MUTACIÓN")
    print(str(indice_individuo) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo]) + "]")
    indice_mutado = random.randint(0, cromosomas - 1)
 
    if poblacion[indice_individuo][indice_mutado] == 0:
        poblacion[indice_individuo][indice_mutado] = 1
    else:
        poblacion[indice_individuo][indice_mutado] = 0

    print(str(indice_individuo) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo]) + "]")
    print("")


#Función de cruce que intercambia un bit de dos individuos,la posicion del bit se elige al azar
def cruce(indice_individuo1, indice_individuo2):
    print("CRUCE")
    print(str(indice_individuo1) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo1]) + "]")
    print(str(indice_individuo2) + " - [" + ", ".join(str(f) for f in poblacion[indice_individuo2]) + "]")
    indice_cruce = random.randint(1, cromosomas - 1)
    print("Índice de cruce " + str(indice_cruce));
    print("Descendencias")
    descendencia1 = poblacion[indice_individuo1][:indice_cruce] + poblacion[indice_individuo2][indice_cruce:]
    print(descendencia1)
    descendencia2 = poblacion[indice_individuo2][:indice_cruce] + poblacion[indice_individuo1][indice_cruce:]
    print(descendencia2)
    return descendencia1, descendencia2


#Imprime población
def imprime_poblacion():
    for individuo in range(individuos):
        print(str(individuo) + " - [" + ", ".join(str(f) for f in poblacion[individuo]) + "]")


for generacion in range(generaciones):
    print("")
    print("--------- GENERACIÓN " + str(generacion) +" ---------")
    imprime_poblacion()
    nueva_generacion = [0 for x in range(individuos)]
 
    aptitud = medir_aptitud(poblacion)

    for i in range(individuos // 2):
        individuo_ganador = torneo(i, individuos - 1 -i)
        nueva_generacion[i] = poblacion[individuo_ganador]

    mutaciones = random.randint(0, individuos // 2)
    for j in range(mutaciones):
        mutacion(random.randint(0, mutaciones))

    indice_hijos = individuos // 2
    for k in range(0, individuos // 2, 2):
        nueva_generacion[indice_hijos], nueva_generacion[indice_hijos + 1] = cruce(k, k+1)
        indice_hijos += 2
        print("")

    poblacion = nueva_generacion

print("")
print("------- ÚLTIMA GENERACIÓN -------")
imprime_poblacion()
medir_aptitud(poblacion)