{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# APLICACIONES EN CIENCIAS DE COMPUTACION\n",
"Dr. Edwin Villanueva"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": []
},
"source": [
"## Algoritmo genetico para resolver el VRPTW\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 140,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"import matplotlib.pyplot as plt\n",
"import csv"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Clase abstracta de un individuo de algoritmo genético"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"class Individual:\n",
" \"Clase abstracta para individuos de un algoritmo evolutivo.\"\n",
"\n",
" def __init__(self, chromosome):\n",
" self.chromosome = chromosome\n",
"\n",
" def crossover(self, other):\n",
" \"Retorna un nuevo individuo cruzando self y other.\"\n",
" raise NotImplementedError\n",
" \n",
" def mutate(self):\n",
" \"Cambia los valores de algunos genes.\"\n",
" raise NotImplementedError "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Clase concreta de un individuo del problema de las n-reinas"
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {},
"outputs": [],
"source": [
"class Individual_VRPTW(Individual):\n",
" \"Clase que implementa el individuo en VRPTW.\"\n",
"\n",
" def __init__(self, chromosome):\n",
" self.chromosome = chromosome[:]\n",
" self.fitness = -1\n",
" \n",
" def crossover_order(self, other):\n",
" \"\"\"\n",
" Copies a part of the child chromosome from the first parent and constructs \n",
" the remaining part by following the vertex ordering in the second parent\n",
" \"\"\"\n",
" cut_point1 = random.randrange(0, len(self.chromosome) + 1)\n",
" cut_point2 = random.randrange(cut_point1, len(self.chromosome) + 1)\n",
" \n",
" c1 = self.chromosome[:]\n",
" c2 = other.chromosome[:]\n",
" p1_rem = self.chromosome[:cut_point1] + self.chromosome[cut_point2:]\n",
" p2_rem = other.chromosome[:cut_point1] + other.chromosome[cut_point2:]\n",
" # Change the genes in the remaining part of the child...\n",
" for i in range(len(self.chromosome)):\n",
" if i not in range(cut_point1, cut_point2):\n",
" # ...following the vertex ordering in the second parent\n",
" for gene in other.chromosome:\n",
" if gene in p1_rem:\n",
" c1.chromosome[i] = gene\n",
" \n",
" # (now for the other child)\n",
" for gene in self.chromosome:\n",
" if gene in p2_rem:\n",
" c2.chromosome[i] = gene\n",
" \n",
" return [Individual_VRPTW(c1), Individual_VRPTW(c2)]\n",
" \n",
"\n",
" def crossover_onepoint(self, other):\n",
" \"Retorna dos nuevos individuos del cruzamiento de un punto entre self y other \"\n",
" c = random.randrange(len(self.chromosome))\n",
" ind1 = Individual_VRPTW(self.chromosome[:c] + other.chromosome[c:])\n",
" ind2 = Individual_VRPTW(other.chromosome[:c] + self.chromosome[c:])\n",
" return [ind1, ind2] \n",
" \n",
" def crossover_uniform(self, other):\n",
" chromosome1 = []\n",
" chromosome2 = []\n",
" \"Retorna dos nuevos individuos del cruzamiento uniforme entre self y other \"\n",
" for i in range(len(self.chromosome)):\n",
" if random.uniform(0, 1) < 0.5:\n",
" chromosome1.append(self.chromosome[i])\n",
" chromosome2.append(other.chromosome[i])\n",
" else:\n",
" chromosome1.append(other.chromosome[i])\n",
" chromosome2.append(self.chromosome[i])\n",
" ind1 = Individual_VRPTW(chromosome1)\n",
" ind2 = Individual_VRPTW(chromosome2)\n",
" return [ind1, ind2] \n",
"\n",
" def mutate_position(self):\n",
" mutated_ind = Individual_VRPTW(self.chromosome[:])\n",
" indexPos = random.randint(0, len(mutated_ind.chromosome)-1)\n",
" newPos = random.randint(0, len(mutated_ind.chromosome)-1)\n",
" mutated_ind.chromosome[indexPos] = newPos\n",
" return mutated_ind\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Funcion de fitness para evaluar un individuo del problema de las n-reinas"
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {},
"outputs": [],
"source": [
"def fitness_VRPTW(chromosome):\n",
" \"\"\"Retorna el fitness de un cromosoma en el problema VRPTW (distancia total de todas las rutas) \"\"\"\n",
" n = len(chromosome) # No. of vertices\n",
" fitness = 10**6\n",
" # feasibility\n",
" # TODO: considerar todas las restricciones\n",
" # desirability\n",
" for i in range(0, n):\n",
" fitness -= distancia[i][i + 1]\n",
" \n",
" return fitness"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Funcion para evaluar toda una población de individuos con la funcion de fitnes especificada"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def evaluate_population(population, fitness_fn):\n",
" \"\"\" Evalua una poblacion de individuos con la funcion de fitness pasada \"\"\"\n",
" popsize = len(population)\n",
" for i in range(popsize):\n",
" if population[i].fitness == -1: # si el individuo no esta evaluado\n",
" population[i].fitness = fitness_fn(population[i].chromosome)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Funcion que selecciona con el metodo de la ruleta un par de individuos de population para cruzamiento "
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [],
"source": [
"def select_parents_roulette(population):\n",
" popsize = len(population)\n",
" \n",
" # Escoje el primer padre\n",
" sumfitness = sum([indiv.fitness for indiv in population]) # suma total del fitness de la poblacion\n",
" pickfitness = random.uniform(0, sumfitness) # escoge un numero aleatorio entre 0 y sumfitness\n",
" cumfitness = 0 # fitness acumulado\n",
" for i in range(popsize):\n",
" cumfitness += population[i].fitness\n",
" if cumfitness > pickfitness: \n",
" iParent1 = i\n",
" break\n",
" \n",
" # Escoje el segundo padre, desconsiderando el padre ya escogido\n",
" sumfitness = sumfitness - population[iParent1].fitness # retira el fitness del padre ya escogido\n",
" pickfitness = random.uniform(0, sumfitness) # escoge un numero aleatorio entre 0 y sumfitness\n",
" cumfitness = 0 # fitness acumulado\n",
" for i in range(popsize):\n",
" if i == iParent1: continue # si es el primer padre \n",
" cumfitness += population[i].fitness\n",
" if cumfitness > pickfitness: \n",
" iParent2 = i\n",
" break \n",
" return (population[iParent1], population[iParent2])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Funcion que selecciona sobrevivientes para la sgte generacion, dada la poblacion actual y poblacion de hijos "
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"def select_survivors(population, offspring_population, numsurvivors):\n",
" next_population = []\n",
" population.extend(offspring_population) # une las dos poblaciones\n",
" isurvivors = sorted(range(len(population)), key=lambda i: population[i].fitness, reverse=True)[:numsurvivors]\n",
" for i in range(numsurvivors): next_population.append(population[isurvivors[i]])\n",
" return next_population"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Algoritmo Genetico \n",
"Recibe una poblacion inicial, funcion de fitness, numero de generaciones (ngen) y taza de mutación (pmut)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def genetic_algorithm(population, fitness_fn, ngen=100, pmut=0.1):\n",
" \"Algoritmo Genetico \"\n",
" \n",
" popsize = len(population)\n",
" evaluate_population(population, fitness_fn) # evalua la poblacion inicial\n",
" ibest = sorted(range(len(population)), key=lambda i: population[i].fitness, reverse=True)[:1]\n",
" bestfitness = [population[ibest[0]].fitness]\n",
" print(\"Poblacion inicial, best_fitness = {}\".format(population[ibest[0]].fitness))\n",
" \n",
" for g in range(ngen): # Por cada generacion\n",
" \n",
" ## Selecciona las parejas de padres para cruzamiento \n",
" mating_pool = []\n",
" for i in range(int(popsize/2)): mating_pool.append(select_parents_roulette(population)) \n",
" \n",
" ## Crea la poblacion descendencia cruzando las parejas del mating pool con Recombinación de 1 punto\n",
" offspring_population = []\n",
" for i in range(len(mating_pool)): \n",
" #offspring_population.extend( mating_pool[i][0].crossover_onepoint(mating_pool[i][1]) )\n",
" #offspring_population.extend( mating_pool[i][0].crossover_uniform(mating_pool[i][1]) )\n",
" offspring_population.extend( mating_pool[i][0].crossover_order(mating_pool[i][1]) )\n",
"\n",
" ## Aplica el operador de mutacion con probabilidad pmut en cada hijo generado\n",
" for i in range(len(offspring_population)):\n",
" if random.uniform(0, 1) < pmut: \n",
" offspring_population[i] = offspring_population[i].mutate_position()\n",
" \n",
" ## Evalua la poblacion descendencia\n",
" evaluate_population(offspring_population, fitness_fn) # evalua la poblacion inicial\n",
" \n",
" ## Selecciona popsize individuos para la sgte. generación de la union de la pob. actual y pob. descendencia\n",
" population = select_survivors(population, offspring_population, popsize)\n",
"\n",
" ## Almacena la historia del fitness del mejor individuo\n",
" ibest = sorted(range(len(population)), key=lambda i: population[i].fitness, reverse=True)[:1]\n",
" bestfitness.append(population[ibest[0]].fitness)\n",
" print(\"generacion {}, best_fitness = {}\".format(g, population[ibest[0]].fitness))\n",
" \n",
" return population[ibest[0]], bestfitness "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" Algoritmo de Busqueda Genetica para el VRPTW "
]
},
{
"cell_type": "code",
"execution_count": 117,
"metadata": {},
"outputs": [],
"source": [
"def genetic_algorithm_VRPTW(fitness_fn, num_depots=1, num_vehicles=1, vehicle_capacity=200, popsize=10, ngen=1000, pmut=0):\n",
" population = []\n",
" \n",
" # Crea la poblacion inicial con cromosomas aleatorios\n",
" for i in range(popsize):\n",
" chromosome = [j for j in range(1,num_vertices+1)]\n",
" random.shuffle(chromosome)\n",
" population.append(Individual_VRPTW(chromosome))\n",
" \n",
" return genetic_algorithm(population, fitness_fn, ngen, pmut)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"def genetic_search_nqueens(fitness_fn, num_queens=10, popsize=10, ngen=100, pmut=0.5):\n",
" import random\n",
" population = []\n",
"\n",
" ## Crea la poblacion inicial con cromosomas aleatorios\n",
" for i in range(popsize):\n",
" chromosome = [j for j in range(1,num_queens+1)]\n",
" random.shuffle(chromosome)\n",
" population.append( Individual_nqueens(chromosome) )\n",
" \n",
" ## Crea la poblacion inicial con los siguientes cromosomas \n",
" #chromosomes = [[1,3,1,3,1,3,1,3,1,3],\n",
" # [2,4,2,4,2,4,2,4,2,4],\n",
" # [3,5,3,5,3,5,3,5,3,5],\n",
" # [4,6,4,6,4,6,4,6,4,6],\n",
" # [5,7,5,7,5,7,5,7,5,7],\n",
" # [6,8,6,8,6,8,6,8,6,8],\n",
" # [7,9,7,9,7,9,7,9,7,9],\n",
" # [8,10,8,10,8,10,8,10,8,10],\n",
" # [9,1,9,1,9,1,9,1,9,1],\n",
" # [10,2,10,2,10,2,10,2,10,2] ] \n",
" #for i in range(popsize):\n",
" # population.append( Individual_nqueens(chromosomes[i]) ) \n",
" \n",
" ## llama al algoritmo genetico para encontrar una solucion al problema de las n reinas\n",
" return genetic_algorithm(population, fitness_fn, ngen, pmut)\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Probando el Algoritmo genetico"
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {},
"outputs": [
{
"ename": "NameError",
"evalue": "name 'distancia' is not defined",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
"Input \u001b[0;32mIn [115]\u001b[0m, in \u001b[0;36m| \u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;28;01mimport\u001b[39;00m \u001b[38;5;21;01mmatplotlib\u001b[39;00m\u001b[38;5;21;01m.\u001b[39;00m\u001b[38;5;21;01mpyplot\u001b[39;00m \u001b[38;5;28;01mas\u001b[39;00m \u001b[38;5;21;01mplt\u001b[39;00m\n\u001b[1;32m 3\u001b[0m \u001b[38;5;66;03m# busca solucion para el problema de 10 reinas. Usa 100 individuos aleatorios, 100 generaciones y taza de mutación de 0.5\u001b[39;00m\n\u001b[0;32m----> 4\u001b[0m best_ind, bestfitness \u001b[38;5;241m=\u001b[39m \u001b[43mgenetic_algorithm_VRPTW\u001b[49m\u001b[43m(\u001b[49m\u001b[43mfitness_VRPTW\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 5\u001b[0m plt\u001b[38;5;241m.\u001b[39mplot(bestfitness)\n\u001b[1;32m 6\u001b[0m plt\u001b[38;5;241m.\u001b[39mshow()\n",
"Input \u001b[0;32mIn [113]\u001b[0m, in \u001b[0;36mgenetic_algorithm_VRPTW\u001b[0;34m(fitness_fn, num_vertices, num_depots, num_vehicles, popsize, ngen, pmut)\u001b[0m\n\u001b[1;32m 7\u001b[0m random\u001b[38;5;241m.\u001b[39mshuffle(chromosome)\n\u001b[1;32m 8\u001b[0m population\u001b[38;5;241m.\u001b[39mappend(Individual_VRPTW(chromosome))\n\u001b[0;32m---> 10\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mgenetic_algorithm\u001b[49m\u001b[43m(\u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mfitness_fn\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mngen\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mpmut\u001b[49m\u001b[43m)\u001b[49m\n",
"Input \u001b[0;32mIn [10]\u001b[0m, in \u001b[0;36mgenetic_algorithm\u001b[0;34m(population, fitness_fn, ngen, pmut)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mAlgoritmo Genetico \u001b[39m\u001b[38;5;124m\"\u001b[39m\n\u001b[1;32m 4\u001b[0m popsize \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlen\u001b[39m(population)\n\u001b[0;32m----> 5\u001b[0m \u001b[43mevaluate_population\u001b[49m\u001b[43m(\u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mfitness_fn\u001b[49m\u001b[43m)\u001b[49m \u001b[38;5;66;03m# evalua la poblacion inicial\u001b[39;00m\n\u001b[1;32m 6\u001b[0m ibest \u001b[38;5;241m=\u001b[39m \u001b[38;5;28msorted\u001b[39m(\u001b[38;5;28mrange\u001b[39m(\u001b[38;5;28mlen\u001b[39m(population)), key\u001b[38;5;241m=\u001b[39m\u001b[38;5;28;01mlambda\u001b[39;00m i: population[i]\u001b[38;5;241m.\u001b[39mfitness, reverse\u001b[38;5;241m=\u001b[39m\u001b[38;5;28;01mTrue\u001b[39;00m)[:\u001b[38;5;241m1\u001b[39m]\n\u001b[1;32m 7\u001b[0m bestfitness \u001b[38;5;241m=\u001b[39m [population[ibest[\u001b[38;5;241m0\u001b[39m]]\u001b[38;5;241m.\u001b[39mfitness]\n",
"Input \u001b[0;32mIn [7]\u001b[0m, in \u001b[0;36mevaluate_population\u001b[0;34m(population, fitness_fn)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(popsize):\n\u001b[1;32m 5\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m population[i]\u001b[38;5;241m.\u001b[39mfitness \u001b[38;5;241m==\u001b[39m \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m1\u001b[39m: \u001b[38;5;66;03m# si el individuo no esta evaluado\u001b[39;00m\n\u001b[0;32m----> 6\u001b[0m population[i]\u001b[38;5;241m.\u001b[39mfitness \u001b[38;5;241m=\u001b[39m \u001b[43mfitness_fn\u001b[49m\u001b[43m(\u001b[49m\u001b[43mpopulation\u001b[49m\u001b[43m[\u001b[49m\u001b[43mi\u001b[49m\u001b[43m]\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mchromosome\u001b[49m\u001b[43m)\u001b[49m\n",
"Input \u001b[0;32mIn [109]\u001b[0m, in \u001b[0;36mfitness_VRPTW\u001b[0;34m(chromosome)\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[38;5;66;03m# feasibility\u001b[39;00m\n\u001b[1;32m 6\u001b[0m \u001b[38;5;66;03m# TODO: considerar todas las restricciones\u001b[39;00m\n\u001b[1;32m 7\u001b[0m \u001b[38;5;66;03m# desirability\u001b[39;00m\n\u001b[1;32m 8\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m0\u001b[39m, n):\n\u001b[0;32m----> 9\u001b[0m fitness \u001b[38;5;241m-\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[43mdistancia\u001b[49m[i][i \u001b[38;5;241m+\u001b[39m \u001b[38;5;241m1\u001b[39m]\n\u001b[1;32m 11\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m fitness\n",
"\u001b[0;31mNameError\u001b[0m: name 'distancia' is not defined"
]
}
],
"source": [
"import matplotlib.pyplot as plt\n",
"\n",
"best_ind, bestfitness = genetic_algorithm_VRPTW(fitness_VRPTW)\n",
"plt.plot(bestfitness)\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": 141,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Poblacion inicial, best_fitness = 44\n",
"generacion 0, best_fitness = 44\n",
"generacion 1, best_fitness = 44\n",
"generacion 2, best_fitness = 44\n",
"generacion 3, best_fitness = 44\n",
"generacion 4, best_fitness = 44\n",
"generacion 5, best_fitness = 44\n",
"generacion 6, best_fitness = 44\n",
"generacion 7, best_fitness = 44\n",
"generacion 8, best_fitness = 44\n",
"generacion 9, best_fitness = 44\n",
"generacion 10, best_fitness = 44\n",
"generacion 11, best_fitness = 44\n",
"generacion 12, best_fitness = 44\n",
"generacion 13, best_fitness = 44\n",
"generacion 14, best_fitness = 44\n",
"generacion 15, best_fitness = 44\n",
"generacion 16, best_fitness = 44\n",
"generacion 17, best_fitness = 44\n",
"generacion 18, best_fitness = 44\n",
"generacion 19, best_fitness = 44\n",
"generacion 20, best_fitness = 44\n",
"generacion 21, best_fitness = 44\n",
"generacion 22, best_fitness = 44\n",
"generacion 23, best_fitness = 44\n",
"generacion 24, best_fitness = 44\n",
"generacion 25, best_fitness = 44\n",
"generacion 26, best_fitness = 44\n",
"generacion 27, best_fitness = 44\n",
"generacion 28, best_fitness = 44\n",
"generacion 29, best_fitness = 44\n",
"generacion 30, best_fitness = 45\n",
"generacion 31, best_fitness = 45\n",
"generacion 32, best_fitness = 45\n",
"generacion 33, best_fitness = 45\n",
"generacion 34, best_fitness = 45\n",
"generacion 35, best_fitness = 45\n",
"generacion 36, best_fitness = 45\n",
"generacion 37, best_fitness = 45\n",
"generacion 38, best_fitness = 45\n",
"generacion 39, best_fitness = 45\n",
"generacion 40, best_fitness = 45\n",
"generacion 41, best_fitness = 45\n",
"generacion 42, best_fitness = 45\n",
"generacion 43, best_fitness = 45\n",
"generacion 44, best_fitness = 45\n",
"generacion 45, best_fitness = 45\n",
"generacion 46, best_fitness = 45\n",
"generacion 47, best_fitness = 45\n",
"generacion 48, best_fitness = 45\n",
"generacion 49, best_fitness = 45\n",
"generacion 50, best_fitness = 45\n",
"generacion 51, best_fitness = 45\n",
"generacion 52, best_fitness = 45\n",
"generacion 53, best_fitness = 45\n",
"generacion 54, best_fitness = 45\n",
"generacion 55, best_fitness = 45\n",
"generacion 56, best_fitness = 45\n",
"generacion 57, best_fitness = 45\n",
"generacion 58, best_fitness = 45\n",
"generacion 59, best_fitness = 45\n",
"generacion 60, best_fitness = 45\n",
"generacion 61, best_fitness = 45\n",
"generacion 62, best_fitness = 45\n",
"generacion 63, best_fitness = 45\n",
"generacion 64, best_fitness = 45\n",
"generacion 65, best_fitness = 45\n",
"generacion 66, best_fitness = 45\n",
"generacion 67, best_fitness = 45\n",
"generacion 68, best_fitness = 45\n",
"generacion 69, best_fitness = 45\n",
"generacion 70, best_fitness = 45\n",
"generacion 71, best_fitness = 45\n",
"generacion 72, best_fitness = 45\n",
"generacion 73, best_fitness = 45\n",
"generacion 74, best_fitness = 45\n",
"generacion 75, best_fitness = 45\n",
"generacion 76, best_fitness = 45\n",
"generacion 77, best_fitness = 45\n",
"generacion 78, best_fitness = 45\n",
"generacion 79, best_fitness = 45\n",
"generacion 80, best_fitness = 45\n",
"generacion 81, best_fitness = 45\n",
"generacion 82, best_fitness = 45\n",
"generacion 83, best_fitness = 45\n",
"generacion 84, best_fitness = 45\n",
"generacion 85, best_fitness = 45\n",
"generacion 86, best_fitness = 45\n",
"generacion 87, best_fitness = 45\n",
"generacion 88, best_fitness = 45\n",
"generacion 89, best_fitness = 45\n",
"generacion 90, best_fitness = 45\n",
"generacion 91, best_fitness = 45\n",
"generacion 92, best_fitness = 45\n",
"generacion 93, best_fitness = 45\n",
"generacion 94, best_fitness = 45\n",
"generacion 95, best_fitness = 45\n",
"generacion 96, best_fitness = 45\n",
"generacion 97, best_fitness = 45\n",
"generacion 98, best_fitness = 45\n",
"generacion 99, best_fitness = 45\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAATz0lEQVR4nO3dYbBc513f8e/PV4kd23GtYDVGVtxrxk47AQKYO2k6pq3HtCHYqkgG3HFJS17AGGZw6xaoiaYzaeKSF9Q0uE4pMxqTkDY0aevS9ta0ZIKNhhkGQiTbJFEUGgUT4iBXchNIlQxKdvffF7tX3tzcq7v3nCvvOavvZ+aOdp/ds/ucOXt++t9nn/ucVBWSpMV1ybw7IEm6sAx6SVpwBr0kLTiDXpIWnEEvSQtu17w7sN4111xTy8vL8+6GJPXK0aNHn6uqPRs91rmgX15e5siRI/PuhiT1SpLPbPaYQzeStOAMeklacAa9JC04g16SFpxBL0kLbuagT7KU5Mkkj07u/3KSp5M8Nfn59k22e3OST01+3rxD/ZYkzWg70yvvBY4DV021/dOqemSzDZK8DPjnwApQwNEkq1X1hSadlSRt30xBn2QfcAfwDuAntvH63wN8qKo+P3mdDwGvB96/zX6qww7/wSme+Iz/d0ttvfLal7L/1Xt3/HVnregfBO4DXrqu/R1J3go8Brylqs6ue/w64LNT95+ZtH2NJHcDdwNcf/31M3ZJXfH2//EJnn7uSyTz7onUb/tfvXc+QZ9kP3Cqqo4muXXqoYPAs8CLgUPATwP3N+lEVR2avAYrKyteCaVnvjIY8f037+Nf/d1vm3dXJG1gli9jbwEOJPkj4APAbUneV1Una+ws8B7gNRts+zngFVP3903atECGo2LXJZbzUldtGfRVdbCq9lXVMnAX8HhV/f0k3wiQJMAbgI9vsPkHgdcl2Z1kN/C6SZsWyGBULC0Z9FJXtVnU7FeS7AECPAX8GECSFeDHqupHqurzSf4F8JHJNvevfTGrxTEcjazopQ7bVtBX1WHg8OT2bZs85wjwI1P33w28u3EP1XmDUbFk0Eud5V/GqjXH6KVuM+jV2rii96MkdZVnp1qzope6zaBXK1XF0DF6qdMMerUyHI3/vs2KXuoug16tDCZB7zx6qbsMerViRS91n0GvVs5V9M66kTrLs1OtWNFL3WfQq5XBaATgrBupwwx6tWJFL3WfQa9WBsO1MXqDXuoqg16tDEcGvdR1Br1aGZZBL3WdQa9Wnh+j96MkdZVnp1pxjF7qPoNerTjrRuo+g16tnJtH71o3UmcZ9GrFil7qPoNerQycXil1nkGvVpx1I3WfZ6dasaKXus+gVyvDyZexjtFL3WXQqxXn0UvdZ9CrlXNj9E6vlDrLoFcrA6dXSp1n0KuVoZcSlDrPs1OtWNFL3WfQq5WhlxKUOs+gVyvOo5e6z6BXKyODXuq8mYM+yVKSJ5M8uq79oSRnNtnmRUnem+RjSY4nOdi2w+oWx+il7ttORX8vcHy6IckKsPs829wJXFpV3wp8J/CjSZa320l1l9eMlbpvpqBPsg+4A3h4qm0JeAC47zybFnBFkl3AS4CvAF9s3Ft1zsBFzaTOm/XsfJBxoI+m2u4BVqvq5Hm2ewT4EnAS+GPg56rq8+uflOTuJEeSHDl9+vSMXVIXWNFL3bdl0CfZD5yqqqNTbXsZD8u8a4vNXwMMgb3ADcBPJvmm9U+qqkNVtVJVK3v27NlO/zVna2vdOEYvddeuGZ5zC3Agye3AZcBVwDHgLHAiCcDlSU5U1Y3rtv1B4Ner6qvAqSS/DawAf7hTO6D5Go5GJHCJQS911pYVfVUdrKp9VbUM3AU8XlW7q+raqlqetH95g5CH8XDNbQBJrgBeC3xyx3qvuRuMympe6rgd/wYtyYEk90/u/gJwZZJjwEeA91TVR3f6PTU/w1E5Pi913CxDN+dU1WHg8AbtV07dXgVWJ7fPMB7L14IaV/TOuJG6zDNUrVjRS91n0KuVwWjkGL3UcQa9WrGil7rPoFcrg6GzbqSuM+jVynBULHm9WKnTDHq1MhgVSzHopS4z6NXKsByjl7rOoFcrw6Hz6KWu8wxVKwNn3UidZ9CrleFoxC6/jJU6zaBXK1b0UvcZ9Gpl6OqVUucZ9GrFil7qPoNerQxdvVLqPM9QtWJFL3WfQa9Whq5eKXWeQa9WBkMreqnrDHq1MhyV8+iljjPo1cp4PXo/RlKXeYaqlYHz6KXOM+jVileYkrrPoFcrXjNW6j6DXq0MR8UlBr3UaQa9WnGtG6n7DHq14l/GSt1n0KsVK3qp+wx6tTJwHr3UeZ6hasWKXuo+g16NVZXz6KUeMOjV2HBUAFb0UsfNHPRJlpI8meTRde0PJTlznu1eneR3khxL8rEkl7XpsLpjMAn6JRc1kzpt1zaeey9wHLhqrSHJCrB7sw2S7ALeB/yDqvr9JN8AfLVhX9UxVvRSP8xU0SfZB9wBPDzVtgQ8ANx3nk1fB3y0qn4foKr+b1UNm3dXXXKuonfWjdRps56hDzIO9NFU2z3AalWdPM92rwQqyQeTPJFkw/8Uktyd5EiSI6dPn56xS5o3K3qpH7YM+iT7gVNVdXSqbS9wJ/CuLTbfBXwX8KbJv29M8t3rn1RVh6pqpapW9uzZs53+a44Go/H/+866kbptljH6W4ADSW4HLmM8Rn8MOAucSAJweZITVXXjum2fAX6rqp4DSPI/gZuBx3ao/5ojK3qpH7as6KvqYFXtq6pl4C7g8araXVXXVtXypP3LG4Q8wAeBb01y+eSL2b8JfGIH+685GgzXxugNeqnLdvxbtCQHktwPUFVfAN4JfAR4Cniiqn5tp99T83Guond6pdRp25leSVUdBg5v0H7l1O1VYHXq/vsYT7HUgnHWjdQPnqFqbK2iX4oVvdRlBr0aOxf0jtFLnWbQqzFn3Uj9YNCrsXPz6P0yVuo0g16NWdFL/WDQq7GBY/RSLxj0auz5it6PkdRlnqFqzIpe6geDXo0NJ1/GOkYvdZtBr8Zc60bqB4NejbnWjdQPBr0aGzi9UuoFg16NDV3UTOoFz1A1ZkUv9YNBr8aGXkpQ6gWDXo1Z0Uv9YNCrMZcplvrBoFdjzqOX+sGgV2OjMuilPjDo1djARc2kXvAMVWOO0Uv9YNCrsbUxemfdSN1m0Kux4WhEApcY9FKnGfRqbDAqq3mpBwx6NTYclePzUg8Y9GpsXNH7EZK6zrNUjVnRS/1g0KuxwWjkGL3UAwa9GrOil/rBoFdjg6GzbqQ+MOjV2HBULHm9WKnzZg76JEtJnkzy6Lr2h5Kc2WLb65OcSfJTTTuq7nHWjdQP2zlL7wWOTzckWQF2z7DtO4H/tY33Ug84Ri/1w0xBn2QfcAfw8FTbEvAAcN8W274BeBo41riX6qTBaMRSDHqp62at6B9kHOijqbZ7gNWqOrnZRkmuBH4aePv5XjzJ3UmOJDly+vTpGbukeRuOXLlS6oMtgz7JfuBUVR2datsL3Am8a4vN3wb8fFWddwy/qg5V1UpVrezZs2frXqsThqMRu/wyVuq8XTM85xbgQJLbgcuAqxgPw5wFTmT8q/vlSU5U1Y3rtv2rwA8k+ZfA1cAoyZ9X1b/ZqR3Q/Awco5d6Ycugr6qDwEGAJLcCP1VV+6efk+TMBiFPVf31qee8DThjyC+OoatXSr2w43PjkhxIcv9Ov666x4pe6odZhm7OqarDwOEN2q+cur0KrG7wnLdtu3fqtOGoePGLlubdDUlb8K9d1JgVvdQPBr0aG7p6pdQLBr0aGwyt6KU+MOjV2HBUzqOXesCgV2PjtW78CEld51mqxgbOo5d6waBXY65eKfWDQa/GvGas1A8GvRqzopf6waBXY47RS/1g0Kux4bC4xKCXOs+gV2PDsqKX+sCgV2MD59FLveBZqsZcj17qB4NejVSVs26knjDo1chwVABW9FIPGPRqZDAJ+iUXNZM6z6BXI1b0Un8Y9GrkXEXvrBup8zxL1YgVvdQfBr0aGYxGAM66kXrAoFcjVvRSfxj0amQwXBujN+ilrjPo1ci5it7plVLnGfRqxFk3Un94lqoRx+il/jDo1YizbqT+MOjVyFpFvxSDXuo6g16NDF3rRuoNg16NOEYv9cfMQZ9kKcmTSR5d1/5QkjObbPO3kxxN8rHJv7e17bC64flZNwa91HW7tvHce4HjwFVrDUlWgN3n2eY54O9U1Z8k+Rbgg8B1TTqqbnm+oveXQqnrZjpLk+wD7gAenmpbAh4A7ttsu6p6sqr+ZHL3GPCSJJc27666wope6o9Zy7EHGQf6aKrtHmC1qk7O+BrfDzxRVWfXP5Dk7iRHkhw5ffr0jC+neRpOplc6Ri9135ZBn2Q/cKqqjk617QXuBN41y5sk+WbgZ4Ef3ejxqjpUVStVtbJnz56ZOq75cq0bqT9mGaO/BTiQ5HbgMsZj9MeAs8CJjOdRX57kRFXduH7jybDPfwV+qKo+vWM911y51o3UH1tW9FV1sKr2VdUycBfweFXtrqprq2p50v7lTUL+auDXgLdU1W/vbNc1TwOnV0q9seNTJpIcSHL/5O49wI3AW5M8Nfn5izv9nnrhDV3UTOqN7UyvpKoOA4c3aL9y6vYqsDq5/TPAz7TqoTrJil7qD8sxNTJ0UTOpNwx6NWJFL/WHQa9Ghv7BlNQbBr0aWZtH7xIIUvd5lqoRlymW+sOgVyMDLzwi9YZBr0ZG5Ri91BcGvRp5fozeoJe6zqBXI8PRiAQuMeilzjPo1chgVFbzUk8Y9GpkOCrH56WeMOjVyLii9+Mj9YFnqhqxopf6w6BXI4PRyDF6qScMejViRS/1h0GvRgZDZ91IfWHQq5HhqFznRuoJg16NOOtG6g/PVDXiGL3UHwa9GnHWjdQfBr0asaKX+sOgVyMDg17qDYNejVjRS/1h0KuRoatXSr1h0KsRh26k/jDo1cjQefRSb3imqhEreqk/DHo1MnQevdQbBr0aGQyt6KW+MOjVyHBU7HJRM6kXDHo1Mp5H78dH6oOZz9QkS0meTPLouvaHkpw5z3YHk5xI8gdJvqdNZ9UdA+fRS72xaxvPvRc4Dly11pBkBdi92QZJXgXcBXwzsBf4jSSvrKphs+6qK/zLWKk/Zgr6JPuAO4B3AD8xaVsCHgB+EHjjJpt+H/CBqjoLPJ3kBPAa4Hda9vvrfPLZL/IP/8OTO/2y2sSzX/xzlmLQS30wa0X/IHAf8NKptnuA1ao6mc1P+OuA3526/8yk7WskuRu4G+D666+fsUtf67JdS9z08isbbavte+XLX8obb/66Qympg7YM+iT7gVNVdTTJrZO2vcCdwK070YmqOgQcAlhZWakmr7F8zRX82zd95050R5IWyiwV/S3AgSS3A5cxHqM/BpwFTkyq+cuTnKiqG9dt+zngFVP3903aJEkvkC1n3VTVwaraV1XLjL9YfbyqdlfVtVW1PGn/8gYhD7AK3JXk0iQ3ADcBv7eD/ZckbWE7s25mkuQAsFJVb62qY0n+E/AJYAD8uDNuJOmFlapGQ+IXzMrKSh05cmTe3ZCkXklytKpWNnrMP22UpAVn0EvSgjPoJWnBGfSStOA692VsktPAZ1q8xDXAczvUnT642PYX3OeLhfu8PX+pqvZs9EDngr6tJEc2++Z5EV1s+wvu88XCfd45Dt1I0oIz6CVpwS1i0B+adwdeYBfb/oL7fLFwn3fIwo3RS5K+1iJW9JKkKQa9JC24hQn6JK+fXID8RJK3zLs/F0KSVyT5zSSfSHIsyb2T9pcl+VCST03+3fQ6vn20/sL0SW5I8uHJsf6PSV487z7utCRXJ3kkySeTHE/y1xb5OCf5J5PP9MeTvD/JZYt4nJO8O8mpJB+fatvwuGbsocn+fzTJzU3fdyGCfnL92l8Avhd4FfD3JhcmXzQD4Cer6lXAa4Efn+znW4DHquom4LHJ/UWydmH6NT8L/PzkGghfAH54Lr26sP418OtV9VeAb2O8/wt5nJNcB/wjxsubfwuwxPjaF4t4nH8ZeP26ts2O6/cyvobHTYwvtfqLTd90IYKe8QXHT1TVH1bVV4APML4w+UKpqpNV9cTk9v9jfPJfx3hf3zt52nuBN8ylgxfA1IXpH57cD3Ab8MjkKQu1vwBJ/gLwN4BfAqiqr1TVn7LAx5nxtTFekmQXcDlwkgU8zlX1W8Dn1zVvdly/D/h3Nfa7wNVJvrHJ+y5K0F8HfHbq/oYXIV8kSZaB7wA+DLy8qk5OHnoWePm8+nUBPMj4wvSjyf1vAP60qgaT+4t4rG8ATgPvmQxZPZzkChb0OFfV54CfA/6YccD/GXCUxT/OazY7rjuWa4sS9BeVJFcC/wX4x1X1xenHajxfdiHmzE5fmH7efXmB7QJuBn6xqr4D+BLrhmkW7DjvZly93gDsBa7g64c3LgoX6rguStBfNBchT/IixiH/K1X1q5Pm/7P2K93k31Pz6t8OW7sw/R8xHo67jfHY9dWTX/FhMY/1M8AzVfXhyf1HGAf/oh7nvwU8XVWnq+qrwK8yPvaLfpzXbHZcdyzXFiXoPwLcNPmW/sWMv8hZnXOfdtxkfPqXgONV9c6ph1aBN09uvxn47y903y6ETS5M/ybgN4EfmDxtYfZ3TVU9C3w2yV+eNH034+suL+RxZjxk89okl08+42v7u9DHecpmx3UV+KHJ7JvXAn82NcSzPVW1ED/A7cD/Bj4N/LN59+cC7eN3Mf617qPAU5Of2xmPWz8GfAr4DeBl8+7rBdj3W4FHJ7e/Cfg94ATwn4FL592/C7C/3w4cmRzr/wbsXuTjDLwd+CTwceDfA5cu4nEG3s/4e4ivMv7N7Yc3O65AGM8m/DTwMcazkhq9r0sgSNKCW5ShG0nSJgx6SVpwBr0kLTiDXpIWnEEvSQvOoJekBWfQS9KC+//Rh3QID9ptGwAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 343 ms, sys: 108 ms, total: 450 ms\n",
"Wall time: 329 ms\n"
]
}
],
"source": [
"%%time\n",
"# busca solucion para el problema de 10 reinas. Usa 100 individuos aleatorios, 100 generaciones y taza de mutación de 0.5\n",
"best_ind, bestfitness = genetic_search_nqueens(fitness_nqueens, 10, 100, 100, 0.90)\n",
"plt.plot(bestfitness)\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Lectura de datos"
]
},
{
"cell_type": "code",
"execution_count": 139,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CUST NO.XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME\n",
"1 40 50 0 0 240 0 \n",
"2 25 85 20 145 175 10 \n",
"3 22 75 30 50 80 10 \n",
"4 22 85 10 109 139 10 \n",
"5 20 80 40 141 171 10 \n",
"6 20 85 20 41 71 10 \n",
"7 18 75 20 95 125 10 \n",
"8 15 75 20 79 109 10 \n",
"9 15 80 10 91 121 10 \n",
"10 10 35 20 91 121 10 \n",
"11 10 40 30 119 149 10 \n",
"12 8 40 40 59 89 10 \n",
"13 8 45 20 64 94 10 \n",
"14 5 35 10 142 172 10 \n",
"15 5 45 10 35 65 10 \n",
"16 2 40 20 58 88 10 \n",
"17 0 40 20 72 102 10 \n",
"18 0 45 20 149 179 10 \n",
"19 44 5 20 87 117 10 \n",
"20 42 10 40 72 102 10 \n",
"21 42 15 10 122 152 10 \n",
"22 40 5 10 67 97 10 \n",
"23 40 15 40 92 122 10 \n",
"24 38 5 30 65 95 10 \n",
"25 38 15 10 148 178 10 \n",
"26 35 5 20 154 184 10 \n",
"27 95 30 30 115 145 10 \n",
"28 95 35 20 62 92 10 \n",
"29 92 30 10 62 92 10 \n",
"30 90 35 10 67 97 10 \n",
"31 88 30 10 74 104 10 \n",
"32 88 35 20 61 91 10 \n",
"33 87 30 10 131 161 10 \n",
"34 85 25 10 51 81 10 \n",
"35 85 35 30 111 141 10 \n",
"36 67 85 20 139 169 10 \n",
"37 65 85 40 43 73 10 \n",
"38 65 82 10 124 154 10 \n",
"39 62 80 30 75 105 10 \n",
"40 60 80 10 37 67 10 \n",
"41 60 85 30 85 115 10 \n",
"42 58 75 20 92 122 10 \n",
"43 55 80 10 33 63 10 \n",
"44 55 85 20 128 158 10 \n",
"45 55 82 10 64 94 10 \n",
"46 20 82 10 37 67 10 \n",
"47 18 80 10 113 143 10 \n",
"48 2 45 10 45 75 10 \n",
"49 42 5 10 151 181 10 \n",
"50 42 12 10 104 134 10 \n",
"51 72 35 30 116 146 10 \n",
"52 55 20 19 83 113 10 \n",
"53 25 30 3 52 82 10 \n",
"54 20 50 5 91 121 10 \n",
"55 55 60 16 139 169 10 \n",
"56 30 60 16 140 170 10 \n",
"57 50 35 19 130 160 10 \n",
"58 30 25 23 96 126 10 \n",
"59 15 10 20 152 182 10 \n",
"60 10 20 19 42 72 10 \n",
"61 15 60 17 155 185 10 \n",
"62 45 65 9 66 96 10 \n",
"63 65 35 3 52 82 10 \n",
"64 65 20 6 39 69 10 \n",
"65 45 30 17 53 83 10 \n",
"66 35 40 16 11 41 10 \n",
"67 41 37 16 133 163 10 \n",
"68 64 42 9 70 100 10 \n",
"69 40 60 21 144 174 10 \n",
"70 31 52 27 41 71 10 \n",
"71 35 69 23 180 210 10 \n",
"72 65 55 14 65 95 10 \n",
"73 63 65 8 30 60 10 \n",
"74 2 60 5 77 107 10 \n",
"75 20 20 8 141 171 10 \n",
"76 5 5 16 74 104 10 \n",
"77 60 12 31 75 105 10 \n",
"78 23 3 7 150 180 10 \n",
"79 8 56 27 90 120 10 \n",
"80 6 68 30 89 119 10 \n",
"81 47 47 13 192 222 10 \n",
"82 49 58 10 86 116 10 \n",
"83 27 43 9 42 72 10 \n",
"84 37 31 14 35 65 10 \n",
"85 57 29 18 96 126 10 \n",
"86 63 23 2 87 117 10 \n",
"87 21 24 28 87 117 10 \n",
"88 12 24 13 90 120 10 \n",
"89 24 58 19 67 97 10 \n",
"90 67 5 25 144 174 10 \n",
"91 37 47 6 86 116 10 \n",
"92 49 42 13 167 197 10 \n",
"93 53 43 14 14 44 10 \n",
"94 61 52 3 178 208 10 \n",
"95 57 48 23 95 125 10 \n",
"96 56 37 6 34 64 10 \n",
"97 55 54 26 132 162 10 \n",
"98 4 18 35 120 150 10 \n",
"99 26 52 9 46 76 10 \n",
"100 26 35 15 77 107 10 \n",
"101 31 67 3 180 210 10 \n"
]
}
],
"source": [
"with open('data/RC101.csv', newline='') as csvfile:\n",
" orders = csv.reader(csvfile)\n",
" for row in orders:\n",
" print(f\"{row[0]:8}{row[1]:8}{row[2]:8}{row[3]:8}{row[4]:12}{row[5]:12}{row[6]:12}\")\n",
" #print(\", \".join(row))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.2"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
|