Guest User

Mochila (?)

a guest
Aug 13th, 2019
151
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import datetime
  2. import random as rnd
  3. import os
  4.  
  5. # Inicializar parámetros de ejecución
  6. popSize = 50
  7. chromSize = 24
  8. probCrossover = 0.75
  9. probMutacionFinal = 0.4
  10.  
  11. def clearScreen():
  12.     # Limpia la terminal
  13.     os.system('cls' if os.name == 'nt' else 'clear')
  14.  
  15. def decision(probability):
  16.     # Toma una decision aleatoria en base a una probabilidad
  17.     return rnd.random() < probability
  18.  
  19. class Chromosome(object):
  20.  
  21.     number_list = list(range(chromSize))
  22.  
  23.     def __init__(self, size, madre=None, padre=None, punto=None):
  24.         # Constructor del cromosoma
  25.         self.gen = []
  26.         if madre == None:
  27.             self.gen = random.sample(number_list, len(number_list))
  28.             self.calculateValue()
  29.             self.calculateScore()
  30.         else:
  31.             index = 0
  32.             while(True):
  33.                 self.gen[index] = madre.gen[index]
  34.                 index = madre.index(padre.gen[index])
  35.                 if (index == 0):
  36.                     break
  37.             for i in range(chromSize):
  38.                 if (self.gen[i] is None):
  39.                     self.gen[i] = padre.gen[i]
  40.  
  41.  
  42.     def asString(self):
  43.         # Devuelve un string en base al arreglo de genes
  44.         chromStr = ""
  45.         for g in self.gen:
  46.             chromStr += str(g)
  47.         return chromStr
  48.  
  49.     def calculateValue(self):
  50.         # Calcula y guarda el valor entero decimal del cromosoma
  51.         v = 0
  52.         for g in range(len(self.gen)):
  53.             v += self.gen[g] * (2 ** (chromSize - 1 - g))
  54.         self.value = v
  55.  
  56.     def calculateScore(self):
  57.         # Calcula y guarda el puntaje según la función objetivo
  58.         self.score = ((self.value/((2**30)-1))**2)
  59.  
  60.     def calculateFitness(self, totalScore):
  61.         # Calcula y guarda el valor fitness
  62.         self.fitness = self.score/totalScore
  63.  
  64.     def mutate(self):
  65.         # Muta un gen aleatorio del cromosoma
  66.         punto = rnd.randint(0, chromSize-1)
  67.         self.gen[punto] = 1 - self.gen[punto]
  68.         self.calculateValue()
  69.         self.calculateScore()
  70.      
  71. class Population(object):
  72.  
  73.     def __init__(self, prevPopulation=None):
  74.         # Constructor de la población
  75.         self.chromosomes = []
  76.         self.totalScore = 0
  77.         # Crear población aleatoriamente
  78.         if prevPopulation == None:
  79.             for i in range(popSize):
  80.                 individuo = Chromosome(chromSize)
  81.                 self.addChromosome(individuo)
  82.         # Crear población hija en base a la población previa
  83.         else:
  84.             # Aplicar elitismo
  85.             self.addChromosome(prevPopulation.chromosomes[-2])
  86.             self.addChromosome(prevPopulation.chromosomes[-1])
  87.             for i in range(int(popSize/2)-2):
  88.                 padre = prevPopulation.selectWeightedChromosome()
  89.                 madre = prevPopulation.selectWeightedChromosome()
  90.                 # Aplicar crossover
  91.                 if decision(probCrossover):
  92.                     hijo1 = Chromosome(chromSize, madre, padre)
  93.                     hijo2 = Chromosome(chromSize, madre, padre)
  94.                     isNew = True
  95.                 else:
  96.                     hijo1 = padre
  97.                     hijo2 = madre
  98.                     isNew = False
  99.                 # Aplicar mutación
  100.                 if decision(probMutacionActual):
  101.                     hijo1.mutate()
  102.                 elif isNew:
  103.                     hijo1.calculateValue()
  104.                     hijo1.calculateScore()
  105.                 if decision(probMutacionActual):
  106.                     hijo2.mutate()
  107.                 elif isNew:
  108.                     hijo2.calculateValue()
  109.                     hijo2.calculateScore()
  110.                 # Agregar cromosomas hijos
  111.                 self.addChromosome(hijo1)
  112.                 self.addChromosome(hijo2)
  113.  
  114.     def addChromosome(self, c):
  115.         # Agrega un cromosoma a la población
  116.         self.chromosomes.append(c)
  117.  
  118.     def calculateTotalScore(self):
  119.         # Calcula y guarda la suma de los puntajes de todos los cromosomas
  120.         for c in self.chromosomes:
  121.             self.totalScore += c.score
  122.  
  123.     def sortByFitness(self):
  124.         # Calcula los valores fitness de cada cromosoma y ordena de menor a mayor
  125.         for c in self.chromosomes:
  126.             c.calculateFitness(self.totalScore)
  127.         self.chromosomes.sort(key = lambda Chromosome: Chromosome.fitness)
  128.  
  129.     def selectWeightedChromosome(self):
  130.         # Devuelve un cromosoma, teniendo mayor probabilidad dependiendo de su valor fitness
  131.         # Obtener lista de los valores fitness de los cromosomas
  132.         w = []
  133.         for c in self.chromosomes:
  134.             w.append(c.fitness)
  135.         # Devolver cromosoma aleatorio
  136.         return rnd.choices(
  137.             population = self.chromosomes,
  138.             weights = w
  139.         )[0]
  140.  
  141.     def printStats(self):
  142.         # Imprime en pantalla estadisticas de la población
  143.         minimo = self.chromosomes[0].score
  144.         maximo = self.chromosomes[-1].score # Indice -1 devuelve el último item
  145.         promedio = self.totalScore / len(self.chromosomes)
  146.         print("Máximo: ", maximo, "Mínimo: ", minimo, "Promedio: ", promedio)
  147.  
  148.     def printChrom(self):
  149.         # Imprime en pantalla la lista de cromosomas
  150.         for c in self.chromosomes:
  151.             print(c.asString(), " f:", c.fitness)
  152.  
  153. #################################
  154. # INICIO DEL PROGRAMA PRINCIPAL #
  155. #################################
  156.  
  157. clearScreen()
  158.  
  159. # Obtener número de iteraciones del usuario
  160. iteraciones = int(input("Ingrese cantidad de iteraciones a ejecutar: "))
  161.  
  162. # Crear primera instancia de la población
  163. newPopulation = Population()
  164. for n in range(iteraciones):
  165.     # Calcular y guardar puntajes y valores fitness de los cromosomas
  166.     probMutacionActual=probMutacionFinal*n/iteraciones
  167.     newPopulation.calculateTotalScore()
  168.     newPopulation.sortByFitness()
  169.     # Crear nueva población en base a la anterior
  170.     prevPopulation = newPopulation
  171.     newPopulation = Population(prevPopulation)
  172.  
  173. resultChrom = prevPopulation.chromosomes[-1]
  174.  
  175. # Imprimir resultado final en pantalla
  176. print("Resultado\n Cromosoma: {chrom}\n Valor entero: {value}\n Objetivo: {score}\n Fitness: {fitness}"
  177.     .format(
  178.        chrom = resultChrom.asString(),
  179.        value = resultChrom.value,
  180.        score = resultChrom.score,
  181.        fitness = resultChrom.fitness))
  182. input("Presione una tecla para cerrar...")
RAW Paste Data