Practica #2 - Algoritmos genéticos

Introducción

El tema seleccionado de Cómputo evolutivo, fue el de algoritmos genéticos.

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización.

Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación.

Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.

Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual.

En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo genético, sin embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. La optimización que busca diferentes objetivos simultáneamente, denominada multimodal o multiobjetivo, también se suele abordar con un algoritmo genético especializado.

Por lo tanto, un algoritmo genético consiste en lo siguiente: hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y se aplican los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad. En las siguientes secciones se verán cada uno de los aspectos de un algoritmo genético.

Objetivo ¿Qué piensas lograr?

La solución de un problema de maximización de Optimización…

Un escritor tiene que redactar un número de obras de la literatura en un tiempo conocido. Cada libro tiene un tiempo de redacción y un beneficio asociado. Se desea saber cuál es el máximo benecito alcanzable.

Una vez evaluado el fitness, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores se transmitan a esta. Para ello, hay que seleccionar a una serie de individuos encargados de tan ardua tarea. Y esta selección, y la consiguiente reproducción.

Rueda de ruleta: se crea un pool genético formado por cromosomas de la generación actual, en una cantidad proporcional a su fitness. Si la proporción hace que un individuo domine la población, se le aplica alguna operación de escalado. Dentro de este pool, se cogen parejas aleatorias de cromosomas y se emparejan, sin importar incluso que sean del mismo progenitor (para eso están otros operadores, como la mutación).

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización.

Justificación ¿Por qué ese tema?

Porque la técnica de los algoritmos genéticos, resuelven problemas, de una forma muy eficaz, Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real y este tema ya fue abordado en clase.

Desarrollo

Se programo un Algoritmo Genético resolviendo el problema mencionado anteriormente, generando las poblaciones sucesivas a las que se aplican los operadores de mutación y cruce.

Cada individuo representa una solución al problema, y se trata de encontrar al individuo que represente a la mejor solución.

Instancia Aleatoria para Establecer el Valor de cada obra (1000,2000, o 3000 pesos) y tiempo Empleado en redacción( 20 a 100 horas) correspondiente a cada Libro.

Parámetros importantes en el ag. Llamado Libros: cantidad de libros, valor de los libros (miles de pesos), tiempo total en redacción de las obras, tiempo del que se dispone para efectuarlas, el tamaño de la generación, la lista de la generación, probabilidad de mutación de los cromosomas, la aptitud total, mejor individuo , aptitud, tiempo, la nueva generación, y la lista con los mejores individuos y aptitudes del ag.

Código

import random
import math

class Libros:
    
    def __init__(self, cl, v, t, td, pm, tm, Lmi, Lma):
        
        self.cant_libros=cl
        self.valor_libros=v
        self.tiempos=t
        self.tiempo_disponible=td
        self.tam_generacion=tm
        self.generacion=[] 
        self.prob_mutacion=pm 
        self.aptitud_total=0.0
        self.aptitudes={} 
        self.mejor_individuo='' 
        self.mejor_aptitud=-1
        self.ruleta=[]
        self.mejor_tiempo=100
        self.nueva_generacion=[] 
        self.Lista_mejores_individuos=Lmi
        self.Lista_mejores_aptitudes=Lma
    def poblacion_inicial(self):
        poblacion=random.sample(xrange(0,pow(2,self.cant_libros)-1),self.tam_generacion) #Obtiene una muestra de numeros aleatorios en un cierto rango
        print '......Poblacion inicial......: '
        print '__________________________________________________________________'
        for individuo in poblacion:
            cromosoma=bin(individuo)[2:] #Para quitar el 0b del string
            cromosoma=cromosoma.zfill(self.cant_libros) #Rellena con ceros el string para que quede de un cierto largo (asi todos quedan iguales)
            self.generacion.append(cromosoma)
            print individuo,' ',cromosoma
        
            
    def evaluacion_poblacion(self):
        print '......Evaluacion de poblacion......'
        print '__________________________________________________________________'
        self.aptitud_total=0
        self.aptitudes={}
        
        for cromosoma in self.generacion:
            aptitud=0.0
            tiempo=0.0
            for i in range(0,self.cant_libros):
              
                aptitud+=int(cromosoma[i])*self.valor_libros[i] 
                tiempo+=int(cromosoma[i])*self.tiempos[i]
            if tiempo > self.tiempo_disponible:
                aptitud=0.0
            self.aptitudes[cromosoma]=aptitud
            self.aptitud_total+=aptitud
            if aptitud > self.mejor_aptitud:
                self.mejor_individuo=cromosoma
                self.mejor_aptitud=aptitud
                self.mejor_tiempo=tiempo
                Lista_mejores_aptitudes.append(aptitud)
                Lista_mejores_individuos.append(cromosoma)
            
                
             
            print cromosoma,' ',aptitud,' ',tiempo
            
            
            print "Aptitud total: " + str(self.aptitud_total)
        
    def seleccion(self):
        print 'Seleccion de individuos'
        self.ruleta=[]
        for cromosoma in self.aptitudes:
            cacho=int(math.ceil(self.aptitudes[cromosoma]/self.aptitud_total*100))
            print 'Al cromosoma ',cromosoma,' le corresponden ',cacho,' espacios.'
            for i in range(0,cacho):
                self.ruleta.append(cromosoma)
        random.shuffle(self.ruleta) 
    
    def cruce(self):
        
        print 'Cruza de individuos'
        print '__________________________________________________________________'
        punto_cruce=random.randint(1,self.cant_libros-2)
        bebes=[]
        print 'El punto de cruce escogido es ',punto_cruce
        for  i in range(len(self.generacion)):
            papa=random.choice(self.ruleta) #Este metodo obtiene de manera aleatoria un elemento de una lista.
            mama=random.choice(self.ruleta)
            hijo1=papa[:punto_cruce] + mama[punto_cruce:] 
            hijo2=mama[:punto_cruce] + papa[punto_cruce:]
            bebes.append(hijo1) #Se guardan los hijos 
            bebes.append(hijo2)
            #print len(bebes)
            print 'Papas',papa,' ',mama,' generan hijos ',hijo1,' y ',hijo2
        self.nueva_generacion=random.sample(bebes,len(self.generacion))
        print 
        print 'Nueva generacion: '
        for individuo in self.nueva_generacion:
            print individuo
          
  
    def mutar(self):
        print 'Mutacion'
        print '__________________________________________________________________'
        poblacion=[]
        for cromosoma in self.nueva_generacion:
            crom_mutado=''
            for gen in cromosoma:
                r=random.random()
                if(r<=self.prob_mutacion):
                    crom_mutado+=str(abs(int(gen)-1))
                    print 'Mutando el gen del cromosoma',cromosoma
                else:
                    crom_mutado+=gen
            poblacion.append(crom_mutado)
        self.nueva_generacion=poblacion #Se restablecen los cromosomas
        print
        print 'Nueva generacion mutada (X-boys): '
        for individuo in self.nueva_generacion:
            print individuo
            

    #Se cambia la generacion anterior
    def hacer_cambio_generacional(self):
        self.generacion=self.nueva_generacion

    #Metodo get para el mejor individuo
    def get_mejor_individuo(self):
        return self.mejor_individuo
     
    #Metodo get para la mejor aptitud
    def get_mejor_aptitud(self):
        return self.mejor_aptitud

    #Metodo get para la mejor aptitud
    def get_mejor_tiempo(self):
        return self.mejor_tiempo
    #metodo get para obtener lista con mejores individuos

