Guest User

@makiolo

a guest
Jul 22nd, 2011
477
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # -*- coding: utf-8 -*-
  2. # Implementacion de un Algoritmo genetico sencillo
  3. # Autor: Ricardo Marmolejo Garcia
  4. # Dado:
  5. # f(x) = A*x^2-4*x-1
  6. # Y 3 puntos:
  7. #
  8. tests = []
  9. tests.append([-10, 339])
  10. tests.append([0.0, -1])
  11. tests.append([10, 259])
  12. # Calcular A
  13.  
  14. # La solucion es 3 y es hallada mediante AG
  15. # El ejemplo no es muy util, se centra en ejemplificar un AG sencillo
  16.  
  17. #########################################################
  18. # Define la probabilidad de que haya una mutacion
  19. pMutacionRatio = 1.0 # Siempre
  20.  
  21. # Define la probabilidad de que haya un cruce
  22. pCruceRatio = 1.0 # Siempre
  23.  
  24. # Define la maxima perturbacion en la mutacion
  25. maxPerturbacion = 0.05
  26.  
  27. # criterio de terminacion
  28. UMBRAL_ERROR = 0.0001
  29.  
  30. ################ AUXILIAR ###############################
  31.  
  32. import random
  33. import math
  34.  
  35. def randomClamp(a, b):
  36.     return random.random() * (b - a) + a
  37.    
  38. def ordenar_por_fitness(ind1, ind2):
  39.     if ind1.fitness > ind2.fitness:
  40.         return +1
  41.     else:
  42.         return -1
  43.  
  44. class Cromosoma:
  45.     def __init__(self, a, b, c):
  46.         self.a = a
  47.         self.b = b
  48.         self.c = c
  49.         self.fitness = 0.0
  50.        
  51.     def __repr__(self):
  52.         # aplanamiento del tipo a texto
  53.         return "f(x) = [%f] * x^2 + [%f] * x + [%f] - ERROR = %f" % (self.a, self.b, self.c, self.fitness)
  54.        
  55.     def computarFitness(self):
  56.         # nos dice como de apto es el individuo
  57.         # El proceso AG busca la minimizacion, por tanto
  58.         # menos es mejor
  59.         error = 0
  60.         for test in tests:
  61.             x = test[0]
  62.             y = test[1]
  63.             error += y - (self.a * x * x + self.b * x + self.c)
  64.        
  65.         self.fitness = error * error
  66.        
  67.     def cruce(self, otro):
  68.        
  69.         # si hay cruce ...
  70.         if (randomClamp(0, 1) < pCruceRatio):
  71.             # Es un cruce multipunto    
  72.             # tenemos 3 genes con 2 puntos de corte
  73.             # elegimos las 2 formas posibles aleatoriamente al 50%
  74.             if (randomClamp(0, 1) < 0.5):
  75.                 # Cruce impar
  76.                 aa = self.a
  77.                 bb = otro.b
  78.                 cc = self.c
  79.             else:
  80.                 # Crece par
  81.                 aa = otro.a
  82.                 bb = self.b
  83.                 cc = otro.c
  84.         else:
  85.             # No hay cruce
  86.             aa = self.a
  87.             bb = self.b
  88.             cc = self.c
  89.        
  90.         return Cromosoma(aa, bb, cc)
  91.        
  92.     def mutar(self):
  93.  
  94.         # si hay mutacion ...
  95.         if (randomClamp(0, 1) < pMutacionRatio):
  96.            
  97.             # maxPerturbacion es una constante que marca la maxima perturbacion
  98.             # Esto define tambien la velocidad de convergencia
  99.             # Un valor pequenio puede hacer converger lento, pero:
  100.             # Un valor grande podria saltarse la solucion
  101.             # solo mutamos A        
  102.             self.a += randomClamp(-1, 1) * maxPerturbacion
  103.  
  104. ################ EMPIEZA PROGRAMA ###############################
  105.  
  106. # generar poblacion inicial
  107. # 100 cromosomas son repartidos aleatoriamente en A
  108. # El espacio de soluciones de A es un rango grande
  109. cromosomas = []
  110. for i in range(100):
  111.     # 3, -4, -1
  112.     cromosomas.append( Cromosoma(randomClamp(-10000, 10000), -4, -1) )
  113.    
  114. fin = False
  115. gen = 0
  116. while not fin:
  117.     # ***** EVALUAR LA POBLACION
  118.     for ind in cromosomas:
  119.         ind.computarFitness()
  120.        
  121.     # SELECCION
  122.     # En este caso *elitisita*: cogemos los 2 mejores
  123.     # Esto supone practicamente un algoritmo voraz
  124.     # y es facil caer en un optimo local, aunque en el ejemplo no pasa
  125.     # Los AG no garantizan encontrar un optimo global
  126.     # Para coger a los 2 primeros hay que ordenar por adaptacion
  127.     cromosomas.sort(ordenar_por_fitness)
  128.     padre = cromosomas[0]
  129.     madre = cromosomas[1]
  130.  
  131.     # REPRODUCCION / CRUCE DE LOS SELECCIONADOS
  132.     hijo = padre.cruce(madre)
  133.    
  134.     # MUTAMOS el descendiente
  135.     hijo.mutar()
  136.    
  137.     # CRITERIO DE REEMPLAZO
  138.     # Eliminar tantos peores como mejores haya (1 en este caso)
  139.     cromosomas = cromosomas[:-1]
  140.    
  141.     # INSERCION de los hijos en la poblacion
  142.     cromosomas.append( hijo )
  143.    
  144.     # actualizar criterio de terminacion
  145.     fin = math.fabs(padre.fitness) < UMBRAL_ERROR
  146.    
  147.     # mostrar adaptacion del mejor adaptado
  148.     print padre.fitness
  149.     gen += 1
  150.  
  151. # Mostrar la solucion
  152. print "Problema: f(x) = A*x^2-4*x-1 y 3 puntos. Calcular A:"
  153. print "Solucion A = %f - Con un Error de %f en %d generaciones" % (cromosomas[0].a, cromosomas[0].fitness, gen)
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×