path: root/test/LAB_5_ACC_2021_1.ipynb

{
 "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
}