def get_mejores_individuos(self):
    return self.Lista_mejores_individuos
    #metdo get paraobtener la lista con mejores aptitudes
def get_mejores_aptitudes(self):
    return self.Lista_mejores_aptitudes

valor_libros=[]

for i in range(0,10):
    
    valor_libros.append(random.randint(1, 3))
print" Valor correspondiente de cada libro(miles pesos):", valor_libros

tiempos=[]
Lista_mejores_individuos=[]
Lista_mejores_aptitudes=[]
for i in range(0,10):
    
    tiempos.append(random.randint(20, 100))
print "Tiempo que se emplea en escribir cada libro(horas): ", tiempos


cantidad_objetos=len(valor_libros)

# se pide el tiempo limite para escribir las obras
# se crea el objeto algoritmo genetico
td = int(raw_input(" Ingrese las horas disponibles para escribir las obras: "))
while td < 40:
    print "No se puede escribir ninguna obra \n"
    td = int(raw_input(" Ingrese las horas disponibles para escribir las obras: "))


ag=Libros(cantidad_objetos, valor_libros, tiempos, td, 0.1, 20, Lista_mejores_individuos, Lista_mejores_aptitudes)
print

#Se crea una poblacion incial
ag.poblacion_inicial()
print


iteraciones=10
#Proceso de el algoritmo genetico
for i in range(0,iteraciones):
    ag.evaluacion_poblacion()
    print 
    ag.seleccion()
    print
    ag.cruce()
    print
    ag.mutar()
    print
    ag.hacer_cambio_generacional()

ag.evaluacion_poblacion()


print 
print 'Mejor combinacion de libros : ',ag.get_mejor_individuo()
print 'Mejor aptitud (ganancia miles ): ',ag.get_mejor_aptitud()
print "El tiempo que se escribiran las obras:", ag.get_mejor_tiempo()

print "Lista de mejores individuos", Lista_mejores_individuos
print "Lista de mejres aptitudes", Lista_mejores_aptitudes
print "\n\n\n"
print "La grafica de aptitudes es:"
c=0
for elementos in Lista_mejores_individuos:
    c=c+1
g=0.0
x=0
Lista_grafica=[]
for i in range(0,c):
    print "\n"
    g=Lista_mejores_aptitudes[i]
    while (x<g):
        Lista_grafica.append("*")
        x=x+1
    print Lista_mejores_individuos[i], Lista_grafica

Resultados

Primeramente se muestra El precio correspondiente a cada obra , junto con el tiempo en horas que se empleara para la transcripción.

Se ingresa las horas disponibles que el escritor tendrá, en este caso 20.

Se genera la población inicial aleatorea

Se evalúa la población, podemos notar que si el tiempo se sobrepasa del establecido la aptitud se hace 0.0 (no es factible)

Selección de individuos correspondientes a su aptitud.(utilizando al ruleta), 

Cruza de individuos
Se seleccionan aleatoriamente dos individuos de la ruleta, de los cuales posteriormente nacerán las próximas generaciones. Con los genes antes del punto cruce de el primer individuo, y después del punto cruce del segundo individuo. Y viceversa.

Entonces se obtiene la nueva generación

Que después se mutara lanzando un numero aleatorio; si cae dentro del rango de la probabilidad de mutación, se cambia el gen por su contrario: es decir, si es 1 lo cambiamos por 0 y viceversa.

Se obtiene la nueva generación mutada y se evalúa nuevamente de acuerdo a su aptitud.

Se repite el proceso 10 veces(10 iteraciones) para obtener a el mejor individuo, obteniendo los resultados siguientes

Vídeo

Conclusiones

La realización de este algoritmo genético nos permitió conocer e implementar una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad en todo el mundo durante los últimos años. 

El tema es muy interesante, las mejoras futuras pueden una interfaz que muestre como van incrementando las aptitudes a lo largo de este proceso, 

Se aprendió que mediante esta técnica se pueden resolver una gran cantidad de problemas