SHARE
TWEET

@makiolo

a guest Jul 22nd, 2011 423 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
Want to get better at Python?
Learn to code Python in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top