summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
authorDayana31 <[email protected]>2022-05-23 22:38:10 -0500
committerDayana31 <[email protected]>2022-05-23 22:38:10 -0500
commit2da5eab182017b29c131304a90a3633fe4d887ca (patch)
tree51273fac8b8590fca477fd748bc1cc4c15dd0fcb /test
parent758d03eae1d7d83c8e7685fa04e8ae9b3a62bddb (diff)
parent11a08a862b3c87ae9699dc5625d9104adaea9528 (diff)
downloadDP1_project-2da5eab182017b29c131304a90a3633fe4d887ca.tar.gz
DP1_project-2da5eab182017b29c131304a90a3633fe4d887ca.tar.bz2
DP1_project-2da5eab182017b29c131304a90a3633fe4d887ca.zip
Merge branch 'develop' into dayana
Diffstat (limited to 'test')
-rw-r--r--test/.ipynb_checkpoints/GA-checkpoint.ipynb112
-rw-r--r--test/GA.ipynb361
-rw-r--r--test/VRPTW_GA.ipynb724
-rw-r--r--test/data/RC101.csv102
-rw-r--r--test/mitsuo.ipynb771
5 files changed, 771 insertions, 1299 deletions
diff --git a/test/.ipynb_checkpoints/GA-checkpoint.ipynb b/test/.ipynb_checkpoints/GA-checkpoint.ipynb
deleted file mode 100644
index bab966d..0000000
--- a/test/.ipynb_checkpoints/GA-checkpoint.ipynb
+++ /dev/null
@@ -1,112 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "2fd45b3a-9a24-4782-812c-08223edb750e",
- "metadata": {},
- "source": [
- "# Prueba del algoritmo genetico"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "f6b4829a-9001-410c-b20c-01c65c777d8a",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "2c3c85e0-a90c-4fda-86f7-778d7328c74d",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "511ff788-0d1a-4ac7-9575-de182d236574",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "078280b5-70ef-4691-8798-a686d85d188c",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b3ad92de-b2ed-4f21-a696-1fa2981f89dc",
- "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",
- "\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 "
- ]
- }
- ],
- "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": 5
-}
diff --git a/test/GA.ipynb b/test/GA.ipynb
deleted file mode 100644
index 9d73164..0000000
--- a/test/GA.ipynb
+++ /dev/null
@@ -1,361 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "2fd45b3a-9a24-4782-812c-08223edb750e",
- "metadata": {},
- "source": [
- "# Prueba del algoritmo genetico"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 21,
- "id": "45972b70-b2a6-48f2-aafa-9f660548079a",
- "metadata": {},
- "outputs": [],
- "source": [
- "import numpy as np\n",
- "import random"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "34eab22f-a400-4a14-9ac4-047d87dff69f",
- "metadata": {},
- "source": [
- "Data"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 97,
- "id": "a5736dba-4c38-4b7f-9a1a-963bdb006236",
- "metadata": {},
- "outputs": [],
- "source": [
- "class Ciudad:\n",
- " regiones = {\n",
- " 'costa': {\n",
- " 'plazoentrega': 1\n",
- " },\n",
- " 'sierra': {\n",
- " 'plazoentrega': 2\n",
- " },\n",
- " 'selva': {\n",
- " 'plazoentrega': 3\n",
- " }\n",
- " }\n",
- " def __init__(self, nombre, region, longitud, latitud):\n",
- " self.nombre = nombre\n",
- " self.region = region\n",
- " self.x = longitud\n",
- " self.y = latitud"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 101,
- "id": "8ee9610f-d128-4d1b-9458-ca9048073f20",
- "metadata": {},
- "outputs": [],
- "source": [
- "class Road_network:\n",
- " def __init__(self, cities, distances):\n",
- " \"\"\"Grafo completo del pais\n",
- " \n",
- " Params\n",
- " ------\n",
- " \n",
- " cities: list\n",
- " Lista de objetos Ciudad\n",
- " \n",
- " routes: dict\n",
- " (Aun no se como implementar esto)\n",
- " \"\"\"\n",
- " \n",
- " self.cities = cities\n",
- " self.routes = {}"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 102,
- "id": "7dd72c93-acba-46f9-ac99-8c3d1a8cfa67",
- "metadata": {},
- "outputs": [],
- "source": [
- "class Vehiculo:\n",
- " tipos = {\n",
- " 1: {\n",
- " 'cargamax': 50\n",
- " },\n",
- " 2: {\n",
- " 'cargamax': 100\n",
- " },\n",
- " 3: {\n",
- " 'cargamax': 200\n",
- " }\n",
- " }\n",
- " \n",
- " def __init__(self):\n",
- " pass"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 96,
- "id": "474a3596-f75d-411e-bf4c-20b8b8259434",
- "metadata": {},
- "outputs": [],
- "source": [
- "class Pedido:\n",
- " def __init__(self, cliente, cantidad):\n",
- " self.cliente = cliente\n",
- " self.cantidad = cantidad"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 98,
- "id": "7602722f-9026-44dc-b922-e17a7d3af45b",
- "metadata": {},
- "outputs": [],
- "source": [
- "class Cliente:\n",
- " def __init__(self, nombre, ciudad):\n",
- " self.nombre = nombre\n",
- " self.ciudad = ciudad"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 100,
- "id": "f6b4829a-9001-410c-b20c-01c65c777d8a",
- "metadata": {},
- "outputs": [],
- "source": [
- "class VRP:\n",
- " def __init__(self):\n",
- " # Conjuntos\n",
- " self.I = range(2)\n",
- " self.J = range(3)\n",
- " self.T = range(5) # en horas\n",
- " self.V = range(3) # 3 tipos de vehiculos\n",
- " \n",
- " def init_data(self):\n",
- " \"\"\"\n",
- " Lista los parametros iniciales, definidos en \"Modelo Matematico\" en ISA v02\n",
- " \n",
- " i: almacen grande (depot)\n",
- " j: almacen pequeño (customer)\n",
- " v: tipo de vehiculo\n",
- " t: tiempo\n",
- " \"\"\"\n",
- " # Parametros\n",
- " # Nombres cortos confunden, pero matrices de varias dimensiones \n",
- " # sin etiquetas confunden mas\n",
- " \n",
- " # Demanda\n",
- " self.D_jt = [ [ random.choice([0,1,2,3]) for _ in self.I ] for _ in self.T ]\n",
- " # Capacidades de vehiculos\n",
- " self.VL_v = [ random.choice([10, 15, 20]) for _ in self.V ]\n",
- " # distancia entre almacen i, j\n",
- " self.d_ij = [ random.choice([25,50,100]) for _ in self.V ]\n",
- " #self.r_ijvt = [ [ 0 for _ in self.V ] for "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 82,
- "id": "ab559513-5c14-4dd2-a51d-7737114dfba1",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "array([10, 10, 15])"
- ]
- },
- "execution_count": 82,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "p = VRP()\n",
- "p.init_data()\n",
- "np.array(p.VL_v)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 83,
- "id": "2c3c85e0-a90c-4fda-86f7-778d7328c74d",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "[25, 50, 50]"
- ]
- },
- "execution_count": 83,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "p.d_ij"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "511ff788-0d1a-4ac7-9575-de182d236574",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "078280b5-70ef-4691-8798-a686d85d188c",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "611c9a0d-bb1a-48eb-af37-f033abe8ed66",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "64c68216-b9f1-45f9-a0fe-3862ab106c24",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "9cb6bb08-1547-4b64-993f-b2c453535264",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b83d9e98-db8f-45cd-9eff-07d4194f7e07",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b8c06031-9c55-4e13-a27b-91b0886902e6",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "e9483c22-243f-44e5-9a6d-09da92354554",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "12952643-4a10-40bf-8af3-41319c744732",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b0306c4f-eb68-4009-9390-0f881c6a8cb4",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b3ad92de-b2ed-4f21-a696-1fa2981f89dc",
- "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",
- "\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 "
- ]
- }
- ],
- "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": 5
-}
diff --git a/test/VRPTW_GA.ipynb b/test/VRPTW_GA.ipynb
deleted file mode 100644
index 042836e..0000000
--- a/test/VRPTW_GA.ipynb
+++ /dev/null
@@ -1,724 +0,0 @@
-{
- "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": [
- "<b>Clase abstracta de un individuo de algoritmo genético</b>"
- ]
- },
- {
- "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": [
- "<b>Clase concreta de un individuo del problema de las n-reinas</b>"
- ]
- },
- {
- "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": [
- "<b>Funcion de fitness para evaluar un individuo del problema de las n-reinas</b>"
- ]
- },
- {
- "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": [
- "<b>Funcion para evaluar toda una población de individuos con la funcion de fitnes especificada</b>"
- ]
- },
- {
- "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": [
- "<b>Funcion que selecciona con el metodo de la ruleta un par de individuos de population para cruzamiento </b>"
- ]
- },
- {
- "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": [
- "<b>Funcion que selecciona sobrevivientes para la sgte generacion, dada la poblacion actual y poblacion de hijos </b>"
- ]
- },
- {
- "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": [
- "<b>Algoritmo Genetico</b> \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": [
- " <b>Algoritmo de Busqueda Genetica para el VRPTW</b> "
- ]
- },
- {
- "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<cell line: 4>\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": [
- "<Figure size 432x288 with 1 Axes>"
- ]
- },
- "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
-}
diff --git a/test/data/RC101.csv b/test/data/RC101.csv
deleted file mode 100644
index ff64970..0000000
--- a/test/data/RC101.csv
+++ /dev/null
@@ -1,102 +0,0 @@
-CUST NO.,XCOORD.,YCOORD.,DEMAND,READY TIME,DUE DATE,SERVICE TIME
-1,40,50,0,0,240,0
-2,25,85,20,145,175,10
-3,22,75,30,50,80,10
-4,22,85,10,109,139,10
-5,20,80,40,141,171,10
-6,20,85,20,41,71,10
-7,18,75,20,95,125,10
-8,15,75,20,79,109,10
-9,15,80,10,91,121,10
-10,10,35,20,91,121,10
-11,10,40,30,119,149,10
-12,8,40,40,59,89,10
-13,8,45,20,64,94,10
-14,5,35,10,142,172,10
-15,5,45,10,35,65,10
-16,2,40,20,58,88,10
-17,0,40,20,72,102,10
-18,0,45,20,149,179,10
-19,44,5,20,87,117,10
-20,42,10,40,72,102,10
-21,42,15,10,122,152,10
-22,40,5,10,67,97,10
-23,40,15,40,92,122,10
-24,38,5,30,65,95,10
-25,38,15,10,148,178,10
-26,35,5,20,154,184,10
-27,95,30,30,115,145,10
-28,95,35,20,62,92,10
-29,92,30,10,62,92,10
-30,90,35,10,67,97,10
-31,88,30,10,74,104,10
-32,88,35,20,61,91,10
-33,87,30,10,131,161,10
-34,85,25,10,51,81,10
-35,85,35,30,111,141,10
-36,67,85,20,139,169,10
-37,65,85,40,43,73,10
-38,65,82,10,124,154,10
-39,62,80,30,75,105,10
-40,60,80,10,37,67,10
-41,60,85,30,85,115,10
-42,58,75,20,92,122,10
-43,55,80,10,33,63,10
-44,55,85,20,128,158,10
-45,55,82,10,64,94,10
-46,20,82,10,37,67,10
-47,18,80,10,113,143,10
-48,2,45,10,45,75,10
-49,42,5,10,151,181,10
-50,42,12,10,104,134,10
-51,72,35,30,116,146,10
-52,55,20,19,83,113,10
-53,25,30,3,52,82,10
-54,20,50,5,91,121,10
-55,55,60,16,139,169,10
-56,30,60,16,140,170,10
-57,50,35,19,130,160,10
-58,30,25,23,96,126,10
-59,15,10,20,152,182,10
-60,10,20,19,42,72,10
-61,15,60,17,155,185,10
-62,45,65,9,66,96,10
-63,65,35,3,52,82,10
-64,65,20,6,39,69,10
-65,45,30,17,53,83,10
-66,35,40,16,11,41,10
-67,41,37,16,133,163,10
-68,64,42,9,70,100,10
-69,40,60,21,144,174,10
-70,31,52,27,41,71,10
-71,35,69,23,180,210,10
-72,65,55,14,65,95,10
-73,63,65,8,30,60,10
-74,2,60,5,77,107,10
-75,20,20,8,141,171,10
-76,5,5,16,74,104,10
-77,60,12,31,75,105,10
-78,23,3,7,150,180,10
-79,8,56,27,90,120,10
-80,6,68,30,89,119,10
-81,47,47,13,192,222,10
-82,49,58,10,86,116,10
-83,27,43,9,42,72,10
-84,37,31,14,35,65,10
-85,57,29,18,96,126,10
-86,63,23,2,87,117,10
-87,21,24,28,87,117,10
-88,12,24,13,90,120,10
-89,24,58,19,67,97,10
-90,67,5,25,144,174,10
-91,37,47,6,86,116,10
-92,49,42,13,167,197,10
-93,53,43,14,14,44,10
-94,61,52,3,178,208,10
-95,57,48,23,95,125,10
-96,56,37,6,34,64,10
-97,55,54,26,132,162,10
-98,4,18,35,120,150,10
-99,26,52,9,46,76,10
-100,26,35,15,77,107,10
-101,31,67,3,180,210,10
diff --git a/test/mitsuo.ipynb b/test/mitsuo.ipynb
new file mode 100644
index 0000000..653663c
--- /dev/null
+++ b/test/mitsuo.ipynb
@@ -0,0 +1,771 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "956275e8-e4e6-4a03-afe5-31eca1c3272b",
+ "metadata": {},
+ "source": [
+ "# Testing possible algorithms to solve MDHVRPTW"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "234feb6e-4c52-443c-a3d6-6da8e903dd5c",
+ "metadata": {
+ "tags": []
+ },
+ "source": [
+ "Travelling salesman problem\n",
+ "\n",
+ "TSP es *casi* MDHVRPTW (*Multi-Depot Heterogeneous VRP with Time Windows) *del profe* pero:\n",
+ "- Solo 1 camion\n",
+ "- Todos los ciudades (aka. almacenes pequeños) tienen al menos 1 pedido\n",
+ "- Capacidad infinita (1 solo tipo de vehiculo)\n",
+ "- Sin ventanas de tiempo (aka. plazos de entrega)\n",
+ "- Solo 1 deposito\n",
+ "- No hay entregas parciales\n",
+ " - Relajar la restriccion de que la demanda de los \"customers\" debe ser satisfecha al 100% por\n",
+ " un solo camion. Entonces, si un \"customer\" requiere 8 paquetes, se le puede entregar solo 5,\n",
+ " y quedan pendientes 3. **Esto modifica la solucion, ahora es una lista donde los nodos a visitar\n",
+ " ya no son unicos**. Se debe terminar la solucion cuando ya no hayan pedidos pendientes (paquetes por entregar > 0).\n",
+ "- No hay \"trasvaces\"\n",
+ " - F\n",
+ "\n",
+ "Cambios identificados, necesarios para adaptar el TSP a nuestro caso:\n",
+ "- Tramos no conectados -> distancia grande entre ellos\n",
+ "- Distancias no son euclidianas, usar \"geodistance\"\n",
+ "- [...]"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6ce403ac-eb32-4f74-ae8d-41cb70fe4a20",
+ "metadata": {
+ "tags": []
+ },
+ "source": [
+ "## Posibilidades\n",
+ "\n",
+ "Una manera de implementar \n",
+ "\n",
+ "- [scikit-opt](https://github.com/guofei9987/scikit-opt)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "98fe5cbb-4fb3-478b-b22f-c14a0408e638",
+ "metadata": {
+ "tags": []
+ },
+ "source": [
+ "## NetworkX to find all_pairs_shortest_path"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "4b854709-fe5c-4c5a-8a05-b2e438c92a1a",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import networkx as nx\n",
+ "G = nx.Graph()\n",
+ "G.add_edge(1, 2) # default edge data=1\n",
+ "G.add_edge(2, 3, weight=0.9) # specify edge data"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "44bf2120-1e55-4c1d-b806-3e66227483a3",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import math\n",
+ "G.add_edge('y', 'x', function=math.cos)\n",
+ "G.add_node(math.cos) # any hashable can be a node"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "2ed6d6e2-921a-4376-8f8e-c6731385d561",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "elist = [(1, 2), (2, 3), (1, 4), (4, 2)]\n",
+ "G.add_edges_from(elist)\n",
+ "elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]\n",
+ "G.add_weighted_edges_from(elist)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "16aad098-3702-4d81-889b-3dc8b3e46ca7",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import matplotlib.pyplot as plt\n",
+ "#G = nx.cubical_graph()\n",
+ "subax1 = plt.subplot(121)\n",
+ "nx.draw(G) # default spring_layout"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "1cc6e56b-3dcf-45fe-9127-0cd63f01ccec",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print(G.adj)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "bad6e2e8-cff5-4a7d-9e3f-f37bae5dff2d",
+ "metadata": {},
+ "source": [
+ "## Pre-processing"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "22af16ef-7df6-49c8-8e55-157069c03830",
+ "metadata": {},
+ "source": [
+ "La data del profe es muy tedioso de leer. Formato raro. Pasar primero a csv.\n",
+ "\n",
+ "Distancia entre nodos:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "id": "db46bd0b-46c7-4125-bfff-33205c578e27",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'/home/mitsuo/docs/courses/2022-1/INF226_DP1/project/code/DP_project/test'"
+ ]
+ },
+ "execution_count": 8,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "%pwd"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "id": "b87961d0-f9b4-417e-9138-3db1b0a36d2f",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import numpy as np\n",
+ "\n",
+ "import csv\n",
+ "import math\n",
+ "import random\n",
+ "\n",
+ "import networkx as nx\n",
+ "import matplotlib.pyplot as plt"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "id": "aeca1be3-1394-4ae1-b488-6abe8bd1e808",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def degreesToRadians(degrees):\n",
+ " return degrees * math.pi / 180\n",
+ "\n",
+ "def distanceInKmBetweenEarthCoordinates(lat1, lon1, lat2, lon2):\n",
+ " earthRadiusKm = 6371 # Avg. radius\n",
+ "\n",
+ " dLat = degreesToRadians(lat2-lat1)\n",
+ " dLon = degreesToRadians(lon2-lon1)\n",
+ "\n",
+ " lat1 = degreesToRadians(lat1)\n",
+ " lat2 = degreesToRadians(lat2)\n",
+ "\n",
+ " a = math.sin(dLat/2) * math.sin(dLat/2) \\\n",
+ " + math.sin(dLon/2) * math.sin(dLon/2) * math.cos(lat1) * math.cos(lat2)\n",
+ " c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a));\n",
+ " return earthRadiusKm * c\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "id": "80a0fef2-ae25-40e3-94ab-e3d07b9b60c0",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "class Node:\n",
+ " \"\"\"\n",
+ " \n",
+ " Attributes\n",
+ " ----------\n",
+ " lat : float\n",
+ " Latitud (angulo de los Paralelos) en grados sexagesimales\n",
+ " lon : float\n",
+ " Longitud (angulo de los Meridianos) en grados sexagesimales\n",
+ " x : float\n",
+ " Aproximacion local, en Km respecto (\"Lima\": -12.04591952,-77.03049615 (lat, long))\n",
+ " x = (longitud - (-77.03049615)) * (pi / 180) * earthRadiusKm\n",
+ " y : float\n",
+ " Aproximacion local, en Km respecto (\"Lima\")\n",
+ " y = (latitud - (-12.04591952)) * (pi / 180) * earthRadiusKm\n",
+ " demand : float\n",
+ " Cantidad de paquetes (facil cambiar a int)\n",
+ " *_time : float\n",
+ " Cantidades de tiempo en minutos\n",
+ " \n",
+ " Notes\n",
+ " -----\n",
+ " Web Mercator projection (BAD):\n",
+ " \n",
+ " x = floor(256 / (2 * math.pi) * 2**(zoom_level) * (lon + math.pi))\n",
+ " y = floor(265 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.ln(math.tan( math.pi / 4 + lat / 2 ))))\n",
+ " \n",
+ " x = R * lon\n",
+ " y = R * ln(tan(pi/4 + lat/2)\n",
+ " \n",
+ " Both `lon` and `lat` in radians.\n",
+ " \n",
+ " \"Lima\": -12.04591952,-77.03049615 (lat, long)\n",
+ " \"\"\"\n",
+ " def __init__(self, id: int, ubigeo, lat, lon, is_depot,\n",
+ " demand, ready_time, due_time, service_time):\n",
+ " super()\n",
+ " self.id = id\n",
+ " self.ubigeo = ubigeo\n",
+ "\n",
+ " if is_depot:\n",
+ " self.is_depot = True\n",
+ " else:\n",
+ " self.is_depot = False\n",
+ " \n",
+ " earthRadiusKm = 6371 # Avg. radius\n",
+ " zoom_level = 1\n",
+ " lima_lat = (-12.04591952)\n",
+ " lima_lon = (-77.03049615)\n",
+ " \n",
+ " self.lat = lat\n",
+ " self.lon = lon\n",
+ " self.x = (lon - lima_lon) * (math.pi / 180) * earthRadiusKm\n",
+ " self.y = (lat - lima_lat) * (math.pi / 180) * earthRadiusKm\n",
+ " #self.lat *= (math.pi / 180)\n",
+ " #self.lon *= (math.pi / 180)\n",
+ " #self.x = 256 / (2 * math.pi) * 2**(zoom_level) * (self.lon + math.pi)\n",
+ " #self.y = 256 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.log(math.tan( math.pi / 4 + self.lat / 2 )))\n",
+ " self.x = round(self.x, 3)\n",
+ " self.y = round(self.y, 3)\n",
+ " self.demand = demand\n",
+ " self.ready_time = 0 #ready_time\n",
+ " self.due_time = due_time\n",
+ " self.service_time = service_time"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "id": "fd72a504-3538-4b43-9e90-bef4299ca83d",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "nodes = []\n",
+ "\n",
+ "with open('data/VRPTW_python/inf226.oficinas_mod.csv', newline='') as csvfile:\n",
+ " orders = csv.reader(csvfile)\n",
+ " count = 1\n",
+ " id = 0\n",
+ " for row in orders:\n",
+ " if count >= 2:\n",
+ " ubigeo, dept, prov, latitud, longitud, region_natural, is_depot = row[:7]\n",
+ " demand, ready_time, due_time, service_time = row[7:]\n",
+ " nodes.append(Node(\n",
+ " id, ubigeo, float(latitud), float(longitud), int(is_depot),\n",
+ " #int(100 * random.random()), 0, int(5000 + 500 * (1.5 - random.random())), service_time=60\n",
+ " demand=float(demand), ready_time=0, due_time=float(due_time), service_time=60\n",
+ " ))\n",
+ " id += 1\n",
+ " count += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "id": "8a9cb3eb-d434-44de-a179-01464ba7bbf8",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "{'id': 34, 'ubigeo': '040101', 'is_depot': True, 'lat': -16.39881421, 'lon': -71.537019649, 'x': 610.847, 'y': -484.02, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n",
+ "{'id': 122, 'ubigeo': '130101', 'is_depot': True, 'lat': -8.11176389, 'lon': -79.02868652, 'x': -222.189, 'y': 437.458, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n",
+ "{'id': 134, 'ubigeo': '150101', 'is_depot': True, 'lat': -12.04591952, 'lon': -77.03049615, 'x': 0.0, 'y': 0.0, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n"
+ ]
+ }
+ ],
+ "source": [
+ "for node in nodes:\n",
+ " if node.is_depot:\n",
+ " print(node.__dict__)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "id": "79fcde2d-d0df-4cca-8334-3ffd7a0da997",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "node_num = len(nodes)\n",
+ "\n",
+ "tramos = []\n",
+ "with open('../data/inf226.tramos.v.2.0.csv', newline='') as f:\n",
+ " rows = csv.reader(f)\n",
+ " count = 1\n",
+ " for row in rows:\n",
+ " if count >= 2:\n",
+ " tramos.append([row[0], row[1]])\n",
+ " count += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "id": "945de058-6fc3-44c1-8d59-227064323bae",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "7008\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "[['010201', '010301'],\n",
+ " ['010301', '010201'],\n",
+ " ['010201', '010401'],\n",
+ " ['010401', '010201'],\n",
+ " ['010201', '010501']]"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "print(len(tramos))\n",
+ "tramos[:5]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "id": "e6895a35-ff22-48a1-88a8-ceb8344f36cb",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "node_dist_mat = np.zeros((node_num, node_num))\n",
+ "\n",
+ "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n",
+ "for ubigeo1, ubigeo2 in tramos:\n",
+ " #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n",
+ " id1 = nodes_d[ubigeo1].id\n",
+ " id2 = nodes_d[ubigeo2].id\n",
+ " n1 = nodes[id1]\n",
+ " n2 = nodes[id2]\n",
+ " node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "id": "b971e3b3-cea5-43b8-9c57-5bbb83180ee6",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(196, 196)"
+ ]
+ },
+ "execution_count": 18,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "node_dist_mat.shape"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "id": "abc75da4-fed7-493e-ae9d-f5daba33c693",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "array([[ 0. , 86.349, 0. , 137.864],\n",
+ " [ 86.349, 0. , 0. , 146.07 ],\n",
+ " [ 0. , 0. , 0. , 0. ],\n",
+ " [137.864, 146.07 , 0. , 0. ]])"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "node_dist_mat[:4, :4]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "id": "e818c9bb-28cb-475d-b8b5-98dfe4d11f91",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# depots are '040101', '130101', '150101'\n",
+ "\n",
+ "depots = []\n",
+ "customers = []\n",
+ "for n in nodes:\n",
+ " if n.is_depot:\n",
+ " depots.append(n)\n",
+ " else:\n",
+ " customers.append(n)\n",
+ "depots_customers = depots + customers\n",
+ "\n",
+ "with open('data/VRPTW_python/pedidosperu195.txt', 'w', newline='') as csvfile:\n",
+ " spamwriter = csv.writer(csvfile, delimiter=' ', quoting=csv.QUOTE_MINIMAL)\n",
+ " i = 0\n",
+ " for node in depots_customers:\n",
+ " spamwriter.writerow([\n",
+ " #node.id,\n",
+ " i,\n",
+ " node.x, node.y,\n",
+ " node.demand, node.ready_time, node.due_time, node.service_time\n",
+ " ])\n",
+ " i += 1"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4cf94976-9003-4b9a-a600-ad9b48d3e60e",
+ "metadata": {},
+ "source": [
+ "### Transformar a matriz conexa de nodos \"customer\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "ac9f4ce7-7f54-4d26-9bbf-75252f083046",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "for n in nodes[:5]:\n",
+ " print(n.__dict__)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b3f18eaf-a962-454f-99d4-67bf71067e39",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "count = 0\n",
+ "for n in nodes:\n",
+ " if n.demand:\n",
+ " print(n.__dict__)\n",
+ " count += 1\n",
+ "count"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "4308a3df-27ca-4910-bff3-1302c8fb589d",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "14d8d583-7766-421b-96cc-ec95ad9604e6",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "f85c9cab",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "#node_dist_mat = np.zeros((node_num, node_num))\n",
+ "elist = []\n",
+ "\n",
+ "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n",
+ "for ubigeo1, ubigeo2 in tramos:\n",
+ " #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n",
+ " id1 = nodes_d[ubigeo1].id\n",
+ " id2 = nodes_d[ubigeo2].id\n",
+ " n1 = nodes[id1]\n",
+ " n2 = nodes[id2]\n",
+ " #node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n",
+ " dist = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n",
+ " elist.append((ubigeo1, ubigeo2, dist))\n",
+ " \n",
+ "G = nx.Graph()\n",
+ "G.add_weighted_edges_from(elist)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "b3c522d4",
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "print(len(list(nodes_d)))\n",
+ "print(len(list(G.nodes)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "86771f42",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "G['010201']['010301']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "001a04b8",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "node_dist_mat[nodes_d['010201'].id, nodes_d['010301'].id]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "71e54f4d",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "G['010201']['250301']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "7ebe3cdc",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "path1 = nx.shortest_path(G, source='010201', target='250301', weight='weight')\n",
+ "path1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "cca62d40",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "path2 = nx.shortest_path(G, source='010201', target='250301')\n",
+ "path2"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "756f1845",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "l1, l2 = 0, 0\n",
+ "for i in range(len(path1)):\n",
+ " if i == 0:\n",
+ " continue\n",
+ " l1 += G[path1[i-1]][path1[i]]['weight']\n",
+ " l2 += G[path2[i-1]][path2[i]]['weight']\n",
+ "print(l1, l2)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "9e124757",
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "# https://stackoverflow.com/a/63169428/7498073\n",
+ "H = nx.subgraph(G, path1)\n",
+ "nx.draw(H, with_labels=True, font_weight='bold', node_color='lightblue', node_size=500)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "c5ded33b",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))\n",
+ "#for node, (dist, path) in len_path:\n",
+ "# print(f\"{node}: {dist} [{path}]\")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "3361d460",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "print(len_path['010201'][0]['250301'])\n",
+ "print(len_path['010201'][1]['250301'])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "ba3d4ae7-c6b5-484a-a1b4-0f6ffe1890b6",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "help(G)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "596bf42a-3600-4446-a904-a4e9080d2f2b",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "132bea6b-c50c-4406-8e2f-2279a87e9cbf",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "bf5cac1d-9ae4-4423-ab96-48728c14fa01",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "00f4cd39-c093-4397-ae96-cb3ae2a433c6",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ff3f7473-6418-4f4a-828f-172f2996ba54",
+ "metadata": {},
+ "source": [
+ "## Pruebitas"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "6956f235-0401-4a67-8ed2-d2b3fd07b3bf",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "0ab3843c-faba-46a0-9f7b-97897430ba67",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "e45dd91b-fc32-4da3-a340-d3dc888b1335",
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "5fdfcaa8-9000-48d7-b3ab-4d2f2efc2bcc",
+ "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": 5
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-28 16:18:53 +0000