discrete genetic algorithm (shortest route).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "3b1f963b-aae3-484c-9f96-4e40fdcb2638",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "from numpy.random import randint, choice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "20b1e5c5-47d1-45ec-a832-d24d7e1ab7ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "This is the routing table containing the bandwidth related to each car/base station. \n",
    "Every unknown cost of a node to another or a node to itself is represented by negative infinity\n",
    "'''\n",
    "routing_table = np.array([\n",
    "   # Car_1    Car_2    Car_3    Car_4    Car_5    Car_6    Car_7    Car_8    Car_9    Base_1   Base_2\n",
    "    [-np.inf, 4,       4,       4,       3,       -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf],  # Car_1\n",
    "    [4,       -np.inf, -np.inf, 5,       -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, 6,       -np.inf],  # Car_2\n",
    "    [4,       -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf],  # Car_3\n",
    "    [4,       5,       -np.inf, -np.inf, 4,       -np.inf, 1,       -np.inf, -np.inf, -np.inf, -np.inf],  # Car_4\n",
    "    [3,       -np.inf, -np.inf, 4,       -np.inf, 5,       2,       7,       4,       -np.inf, -np.inf],  # Car_5\n",
    "    [-np.inf, -np.inf, 3,       -np.inf, 5,       -np.inf, -np.inf, -np.inf, 5,       -np.inf, -np.inf],  # Car_6\n",
    "    [-np.inf, -np.inf, -np.inf, 1,       2,       -np.inf, -np.inf, 3,       -np.inf, -np.inf, 6      ],  # Car_7\n",
    "    [-np.inf, -np.inf, -np.inf, -np.inf, 7,       -np.inf, 3,       -np.inf, 4,       -np.inf, -np.inf],  # Car_8\n",
    "    [-np.inf, -np.inf, -np.inf, -np.inf, 4,       5,       -np.inf, 4,       -np.inf, -np.inf, -np.inf],  # Car_9\n",
    "    [-np.inf, 6,       -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf],  # Base_1\n",
    "    [-np.inf, -np.inf, -np.inf, -np.inf, -np.inf, -np.inf, 6,       -np.inf, -np.inf, -np.inf, -np.inf],  # Base_2\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "621285a1-f453-4bab-904c-9c3601b93364",
   "metadata": {},
   "outputs": [],
   "source": [
    "# this is a dict containing the indices of the matrix above and their corresponding/base station car value \n",
    "routing_table_indices = {\n",
    "    'car_1': 0, 'car_2': 1, 'car_3': 2, 'car_4': 3, 'car_5': 4, 'car_6': 5,\\\n",
    "    'car_7': 6, 'car_8': 7, 'car_9': 8, 'base_station_1': 9, 'base_station_2': 10\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "3b8b04a4-9843-4020-9ee5-512950184e91",
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_population(origin, destination, pop_len):\n",
    "    \"\"\"\n",
    "    init_population(origin, destination, pop_len)\n",
    "    initializes a population that represents various permutations of possible paths\n",
    "    from the origin node to destination node. However due to stochastic nature of the \n",
    "    initialization, some paths are invalid while others are possibly repeated. \n",
    "    This problem will be handled in 'get_valid_paths()' function.\n",
    "    origin: the node from which you want to start the search\n",
    "    destination: the node to which you are trying to establish the best path (highest bandwidth)\n",
    "    returns: various permutations of the paths with origin node at the start and destination\n",
    "    node at the end\n",
    "    \"\"\"\n",
    "    routes = []\n",
    "    '''\n",
    "    get indices that can be randomly used to create a population but \n",
    "    exclude the origin and destination since they will have a fixed position\n",
    "    '''\n",
    "    usable_route_indices = {car: idx for car, idx in routing_table_indices.items() if car != origin and car != destination}\n",
    "    node_indices = list(usable_route_indices.values())\n",
    "    # generate population of length defined as a parameter\n",
    "    for i in range(pop_len):\n",
    "        # length of path (chromosome) is not fixed so generate a random length of path for each iteration\n",
    "        path_length = randint(1, len(node_indices))\n",
    "        # choose indices to be used as genes\n",
    "        chosen_indices = choice(np.array(node_indices), path_length, replace=False)\n",
    "        # prepend and append origin and destination respectively to the generated path\n",
    "        route = np.append(routing_table_indices[origin], chosen_indices)\n",
    "        route = np.append(route, routing_table_indices[destination])\n",
    "        # add route to list of routes (the population)\n",
    "        routes.append(route)\n",
    "\n",
    "    return routes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "6adae677-7683-4200-8c95-853ea3ae1a02",
   "metadata": {},
   "outputs": [],
   "source": [
    "routes = init_population('car_9', 'base_station_2', 10000)\n",
    "#print(routes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "2c881f60-0306-48ef-80b7-80221dd7dba9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pop_fitness_combine(population, fitness_vals):\n",
    "    \"\"\"\n",
    "    pop_fitness_combine(population, fitness_vals)\n",
    "    combines the population and fitness data into a list\n",
    "    of tuples that are like (chromosome, fitness val)\n",
    "    population: list of chromosomes (indices of paths from origin node to \n",
    "    destination node)\n",
    "    fitness_vals: list of fitness values which are ordered in same manner as \n",
    "    corresponding chromosomes\n",
    "    returns: a list of tuples with the chromosome fitness value pair\n",
    "    \"\"\"\n",
    "    pop_fitness_data = []\n",
    "    for i in range(len(population)):\n",
    "        pop_fitness_data.append((population[i], fitness_vals[i]))\n",
    "\n",
    "    return pop_fitness_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "df92727c-e6eb-4a1a-8e74-593ff02c6f14",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bandwidth_calc(routes):\n",
    "    \"\"\"\n",
    "    bandwidth_calc(routes)\n",
    "    calculates the end-to-end transmission rate for each route provided\n",
    "    (represented as a chromosome)\n",
    "    routes: the population (list of paths/chromosomes) whose end-to-end transmissions\n",
    "    are being calculated\n",
    "    returns: a list of tuples containing chromosomes and their corresponding end-to-end\n",
    "    transmission cost\n",
    "    \"\"\"\n",
    "    route_bandwidths = []\n",
    "    # loop through every route and get the complete end-to-end transmission rate\n",
    "    for route in routes:\n",
    "        # var for storing all path bandwidths\n",
    "        path_bandwidths = []\n",
    "        # we do -1 because we need to get to second last node where we will check cost between it and last node\n",
    "        for i in range(len(route) - 1):\n",
    "            # get bandwidth between node and its next node and append it to path bandwidths var\n",
    "            path_bandwidths.append(routing_table[route[i]][route[i + 1]])\n",
    "        # computed end-to-end bandwidth rate\n",
    "        end_to_end_bandwidth = min(path_bandwidths)\n",
    "        # add end-to-end bandwidth to list containing all cost data\n",
    "        route_bandwidths.append(end_to_end_bandwidth)\n",
    "    # combine routes and path bandwidths to tuples\n",
    "    pop_fitness_data = pop_fitness_combine(routes, route_bandwidths)\n",
    "\n",
    "    return pop_fitness_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "8ea17119-b5f6-4155-a801-50dc2a2904c4",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "pop_performance = bandwidth_calc(routes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "ecbb503f-0882-4cc4-9652-ef81e4b62251",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_valid_paths(pop_performance):\n",
    "    \"\"\"\n",
    "    get_valid_paths(pop_performance)\n",
    "    evaluates the initialized paths and excludes invalid paths on the basis \n",
    "    of their end-to-end transmission rates. As defined in the routing table, \n",
    "    any none existent node links set to have a bandwidth cost of -infinity. In\n",
    "    the same function, any end-to-end trnasmission rate that will read -infinity\n",
    "    will be eliminated. The function further removes duplicated paths for purposes\n",
    "    of fast convergence and reduction of computational complexities\n",
    "    pop_performance: list of tuples containing chromosomes and their corresponding end-to-end\n",
    "    transmission cost\n",
    "    returns: valid paths with no redundancies (in the same format as their input: list of \n",
    "    tuples containing chromosomes and their corresponding end-to-end transmission cost)\n",
    "    \"\"\"\n",
    "    # Remove repeating tuples\n",
    "    pop_performance = list({tuple(pop): (pop, perform) for pop, perform in pop_performance}.values())\n",
    "    # init list that will contain only valid paths\n",
    "    pop_fitness_data = []\n",
    "    print(\"********************************************Performance**********************************\")\n",
    "    for individual in  pop_performance:\n",
    "        # check validity on basis of end-to-end transmission rate. any -infinity denotes an invalid path\n",
    "        if individual[1] > 0:\n",
    "            path = ''\n",
    "            '''\n",
    "            the following lines are for parsing the valid paths into human \n",
    "            readable strings for purposes of convergence analysis\n",
    "            '''\n",
    "            dest_node_idx = len(individual[0]) - 1\n",
    "            for idx, j in enumerate(individual[0]):\n",
    "                for name, code in routing_table_indices.items():\n",
    "                    if code == j:\n",
    "                        path += name\n",
    "                        if idx != dest_node_idx:\n",
    "                            path += \"->\"\n",
    "            print(f\"Chromosome: {individual[0]}-----actual route: {path}----Score (end-to-end Transmission rate): {int(individual[1])} mbps\")\n",
    "            # finally add valid path to the pop_fitness_data list which will be returned\n",
    "            pop_fitness_data.append(individual)\n",
    "    print(\"*****************************************************************************************\")\n",
    "\n",
    "    return pop_fitness_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "03427123-49dc-4798-a146-123fd95acd49",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********************************************Performance**********************************\n",
      "Chromosome: [ 8  7  6 10]-----actual route: car_9->car_8->car_7->base_station_2----Score (end-to-end Transmission rate): 3 mbps\n",
      "Chromosome: [ 8  4  3  6 10]-----actual route: car_9->car_5->car_4->car_7->base_station_2----Score (end-to-end Transmission rate): 1 mbps\n",
      "Chromosome: [ 8  7  4  6 10]-----actual route: car_9->car_8->car_5->car_7->base_station_2----Score (end-to-end Transmission rate): 2 mbps\n",
      "Chromosome: [ 8  4  6 10]-----actual route: car_9->car_5->car_7->base_station_2----Score (end-to-end Transmission rate): 2 mbps\n",
      "Chromosome: [ 8  4  7  6 10]-----actual route: car_9->car_5->car_8->car_7->base_station_2----Score (end-to-end Transmission rate): 3 mbps\n",
      "Chromosome: [ 8  5  4  6 10]-----actual route: car_9->car_6->car_5->car_7->base_station_2----Score (end-to-end Transmission rate): 2 mbps\n",
      "Chromosome: [ 8  7  4  3  6 10]-----actual route: car_9->car_8->car_5->car_4->car_7->base_station_2----Score (end-to-end Transmission rate): 1 mbps\n",
      "Chromosome: [ 8  4  5  2  0  3  6 10]-----actual route: car_9->car_5->car_6->car_3->car_1->car_4->car_7->base_station_2----Score (end-to-end Transmission rate): 1 mbps\n",
      "Chromosome: [ 8  5  4  0  3  6 10]-----actual route: car_9->car_6->car_5->car_1->car_4->car_7->base_station_2----Score (end-to-end Transmission rate): 1 mbps\n",
      "*****************************************************************************************\n"
     ]
    }
   ],
   "source": [
    "pop_fitness_data = get_valid_paths(pop_performance)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "654c0705-973b-47ef-8a40-d9e95e3ae5ea",
   "metadata": {},
   "source": [
    "## The above are the valid paths from the population"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "c5c9eced-17d7-44a0-8f84-339fa4060a7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tournament_fitness_selection(pop_fitness_data, selection_limit=20):\n",
    "    \"\"\"\n",
    "    tournament_fitness_selection(pop_fitness_data, min_selection=10, selection_limit=50)\n",
    "    fitness selection method that selects the best performing chromosomes (routes) based\n",
    "    on their end-to-end transmission rates. Paths with higher rates get selected\n",
    "    pop_fitness_data: list of tuples containing chromosomes and their corresponding \n",
    "    end-to-end transmission cost. This list only contains valid paths and has no redundancies\n",
    "    selection_limit (optional): the maximum number of selected winners beyond which the top n \n",
    "    are selected. The default is set to 20\n",
    "    returns: a list of selected winners (chromosomes)\n",
    "    \"\"\"\n",
    "    comparison_pairs = []\n",
    "    selected_winners = []\n",
    "    # loop through each route and generate a random pair of indices that are used for tournament elimination\n",
    "    for i in range(len(pop_fitness_data)):\n",
    "        '''\n",
    "        generate random pair of indices on basis of length of population. \n",
    "        Ensure you exclude the current index to avoid pairing a chromosome to itself\n",
    "        '''\n",
    "        possible_pair_indices = [j for j in range(len(pop_fitness_data)) if j != i]\n",
    "        # append the choices to a tuple\n",
    "        comparison_pairs.append((i, choice(possible_pair_indices)))\n",
    "    for j in comparison_pairs:\n",
    "        # compare the performance data. One with gretaest end-to-end bandwidth wins\n",
    "        if pop_fitness_data[j[0]][1] > pop_fitness_data[j[1]][1]:\n",
    "            selected_winners.append(pop_fitness_data[j[0]][0])\n",
    "    # if selected winners exceeds the selection limit, truncate the list to the limit\n",
    "    if len(selected_winners) > selection_limit:\n",
    "        selected_winners = selected_winners[:selection_limit]\n",
    "\n",
    "    return selected_winners"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "88e446fd-1e49-4cf8-899f-fc5162779f2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "selection_winners = tournament_fitness_selection(pop_fitness_data, selection_limit=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "e35b32c1-8939-4016-bca3-da07f9510f78",
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossover_parent_pairing(selection_winners):\n",
    "    \"\"\"\n",
    "    crossover_parent_pairing(selection_winners)\n",
    "    pairs winners of a selection into parents in readiness for crossover\n",
    "    selection_winners: the selected winners from based on the evaluation \n",
    "    and selection function used\n",
    "    returns: a 2D array of parents that will be crossed over\n",
    "    \"\"\"\n",
    "    return [selection_winners[i:i+2] for i in range(0, len(selection_winners), 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "99a2e5c9-42f9-4e7d-b7aa-cdcacaa7cbf7",
   "metadata": {},
   "outputs": [],
   "source": [
    "parents = crossover_parent_pairing(selection_winners)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "a3b609d0-f8e6-4c59-9a5e-c4f3a83ed6c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossover(parents_list, type='single-point'):\n",
    "    \"\"\"\n",
    "    crossover(parents_list, type='single-point')\n",
    "    function that performs a crossover of 2 parents in the population\n",
    "    and returns 2 children\n",
    "    The type of crossover is dependent on the argument passed in as an\n",
    "    argument. Crossover is done by breaking down the chromosome at randomly\n",
    "    selected points and concatenating with the other parents genes from that\n",
    "    position. This is done without changing the genes of the parents since new\n",
    "    children chromosomes are created.\n",
    "    parents_list: a list of 2 parents that need a crossover done on them\n",
    "    type(optional): the type of crossover desired to be done. The default type \n",
    "    is single point\n",
    "    returns: a list of 2 children that result from the crossover\n",
    "    \"\"\"\n",
    "    children_list = []\n",
    "\n",
    "    if type == 'single-point':\n",
    "        # if the type is set to single-point, perform a single-point crossover\n",
    "        crossover_point = randint(1, len(parents_list[0])-1)\n",
    "        '''\n",
    "        slice the list from beginning to randomly selected index,\n",
    "        append slice of second list from that point to the end to the first.\n",
    "        perform the inverse on the second parent\n",
    "        '''\n",
    "        children_list.append([*parents_list[0][:crossover_point],\\\n",
    "                                  *parents_list[1][crossover_point:]])\n",
    "        children_list.append([*parents_list[1][:crossover_point],\\\n",
    "                                  *parents_list[0][crossover_point:]])\n",
    "    elif type == 'two-point':\n",
    "        # if the type is set to two-point, perform a two-point crossover\n",
    "        crossover_point = randint(low=1, high=len(parents_list[0])-1, size=2)\n",
    "        '''\n",
    "        slice the list from beginning to the first randomly selected index, insert \n",
    "        part of the second part from that index up until the second randomly selected \n",
    "        index and add the last part of the forst index from that point to the end\n",
    "        perform the inverse on the second parent\n",
    "        '''\n",
    "        children_list.append([*parents_list[0][:crossover_point[0]],\\\n",
    "                                  *parents_list[1][crossover_point[0]:crossover_point[1]],\\\n",
    "                                  *parents_list[0][crossover_point[1]:]])\n",
    "        children_list.append([*parents_list[1][:crossover_point[0]],\\\n",
    "                                  *parents_list[0][crossover_point[0]:crossover_point[1]],\\\n",
    "                                  *parents_list[1][crossover_point[1]:]])\n",
    "    elif type == 'uniform':\n",
    "        # if the type is set to uniform, perform uniform crossover\n",
    "        child1 = []\n",
    "        child2 = []\n",
    "        # randomly and uniformly swap bits between the two parents\n",
    "        for i in range(len(parents_list[0])):\n",
    "            crossover_point = randint(0, 2)\n",
    "            if crossover_point == 1:\n",
    "                child1.append(parents_list[1][i])\n",
    "                child2.append(parents_list[0][i])\n",
    "            else:\n",
    "                child1.append(parents_list[0][i])\n",
    "                child2.append(parents_list[1][i])\n",
    "        children_list.append(child1)\n",
    "        children_list.append(child2)\n",
    "                \n",
    "    return np.array(children_list, dtype=object)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "a03e07ce-4adc-4c75-8a53-18d4f92bcc37",
   "metadata": {},
   "outputs": [],
   "source": [
    "# combining parents and children to form a new generation\n",
    "children = []\n",
    "for i in parents:\n",
    "    if len(i) == 2:\n",
    "        crossover_result = crossover(i)\n",
    "        for j in crossover_result:\n",
    "            children.append(j)\n",
    "parent_children = np.array(selection_winners + children, dtype=object)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "1fa21f25-1030-4951-bc7d-30cd41edf685",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(population, mutation_rate=0.1, mutation_ratio=0.1):\n",
    "    \"\"\"\n",
    "    mutate(population, mutation_rate=0.1)\n",
    "    function that performs mutation of random individuals in\n",
    "    a population. The number of individuals on which mutation\n",
    "    will take place is determined by the mutation rate \n",
    "    population: the population on in which mutation will is performed\n",
    "    mutation_rate(optional): The percentage of the populations being mutated\n",
    "    returns: the population that has been mutated based in the parameters provided\n",
    "    \"\"\"\n",
    "    '''\n",
    "    randomly obtain the indices of the individuals being mutated. \n",
    "    The number of indices will approximately be based on the percentage \n",
    "    provided as the mutation_rate parameter\n",
    "    '''\n",
    "    mutation_chromosome_indices = choice(np.array(range(len(population))),\\\n",
    "                                         int(math.ceil(len(population) * mutation_rate)),\\\n",
    "                                         replace=False)\n",
    "\n",
    "    #print(\"Mutation Chromosome indices:\"+str(mutation_chromosome_indices))\n",
    "    # loop through each individual in the population\n",
    "    for i in mutation_chromosome_indices:\n",
    "        '''\n",
    "        randomly obtain the indices of the bits being mutated. \n",
    "        The number of indices will approximately be based on the percentage \n",
    "        provided as the mutation_ratio parameter\n",
    "        '''\n",
    "        mutation_gene_indices = choice(np.array(range(len(population[i])))[1:-1],\\\n",
    "                                         2,\\\n",
    "                                         replace=False)\n",
    "        # swap the genes\n",
    "        temp = population[i][mutation_gene_indices[0]]\n",
    "        population[i][mutation_gene_indices[0]] = population[i][mutation_gene_indices[1]]\n",
    "        population[i][mutation_gene_indices[1]] = temp\n",
    "\n",
    "    return np.array(population)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "c809b79b-9f2a-4c34-bf7b-83840a534d17",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Population before mutation:\n",
      "[array([ 8,  7,  6, 10]) array([ 8,  4,  6, 10])\n",
      " array([ 8,  4,  7,  6, 10]) array([ 8,  5,  4,  6, 10])\n",
      " array([8, 7, 6, 10], dtype=object) array([8, 4, 6, 10], dtype=object)\n",
      " array([8, 5, 4, 6, 10], dtype=object)\n",
      " array([8, 4, 7, 6, 10], dtype=object)]\n",
      "------------------------------------------\n",
      "Population after mutation:\n",
      "[array([ 8,  7,  6, 10]) array([ 8,  4,  6, 10])\n",
      " array([ 8,  4,  7,  6, 10]) array([ 8,  5,  4,  6, 10])\n",
      " array([8, 7, 6, 10], dtype=object) array([8, 4, 6, 10], dtype=object)\n",
      " array([8, 5, 4, 6, 10], dtype=object)\n",
      " array([8, 7, 4, 6, 10], dtype=object)]\n"
     ]
    }
   ],
   "source": [
    "print(\"Population before mutation:\\n\"+str(parent_children))\n",
    "print(\"------------------------------------------\")\n",
    "print(\"Population after mutation:\\n\"+str(mutate(parent_children)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c1d5722-1eeb-446d-ae4c-15da092863e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def discrete_genetic_algorithm(init_bin_population, generations=10):\n",
    "    \"\"\"\n",
    "    discrete_genetic_algorithm(init_bin_population, generations=10)\n",
    "    consolidates all the sub-functions of the genetic algorithm and\n",
    "    calls them recurrsively on a generation-to-generation basis as we\n",
    "    analyse convergence performance\n",
    "    init_bin_population: the initial population that represent the \n",
    "    first generation\n",
    "    generations (optional): the maximum number of generations that you would \n",
    "    want to you do work with (termination criteria). Default is set to 10\n",
    "    returns: nothing\n",
    "    \"\"\"\n",
    "    population = init_bin_population\n",
    "    for i in range(generations):\n",
    "        print(f\"**********************************Generation {i + 1}**********************************\")\n",
    "        pop_performance = bandwidth_calc(population)\n",
    "        pop_fitness_data = get_valid_paths(pop_performance)\n",
    "        selection_winners = tournament_fitness_selection(pop_fitness_data)\n",
    "        parents = crossover_parent_pairing(selection_winners)\n",
    "        children = []\n",
    "        for i in parents:\n",
    "            if len(i) == 2:\n",
    "                crossover_result = crossover(i)\n",
    "                for j in crossover_result:\n",
    "                    children.append(j)\n",
    "        parent_children = np.array(selection_winners + children, dtype=object)\n",
    "        population = mutate(parent_children)\n",
    "\n",
    "    return"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d37e0f97-0c2a-45ab-9e75-0aeed815a812",
   "metadata": {},
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bc60fdb-0575-42e9-adb0-a8f16cd6fa25",
   "metadata": {},
   "source": [
    "## Implementation for car 9 to base station 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1179ae02-571a-4857-9fd8-25bfd3cb1ecf",
   "metadata": {},
   "outputs": [],
   "source": [
    "routes = init_population('car_9', 'base_station_2', 100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8f4940c1-4b1c-4f6f-ba2e-ffa48d8944af",
   "metadata": {},
   "outputs": [],
   "source": [
    "discrete_genetic_algorithm(routes, generations=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64b4c18a-809e-46c3-acf7-850e4dde08da",
   "metadata": {},
   "source": [
    "## Implementation for car 9 to base station 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93dd68b0-bcc2-477e-8677-021b1ee3d4af",
   "metadata": {},
   "outputs": [],
   "source": [
    "routes = init_population('car_9', 'base_station_1', 100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f0c7080-a6d0-4735-a624-c9632c3f5fee",
   "metadata": {},
   "outputs": [],
   "source": [
    "discrete_genetic_algorithm(routes, generations=5)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "base"
  },
  "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}