summaryrefslogtreecommitdiffstats
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/.ipynb_checkpoints/GA-checkpoint.ipynb112
-rw-r--r--test/GA.ipynb361
-rw-r--r--test/LAB_5_ACC_2021_1.ipynb700
-rw-r--r--test/VRPTW_GA.ipynb724
-rw-r--r--test/data/RC101.csv102
5 files changed, 1999 insertions, 0 deletions
diff --git a/test/.ipynb_checkpoints/GA-checkpoint.ipynb b/test/.ipynb_checkpoints/GA-checkpoint.ipynb
new file mode 100644
index 0000000..bab966d
--- /dev/null
+++ b/test/.ipynb_checkpoints/GA-checkpoint.ipynb
@@ -0,0 +1,112 @@
+{
+ "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
new file mode 100644
index 0000000..9d73164
--- /dev/null
+++ b/test/GA.ipynb
@@ -0,0 +1,361 @@
+{
+ "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/LAB_5_ACC_2021_1.ipynb b/test/LAB_5_ACC_2021_1.ipynb
new file mode 100644
index 0000000..8eed3f8
--- /dev/null
+++ b/test/LAB_5_ACC_2021_1.ipynb
@@ -0,0 +1,700 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "2VP6d4IEg-qk"
+ },
+ "source": [
+ "# APLICACIONES EN CIENCIAS DE COMPUTACION"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "s4LxYBghg-qy"
+ },
+ "source": [
+ "## Laboratorio 5: Algoritmo genético\n",
+ "Indicaciones previas:\n",
+ "- Las respuestas deben tener un buen fundamento teórico, se realizarán descuentos en el puntaje a respuestas que no contesten a lo solicitado\n",
+ "- Cualquier indicio de plagio resultará en la anulación de la prueba.\n",
+ "\n",
+ "La tarea de este laboratorio consiste en comparar métodos en la elaboración de un algoritmo genético para la resolución de la asignación de vuelos.<br>Al final de este notebook se encuentran las preguntas que serán evaluadas en este laboratorio. \n",
+ "\n",
+ "\n",
+ "#### Representacion de Individuo:\n",
+ "\n",
+ "Un objeto Individual representaa una determinada asignacion de un subconjunto de vuelos (almacenado en <b>list_of_flights</b>) a un conjunto de gates (almacenado en <b>chromosome</b>). La lista de gates disponibles que se pueden asignar a los vuelos se almacena en la variable <b>allele_pool</b> del individuo. Ver el siguiente grafico ilustrativo:\n",
+ "\n",
+ "<img src=\"EjemploIndividuo.png\">\n",
+ "\n",
+ "**Usted deberá completar el código en las secciones indicadas con ######### COMPLETAR #########**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "3BiTFdyNhskY"
+ },
+ "outputs": [],
+ "source": [
+ "from random import seed, randint, sample, uniform, randrange\n",
+ "from copy import deepcopy"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "IRVDEMS3g-q1"
+ },
+ "source": [
+ "### Clase <b>Individual</b>\n",
+ "\n",
+ "Esta es una clase para definir a un individuo de la población. Cada individuo posee un cromosoma, los vuelos a asignar, todos los posibles alelos y su respectivo fitness. Además, los métodos de esta clase permiten realizar el cruzamiento (crossover) y la mutación (mutation) sobre el cromosoma del individuo."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "wD-qU6LnGM8_"
+ },
+ "outputs": [],
+ "source": [
+ "class Individual(object):\n",
+ " \"\"\" Clase que implementa el individuo y sus operadores. El cromosoma de un individuo es una lista de caracteres,\n",
+ " cada elemento de la lista es un gen cuyos alelos (caracteres) posibles se indican en allele_pool\"\"\"\n",
+ "\n",
+ " def __init__(self, chromosome, list_of_flights, allele_pool): # El constructor recibe el cromosoma y el pool de alelos posibles\n",
+ " self.chromosome = chromosome[:]\n",
+ " self.list_of_flights = list_of_flights[:]\n",
+ " self.allele_pool = allele_pool\n",
+ " self.fitness = -1 # -1 indica que el individuo no ha sido evaluado\n",
+ "\n",
+ " def crossover_onepoint(self, other):\n",
+ " \"Retorna dos nuevos individuos del cruzamiento de un punto entre individuos self y other \"\n",
+ " c = randrange(len(self.chromosome))\n",
+ " ind1 = Individual(self.chromosome[:c] + other.chromosome[c:], self.list_of_flights, self.allele_pool)\n",
+ " ind2 = Individual(other.chromosome[:c] + self.chromosome[c:], self.list_of_flights, self.allele_pool)\n",
+ " return [ind1, ind2]\n",
+ " \n",
+ " def crossover_permutation(self, other):\n",
+ " new_list = list(set(self.chromosome + other.chromosome))\n",
+ " flights_to_assign = len(self.list_of_flights)\n",
+ " ind1 = Individual(sample(new_list, flights_to_assign), self.list_of_flights, self.allele_pool)\n",
+ " ind2 = Individual(sample(new_list, flights_to_assign), self.list_of_flights, self.allele_pool)\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 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(chromosome1, self.list_of_flights, self.allele_pool)\n",
+ " ind2 = Individual(chromosome2, self.list_of_flights, self.allele_pool)\n",
+ " return [ind1, ind2]\n",
+ "\n",
+ " def mutate_swap(self):\n",
+ " \"Escoge dos genes e intercambia sus alelos\"\n",
+ " mutated_chromosome = deepcopy(self.chromosome)\n",
+ " mutGen1 = randrange(0, len(mutated_chromosome))\n",
+ " mutGen2 = randrange(0, len(mutated_chromosome))\n",
+ " temp = mutated_chromosome[mutGen1]\n",
+ " mutated_chromosome[mutGen1] = mutated_chromosome[mutGen2]\n",
+ " mutated_chromosome[mutGen2] = temp\n",
+ " return Individual(mutated_chromosome, self.list_of_flights, self.allele_pool)\n",
+ " \n",
+ " def mutate_position(self):\n",
+ " \"Cambia aleatoriamente el alelo de un gen.\"\n",
+ " mutated_chromosome = deepcopy(self.chromosome)\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " return Individual(mutated_chromosome, self.list_of_flights, self.allele_pool)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "c8x_4uA5i9XT"
+ },
+ "source": [
+ "### Clase <b>Gate</b>\n",
+ "\n",
+ "Esta es una clase abstracta para definir los lugares donde los vuelos serán asignados. Se debe hacer subclases con el fin de diferenciar los tipos de lugar donde un vuelo puede ser asignado."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "rycIj2j6i_PZ"
+ },
+ "outputs": [],
+ "source": [
+ "class Gate(object):\n",
+ " def __init__(self, identifier, x, y, z):\n",
+ " self.identifier = identifier\n",
+ " self.distance = x\n",
+ " self.potential_of_speed = y\n",
+ " self.number_of_persons_every_10m = z\n",
+ " \n",
+ " def __hash__(self):\n",
+ " return self.identifier"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "fbHPYQ4qj6fb"
+ },
+ "source": [
+ "### Clase <b>Sleeve</b>\n",
+ "\n",
+ "Esta clase implementa concretamente el Gate tipo Sleeve (Manga). En este tipo de gate, los pasajeros deben realizar un recorrido a pie hasta abandonar totalmente el Gate. Se tiene en cuenta la longitud de la manga, la velocidad de los pasajeros y la cantidad de personas que pueden estar cada 10m (este valor es variable porque ya refleja el ancho de la manga, puesto que una manga más ancha permite una mayor cantidad de pasajeros)."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "E9XCmO-3j472"
+ },
+ "outputs": [],
+ "source": [
+ "class Sleeve(Gate):\n",
+ " def __init__(self, identifier, length_of_sleeve, speed_of_passengers_on_sleeve, number_of_passengers_every_10m):\n",
+ " super().__init__(identifier, length_of_sleeve, speed_of_passengers_on_sleeve, number_of_passengers_every_10m)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "0T5fySg6lytA"
+ },
+ "source": [
+ "### Clase <b>Zone</b>\n",
+ "\n",
+ "Esta clase implementa concretamente el Gate tipo Zone (zona). En este tipo de gate, los pasajeros son recogidos por un bus y son llevados hasta una puerta. Se tiene en cuenta la distancia de la zona a la puerta, la velocidad y capacidad del bus."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "yzwjyLG_l0nz"
+ },
+ "outputs": [],
+ "source": [
+ "class Zone(Gate):\n",
+ " def __init__(self, identifier, distance_zone_door, speed_bus, capacity_of_bus):\n",
+ " super().__init__(identifier, distance_zone_door, speed_bus, capacity_of_bus)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "ieZ9wq8amMgT"
+ },
+ "source": [
+ "### Clase <b>Flight</b>\n",
+ "\n",
+ "Esta es una clase para definir a los vuelos a asignar. Cada vuelo posee una capacidad máxima, la cantidad de pasajeros, el tiempo de estacionamiento que le toma al vuelo, la longitud de las alas del avión, el tiempo de inspección al avión luego de aterrizar, el tiempo que demorarían en bajar las escaleras los pasajeros si el avión estuviera repleto, el momento de llegada al aeropuerto y el momento en que debería irse del aeropuerto."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "3Nt88YPkmLb7"
+ },
+ "outputs": [],
+ "source": [
+ "class Flight(object):\n",
+ " def __init__(self, identifier, maximum_capacity, number_of_passengers, parking_time, length_wings, inspection_time, landing_time_on_stairs, arriving_time, leaving_time):\n",
+ " self.identifier = identifier\n",
+ " self.maximum_capacity = maximum_capacity\n",
+ " self.number_of_passengers = number_of_passengers\n",
+ " self.parking_time = parking_time\n",
+ " self.length_wings = length_wings\n",
+ " self.inspection_time = inspection_time\n",
+ " self.landing_time_on_stairs = landing_time_on_stairs\n",
+ " self.arriving_time = arriving_time\n",
+ " self.leaving_time = leaving_time\n",
+ " \n",
+ " def __hash__(self):\n",
+ " return self.identifier"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "tJ5cKDEOg-q4"
+ },
+ "source": [
+ "### Funciones utilitarias para generar los Gates y Vuelos</b>\n",
+ "Estas son funciones utilitarias para generar automáticamente los Gates y Vuelos"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "k8p8en78FCcq"
+ },
+ "outputs": [],
+ "source": [
+ "def generate_list_of_gates(number_of_gates, max_length_of_sleeve=20, max_speed_of_passengers_on_sleeve=3, max_number_of_passengers_every_10m=12, max_distance_zone_door=50, max_speed_bus=15, max_capacity_of_bus=200):\n",
+ " list_of_gates = list()\n",
+ "\n",
+ " for gate_identifier in range(number_of_gates):\n",
+ " gate_type = randint(0, 1)\n",
+ "\n",
+ " if gate_type == 0:\n",
+ " distance = randint(1, max_length_of_sleeve)\n",
+ " potential_of_speed = randint(1, max_speed_of_passengers_on_sleeve)\n",
+ " number_of_persons_every_10m = randint(1, max_number_of_passengers_every_10m)\n",
+ "\n",
+ " gate = Sleeve(gate_identifier, distance, potential_of_speed, number_of_persons_every_10m)\n",
+ " else:\n",
+ " distance = randint(1, max_distance_zone_door)\n",
+ " potential_of_speed = randint(1, max_speed_bus)\n",
+ " number_of_persons_every_10m = randint(1, max_capacity_of_bus)\n",
+ "\n",
+ " gate = Zone(gate_identifier, distance, potential_of_speed, number_of_persons_every_10m)\n",
+ " \n",
+ " list_of_gates.append(gate)\n",
+ " \n",
+ " return list_of_gates\n",
+ "\n",
+ "def generate_list_of_flights(number_of_flights, max_maximum_capacity=100, max_number_of_passengers_factor=0.8, max_parking_time=30, max_length_wings=25, max_inspection_time=180, max_landing_time_on_stairs=60, max_arriving_time=200, max_leaving_time=1000):\n",
+ " list_of_flights = list()\n",
+ "\n",
+ " max_number_of_passengers = max_number_of_passengers_factor * max_maximum_capacity\n",
+ "\n",
+ " for flight_identifier in range(number_of_flights):\n",
+ " maximum_capacity = randint(max_number_of_passengers, max_maximum_capacity)\n",
+ " number_of_passengers = randint(1, max_number_of_passengers)\n",
+ " parking_time = randint(1, max_parking_time)\n",
+ " length_wings = randint(1, max_length_wings)\n",
+ " inspection_time = randint(1, max_inspection_time)\n",
+ " landing_time_on_stairs = randint(1, max_landing_time_on_stairs)\n",
+ " arriving_time = randint(1, max_arriving_time)\n",
+ " leaving_time = randint(max_arriving_time + 1, max_leaving_time)\n",
+ "\n",
+ " flight = Flight(flight_identifier, maximum_capacity, number_of_passengers, parking_time, length_wings, inspection_time, landing_time_on_stairs, arriving_time, leaving_time)\n",
+ " \n",
+ " list_of_flights.append(flight)\n",
+ " \n",
+ " return list_of_flights"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "uHsytNf6oaXJ"
+ },
+ "source": [
+ "### Funciones utilitarias para ordenar los Vuelos y Gates</b>\n",
+ "Estas son funciones utilitarias para ordenar los Vuelos acorde a su deseabilidad y los Gates por su flujo personas"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "25baejsnob3d"
+ },
+ "outputs": [],
+ "source": [
+ "def process_desirability(n):\n",
+ " return n.number_of_passengers / (n.leaving_time - n.arriving_time)\n",
+ "\n",
+ "def process_flow(n):\n",
+ " return n.number_of_persons_every_10m * n.potential_of_speed * 10 / n.distance"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "Gqws5RELpMG1"
+ },
+ "source": [
+ "### Funciones utilitarias para el Algoritmo Genético</b>\n",
+ "Estas son funciones utilitarias para realizar el Algoritmo Genético que se encargue de la asignación de vuelos"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "Glf8GsaujEF6"
+ },
+ "outputs": [],
+ "source": [
+ "# Inicialización aleatoria de la población\n",
+ "def init_population(population_number, flights_to_assign, allele_pool, list_of_flights):\n",
+ " population = []\n",
+ " for i in range(population_number):\n",
+ " new_chromosome_for_individual = sample(allele_pool, flights_to_assign)\n",
+ " list_of_flights_for_individual = sample(list_of_flights, flights_to_assign)\n",
+ " population.append( Individual(new_chromosome_for_individual, list_of_flights_for_individual, allele_pool) )\n",
+ " return population\n",
+ "\n",
+ "# Funcion de fitness: evalua un individuo dada su lista de vuelos (solution_flights) y los gates asignados (solution_gates)\n",
+ "# El fitness representa la suma total de ratios de numeros de pasajeros desembarcados por unidad de tiempo en cada gate asignado \n",
+ "def fitness(solution_flights, solution_gates):\n",
+ " grace_time = 5/100\n",
+ "\n",
+ " cumulative_time = 0\n",
+ " for flight, gate in zip(solution_flights, solution_gates):\n",
+ " number_of_passengers = flight.number_of_passengers\n",
+ " if isinstance(gate, Sleeve):\n",
+ " disembarkation_time_of_passengers = ( (number_of_passengers * (gate.distance + flight.length_wings) / process_flow(gate)) + flight.parking_time + flight.inspection_time ) * (1 + grace_time)\n",
+ " else:\n",
+ " disembarkation_time_of_passengers = ( (number_of_passengers * gate.distance / process_flow(gate)) + flight.parking_time + (flight.landing_time_on_stairs * number_of_passengers / flight.maximum_capacity) + flight.inspection_time ) * (1 + grace_time)\n",
+ " cumulative_time += number_of_passengers / disembarkation_time_of_passengers\n",
+ " return cumulative_time\n",
+ "\n",
+ "# Evaluar la población con la función fitness\n",
+ "def evaluate_population(population, fitness_fn):\n",
+ " \"\"\" Evalua una poblacion de individuos con la funcion de fitness pasada \"\"\"\n",
+ " population_size = len(population)\n",
+ " for i in range(population_size):\n",
+ " if population[i].fitness == -1: # Evalúa sólo si el individuo no esta evaluado\n",
+ " population[i].fitness = fitness_fn(population[i].list_of_flights, population[i].chromosome)\n",
+ "\n",
+ "# Selección de parientes por el método roulette\n",
+ "def select_parents_roulette(population):\n",
+ " population_size = len(population)\n",
+ " \n",
+ " sumfitness = sum([indiv.fitness for indiv in population])\n",
+ " pickfitness = uniform(0, sumfitness)\n",
+ " cumfitness = 0\n",
+ " for i in range(population_size):\n",
+ " cumfitness += population[i].fitness\n",
+ " if cumfitness > pickfitness: \n",
+ " iParent1 = i\n",
+ " break\n",
+ " \n",
+ " sumfitness = sumfitness - population[iParent1].fitness\n",
+ " pickfitness = uniform(0, sumfitness)\n",
+ " cumfitness = 0\n",
+ " for i in range(population_size):\n",
+ " if i == iParent1:\n",
+ " continue\n",
+ " cumfitness += population[i].fitness\n",
+ " if cumfitness > pickfitness: \n",
+ " iParent2 = i\n",
+ " break\n",
+ " return (population[iParent1], population[iParent2])\n",
+ "\n",
+ "# Selección de parientes por el método tournament\n",
+ "def select_parents_tournament(population, percentage_size):\n",
+ " population_size = len(population)\n",
+ " tournament_size = int(percentage_size*population_size/100)\n",
+ " \n",
+ " # Escoge el primer padre\n",
+ " tournament_pool = sample(population, tournament_size)\n",
+ " max_fitness = -1\n",
+ " for i in range(len(tournament_pool)): # recorre los individuos que participan en el torneo buscando el mejor individuo\n",
+ " if tournament_pool[i].fitness > max_fitness:\n",
+ " max_fitness = tournament_pool[i].fitness\n",
+ " iParent1 = i\n",
+ " \n",
+ " # Escoge el segundo padre\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " return (population[iParent1], population[iParent2])\n",
+ "\n",
+ "# Selección de la nueva población\n",
+ "def select_survivors(population, offspring_population, numsurvivors):\n",
+ " next_population = []\n",
+ " population.extend(offspring_population) # Une las dos poblaciones\n",
+ " survivors = sorted(population, key=lambda x: x.fitness, reverse=True)[:numsurvivors]\n",
+ " next_population.extend(survivors)\n",
+ " return next_population\n",
+ "\n",
+ "def genetic_algorithm(list_of_flights, list_of_gates, num_individuals, flights_to_assign, fitness_fn, n_generations, selection_fn=\"roulette\", crossover=\"onepoint\", mutation=\"position\", percentage_size=5, p_mut=0.05):\n",
+ " seed(0)\n",
+ "\n",
+ " allele_pool = list_of_gates\n",
+ "\n",
+ " #Inicializa una poblacion inicial de forma aleatoria\n",
+ " population = init_population(num_individuals, flights_to_assign, allele_pool, list_of_flights)\n",
+ "\n",
+ " population_size = len(population)\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " \n",
+ " for _ in range(n_generations): # Por cada generacion\n",
+ " \n",
+ " ## Selecciona las parejas de padres para cruzamiento\n",
+ " mating_pool = []\n",
+ " for i in range(int(population_size/2)):\n",
+ " if selection_fn == \"roulette\":\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " elif selection_fn == \"tournament\":\n",
+ " mating_pool.append(select_parents_tournament(population, percentage_size))\n",
+ "\n",
+ " ## Crea la poblacion descendencia cruzando las parejas del mating pool \n",
+ " offspring_population = []\n",
+ " for i in range(len(mating_pool)):\n",
+ " if crossover == \"onepoint\":\n",
+ " offspring_population.extend( mating_pool[i][0].crossover_onepoint(mating_pool[i][1]) )\n",
+ " elif crossover == \"permutation\":\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " elif crossover == \"uniform\":\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " \n",
+ " ## Aplica el operador de mutacion con probabilidad p_mut en cada hijo generado\n",
+ " for i in range(len(offspring_population)):\n",
+ " if uniform(0, 1) < p_mut: \n",
+ " if mutation == \"swap\":\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " elif mutation == \"position\":\n",
+ " offspring_population[i] = offspring_population[i].mutate_position()\n",
+ "\n",
+ " ######### COMPLETAR #########\n",
+ " ....\n",
+ " \n",
+ " best = sorted(population, key=lambda x: x.fitness, reverse=True)[0]\n",
+ "\n",
+ " return best"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "pc90jPukpbwN"
+ },
+ "source": [
+ "### Funciones utilitarias para manejar la solución del Algoritmo Genético</b>\n",
+ "Esta es una función utilitarias que permite mostrar la configuración usada en el Algoritmo Genético y la asignación de Vuelos a Gates encontrada en la solución"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "yb6LUKwKpXDJ"
+ },
+ "outputs": [],
+ "source": [
+ "def make_solution_report(solution, selection_fn, crossover, mutation):\n",
+ " print(\"Selection: {} - Crossover: {} - Mutation: {} - Fitness: {}\".format(selection_fn, crossover, mutation, solution.fitness), flush=True)\n",
+ " print(\" - \".join([\"Flight {} in {} {}\".format(flight.identifier, \"Zone\" if isinstance(gate, Zone) == True else \"Sleeve\", gate.identifier) for flight, gate in zip(solution.list_of_flights, solution.chromosome)]) + \"\\n\", flush=True)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "qYjVdTfeg-q6"
+ },
+ "source": [
+ "## <b>Algoritmo Genético</b> "
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "1m0pxINHqQ2m"
+ },
+ "source": [
+ "### <b>Generación de Gates y Vuelos</b> \n",
+ "\n",
+ "Implementación para generar los Gates y Vuelos, **sin filtrar los primeros N vuelos más deseables que pueden ser asignados, dejando el trabajo de selección de vuelos al Algoritmo Genético**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "DaqP5VHngUVg"
+ },
+ "outputs": [],
+ "source": [
+ "seed(0)\n",
+ "\n",
+ "number_of_gates = 7\n",
+ "number_of_flights = 20\n",
+ "\n",
+ "list_of_gates = generate_list_of_gates(number_of_gates)\n",
+ "list_of_flights = generate_list_of_flights(number_of_flights)\n",
+ "\n",
+ "number_of_gates = len(list_of_gates)\n",
+ "number_of_flights = len(list_of_flights)\n",
+ "\n",
+ "flights_to_assign = number_of_flights if number_of_flights <= number_of_gates\telse number_of_gates\n",
+ " \n",
+ "list_of_flights = sorted(list_of_flights, key=process_desirability, reverse=True)\n",
+ "list_of_gates = sorted(list_of_gates, key=process_flow, reverse=True)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "PmmLPnvYrP6v"
+ },
+ "source": [
+ "### <b>Experimentación con el Algoritmo Genético</b> "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "CnfOnMijrP6x"
+ },
+ "outputs": [],
+ "source": [
+ "num_individuals = 100\n",
+ "\n",
+ "fitness_fn = fitness\n",
+ "n_generations = 20\n",
+ "\n",
+ "best_fitness = 0\n",
+ "\n",
+ "selection_fn = \"roulette\"\n",
+ "crossover = \"onepoint\"\n",
+ "mutation = \"position\"\n",
+ "\n",
+ "solution = genetic_algorithm(list_of_flights, list_of_gates, num_individuals, flights_to_assign, fitness_fn, n_generations, selection_fn, crossover, mutation)\n",
+ "\n",
+ "make_solution_report(solution, selection_fn, crossover, mutation)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "id": "wDZA5IJ5gUVh"
+ },
+ "outputs": [],
+ "source": [
+ "num_individuals = 100\n",
+ "\n",
+ "fitness_fn = fitness\n",
+ "n_generations = 20\n",
+ "\n",
+ "best_fitness = 0\n",
+ "\n",
+ "######### COMPLETAR #########\n",
+ "for selection_fn in [\"roulette\", \"tournament\"]: # por cada operador de seleccion\n",
+ " for crossover in [....]: # por cada operador de cruzamiento\n",
+ " for mutation in [....]: # por cada operador de mutacion\n",
+ " ....\n",
+ "\n",
+ "print(\"Best Fitness: {}\".format(best_fitness))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "JnfUrB-aqegj"
+ },
+ "source": [
+ "# Preguntas:"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "yZHjKv4Lyfa2"
+ },
+ "source": [
+ "**1.** Completar el código\n",
+ "\n",
+ "**(4 Puntos)**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "xCdMlpt1vpJj"
+ },
+ "source": [
+ "**2.** Para la \"Generación de Gates y Vuelos\", experimentar con el algoritmo genético usando las siguientes configuraciones:\n",
+ "\n",
+ "- selection_fn: \"roulette\", \"tournament\"\n",
+ "- crossover: \"onepoint\", \"uniform\", \"permutation\"\n",
+ "- mutation: \"position\", \"swap\"\n",
+ "\n",
+ "En total son 12 combinaciones a realizar. En cada configuración se debe usar la función \"make_solution_report\" para obtener los resultados. La lista de Vuelos y Gates sólo se generan 1 vez, a partir de las cuales se experimenta con cada configuración del Algoritmo Genético.\n",
+ "\n",
+ "**No modificar los valores de \"percentage_size\" y \"p_mut\" al ejecutar el algoritmo genético**\n",
+ "\n",
+ "**Se debe mostrar el código respectivo y la solución generada en cada configuración o se considerará como inválido. Para este fin, puede agregar celdas a su gusto.**\n",
+ "\n",
+ "**(5 Puntos, cada 3 configuraciones realizadas equivale a 1 punto)**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "iobk9RW2vtcr"
+ },
+ "source": [
+ "**3.** Para la \"Generación de Gates y Vuelos no restringida\", seleccionar las soluciones con el mejor fitness.\n",
+ "\n",
+ "**En total debería tener 5 configuraciones con el mejor fitness (contando todos los decimales devueltos en la impresión de make_solution_report**\n",
+ "\n",
+ "**(5 Puntos, cada configuración explicada equivale a 1 punto)**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "id": "h1-xDv92SYnF"
+ },
+ "source": [
+ "**4.** Por cada solución (de la pregunta 3), explicar teóricamente porque dicha configuración (\"selection_fn\", \"crossover\" y \"mutation\") obtiene el mejor fitness. Se debe tener en cuenta que en este caso el Algoritmo Genético se encargó de elegir los vuelos a ser asignados.\n",
+ "\n",
+ "**Es necesario que indique en que parte del código el Algoritmo Genético eligió los vuelos, o las justificaciones teóricas no se considerarán válidas.**\n",
+ "\n",
+ "**Se debe explicar teóricamente cada configuración por separado, o se considerará como inválido.**\n",
+ "\n",
+ "**En total debería tener 5 configuraciones con el mejor fitness (contando todos los decimales devueltos en la impresión de make_solution_report**\n",
+ "\n",
+ "**(6 Puntos, indicar la parte del código el Algoritmo Genético eligió los vuelos equivale 1 punto, y cada configuración explicada equivale a 1 punto)**"
+ ]
+ }
+ ],
+ "metadata": {
+ "colab": {
+ "collapsed_sections": [],
+ "name": "LAB_5_ACC_2021_1.ipynb",
+ "provenance": []
+ },
+ "kernelspec": {
+ "display_name": "Python 3",
+ "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.8.3"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 1
+}
diff --git a/test/VRPTW_GA.ipynb b/test/VRPTW_GA.ipynb
new file mode 100644
index 0000000..042836e
--- /dev/null
+++ b/test/VRPTW_GA.ipynb
@@ -0,0 +1,724 @@
+{
+ "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
new file mode 100644
index 0000000..ff64970
--- /dev/null
+++ b/test/data/RC101.csv
@@ -0,0 +1,102 @@
+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
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-29 17:03:04 +0000