From 624334fec2d4c7c9811f75d05892439e1b1af07a Mon Sep 17 00:00:00 2001 From: Mitsuo Tokumori Date: Sun, 10 Apr 2022 22:44:18 -0500 Subject: Add test/ and .gitignore --- test/GA.ipynb | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 112 insertions(+) create mode 100644 test/GA.ipynb (limited to 'test/GA.ipynb') diff --git a/test/GA.ipynb b/test/GA.ipynb new file mode 100644 index 0000000..bab966d --- /dev/null +++ b/test/GA.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 +} -- cgit v1.2.3 From 212409071524b431d1e8f29d7d3f0e8ef291dd4c Mon Sep 17 00:00:00 2001 From: Mitsuo Tokumori Date: Tue, 19 Apr 2022 22:36:54 -0500 Subject: Add VRPTW_GA.ipynb + test/data dir --- test/GA.ipynb | 257 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 253 insertions(+), 4 deletions(-) (limited to 'test/GA.ipynb') diff --git a/test/GA.ipynb b/test/GA.ipynb index bab966d..9d73164 100644 --- a/test/GA.ipynb +++ b/test/GA.ipynb @@ -10,16 +10,217 @@ }, { "cell_type": "code", - "execution_count": null, + "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": "2c3c85e0-a90c-4fda-86f7-778d7328c74d", + "id": "078280b5-70ef-4691-8798-a686d85d188c", "metadata": {}, "outputs": [], "source": [] @@ -27,7 +228,7 @@ { "cell_type": "code", "execution_count": null, - "id": "511ff788-0d1a-4ac7-9575-de182d236574", + "id": "611c9a0d-bb1a-48eb-af37-f033abe8ed66", "metadata": {}, "outputs": [], "source": [] @@ -35,7 +236,55 @@ { "cell_type": "code", "execution_count": null, - "id": "078280b5-70ef-4691-8798-a686d85d188c", + "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": [] -- cgit v1.2.3