TSPGA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0baa1b46",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T15:44:37.389947Z",
     "start_time": "2021-11-09T15:44:37.373989Z"
    }
   },
   "source": [
    "# Solve TSP problem with Genetic algorithm \n",
    "*SamanArzaghi_610398096*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a02bdee",
   "metadata": {},
   "source": [
    "## Importing libraries\n",
    "First we are going to import some libraries which we may need later..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c79c025d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:57.187553Z",
     "start_time": "2021-11-09T17:34:56.687919Z"
    }
   },
   "outputs": [],
   "source": [
    "# importing some libraries which may we need\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "import operator\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d18267cf",
   "metadata": {},
   "source": [
    "## Extract data from files\n",
    "### A : first test case(bayg29)\n",
    "by opening file we are going to extract weights from tsp.file :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "656c37b4",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:57.518653Z",
     "start_time": "2021-11-09T17:34:57.506611Z"
    }
   },
   "outputs": [],
   "source": [
    "# open file\n",
    "f = open(\"bayg29.tsp\", \"r\")\n",
    "txt = f.readlines()\n",
    "dic_city_length = {}\n",
    "current_node = 0\n",
    "# choosing dimenstion\n",
    "dimension = 29\n",
    "# extracting weightes\n",
    "for i in range(8,36):\n",
    "    current_node += 1\n",
    "    list_weitght = [float(idx) for idx in txt[i].split()]\n",
    "    for j in range(len(list_weitght)):\n",
    "        dic_city_length[current_node, j + current_node + 1] = list_weitght[j]\n",
    "        dic_city_length[j + current_node + 1, current_node] = list_weitght[j]\n",
    "# creat two lists for saving best routes and lengths\n",
    "best_length = []\n",
    "best_routes = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6453ca6c",
   "metadata": {},
   "source": [
    "## Initial population\n",
    "creating 100 unique routes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "55a795c2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:57.959331Z",
     "start_time": "2021-11-09T17:34:57.944371Z"
    }
   },
   "outputs": [],
   "source": [
    "routes = []\n",
    "while(len(routes) < 100): \n",
    "    new_route = random.sample(range(1, dimension + 1), dimension)\n",
    "    # check if new route is unique or not\n",
    "    if new_route not in routes:\n",
    "        routes.append(new_route)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e60096d",
   "metadata": {},
   "source": [
    "# Creating data-frame\n",
    "we use pandas data-frame to access datas better"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "90f390b1",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:58.554445Z",
     "start_time": "2021-11-09T17:34:58.518511Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>routes</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[6, 13, 8, 16, 20, 5, 19, 15, 7, 9, 27, 11, 10...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[10, 16, 15, 19, 14, 5, 25, 6, 8, 4, 2, 20, 12...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[26, 20, 2, 21, 7, 12, 16, 13, 27, 18, 10, 9, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>[13, 27, 16, 24, 8, 21, 3, 7, 9, 12, 22, 17, 2...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>[8, 21, 2, 6, 16, 15, 11, 24, 4, 7, 29, 28, 14...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>95</th>\n",
       "      <td>[6, 4, 23, 15, 5, 28, 11, 25, 18, 14, 10, 22, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>96</th>\n",
       "      <td>[7, 4, 19, 27, 25, 3, 1, 26, 29, 18, 16, 13, 9...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97</th>\n",
       "      <td>[3, 23, 27, 2, 26, 12, 19, 5, 15, 16, 21, 25, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>98</th>\n",
       "      <td>[16, 18, 3, 24, 5, 17, 19, 11, 21, 12, 28, 20,...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>99</th>\n",
       "      <td>[18, 20, 3, 28, 13, 7, 21, 29, 17, 2, 27, 14, ...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>100 rows × 1 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "                                               routes\n",
       "0   [6, 13, 8, 16, 20, 5, 19, 15, 7, 9, 27, 11, 10...\n",
       "1   [10, 16, 15, 19, 14, 5, 25, 6, 8, 4, 2, 20, 12...\n",
       "2   [26, 20, 2, 21, 7, 12, 16, 13, 27, 18, 10, 9, ...\n",
       "3   [13, 27, 16, 24, 8, 21, 3, 7, 9, 12, 22, 17, 2...\n",
       "4   [8, 21, 2, 6, 16, 15, 11, 24, 4, 7, 29, 28, 14...\n",
       "..                                                ...\n",
       "95  [6, 4, 23, 15, 5, 28, 11, 25, 18, 14, 10, 22, ...\n",
       "96  [7, 4, 19, 27, 25, 3, 1, 26, 29, 18, 16, 13, 9...\n",
       "97  [3, 23, 27, 2, 26, 12, 19, 5, 15, 16, 21, 25, ...\n",
       "98  [16, 18, 3, 24, 5, 17, 19, 11, 21, 12, 28, 20,...\n",
       "99  [18, 20, 3, 28, 13, 7, 21, 29, 17, 2, 27, 14, ...\n",
       "\n",
       "[100 rows x 1 columns]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = {'routes' : routes}\n",
    "df = pd.DataFrame(df)\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd6e31e",
   "metadata": {},
   "source": [
    "# Calculate fitness\n",
    "with this function we can calculate a whole cycle length of a rout.\n",
    "\n",
    "**NOTE** : because shorter length is better in this position, we move length between 0 and 1. \n",
    "(divide 1 by length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a2575993",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:59.134169Z",
     "start_time": "2021-11-09T17:34:59.112736Z"
    }
   },
   "outputs": [],
   "source": [
    "def calculate_fitness(route):\n",
    "    '''\n",
    "        route --> a single route ( type : list )\n",
    "    '''\n",
    "    distance = 0\n",
    "    for i in range(len(route) - 1):\n",
    "        distance += dic_city_length[route[i], route[i + 1]]\n",
    "    # from last node to first node\n",
    "    distance += dic_city_length[route[0], route[-1]]\n",
    "    fitness = 1 / float(distance)\n",
    "    return fitness "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "136f3fb2",
   "metadata": {},
   "source": [
    "# Selection\n",
    "by evaluate function we will chose most talented route to survive.\n",
    "\n",
    "**NOTE** : both competitive methods and the survival of the fittest have been tried and the second method has obtained better results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "653a0aa2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:34:59.541869Z",
     "start_time": "2021-11-09T17:34:59.525857Z"
    }
   },
   "outputs": [],
   "source": [
    "def evaluate(df, num_chosens):\n",
    "    '''\n",
    "        df --> data-frame of routes ( type : pandas-df )\n",
    "        num_chosens --> survival rate ( type : int )\n",
    "    '''\n",
    "    # In the comment below, I implemented a competitive method and DID NOT get a good result\n",
    "    '''\n",
    "    for i in range(len(df)):\n",
    "        df.loc[i, 'fitness'] = calculate_fitness(df.loc[i, 'routes'])   \n",
    "    column = df[\"fitness\"]\n",
    "    max_index = column.idxmax()\n",
    "    best_length.append(1 / df.loc[max_index, 'fitness'])\n",
    "    best_routes.append(df.loc[max_index, 'routes'])\n",
    "    sums = df['fitness'].sum()\n",
    "    for i in range(len(df)):\n",
    "        df.loc[i, 'prob_choosing'] = df.loc[i, 'fitness'] / sums\n",
    "    probe_of_routes = list(df['prob_choosing'])\n",
    "    routes_list = list(range(0, len(df)))\n",
    "    accepted_routes = []\n",
    "    while(len(accepted_routes) != num_chosens):\n",
    "        accepted_one = random.choices(routes_list, weights = probe_of_routes, k = 1)[0]\n",
    "        if(accepted_one not in accepted_routes):\n",
    "            accepted_routes.append(accepted_one)\n",
    "    for i in range(len(accepted_routes)):\n",
    "        accepted_routes[i] = df.loc[accepted_routes[i], 'routes']\n",
    "    df = pd.DataFrame({'routes' : accepted_routes})\n",
    "    '''\n",
    "    # calculating fitness for each route\n",
    "    for i in range(len(df)):\n",
    "        df.loc[i, 'fitness'] = calculate_fitness(df.loc[i, 'routes']) \n",
    "    # sorting by fitness\n",
    "    df = df.sort_values(by=['fitness'], ascending=False)\n",
    "    df = df.reset_index()\n",
    "    # save best route and it's length\n",
    "    best_length.append(1 / df.loc[0, 'fitness'])\n",
    "    best_routes.append(df.loc[0, 'routes'])\n",
    "    accepted_routes = []\n",
    "    # convert new generation to data-frame\n",
    "    for i in range(num_chosens):\n",
    "        accepted_routes.append(df.loc[i, 'routes'])\n",
    "    df = pd.DataFrame({'routes' : accepted_routes})\n",
    "    return df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96374588",
   "metadata": {},
   "source": [
    "# Creating mutation functions\n",
    "i decided not to use just one mutation function, but to use several mutation functions and use them all (hybrid mutation).\n",
    "\n",
    "in the next cell, we construct four different mutation functions (swap, inversion, RGIBNNM, and IRGIBNNM, respectively)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "797227a5",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:00.172107Z",
     "start_time": "2021-11-09T17:35:00.154157Z"
    }
   },
   "outputs": [],
   "source": [
    "# make swap mutation\n",
    "def swap_mutation(route):\n",
    "    '''\n",
    "        route --> a single route ( type : list )\n",
    "    '''\n",
    "    # choose two randome cities\n",
    "    first_gen, second_gen = random.sample(range(len(route)), 2)\n",
    "    # change their places\n",
    "    route[first_gen], route[second_gen] = route[second_gen], route[first_gen]\n",
    "    return route"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a445bacc",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:00.534633Z",
     "start_time": "2021-11-09T17:35:00.508638Z"
    }
   },
   "outputs": [],
   "source": [
    "# make inversion mutation\n",
    "def inversion_mutation(route):\n",
    "    '''\n",
    "        route --> a single route ( type : list )\n",
    "    '''\n",
    "    # choose two random cities\n",
    "    first_gen, second_gen = random.sample(range(len(route)), 2)\n",
    "    if(first_gen > second_gen):\n",
    "        first_gen, second_gen = second_gen, first_gen\n",
    "    sub_set = route[first_gen + 1 : second_gen]\n",
    "    # inverse the sub set between two random cities\n",
    "    sub_set = sub_set[::-1]\n",
    "    route[first_gen + 1 : second_gen] = sub_set\n",
    "    return route"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "e3a15d64",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:00.939427Z",
     "start_time": "2021-11-09T17:35:00.903012Z"
    }
   },
   "outputs": [],
   "source": [
    "# make RGIBNNM mutation\n",
    "def RGIBNNM_mutation(route):\n",
    "    '''\n",
    "        route --> a single route ( type : list )\n",
    "    '''\n",
    "    # choose one randome city\n",
    "    first_gen = random.sample(range(len(route)), 1)[0]\n",
    "    # finde the closes city to random city\n",
    "    most_close = float(\"inf\")\n",
    "    for i in range(len(route)):\n",
    "        if(i != first_gen):\n",
    "            if(dic_city_length[route[first_gen], route[i]] < most_close):\n",
    "                most_close = dic_city_length[route[first_gen], route[i]]\n",
    "                second_gen = i\n",
    "    # move the random city before closest that we found and shift others\n",
    "    temp_number = route[first_gen]\n",
    "    temp_number_2 = route[second_gen]\n",
    "    route.remove(temp_number)\n",
    "    route.insert(route.index(temp_number_2), temp_number)\n",
    "    return route"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e9ed4c9b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:01.322787Z",
     "start_time": "2021-11-09T17:35:01.295875Z"
    }
   },
   "outputs": [],
   "source": [
    "# make IRGIBNNM mutation\n",
    "def IRGIBNNM_mutation(route):\n",
    "    '''\n",
    "        route --> a single route ( type : list )\n",
    "    '''\n",
    "    # apply inversion mutation first\n",
    "    route = inversion_mutation(route)\n",
    "    # choose a random city\n",
    "    first_gen = random.sample(range(len(route)), 1)[0]\n",
    "    # find the closest city to random city\n",
    "    most_close = float(\"inf\")\n",
    "    for i in range(len(route)):\n",
    "        if(i != first_gen):\n",
    "            if(dic_city_length[route[first_gen], route[i]] < most_close):\n",
    "                most_close = dic_city_length[route[first_gen], route[i]]\n",
    "                second_gen = i\n",
    "    # find the closest five cities to second city\n",
    "    neiber_second_gen = []\n",
    "    for i in range(len(route)):\n",
    "        if(i != second_gen):\n",
    "            neiber_second_gen.append([route[i], dic_city_length[route[second_gen], route[i]]])\n",
    "    neiber_second_gen = sorted(neiber_second_gen, key = lambda x: x[1])\n",
    "    temp_number = route[first_gen]\n",
    "    # randomly choose one of five citys that we found\n",
    "    while(True):\n",
    "        random_gen = random.sample(range(5), 1)[0]\n",
    "        if(neiber_second_gen[random_gen][0] != temp_number):\n",
    "            temp_number_2 = neiber_second_gen[random_gen][0]\n",
    "            break\n",
    "    # move first random city before third city we choose and shift other ones\n",
    "    route.remove(temp_number)\n",
    "    route.insert(route.index(temp_number_2), temp_number)\n",
    "    return route"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a9b2d1c",
   "metadata": {},
   "source": [
    "# Make new generation( apply mutation function)\n",
    "with the below code we are going to apply mutation function on all routes and twice the population.\n",
    "\n",
    "how we do it?!\n",
    "\n",
    "it's easy : we apply for mutation functions on every single route and choose the best mutation that have made, check it if it's unique, and then add it to data-frame.\n",
    "\n",
    "**Note :** if you noticed, we did not do any cross over... because i've tried both with cross over and without cross over, and every time without cross over performed better. so, some how in TSP problem cross over does not work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "38c831fd",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:01.717582Z",
     "start_time": "2021-11-09T17:35:01.706586Z"
    }
   },
   "outputs": [],
   "source": [
    "# make new generation\n",
    "def new_generation(df):\n",
    "    '''\n",
    "            df --> data-frame of routes ( type : pandas-df )\n",
    "    '''\n",
    "    new_gen_list = []\n",
    "    # apply for mutations on every single rout\n",
    "    for i in list(df['routes']):\n",
    "        mutation_list = []\n",
    "        test =  i.copy()\n",
    "        swap_mut = swap_mutation(test)\n",
    "        mutation_list.append([swap_mut, calculate_fitness(swap_mut)])\n",
    "        test =  i.copy()\n",
    "        inversion_mut = inversion_mutation(test)\n",
    "        mutation_list.append([inversion_mut, calculate_fitness(inversion_mut)])\n",
    "        test =  i.copy()\n",
    "        RGIBNNM_mut = RGIBNNM_mutation(test)\n",
    "        mutation_list.append([RGIBNNM_mut, calculate_fitness(RGIBNNM_mut)])\n",
    "        test =  i.copy()\n",
    "        IRGIBNNM_mut = IRGIBNNM_mutation(test)\n",
    "        mutation_list.append([IRGIBNNM_mut, calculate_fitness(IRGIBNNM_mut)])\n",
    "        mutation_list = sorted(mutation_list, key = lambda x: x[1],reverse=True)\n",
    "        # choose the best one\n",
    "        for i in mutation_list:\n",
    "            if(i not in list(df['routes'])):\n",
    "                new_gen_list.append(i[0])\n",
    "                break\n",
    "    total_list = list(df['routes']) + new_gen_list\n",
    "    df = pd.DataFrame({'routes' : total_list})\n",
    "    return df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb5585fb",
   "metadata": {},
   "source": [
    "# when all is said and done :))\n",
    "in the final step, we put everything together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "16ae725c",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:02.363349Z",
     "start_time": "2021-11-09T17:35:02.355370Z"
    }
   },
   "outputs": [],
   "source": [
    "def ga_tsp(df, num_chosens, epoch):\n",
    "    '''\n",
    "            df --> data-frame of routes ( type : pandas-df )\n",
    "            num_chosens --> survival rate ( type : int )\n",
    "            epoch -->  the number of passes of the entire population ( type : int )\n",
    "    '''\n",
    "    for i in range(epoch):\n",
    "        # creat new generation\n",
    "        df = new_generation(df)\n",
    "        # eliminate weaks\n",
    "        df = evaluate(df, num_chosens)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1de29aae",
   "metadata": {},
   "source": [
    "# first test case(bayg29)\n",
    "we have all data ready at the beginning.\n",
    "\n",
    "we have 100 initialize population, 100 epochs, crossover = 0%, mutation = 100%, and 100 number of survivor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6df899ba",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:12.084804Z",
     "start_time": "2021-11-09T17:35:07.330038Z"
    }
   },
   "outputs": [],
   "source": [
    "ga_tsp(df, 100, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "334ca192",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:12.527811Z",
     "start_time": "2021-11-09T17:35:12.403102Z"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD8CAYAAACb4nSYAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAjp0lEQVR4nO3de5xdZX3v8c937rlNZpKZXMjkBiSGQEggYwiCKBE0oEdoRQutgPWSIngq6jmt1h4vWG21ih4t0iJBwEO5VFBSGqRRYoFqEiYhBHLBTAKYCblBLkNCMpmZ/M4few1ukgmzJ5mZPXvv7/v12i/Wfp611v49Ll+/efKsZ61HEYGZmRWGomwHYGZmfcdJ38ysgDjpm5kVECd9M7MC4qRvZlZAnPTNzApIl0lfUoWkZZKelrRa0leT8sclrUw+L0n6eVL+Tkl70uq+lHauuZKek9Qo6fO91iozM+tUSQb7tABzImKvpFLgCUkPR8TbO3aQdD/wYNoxj0fE+9JPIqkYuAm4EGgCnpS0ICLWHHcrzMwsI1329CNlb/K1NPm8/kSXpEpgDvDzLk41C2iMiI0RcRC4B7jkWII2M7Njk0lPv6OXvhw4GbgpIpamVV8K/CoimtPKzpb0NPAS8L8iYjUwBtiUtk8TcFZXv11TUxMTJkzIJEwzMwOWL1/+ckTUdlaXUdKPiHZghqQq4GeSTouIZ5PqK4Bb03ZfAYxPhoMuJvUvgEndCVjSPGAewLhx42hoaOjO4WZmBU3Si0er69bsnYjYDSwG5iYnriE1bPMfafs0dwwHRcRCoDTZbzMwNu10dUlZZ79zS0TUR0R9bW2nf6zMzOwYZDJ7pzbp4SNpAKkbseuS6suAhyLiQNr+oyQp2Z6V/MYrwJPAJEkTJZUBlwMLerAtZmbWhUyGd0YDdyTj+kXAfRHxUFJ3OfAPh+1/GfBJSW3AfuDySL3Ks03Sp4BHgGLgtmSs38zM+oj6+6uV6+vrw2P6ZmaZk7Q8Iuo7q/MTuWZmBcRJ38ysgDjpm5kVkLxM+gda27nlsQ0s3fhKtkMxM+tX8jLpA9z2xAt85z9/R3+/UW1m1pfyMulXlBZz7fknseyFnfx2g3v7ZmYd8jLpA3yofiyjKiv43i/Xu7dvZpbI26Tv3r6Z2ZHyNumDe/tmZofL66Tv3r6Z2RvlddKHVG+/emAp96/o9IWeZmYFJe+TfkVpMRNrBrFlz/5sh2JmlnV5n/QBRg2tYGvzga53NDPLcwWR9EdWVrBtj5O+mVlBJP1RlRXsO9jOqwdasx2KmVlWFUbSH1oBwDYP8ZhZgctkucQKScskPS1ptaSvJuW3S3pe0srkMyMpl6TvS2qUtErSmWnnulrS+uRzda+16jAjK1NJf+uelr76STOzfimT5RJbgDkRsVdSKfCEpIeTuv8dET89bP+LgEnJ5yzgZuAsScOALwP1QADLJS2IiF090ZA3M6oj6bunb2YFrsuefqTsTb6WJp83e7z1EuDO5LglQJWk0cB7gEURsTNJ9IuAuccXfmY8vGNmlpLRmL6kYkkrge2kEvfSpOrryRDOdyWVJ2VjgE1phzclZUcr7+z35klqkNSwY8eOzFtzFBWlxVQNLGWrZ/CYWYHLKOlHRHtEzADqgFmSTgO+AEwB3goMA/66p4KKiFsioj4i6mtra3vknKMqPVffzKxbs3ciYjewGJgbEVuSIZwW4MfArGS3zcDYtMPqkrKjlfeJkZUVHt4xs4KXyeydWklVyfYA4EJgXTJOjyQBlwLPJocsAK5KZvHMBvZExBbgEeDdkqolVQPvTsr6xKjKCg/vmFnBy2T2zmjgDknFpP5I3BcRD0l6VFItIGAlcE2y/0LgYqAReA34c4CI2Cnpa8CTyX43RMTOHmtJF0YOrWDH3hZa2w9RWlwQjyeYmR2hy6QfEauAMzopn3OU/QO47ih1twG3dTPGHjGqsoII2PFqCydUDchGCGZmWVcwXd5RQ1OTi3wz18wKWcEk/Y6ncv3iNTMrZAWT9P1UrplZASX9YYPKKCsuctI3s4JWMElfEiMqyz28Y2YFrWCSPvipXDOzgkr6I4dWsK3Zr1c2s8JVUEm/46nc1KMEZmaFp+CS/v7WdpoPtGU7FDOzrCiopD/S79U3swJXUEn/9bn6nsFjZgWqMJO+e/pmVqAKKumPqEy9f8dz9c2sUBVU0q8oLaZ6YKl7+mZWsAoq6QOcWDuY/3hmC79+bnu2QzEz63OZrJxVIWmZpKclrZb01aT8LknPSXpW0m2SSpPyd0raI2ll8vlS2rnmJsc0Svp87zXr6L79wemMqqzgz29/ku/853O0H/KcfTMrHJn09FuAORExHZgBzE2WQbyL1MLo04ABwMfTjnk8ImYknxsAkpW3bgIuAqYCV0ia2mMtydDEmkH8/Lpz+ODMOn7waCOfuXdlX4dgZpY1XSb9ZPHzvcnX0uQTEbEwqQtgGamFzt/MLKAxIjZGxEHgHuCS44j9mFWUFvOty6bzqfNPZsHTL/HkC322aqOZWVZlNKYvqVjSSmA7sCgilqbVlQJXAr9IO+TsZDjoYUmnJmVjgE1p+zQlZZ393jxJDZIaduzYkXlruum6809mZGU531i41q9mMLOCkFHSj4j2iJhBqjc/S9JpadU/BB6LiMeT7yuA8clw0A+An3c3qIi4JSLqI6K+tra2u4dnbEBZMZ+5YDJP/X43j6ze2mu/Y2bWX3Rr9k5E7AYWA3MBJH0ZqAU+m7ZPc8dwUEQsBEol1QCbgbFpp6tLyrLqspl1nDxiMN/6xXO0th/KdjhmZr0qk9k7tZKqku0BwIXAOkkfB94DXBERh9L2HyVJyfas5DdeAZ4EJkmaKKkMuBxY0MPt6baS4iL+eu4UNr68j3ue3NT1AWZmOawkg31GA3cks2+KgPsi4iFJbcCLwG+THP9AMlPnMuCTSf1+4PLkZm+bpE8BjwDFwG0Rsbrnm9R9F5wygpnjq5n/+EaunD0+2+GYmfWaLpN+RKwCzuikvNNjI+KfgH86St1CYGE3Y+x1krjotFH83X+sZXvzAUYk7+gxM8s3BfdE7tHMHF8NQMOLu7IciZlZ73HST5x6wlAqSos8Z9/M8pqTfqKspIgZY6toeME9fTPLX076ad46YRhrtjSzr8XLKZpZfnLSTzNzfDXth4KVm3ZnOxQzs17hpJ/mzPHVSHhc38zylpN+msqKUqaMqvS4vpnlLSf9w7x1QjVP/X4XbX4lg5nlISf9w9RPGMa+g+2s2/pqtkMxM+txTvqHqU8e0vK4vpnlIyf9w5xQNYAxVQM8rm9meclJvxP1E6ppeNE9fTPLP076nThjbBXbmlvYuudAtkMxM+tRTvqdmD62CoCVmzzEY2b5xUm/E6eMrqS0WKzctCfboZiZ9ahMVs6qkLQsWeh8taSvJuUTJS2V1Cjp3mQ1LCSVJ98bk/oJaef6QlL+nKT39FqrjlNFaTGnjK7kab+OwczyTCY9/RZgTrLQ+QxgrqTZwDeB70bEycAu4GPJ/h8DdiXl3032Q9JUUksknkpqjd0fJqtx9UvT66p4ZvMe2g9FtkMxM+sxXSb9SNmbfC1NPgHMAX6alN8BXJpsX5J8J6l/V7Jm7iXAPRHREhHPA43ArJ5oRG+YPraKvS1tbNyxt+udzcxyREZj+pKKJa0EtgOLgA3A7ojoeAdxEzAm2R4DbAJI6vcAw9PLOzmm35nx+s3c3VmNw8ysJ2WU9COiPSJmAHWkeudTejMoSfMkNUhq2LFjR2/+1FGdWDOIIeUlPN20Oyu/b2bWG7o1eycidgOLgbOBKkkdi6PXAZuT7c3AWICkfijwSnp5J8cc/ju3RER9RNTX1tZ2J8QeU1QkTh87lKc9g8fM8kgms3dqJVUl2wOAC4G1pJL/ZcluVwMPJtsLku8k9Y9GRCTllyezeyYCk4BlPdSOXjG9roq1W5o50Nqe7VDMzHpESde7MBq4I5lpUwTcFxEPSVoD3CPp74CngPnJ/vOBn0hqBHaSmrFDRKyWdB+wBmgDrouIfp1Np4+tou1QsGZLM2eOq852OGZmx63LpB8Rq4AzOinfSCezbyLiAPDBo5zr68DXux9mdrx+M/f3u530zSwv+IncNzGysoJRlRW+mWtmecNJvwvTxw71k7lmljec9Lswc3w1L7zyGtua/cZNM8t9TvpdOPfk1JTRx36XnecFzMx6kpN+F04ZPYSaweU8vv7lbIdiZnbcnPS7IInzJtXwROPLHPLL18wsxznpZ+C8ybXs3HeQZ1/y07lmltuc9DNw7qQaAA/xmFnOc9LPQM3gck49oZL/8s1cM8txTvoZOm9yLSte3MWrB1qzHYqZ2TFz0s/QeZNqaTsULNm4M9uhmJkdMyf9DM0cX83AsmLP1zeznOakn6GykiLOPnE4j6130jez3OWk3w2zTxzOi6+8xs59B7MdipnZMXHS74ZRQysAeHlvS5YjMTM7Nk763TB8cBngpG9muSuT5RLHSlosaY2k1ZI+nZTfK2ll8nlB0sqkfIKk/Wl1/5x2rpmSnpHUKOn7ktRrLesFNYPLAXhlr4d3zCw3ZbJcYhvwuYhYIWkIsFzSooj4k44dJH0HSH9HwYaImNHJuW4GPgEsBRYCc4GHjzX4vvaHpO+evpnlpi57+hGxJSJWJNuvkloUfUxHfdJb/xBw95udR9JooDIiliQLpd8JXHrsofe9qgGlFAle8Y1cM8tR3RrTlzSB1Hq5S9OK3w5si4j1aWUTJT0l6b8kvT0pGwM0pe3TRNofj8N+Z56kBkkNO3b0nymSRUVi2KByXvbwjpnlqIyTvqTBwP3A9RHRnFZ1BW/s5W8BxkXEGcBngX+VVNmdoCLiloioj4j62tra7hza62oGl3l4x8xyViZj+kgqJZXw74qIB9LKS4A/BmZ2lEVEC9CSbC+XtAGYDGwG6tJOW5eU5ZThg8s8e8fMclYms3cEzAfWRsSNh1VfAKyLiKa0/WslFSfbJwKTgI0RsQVoljQ7OedVwIM91I4+M3xQucf0zSxnZTK8cw5wJTAnbRrmxUnd5Rx5A/c8YFUyhfOnwDUR0fGWsmuBW4FGYAM5NHOnw/DBZZ6yaWY5q8vhnYh4Auh0Pn1EfKSTsvtJDQV1tn8DcFr3QuxfagaXs7eljQOt7VSUFmc7HDOzbvETud1UkzyV6yEeM8tFTvrdNHyQH9Ays9zlpN9NHe/f8bi+meUiJ/1u6ngVg6dtmlkuctLvpj+8adM9fTPLPU763TSwrIQBpcUe0zeznOSkfwyGDy7z7B0zy0lO+segZnC5x/TNLCc56R+DGj+Va2Y5ykn/GKTev+OevpnlHif9Y9Dx/p3UWjBmZrnDSf8YDB9cTtuhoHl/W7ZDMTPrFif9Y9Dx/p0dvplrZjnGSf8Y+P07ZparnPSPQc0Qv2nTzHJTJitnjZW0WNIaSaslfTop/4qkzZ0srIKkL0hqlPScpPeklc9Nyholfb53mtT73NM3s1yVyRq5bcDnImKFpCHAckmLkrrvRsS303eWNJXUilqnAicAv5Q0Oam+CbgQaAKelLQgItb0REP6UvXAUiS/f8fMck8mK2dtAbYk269KWguMeZNDLgHuSRZIf15SIzArqWuMiI0Aku5J9s25pF9SXET1wDLP1TeznNOtMX1JE4AzgKVJ0ackrZJ0m6TqpGwMsCntsKak7GjlOWn4ID+Va2a5J+OkL2kwqbVvr4+IZuBm4CRgBql/CXynp4KSNE9Sg6SGHTt29NRpe5QXSDezXJRR0pdUSirh3xURDwBExLaIaI+IQ8CP+MMQzmZgbNrhdUnZ0cqPEBG3RER9RNTX1tZ2pz19ZrhfumZmOSiT2TsC5gNrI+LGtPLRabv9EfBssr0AuFxSuaSJwCRgGfAkMEnSREllpG72LuiZZvS9mkFlTvpmlnMymb1zDnAl8IyklUnZ3wBXSJoBBPAC8BcAEbFa0n2kbtC2AddFRDuApE8BjwDFwG0RsbrHWtLHagaX03ygjYNthygr8eMOZpYbMpm98wSgTqoWvskxXwe+3kn5wjc7LpcMT9bKPe9biykueuP/POWlRVx/wWTeP/2EbIRmZnZUmfT0rRMXnDKCZ18ax8G2Q0fUrdvazF/e/RQNL+zki+89hfKS4ixEaGZ2JCf9YzSisoJv/NG0Tuta2w/xrV+s40ePP8/Tm3bzo6vqGVFZ0ccRmpkdyYPRvaC0uIgvvncq/3LlTNZv38u8nyznQGt7tsMyM3PS703vOXUUN35oOis37eZLDz7rRVfMLOuc9HvZ3NNG85dzTua+hibu/O2L2Q7HzAqcx/T7wPUXTGbNlmZueGgNv9/5Gm87aThvnTiMyorSbIdmZgXGPf0+UFQkvvsnMzj/LbX8ZMmLfOyOBs64YREPrXop26GZWYFxT7+PDKko5dar38qB1nZW/H4Xf/PAM/y/JS/yvtM9l9/M+o57+n2sorSYt51Uw0XTRvPkC7vYs7812yGZWQFx0s+Sd00ZQfuh4PH1/fMtomaWn5z0s+SMcdVUDSzl0XXbsx2KmRUQJ/0sKS4S75hcy6+f20H7Ic/fN7O+4aSfRXOmjGDnvoM83bQ726GYWYFw0s+id0yupUiw2EM8ZtZHnPSzqGpgGTPHV/OrtU76ZtY3nPSzbM6UkazZ0szWPQeyHYqZFYBMlkscK2mxpDWSVkv6dFL+j5LWSVol6WeSqpLyCZL2S1qZfP457VwzJT0jqVHS95OlGAvanCkjADyLx8z6RCY9/TbgcxExFZgNXCdpKrAIOC0iTgd+B3wh7ZgNETEj+VyTVn4z8AlS6+ZOAub2RCNy2eSRgzmxdhDzn9jY6YIsZmY9qcukHxFbImJFsv0qsBYYExH/GRFtyW5LgLo3O0+ykHplRCyJ1DuG7wQuPZ7g84Ek/va9p7Bhxz7u+M0L2Q7HzPJct8b0JU0AzgCWHlb1UeDhtO8TJT0l6b8kvT0pGwM0pe3TlJR19jvzJDVIatixI/+fWJ0zZSTvmjKC7/3yd2xv9ti+mfWejJO+pMHA/cD1EdGcVv5FUkNAdyVFW4BxEXEG8FngXyVVdieoiLglIuojor62trY7h+asL/2PqbS2B3//8Lpsh2JmeSyjt2xKKiWV8O+KiAfSyj8CvA94VzJkQ0S0AC3J9nJJG4DJwGbeOARUl5QZMH74IP7iHSfyg0cbmV439PU1dU+vG0pd9cAsR2dm+aLLpJ/MsJkPrI2IG9PK5wJ/BbwjIl5LK68FdkZEu6QTSd2w3RgROyU1S5pNanjoKuAHPduc3HbtO09mwdMv8ZV/X/N62VkTh3HvX5ydxajMLJ9k0tM/B7gSeEbSyqTsb4DvA+XAomTm5ZJkps55wA2SWoFDwDURsTM57lrgdmAAqXsA6fcBCt6AsmIe/vTb2bRzPwC3PLaRhc9sof1QUFxU8LNbzawHdJn0I+IJoLOMs/Ao+99Paiios7oG4LTuBFhoBpaV8JZRQwA45+Th3L+iiQ079jJ55JAsR2Zm+cBP5PZjp9cNBeCZpj1ZjsTM8oWTfj82sWYwA8uKeWazk76Z9Qwn/X6suEicdsJQVvnVy2bWQ5z0+7lpdUNZs6WZtna/osHMjp+Tfj83bcxQDrQeonHH3myHYmZ5wEm/n5uW3Mxd5Zu5ZtYDnPT7uYnDBzG4vMQzeMysRzjp93NFReK0MZWewWNmPcJJPwdMG5O6mdvqm7lmdpyc9HPAtLoqDrYd4nfbXs12KGaW45z0c8DpY1I3c5/1EI+ZHaeMXq1s2TV++ECGVJSw7PldvPMtI46oH1xewqByX0oz65ozRQ6QxPS6Ku5f0cT9K5qOqC8rKeJ9p4/mw7PHc8bYKrzevJkdjZN+jvjapafx2w2vdFq3dkszP3tqMw+s2MyMsVX88M/O5ISqAX0coZnlAiULXvVb9fX10dDQkO0w+r29LW387KnNfOvhdQwqL+H2j76VKaO6tUqlmeUJScsjor6zui5v5EoaK2mxpDWSVkv6dFI+TNIiSeuT/1Yn5ZL0fUmNklZJOjPtXFcn+6+XdHVPNdBS4/pXzh7PfdecTRB88Obf8psNL2c7LDPrZzKZvdMGfC4ipgKzgeskTQU+D/wqIiYBv0q+A1xEaonEScA84GZI/ZEAvgycBcwCvtzxh8J6zimjK3ng2nMYNbSCK+cv4zP3rvRUTzN7XZdJPyK2RMSKZPtVYC0wBrgEuCPZ7Q7g0mT7EuDOSFkCVEkaDbwHWBQROyNiF7AImNuTjbGUMVUD+Okn38ZH3jaBXzy7lXd/9zE+cWcDv9nwMv19OM/Mele3buRKmgCcQWph85ERsSWp2gqMTLbHAJvSDmtKyo5W3tnvzCP1rwTGjRvXnRAtMXRAKf/nfVP51Pkn8+PfvMCdv32BRWu2cVLtID48ezx/etY4ykuKsx2mmfWxjB/OkjSY1Nq310dEc3pdpLqPPdaFjIhbIqI+Iupra2t76rQFqXpQGZ+9cDJLvvAuvvPB6QypKOWr/76GS2/6jYd9zApQRklfUimphH9XRDyQFG9Lhm1I/rs9Kd8MjE07vC4pO1q59YGK0mI+MLOOn193DrdeVc/25gO87wdPMP+J5z3kY1ZAMpm9I2A+sDYibkyrWgB0zMC5GngwrfyqZBbPbGBPMgz0CPBuSdXJDdx3J2XWxy6YOpJHPnMe502q4WsPreHuZZu6PsjM8kImPf1zgCuBOZJWJp+LgX8ALpS0Hrgg+Q6wENgINAI/Aq4FiIidwNeAJ5PPDUmZZUHN4HJ+dFU9Z46r4gePrqelrT3bIZlZH/DDWQXuifUv8+H5S7nhklO56uwJ2Q7HzHrAcT2cZfntnJOHM2viMG5a3MiBVvf2zfKdk36Bk8RnL5zMtuYW/nXp77Mdjpn1Mid9Y/aJw3nbScP54a83sP+ge/tm+cxJ3wD4zIWTeXlvCzctbsx2KGbWi5z0DYC3ThjGB86s44e/bmT5i55UZZavnPTtdV95/1ROqBrAZ+59mr0tbdkOx8x6gZO+vW5IRSk3fmgGm3a9xtf+fU22wzGzXuCVs+wNZk0cxiffcRI//PUG1m17leJOVl68fNY4PlQ/9sgKM+v3nPTtCNdfMJnmA628+MprR9Rt3XOAz9+/ipGVFbxjsl+GZ5Zr/ESudcu+ljY+cPNveGn3fhZ86lwm1AzKdkhmdhg/kWs9ZlB5CT+6qp6iIjHvJw2+4WuWY9zTt2Py340vc9VtyygSFOnIgf+BZcXUVQ+krnoAbztpOB+ePR51sp+Z9bw36+l7TN+OyTkn13Dr1fUs2fhKp/WvHmijadd+1mxp5uFnt9J8oI3rzj+5j6M0s8M56dsxO/8tIzj/LSPedJ9Dh4LP3reSf3zkOWqHlHvWj1mWOelbryoqEt+6bDqv7DvIFx54hprBZcyZMrLrA82sV2SyctZtkrZLejat7N60BVVekLQyKZ8gaX9a3T+nHTNT0jOSGiV9Xx7gLRhlJUXc/OGZTB1dyTU/WcEtj23g0KH+fS/JLF9lMnvndmBuekFE/ElEzIiIGaTWzn0grXpDR11EXJNWfjPwCWBS8nnDOS2/DS4v4c6PzuKdb6nlGwvX8ae3LqFp12u0H4qMP/5DYXb8uhzeiYjHJE3orC7prX8ImPNm50gWTq+MiCXJ9zuBS4GHuxmv5bDqQWX8y5Uz+bflTXx1wWrO/ebibh0vwXmTarly9njOnzKC4iL/Y9Gsu453TP/twLaIWJ9WNlHSU0Az8LcR8TgwBmhK26cpKbMCI4kP1Y/l7BOHs+Dpl2jvRu/91QOtLHj6JT5+ZwNjqgbwzQ+czrmTanoxWrP8c7xJ/wrg7rTvW4BxEfGKpJnAzyWd2t2TSpoHzAMYN27ccYZo/dHYYQOPaQrnX82dwi/XbOPGRb/j43c+yR1/PouzThzeCxGa5adjfiJXUgnwx8C9HWUR0RIRryTby4ENwGRgM1CXdnhdUtapiLglIuojor621u93sT8oLS7iommjuXvebMZUDeCjtz/Jyk27sx2WWc44ntcwXACsi4jXh20k1UoqTrZPJHXDdmNEbAGaJc1O7gNcBTx4HL9tBa5mcDl3fXw2wweXc9X8pdz+38/z340vs635AAda21//dGf4yKwQdDm8I+lu4J1AjaQm4MsRMR+4nDcO7QCcB9wgqRU4BFwTER3LMF1LaibQAFI3cH0T147LqKEV3PXxs7hy/lK+cpT3/0upmUOVFaWUlxbRcet32pih3HDpaVRWlPZdwGb9gN+9YzkvItj+aguN2/eyYcde9rWkFncPgpbWQ+zZ30rz/lZa2g8B0N4e/HLtNsYNG8i/XDmTSSOHZDN8sx73Zu/ecdK3grTs+Z1ce9cK9h9s49sfnM5F00ZnOySzHuNXK5sdZtbEYTz0P89l8qghfPKuFXzzF+s8/m8FwUnfCtaooRXcM282V8wax82/3sBHfryMXfsOZjsss17lF65ZQSsvKebv/3ga0+uG8qUHVzPrG7+kpOjY+0JlJUWUlxQxoKyYsyYO4/3Tx3D2ScP99LD1G076ZqQWez/1hKE89MxLHOttroigtT1oaWtn92utLHxmK/c1NFEzuJwx1QM6PWbogFLGVg9g7LCBVFaU0tVrCIuU+kNVXlJEaXFRp/uXlxRz+tihnplknXLSN0tMqxvKtLqhPXa+A63tPLpuO794dit79rceUR/Arn0HWdW0m92vHVl/PIoEp40ZSv34YQwsK+7Rc2dqUHkJ08cOZXpdFYPKnWr6C18Js15SUVrMxdNGc3EGM4NePdD6+lTTN9MewcG2Qxxobac1mYJ6uOb9bSx7YSdLNrzCXUtfpC1LN6g7bowXCcYPH0SJh7i6pXpgGfddc3aPn9dJ36wfGFJRypAeHI45d1INXNhjpzsmu187yFObdvPUi7vYsGMfgWdHdUdvDc856ZtZr6gaWJbRkprWtzxl08ysgDjpm5kVECd9M7MC4qRvZlZAnPTNzAqIk76ZWQFx0jczKyBO+mZmBaTfL6IiaQfw4jEeXgO83IPh5IJCbDMUZrsLsc1QmO3ubpvHR0RtZxX9PukfD0kNR1s9Jl8VYpuhMNtdiG2Gwmx3T7bZwztmZgXESd/MrIDke9K/JdsBZEEhthkKs92F2GYozHb3WJvzekzfzMzeKN97+mZmliYvk76kuZKek9Qo6fPZjqe3SBorabGkNZJWS/p0Uj5M0iJJ65P/Vmc71p4mqVjSU5IeSr5PlLQ0ueb3SirLdow9TVKVpJ9KWidpraSz8/1aS/pM8v/tZyXdLakiH6+1pNskbZf0bFpZp9dWKd9P2r9K0pnd+a28S/qSioGbgIuAqcAVkqZmN6pe0wZ8LiKmArOB65K2fh74VURMAn6VfM83nwbWpn3/JvDdiDgZ2AV8LCtR9a7/C/wiIqYA00m1P2+vtaQxwF8C9RFxGlAMXE5+XuvbgbmHlR3t2l4ETEo+84Cbu/NDeZf0gVlAY0RsjIiDwD3AJVmOqVdExJaIWJFsv0oqCYwh1d47kt3uAC7NSoC9RFId8F7g1uS7gDnAT5Nd8rHNQ4HzgPkAEXEwInaT59ea1Op+AySVAAOBLeThtY6Ix4CdhxUf7dpeAtwZKUuAKkldL8ScyMekPwbYlPa9KSnLa5ImAGcAS4GREbElqdoKjMxWXL3ke8BfAR0rgw8HdkdEW/I9H6/5RGAH8ONkWOtWSYPI42sdEZuBbwO/J5Xs9wDLyf9r3eFo1/a4clw+Jv2CI2kwcD9wfUQ0p9dFanpW3kzRkvQ+YHtELM92LH2sBDgTuDkizgD2cdhQTh5e62pSvdqJwAnAII4cAikIPXlt8zHpbwbGpn2vS8rykqRSUgn/roh4ICne1vHPveS/27MVXy84B3i/pBdIDd3NITXWXZUMAUB+XvMmoCkilibff0rqj0A+X+sLgOcjYkdEtAIPkLr++X6tOxzt2h5XjsvHpP8kMCm5w19G6sbPgizH1CuSsez5wNqIuDGtagFwdbJ9NfBgX8fWWyLiCxFRFxETSF3bRyPiz4DFwGXJbnnVZoCI2ApskvSWpOhdwBry+FqTGtaZLWlg8v/1jjbn9bVOc7RruwC4KpnFMxvYkzYM1LWIyLsPcDHwO2AD8MVsx9OL7TyX1D/5VgErk8/FpMa4fwWsB34JDMt2rL3U/ncCDyXbJwLLgEbg34DybMfXC+2dATQk1/vnQHW+X2vgq8A64FngJ0B5Pl5r4G5S9y1aSf2r7mNHu7aASM1Q3AA8Q2p2U8a/5SdyzcwKSD4O75iZ2VE46ZuZFRAnfTOzAuKkb2ZWQJz0zcwKiJO+mVkBcdI3MysgTvpmZgXk/wNZ+c2cUqFp6wAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(100), best_length)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b30ee0d1",
   "metadata": {},
   "source": [
    "we can see after 40 epochs, the data converged\n",
    "\n",
    "now let's see best route and its length..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "affeb050",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:25.024459Z",
     "start_time": "2021-11-09T17:35:25.013473Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1626.0\n",
      "[5, 29, 3, 26, 9, 12, 6, 28, 1, 24, 8, 27, 23, 7, 25, 11, 22, 17, 14, 18, 15, 4, 19, 16, 13, 10, 20, 2, 21]\n"
     ]
    }
   ],
   "source": [
    "length_bayg29 = best_length[-1]\n",
    "route_bayg29 = best_routes[-1]\n",
    "print(length_bayg29)\n",
    "print(route_bayg29)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e51068cd",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:15:05.610180Z",
     "start_time": "2021-11-09T17:15:05.593154Z"
    }
   },
   "source": [
    "# Second test case(gr229)\n",
    "first, let's get extract data from file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "37f0d8bc",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:31.540247Z",
     "start_time": "2021-11-09T17:35:31.443682Z"
    }
   },
   "outputs": [],
   "source": [
    "f = open(\"gr229.tsp\", \"r\")\n",
    "txt = f.readlines()\n",
    "dic_city_location = {}\n",
    "dic_city_length = {}\n",
    "for i in range(len(txt)):\n",
    "    if 'DIMENSION' in txt[i]:\n",
    "        dimension = [int(s) for s in txt[i].split() if s.isdigit()][0]\n",
    "    if 'NODE_COORD_SECTION' in txt[i]:\n",
    "        for j in range(i + 1, i + 1 + dimension):\n",
    "            city_location = [float(idx) for idx in txt[j].split()]\n",
    "            dic_city_location[city_location[0]] = city_location[1], city_location[2]        \n",
    "for i in range(1, len(dic_city_location)):\n",
    "    for j in range(1, len(dic_city_location)):\n",
    "        if(j >= i):\n",
    "            dic_city_length[i, j + 1] = math.sqrt(pow((dic_city_location[i][0] - dic_city_location[j + 1][0]), 2) + pow((dic_city_location[i][1] - dic_city_location[j + 1][1]), 2))\n",
    "            dic_city_length[j + 1, i] = math.sqrt(pow((dic_city_location[i][0] - dic_city_location[j + 1][0]), 2) + pow((dic_city_location[i][1] - dic_city_location[j + 1][1]), 2))\n",
    "# creat two lists for saving best routes and lengths\n",
    "best_length = []\n",
    "best_routes = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ce20c83",
   "metadata": {},
   "source": [
    "create some initialize population and data-frame it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "89cbf747",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:35:34.694826Z",
     "start_time": "2021-11-09T17:35:34.650598Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>routes</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[181, 43, 81, 89, 168, 110, 124, 34, 169, 228,...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[22, 123, 53, 20, 206, 111, 102, 1, 79, 66, 36...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[19, 132, 18, 130, 72, 87, 128, 186, 9, 173, 1...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>[199, 118, 195, 165, 196, 70, 175, 201, 124, 1...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>[167, 226, 55, 100, 116, 21, 213, 50, 155, 7, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>95</th>\n",
       "      <td>[74, 131, 193, 66, 120, 125, 216, 174, 34, 147...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>96</th>\n",
       "      <td>[147, 18, 111, 90, 93, 99, 146, 49, 125, 106, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97</th>\n",
       "      <td>[184, 106, 176, 112, 185, 25, 57, 192, 199, 95...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>98</th>\n",
       "      <td>[167, 164, 67, 206, 76, 183, 83, 182, 171, 187...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>99</th>\n",
       "      <td>[169, 173, 26, 104, 162, 206, 77, 20, 73, 128,...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>100 rows × 1 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "                                               routes\n",
       "0   [181, 43, 81, 89, 168, 110, 124, 34, 169, 228,...\n",
       "1   [22, 123, 53, 20, 206, 111, 102, 1, 79, 66, 36...\n",
       "2   [19, 132, 18, 130, 72, 87, 128, 186, 9, 173, 1...\n",
       "3   [199, 118, 195, 165, 196, 70, 175, 201, 124, 1...\n",
       "4   [167, 226, 55, 100, 116, 21, 213, 50, 155, 7, ...\n",
       "..                                                ...\n",
       "95  [74, 131, 193, 66, 120, 125, 216, 174, 34, 147...\n",
       "96  [147, 18, 111, 90, 93, 99, 146, 49, 125, 106, ...\n",
       "97  [184, 106, 176, 112, 185, 25, 57, 192, 199, 95...\n",
       "98  [167, 164, 67, 206, 76, 183, 83, 182, 171, 187...\n",
       "99  [169, 173, 26, 104, 162, 206, 77, 20, 73, 128,...\n",
       "\n",
       "[100 rows x 1 columns]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "routes = []\n",
    "while(len(routes) < 100): \n",
    "    new_route = random.sample(range(1, dimension + 1), dimension)\n",
    "    # check if new route is unique or not\n",
    "    if new_route not in routes:\n",
    "        routes.append(new_route)\n",
    "df = {'routes' : routes}\n",
    "df = pd.DataFrame(df)\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ec2e147",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:11:19.990032Z",
     "start_time": "2021-11-09T17:11:19.990032Z"
    }
   },
   "source": [
    "for this case, we have 100 initialize population, 2000 epochs, crossover = 0%, mutation = 100%, and 100 number of survivor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "01f1e6e0",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:39:05.166462Z",
     "start_time": "2021-11-09T17:35:41.362098Z"
    }
   },
   "outputs": [],
   "source": [
    "ga_tsp(df, 100, 2000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "e84913d5",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:39:49.165274Z",
     "start_time": "2021-11-09T17:39:49.050561Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYMAAAD4CAYAAAAO9oqkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAix0lEQVR4nO3deXSc9X3v8fd3ZqTRamv1giXvhhZoCrYDJgSSlNSYpI3pTW4KJylOQuPDDWmb0t4EmtzSkzQ9SdtbbrhNySWBBtoEAjQENyUQF7K0aWywjVc2C68ysi1bkhfJ2r/3j/nJHgvJ2kbzyJrP65w5eub3/J5nvvNoNB89u7k7IiKS22JRFyAiItFTGIiIiMJAREQUBiIigsJARESARNQFjFZVVZXPnTs36jJERM4rGzduPOLu1f3bz9swmDt3Lhs2bIi6DBGR84qZ7R2oXZuJREREYSAiIgoDERFBYSAiIigMREQEhYGIiKAwEBERcjAMvv2L3azZ8mbUZYiITCg5FwaPvriff1UYiIicJefCoLwon+bWzqjLEBGZUHIvDIrzaG5TGIiIpBsyDMzsQTM7bGbbBxj3J2bmZlYVnpuZ3WtmdWa21cwWp/VdZWY7w2NVWvsSM9sWprnXzCxTb24g5UX5NLd1jedLiIicd4azZvBtYEX/RjOrBZYD+9KabwAWhcdq4L7QtwK4G7gSuAK428zKwzT3AZ9Mm+4tr5VJ5UX5tLR10turez+LiPQZMgzc/edA0wCj7gE+C6R/q64EHvaUdUCZmc0ErgfWunuTuzcDa4EVYdwUd1/n7g48DNw4pnc0hLKiPHodTrR3j+fLiIicV0a1z8DMVgIH3H1Lv1GzgP1pz+tD27na6wdoH+x1V5vZBjPb0NjYOJrSqSjOB6BJ+w1ERE4bcRiYWRHwZ8CfZ76cc3P3+919qbsvra5+y70ZhqW8KBUG2oksInLGaNYMFgDzgC1mtgeoATaZ2QzgAFCb1rcmtJ2rvWaA9nFTHtYMdHipiMgZIw4Dd9/m7tPcfa67zyW1aWexux8E1gC3hKOKlgHH3L0BeBZYbmblYcfxcuDZMO64mS0LRxHdAjyVofc2oPKiPAAdUSQikmY4h5Y+AvwSuMjM6s3s1nN0fxrYBdQB3wQ+BeDuTcCXgBfD44uhjdDnW2GaN4Afje6tDE9ZYWrNoEWbiUREThvyHsjufvMQ4+emDTtw+yD9HgQeHKB9A3DpUHVkSmF+HIBTnT3ZekkRkQkv585Azk/ESMSMti6FgYhIn5wLA0itHWjNQETkjJwMg6L8OG2dOulMRKRPjoZBgjatGYiInJaTYVCYp81EIiLpcjIMqkqT7Gtqi7oMEZEJIyfDYG5lEYdPdERdhojIhJGTYVCcTNDa0U3qtAgREcnJMChJJujudTq6e6MuRURkQsjZMABo7dDhpSIikKNhUHw6DHREkYgI5GgY9K0ZnOjQlUtFRCBHw+D0ZaxbFQYiIpCjYVBZkrqM9dFWHV4qIgI5GgYVxUkAmnS3MxERIEfDoKwwj5gpDERE+uRkGMRiRkVxPkdOKgxERCBHwwCgojifJu0zEBEBcj4MtGYgIgI5HAaVxUmOKgxERIAcDgOtGYiInJHTYdDS1kVXjy5WJyIyZBiY2YNmdtjMtqe1/Y2ZvWpmW83sSTMrSxt3l5nVmdlrZnZ9WvuK0FZnZnemtc8zs/Wh/Xtmlp/B9zeovhPPmtu0diAiMpw1g28DK/q1rQUudfe3Aa8DdwGY2cXATcAlYZp/MLO4mcWBrwM3ABcDN4e+AF8F7nH3hUAzcOuY3tEwVerEMxGR04YMA3f/OdDUr+3H7t53/ed1QE0YXgk86u4d7r4bqAOuCI86d9/l7p3Ao8BKMzPgN4AnwvQPATeO7S0NT0Vxas2gSecaiIhkZJ/BJ4AfheFZwP60cfWhbbD2SqAlLVj62gdkZqvNbIOZbWhsbBxT0afDQJuJRETGFgZm9nmgG/hOZso5N3e/392XuvvS6urqMc2rLwyatZlIRITEaCc0s48BvwVc52duJnwAqE3rVhPaGKT9KFBmZomwdpDef1yVhctY61wDEZFRrhmY2Qrgs8AH3L0tbdQa4CYzS5rZPGAR8ALwIrAoHDmUT2on85oQIj8BPhSmXwU8Nbq3MjJ58RhTChJaMxARYXiHlj4C/BK4yMzqzexW4O+BUmCtmW02s28AuPsO4DHgZeAZ4HZ37wn/9X8aeBZ4BXgs9AX4HHCHmdWR2ofwQEbf4TlUliRpatMNbkREhtxM5O43D9A86Be2u38Z+PIA7U8DTw/QvovU0UZZV1mcT+OJ9iheWkRkQsnZM5ABLigrpOGYwkBERGHQ0k5vrw/dWURkEsvpMJhVVkBnTy9HTuq+BiKS23I6DC4oKwTgQMupiCsREYlWTofBjKkFABw6rv0GIpLbcjoMSpKpg6laO3oirkREJFo5HQaF+XEA2roUBiKS23I6DIryU2sGpzq7h+gpIjK55XQYFOfHKcyLc+i4jiYSkdyW02FgZsypLGL3kdaoSxERiVROhwHA/Opi9igMRCTH5XwY1JYXUd98ijNX4RYRyT05HwbTpqTOQj6ocw1EJIflfBhcPrsMgK31x6ItREQkQjkfBrPCJSl0fSIRyWU5HwYFidSJZ+1dvRFXIiISnZwPg2ReahG06yxkEclhCoNEDDOFgYjktpwPAzNjSkGe9hmISE7L+TAAeFvNVDbv19FEIpK7FAbA5bPLee3gcU526IJ1IpKbFAbAxTNL6XV0WQoRyVlDhoGZPWhmh81se1pbhZmtNbOd4Wd5aDczu9fM6sxsq5ktTptmVei/08xWpbUvMbNtYZp7zcwy/SaHUl2auuNZo/YbiEiOGs6awbeBFf3a7gSec/dFwHPhOcANwKLwWA3cB6nwAO4GrgSuAO7uC5DQ55Np0/V/rXE3rTQJQKMuZS0iOWrIMHD3nwNN/ZpXAg+F4YeAG9PaH/aUdUCZmc0ErgfWunuTuzcDa4EVYdwUd1/nqSvFPZw2r6ypDmFw+ISuTyQiuWm0+wymu3tDGD4ITA/Ds4D9af3qQ9u52usHaM+qgrw4UwoSusmNiOSsMe9ADv/RZ+X6z2a22sw2mNmGxsbGjM57fnUJrx86kdF5ioicL0YbBofCJh7Cz8Oh/QBQm9avJrSdq71mgPYBufv97r7U3ZdWV1ePsvSBXVZbxtb6Y3R26xpFIpJ7RhsGa4C+I4JWAU+ltd8SjipaBhwLm5OeBZabWXnYcbwceDaMO25my8JRRLekzSurLp9dxqmuHt0CU0RyUmKoDmb2CPBuoMrM6kkdFfQV4DEzuxXYC3w4dH8aeB9QB7QBHwdw9yYz+xLwYuj3RXfv2yn9KVJHLBUCPwqPrJtdUQTAgZY2LppRGkUJIiKRGTIM3P3mQUZdN0BfB24fZD4PAg8O0L4BuHSoOsbbzKmp+xq82aIjikQk9+gM5KC6NEk8Zuxq1GYiEck9CoMgHjOqS5I8s71h6M4iIpOMwiDNoukldPboaCIRyT0KgzSX1ZbR1NpJT29WTpsQEZkwFAZpqkqS9Do0tXZGXYqISFYpDNL0HV6qcw1EJNcoDNJccsEUALYf0F3PRCS3KAzSTJtSQEVxPjsPn4y6FBGRrFIY9DOtNMm6XUejLkNEJKsUBv3kxWM0t2kHsojkFoVBP+/5lWkcO9VFt843EJEcojDop6okH3dobuuKuhQRkaxRGPRTWZy6Beah47pgnYjkDoVBP782ayoAW+pboi1ERCSLFAb91FYUUpwf57WDugWmiOQOhUE/ZsZls8v45Rs6vFREcofCYACX1Zax60gr7V09UZciIpIVCoMB/NqsMnp6nU17m6MuRUQkKxQGA1g4rRiAxpMdEVciIpIdCoMBTJtSQCJm7HjzeNSliIhkhcJgAFMK8ristkybiUQkZygMBnHprKm80nAcd931TEQmP4XBIBZNL6G1s4cDLaeiLkVEZNyNKQzM7I/NbIeZbTezR8yswMzmmdl6M6szs++ZWX7omwzP68L4uWnzuSu0v2Zm14/xPWXEhdNLAdh5SPc2EJHJb9RhYGazgD8Elrr7pUAcuAn4KnCPuy8EmoFbwyS3As2h/Z7QDzO7OEx3CbAC+Aczi4+2rky5cFoqDF47pDORRWTyG+tmogRQaGYJoAhoAH4DeCKMfwi4MQyvDM8J468zMwvtj7p7h7vvBuqAK8ZY15hNLcpjVlmhboEpIjlh1GHg7geAvwX2kQqBY8BGoMXdu0O3emBWGJ4F7A/Tdof+lentA0xzFjNbbWYbzGxDY2PjaEsftrfVTGWbwkBEcsBYNhOVk/qvfh5wAVBMajPPuHH3+919qbsvra6uHs+XAlJHFO092sbhE7qctYhMbmPZTPReYLe7N7p7F/B94GqgLGw2AqgBDoThA0AtQBg/FTia3j7ANJG6akElAJv3tURbiIjIOBtLGOwDlplZUdj2fx3wMvAT4EOhzyrgqTC8JjwnjH/eUwfxrwFuCkcbzQMWAS+Moa6MWVBVAsDzrx6OuBIRkfGVGLrLwNx9vZk9AWwCuoGXgPuBfwMeNbO/DG0PhEkeAP7JzOqAJlJHEOHuO8zsMVJB0g3c7u4T4nKhU4vyANh7tC3iSkRExteowwDA3e8G7u7XvIsBjgZy93bgvw8yny8DXx5LLePlg4tr+PHLB+npdeIxi7ocEZFxoTOQh7BkTjkn2rtpOKYzkUVk8lIYDGFuVREAOw/rTGQRmbwUBkO4rLaM0mSCZ7YdjLoUEZFxozAYQlF+gqsXVvGfdUd0BVMRmbQUBsNw9aIqDrScYveR1qhLEREZFwqDYbhyXgUAm3TymYhMUgqDYVhQXUJJMsHm/brzmYhMTgqDYYjHjLfVTGXLfl20TkQmJ4XBMC2eXc6ON49x9GRH1KWIiGScwmCYLp9dRq/DnqPaiSwik4/CYJgumpG689kv6o5GXImISOYpDIappryImvJCHV4qIpOSwmAEKkuSHGjRNYpEZPJRGIzApRdMYVu9jigSkclHYTACi6aVcKqrh+26L7KITDIKgxF410XTAPjXLW9GXImISGYpDEZgXlUxAIeOt0dciYhIZikMRuiaRVX89PVG2rsmxJ05RUQyQmEwQp945zxa2rr4xs/eiLoUEZGMURiM0LsWVZOIGS/uaYq6FBGRjFEYjFAsZnx02RzW7Wri2KmuqMsREckIhcEoXH/JDHp6nRd2a+1ARCaHMYWBmZWZ2RNm9qqZvWJmV5lZhZmtNbOd4Wd56Gtmdq+Z1ZnZVjNbnDafVaH/TjNbNdY3Nd4WzymjKD/ON3++K+pSREQyYqxrBl8DnnH3XwF+HXgFuBN4zt0XAc+F5wA3AIvCYzVwH4CZVQB3A1cCVwB39wXIRJVMxLnp7bN5YU8TL795POpyRETGbNRhYGZTgWuBBwDcvdPdW4CVwEOh20PAjWF4JfCwp6wDysxsJnA9sNbdm9y9GVgLrBhtXdnyqfcsAODfXzkUcSUiImM3ljWDeUAj8I9m9pKZfcvMioHp7t4Q+hwEpofhWcD+tOnrQ9tg7W9hZqvNbIOZbWhsbBxD6WNXVZJk2fwKHnlhH729HmktIiJjNZYwSACLgfvc/XKglTObhABwdwcy9k3p7ve7+1J3X1pdXZ2p2Y7ah5bU0nCsnVcOalORiJzfxhIG9UC9u68Pz58gFQ6HwuYfws/DYfwBoDZt+prQNlj7hHfthVUU5MX4++froi5FRGRMRh0G7n4Q2G9mF4Wm64CXgTVA3xFBq4CnwvAa4JZwVNEy4FjYnPQssNzMysOO4+WhbcKbVlrA7y2bw9qXD+nyFCJyXhvr0UR/AHzHzLYClwF/BXwF+E0z2wm8NzwHeBrYBdQB3wQ+BeDuTcCXgBfD44uh7bywdG4F3b3OS/taoi5FRGTUEmOZ2N03A0sHGHXdAH0duH2Q+TwIPDiWWqJyzaIqivPj/PO6vVy1oDLqckRERkVnII9RUX6CT147n3/b1sB/1R2JuhwRkVFRGGTAbe9awJSCBI9t2D90ZxGRCUhhkAEFeXFuvHwWP9zawL6jbVGXIyIyYgqDDFl97Xy6e52vPPNK1KWIiIyYwiBDasqLuGJuBc/uOMSxNl3aWkTOLwqDDLpj+YX09DoP/3JP1KWIiIyIwiCDls2vZFZZIT/YfF6cQC0icprCIMOuvbCKNxpb2fHmsahLEREZNoVBhn3q3QsB+Lsfvx5xJSIiw6cwyLDaiiJ+/53zeO7Vw6x9Wfc6EJHzg8JgHPzxb14IwFPadyAi5wmFwTgoTib4yJWz+eHWBr67fl/U5YiIDElhME7u/u1LuGh6KX+xZge7j7RGXY6IyDkpDMZJfiLG/bcsodedOx7bHHU5IiLnpDAYR3Mqi/ndt9fy0r4WnthYH3U5IiKDUhiMsy+8/2JKCxI8+ZLCQEQmLoXBOCvMj3NZbRmtHbotpohMXAqDLEgm4nR290ZdhojIoBQGWZBMxOjo1pqBiExcCoMsSCZiNBxrj7oMEZFBKQyyYEphHm2dPazZ8mbUpYiIDEhhkAWfee8iivLj/K8fbKen16MuR0TkLRQGWVBWlM8nr5nPsVNd7D5yMupyRETeYsxhYGZxM3vJzH4Yns8zs/VmVmdm3zOz/NCeDM/rwvi5afO4K7S/ZmbXj7WmiejqhVUA3PtcXcSViIi8VSbWDP4ISL8L/FeBe9x9IdAM3BrabwWaQ/s9oR9mdjFwE3AJsAL4BzOLZ6CuCeXtc8tZOqecNVve5J/X7Y26HBGRs4wpDMysBng/8K3w3IDfAJ4IXR4CbgzDK8NzwvjrQv+VwKPu3uHuu4E64Iqx1DURmRmPrF7G/OpivvCD7Zzq1KGmIjJxjHXN4P8AnwX6zqiqBFrcvTs8rwdmheFZwH6AMP5Y6H+6fYBpzmJmq81sg5ltaGxsHGPp2ZcXj/GJq+cBaO1ARCaUUYeBmf0WcNjdN2awnnNy9/vdfam7L62urs7Wy2bUR5fN4YKpBXz56VdoOHYq6nJERICxrRlcDXzAzPYAj5LaPPQ1oMzMEqFPDdB3u68DQC1AGD8VOJrePsA0k9KfLL8IgA//v19qc5GITAijDgN3v8vda9x9LqkdwM+7+0eAnwAfCt1WAU+F4TXhOWH88+7uof2mcLTRPGAR8MJo6zoffHBJDV94/6+yv+kUN379F7zZojUEEYnWeJxn8DngDjOrI7VP4IHQ/gBQGdrvAO4EcPcdwGPAy8AzwO3uPun/Xf79a+bzR9ct4rVDJ/jIt9ZHXY6I5DhL/XN+/lm6dKlv2LAh6jLG7H8+voXHN9Zzz+/+Or9zeU3U5YjIJGdmG919af/2xECdJXv+8LpFvHrwBHc8toWuHufDS2uHnkhEJMN0OYqI1VYU8fhtV/GOBZV84cntbNzbFHVJIpKDFAYTQEFenK9+8G0kEzFu/uZ6tuxvibokEckxCoMJoqa8iCdvv5opBXms/Pov+M+dR6IuSURyiMJgAlk4rYRvf/ztTCtN8tEH1vPDrbr/gYhkh8Jggrl01lQev+0q5lcV8+nvvsRd39+qW2aKyLhTGExAcyqL+cGnr+baC6t55IX9/OnjW+nVTXFEZBwpDCaoKQV5/OPH3s7yi6fzr1ve5KMPrOdEe1fUZYnIJKUwmMDiMeO+jy7hU+9ewC93HeU9f/tTntneEHVZIjIJKQwmuHjM+OyKX+Ff/sc7qCxOcts/b+L272yirbN76IlFRIZJYXCeWDy7nMduu4qbr5jNv21r4IovP8e3/mMXTa2dUZcmIpOArk10HvrRtgb+8Rd7eGFPE3lx44OLa/j9a+azcFpJ1KWJyAQ32LWJFAbnse0HjvF/n9/JszsOUZAX4/Pvv5gbLp1BVUky6tJEZIJSGExirx48zicf3sD+plPkxY1Pv2cRt717PslEPOrSRGSCURhMcu1dPWza18wD/7Gb5149THF+nOWXzOBDS2p4x4JKzCzqEkVkAtAlrCe5grw471hQxbJ5lfzs9Uae2X6Qp7c18ORLB5hVVsj73zaTT1w9jxlTC6IuVUQmIK0ZTGLtXT08vrGeR1/Yx443jwPwyWvmcdWCSpbMqWBqYV7EFYpItmkzUY7buLeZb/zsDZ5/9TA94dIWvzpzCtdeWMVV8ytZPKecKQUKB5HJTmEgAJzs6GZrfQub9jbz851HeGlfM109qc/AomklvHNRFVfOq2Dp3AodlSQyCSkMZEBtnd1s2tvClvoW/uuNI2zc20x7Vy8AKy6ZwQeX1LB0TjnlxfkRVyoimaAwkGHp7O5l24FjfHf9Pp7afIDusElpTmURcyqLmVtZxLyqYi6aUcrlteUU5uvwVZHzicJARqy9q4dNe5tZv7uJNxpPsvtIK3uOtNLambq/QjxmTCtNcuH0Ui65YAqzyguZMaWA6VMKmFdVTHFSB6uJTDQZP7TUzGqBh4HpgAP3u/vXzKwC+B4wF9gDfNjdmy11oPvXgPcBbcDH3H1TmNcq4Ath1n/p7g+Nti7JnIK8OO9YWMU7FladbnN3Go6180IIiDcaT7Jpbwu/qDtyei2iz/QpSapLk8ytLOYDv34BF80opaa8iHhM5zyITDSjXjMws5nATHffZGalwEbgRuBjQJO7f8XM7gTK3f1zZvY+4A9IhcGVwNfc/coQHhuApaRCZSOwxN2bz/X6WjOYWHp6nUPH2zl8ooOGllPsOtLK7iOt7G9q44U9TfR9zIrz48wsK2RhdQlVpflUlSSZPqWARdNKKC/OpySZYGphHgV52vwkMh4yvmbg7g1AQxg+YWavALOAlcC7Q7eHgJ8CnwvtD3sqfdaZWVkIlHcDa929KRS6FlgBPDLa2iT74jHjgrJCLigr5LLasrPGnWjv4vVDJ9h56CSvHjxBffMp3mg8yfrdHTS3DXzDnikFCapLk0wrLaC6NHnmUZKkvDgVFsX5CRZOK6EoP64zrEXGKCMbdc1sLnA5sB6YHoIC4CCpzUiQCor9aZPVh7bB2gd6ndXAaoDZs2dnonTJgtKCPJbMqWDJnIq3jOvq6aWhpZ1dR07S0tZFa2c3za2dNJ7ooPFkB4ePd7ClvoXDxzs41TXwvaDz4sbUwnyqS5OUF+UxtTCP0oIExckERflxChJxCvLiFOTFKMiLM7Uwj5JkanxJQYKSZOL0c5FcNeZPv5mVAP8CfMbdj6f/h+bubmYZ20Pt7vcD90NqM1Gm5ivRyYvHmF1ZxOzKoiH7tnZ0c/hEBy1tnbR39dLU2sneplZOtnfT3JYKkKbWTg6f6OBEexetHT20dXYz3NtHz5hSwNTCPKYW5VGcH6e0II+SggRFeXFmTE2NS+bFSSZiFOXHyY/HyE/ESCbilBYkiMeMRMyIpz0K8+Ik4rptiEx8YwoDM8sjFQTfcffvh+ZDZjbT3RvCZqDDof0AUJs2eU1oO8CZzUp97T8dS10yORUnE8xLJoDiYU/j7nT1OB3dPbR39XKqs4fj7V2c7OimtaObk+Fx9GQne4620trRTXNbF0dOdrLrSOp5a0fPoGslw5FMxE6vmeQnYhTmxSnMi1OcTJCIx8gLwZEXj5HMS4VLPAYxM2KWGhcziMXCc7MwTNqwDX+amGGhLR4zyoryTodYIhY7K8wSMSMRT/U3wAwMCz+Bfs/798MYdFzf/419712iNZajiQx4AHjF3f8ubdQaYBXwlfDzqbT2T5vZo6R2IB8LgfEs8FdmVh76LQfuGm1dIunMjPyEkZ+IUTrKa/S5O0dOdtLe1XMmVLp66OzupbO7l/auHk50dNPb6/S409PrdPekfp7s6Ka9qyc8eunsSfVv7eyhraOb1s4eenp76e5xunp6ae/qpaO7l153esO83FM76Hvc8dA23LWd80lfONhZbWee2YB901oHHhywrw3a197SNvh8bVjzSm+3QWY80Dz62mJmFObH09qNH/7BOzN+kMVY1gyuBn4P2GZmm0Pbn5EKgcfM7FZgL/DhMO5pUkcS1ZE6tPTjAO7eZGZfAl4M/b7YtzNZZCIwM6pLJ96lOfrCp9ed3l7ShlNhkQqNc4VKap/NsVNdqfbw6D79s/d0sDmp6R3CzzPPcT/Tnj5M6jkDTJP+vLc3FYQQ5hekH+joaWP62ofTlwH7vnVe6X2Get10Z81riHoGeq23zvetfXt6nba+NdPQHhuHAyZ00pmISA4Z7NBSbagTERGFgYiIKAxERASFgYiIoDAQEREUBiIigsJARERQGIiICOfxSWdm1kjqDOfRqAKOZLCcTFFdI6O6RkZ1jcxkrWuOu1f3bzxvw2AszGzDQGfgRU11jYzqGhnVNTK5Vpc2E4mIiMJARERyNwzuj7qAQaiukVFdI6O6Rian6srJfQYiInK2XF0zEBGRNAoDERHJrTAwsxVm9pqZ1ZnZnVl+7Voz+4mZvWxmO8zsj0L7X5jZATPbHB7vS5vmrlDra2Z2/TjWtsfMtoXX3xDaKsxsrZntDD/LQ7uZ2b2hrq1mtnicaroobZlsNrPjZvaZqJaXmT1oZofNbHta24iXkZmtCv13mtmqcarrb8zs1fDaT5pZWWifa2an0pbdN9KmWRI+A3Wh9jHdSmuQukb8u8v03+wgdX0vraY9fXduzPLyGuz7IXufMQ+3wJvsDyAOvAHMB/KBLcDFWXz9mcDiMFwKvA5cDPwF8KcD9L841JgE5oXa4+NU2x6gql/bXwN3huE7ga+G4fcBPyJ1q9ZlwPos/e4OAnOiWl7AtcBiYPtolxFQAewKP8vDcPk41LUcSIThr6bVNTe9X7/5vBBqtVD7DeNQ14h+d+PxNztQXf3G/2/gzyNYXoN9P2TtM5ZLawZXAHXuvsvdO4FHgZXZenF3b3D3TWH4BPAKMOsck6wEHnX3DnffTere0VeMf6Vnvf5DYfgh4Ma09oc9ZR1QZmYzx7mW64A33P1cZ5yP6/Jy958D/e/NPdJldD2w1t2b3L0ZWAusyHRd7v5jd+8OT9cBNeeaR6htiruv89Q3ysNp7yVjdZ3DYL+7jP/Nnquu8N/9h4FHzjWPcVpeg30/ZO0zlkthMAvYn/a8nnN/GY8bM5sLXA6sD02fDqt6D/atBpLdeh34sZltNLPVoW26uzeE4YPA9Ajq6nMTZ/+BRr28+ox0GUVR4ydI/QfZZ56ZvWRmPzOza0LbrFBLNuoaye8u28vrGuCQu+9Ma8v68ur3/ZC1z1guhcGEYGYlwL8An3H348B9wALgMqCB1Gpqtr3T3RcDNwC3m9m16SPDfz+RHINsZvnAB4DHQ9NEWF5vEeUyGoyZfR7oBr4TmhqA2e5+OXAH8F0zm5LFkibk7y7NzZz9T0fWl9cA3w+njfdnLJfC4ABQm/a8JrRljZnlkfpFf8fdvw/g7ofcvcfde4FvcmbTRtbqdfcD4edh4MlQw6G+zT/h5+Fs1xXcAGxy90OhxsiXV5qRLqOs1WhmHwN+C/hI+BIhbIY5GoY3ktoef2GoIX1T0rjUNYrfXTaXVwL4b8D30urN6vIa6PuBLH7GcikMXgQWmdm88N/mTcCabL142B75APCKu/9dWnv69vbfAfqOclgD3GRmSTObBywitdMq03UVm1lp3zCpnY/bw+v3HYmwCngqra5bwtEMy4Bjaaux4+Gs/9aiXl79jHQZPQssN7PysIlkeWjLKDNbAXwW+IC7t6W1V5tZPAzPJ7WMdoXajpvZsvA5vSXtvWSyrpH+7rL5N/te4FV3P735J5vLa7DvB7L5GRvLHvDz7UFqD/zrpBL+81l+7XeSWsXbCmwOj/cB/wRsC+1rgJlp03w+1PoaYzxa4Rx1zSd1lMYWYEffcgEqgeeAncC/AxWh3YCvh7q2AUvHcZkVA0eBqWltkSwvUoHUAHSR2g5762iWEalt+HXh8fFxqquO1Hbjvs/ZN0LfD4bf8WZgE/DbafNZSurL+Q3g7wlXJ8hwXSP+3WX6b3agukL7t4Hb+vXN5vIa7Psha58xXY5CRERyajORiIgMQmEgIiIKAxERURiIiAgKAxERQWEgIiIoDEREBPj//nxHEP8WinkAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(2000), best_length)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8bedf90",
   "metadata": {},
   "source": [
    "we can see after 1000 epochs, the data converged\n",
    "\n",
    "now let's see best route and its length..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e96ca771",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:40:35.208623Z",
     "start_time": "2021-11-09T17:40:35.197638Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1766.3385912297\n",
      "[25, 84, 24, 23, 56, 57, 55, 54, 58, 53, 52, 51, 19, 11, 10, 18, 17, 12, 16, 20, 21, 22, 30, 33, 34, 38, 31, 32, 29, 28, 27, 26, 15, 14, 13, 2, 1, 3, 4, 5, 7, 8, 9, 6, 224, 225, 218, 217, 227, 226, 228, 229, 68, 69, 67, 63, 66, 65, 64, 62, 61, 60, 59, 83, 82, 81, 87, 85, 86, 89, 88, 80, 79, 78, 70, 71, 72, 73, 76, 77, 90, 91, 75, 74, 103, 102, 101, 100, 94, 93, 92, 36, 35, 37, 95, 96, 99, 98, 97, 104, 105, 107, 106, 112, 115, 118, 119, 121, 122, 123, 120, 116, 113, 117, 114, 111, 126, 127, 128, 129, 130, 171, 133, 131, 132, 138, 139, 142, 140, 141, 143, 144, 145, 146, 147, 148, 149, 151, 154, 155, 150, 204, 158, 157, 156, 159, 160, 161, 162, 153, 152, 136, 137, 134, 135, 172, 163, 164, 165, 173, 176, 175, 174, 170, 169, 168, 177, 179, 181, 180, 178, 182, 183, 185, 186, 187, 197, 198, 199, 200, 201, 202, 203, 211, 212, 205, 206, 207, 208, 209, 210, 213, 214, 215, 216, 219, 220, 221, 222, 223, 191, 192, 195, 196, 194, 193, 190, 189, 188, 48, 47, 49, 44, 43, 45, 42, 46, 50, 184, 41, 39, 40, 167, 166, 125, 124, 110, 109, 108]\n"
     ]
    }
   ],
   "source": [
    "length_gr229 = best_length[-1]\n",
    "route_gr229 = best_routes[-1]\n",
    "print(length_gr229)\n",
    "print(route_gr229)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b61e35e4",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:26:20.081354Z",
     "start_time": "2021-11-09T17:26:20.066395Z"
    }
   },
   "source": [
    "# Third test case(pr1002)\n",
    "first, let's get extract data from file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "61df5eda",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:40:41.781015Z",
     "start_time": "2021-11-09T17:40:40.329410Z"
    }
   },
   "outputs": [],
   "source": [
    "f = open(\"pr1002.tsp\", \"r\")\n",
    "txt = f.readlines()\n",
    "dic_city_location = {}\n",
    "dic_city_length = {}\n",
    "for i in range(len(txt)):\n",
    "    if 'DIMENSION' in txt[i]:\n",
    "        dimension = [int(s) for s in txt[i].split() if s.isdigit()][0]\n",
    "    if 'NODE_COORD_SECTION' in txt[i]:\n",
    "        for j in range(i + 1, i + 1 + dimension):\n",
    "            city_location = [float(idx) for idx in txt[j].split()]\n",
    "            dic_city_location[city_location[0]] = city_location[1], city_location[2]        \n",
    "for i in range(1, len(dic_city_location)):\n",
    "    for j in range(1, len(dic_city_location)):\n",
    "        if(j >= i):\n",
    "            dic_city_length[i, j + 1] = math.sqrt(pow((dic_city_location[i][0] - dic_city_location[j + 1][0]), 2) + pow((dic_city_location[i][1] - dic_city_location[j + 1][1]), 2))\n",
    "            dic_city_length[j + 1, i] = math.sqrt(pow((dic_city_location[i][0] - dic_city_location[j + 1][0]), 2) + pow((dic_city_location[i][1] - dic_city_location[j + 1][1]), 2))\n",
    "# creat two lists for saving best routes and lengths\n",
    "best_length = []\n",
    "best_routes = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6400e48",
   "metadata": {},
   "source": [
    "create some initialize population and data-frame it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "06ae93e9",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T17:40:59.327032Z",
     "start_time": "2021-11-09T17:40:59.250232Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>routes</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[35, 573, 790, 55, 124, 455, 739, 235, 144, 34...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[478, 134, 536, 68, 53, 832, 971, 908, 578, 97...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[117, 423, 682, 33, 372, 791, 357, 686, 756, 9...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>[59, 874, 396, 633, 71, 425, 456, 755, 384, 64...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>[282, 535, 308, 144, 435, 268, 851, 161, 827, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>95</th>\n",
       "      <td>[167, 579, 893, 792, 388, 134, 300, 153, 617, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>96</th>\n",
       "      <td>[440, 153, 525, 953, 987, 238, 667, 165, 202, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97</th>\n",
       "      <td>[461, 341, 671, 992, 577, 545, 731, 679, 297, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>98</th>\n",
       "      <td>[940, 575, 524, 862, 72, 313, 771, 593, 288, 5...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>99</th>\n",
       "      <td>[649, 399, 700, 297, 58, 149, 971, 471, 175, 2...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>100 rows × 1 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "                                               routes\n",
       "0   [35, 573, 790, 55, 124, 455, 739, 235, 144, 34...\n",
       "1   [478, 134, 536, 68, 53, 832, 971, 908, 578, 97...\n",
       "2   [117, 423, 682, 33, 372, 791, 357, 686, 756, 9...\n",
       "3   [59, 874, 396, 633, 71, 425, 456, 755, 384, 64...\n",
       "4   [282, 535, 308, 144, 435, 268, 851, 161, 827, ...\n",
       "..                                                ...\n",
       "95  [167, 579, 893, 792, 388, 134, 300, 153, 617, ...\n",
       "96  [440, 153, 525, 953, 987, 238, 667, 165, 202, ...\n",
       "97  [461, 341, 671, 992, 577, 545, 731, 679, 297, ...\n",
       "98  [940, 575, 524, 862, 72, 313, 771, 593, 288, 5...\n",
       "99  [649, 399, 700, 297, 58, 149, 971, 471, 175, 2...\n",
       "\n",
       "[100 rows x 1 columns]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "routes = []\n",
    "while(len(routes) < 100): \n",
    "    new_route = random.sample(range(1, dimension + 1), dimension)\n",
    "    # check if new route is unique or not\n",
    "    if new_route not in routes:\n",
    "        routes.append(new_route)\n",
    "df = {'routes' : routes}\n",
    "df = pd.DataFrame(df)\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7bb9277",
   "metadata": {},
   "source": [
    "for this case, we have 100 initialize population, 20000 epochs, crossover = 0%, mutation = 100%, and 100 number of survivor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "281d4771",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T20:02:49.484083Z",
     "start_time": "2021-11-09T17:41:33.347247Z"
    }
   },
   "outputs": [],
   "source": [
    "ga_tsp(df, 100, 20000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "568b279e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T20:03:39.104200Z",
     "start_time": "2021-11-09T20:03:38.980046Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWsAAAEDCAYAAADz4SVPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAbb0lEQVR4nO3dfXRcd33n8fd3nvVsy5ZtJQ524iROnIQkjpaHhKSb0EBICmFLlxMOuwVK69NdYEOXLkuXsz3t2bPnbMt2l21LQ01JgS1gQpqwpUB4akgK5EmOnQfnwbEdO4kfYll+lGw9zMx3/7hX0kiWrJE8d+aO5vM6R0dX917d+5070md+87u/e8fcHRERibdErQsQEZHZKaxFROqAwlpEpA4orEVE6oDCWkSkDiisRUTqQGRhbWZ3m9lBM3u2zPXfb2bPmdk2M/tGVHWJiNQji2qctZndAAwAX3P3y2dZ9yLgHuAmdz9iZsvc/WAkhYmI1KHIWtbu/jBwuHSema0xswfMbLOZ/bOZXRIu+h3gC+5+JPxdBbWISIlq91lvBD7h7tcAvw/8VTj/YuBiM/uFmT1qZrdUuS4RkVhLVWtHZtYKXAt828zGZmdL6rgI+JfASuBhM7vC3Y9Wqz4RkTirWlgTtOKPuvtV0yx7DXjM3UeBl81sO0F4P1HF+kREYqtq3SDufpwgiP81gAWuDBd/h6BVjZktJegW2VWt2kRE4i7KoXvfBB4B1prZa2b2UeCDwEfN7ClgG3B7uPoPgX4zew54EPhP7t4fVW0iIvUmsqF7IiJSObqCUUSkDkRygnHp0qW+evXqKDYtIrIgbd68+ZC7d820PJKwXr16Nb29vVFsWkRkQTKzPWdarm4QEZE6oLAWEakDCmsRkTqgsBYRqQMKaxGROqCwFhGpAwprEZE6EKuw/vOfvsRD2/tqXYaISOzEKqz/+qGdPKywFhE5TazCOpdOMjRaqHUZIiKxE7uwPqWwFhE5TVlhbWaLzOxeM3vBzJ43s7dGUUwunWB4tBjFpkVE6lq5N3L6P8AD7v4bZpYBmqMopimjlrWIyHRmDWsz6wBuAD4M4O4jwEgUxTSlk5waUViLiExVTjfI+UAf8LdmtsXM/sbMWqauZGYbzKzXzHr7+uY3oiOXTjKUV1iLiExVTlingPXAXe5+NTAIfGbqSu6+0d173L2nq2vG+2efUU4taxGRaZUT1q8Br7n7Y+HP9xKEd8U1pZMM53WCUURkqlnD2t0PAK+a2dpw1tuB56IoJpdOqGUtIjKNckeDfAL4ejgSZBfwkSiKadI4axGRaZUV1u6+FeiJthRdFCMiMpNYXcHYlEkyki9SKHqtSxERiZVYhXVzJgmg1rWIyBSxCuumTNArc3IkX+NKRETiJVZh3ZwOW9YaESIiMkmswrpJ3SAiItOKV1irZS0iMq1YhXU2HZQzpNukiohMEquwHmtZ69NiREQmi1dYq89aRGRa8Qpr9VmLiEwrVmGdG+sG0T2tRUQmiWVYq2UtIjJZrMJa3SAiItOLVVhnUgnSSeOkTjCKiEwSq7AGaMmmODmse4OIiJSKX1hnUgwMq2UtIlIqdmHdnEnqrnsiIlPEL6yzKQZ1glFEZJLYhXVLJsmg+qxFRCaJXVg3Z1KcVMtaRGSS2IV1S1Z91iIiU8UurNWyFhE5XezCuiWT1DhrEZEpYhfWzdkUJ0cLFIte61JERGIjdmHdkknirjvviYiUSpWzkpntBk4ABSDv7j1RFdQcfgDB4HCB5kxZ5YmILHhzScMb3f1QZJWExgI6GBGSjXp3IiJ1IX7dINmgZa0RISIiE8oNawd+ZGabzWzDdCuY2QYz6zWz3r6+vnkX1JINWtYDGhEiIjKu3LB+m7uvB94FfMzMbpi6grtvdPced+/p6uqad0EKaxGR05UV1u6+N/x+ELgfeFNUBbWFYa37g4iITJg1rM2sxczaxqaBdwDPRlVQay5sWQ8prEVExpQzGmQ5cL+Zja3/DXd/IKqC1A0iInK6WcPa3XcBV1ahFiD4pBiAE2pZi4iMi93QvWTCdE9rEZEpYhfWEPRbqxtERGRCLMO6JZvihMJaRGRcLMO6LZvSaBARkRKxDGt1g4iITBbLsG7LpjkxNFrrMkREYiOWYd3elOL4KbWsRUTGxDKsO5rSHFfLWkRkXCzDuj2X5uRIgdFCsdaliIjEQjzDuikNwPFTal2LiEBMw7ojDOtjCmsRESCmYd3eFNwf5LjGWouIAHEN65y6QURESsUyrNUNIiIyWSzDevwEo4bviYgAcQ3r8W4Q9VmLiEBMwzqXTpBJJtQNIiISimVYm1lwybm6QUREgJiGNQRdIRoNIiISiG9YN6XVDSIiEop1WOuiGBGRQGzDuqNJ3SAiImNiG9btuZTCWkQkFN+wDu9p7e61LkVEpObKDmszS5rZFjP7xygLGtPRlGa04JwaLVRjdyIisTaXlvWdwPNRFTKVrmIUEZlQVlib2UrgNuBvoi1nwsRtUtVvLSJSbsv688CngRk/Z8vMNphZr5n19vX1nXVhuvOeiMiEWcPazH4NOOjum8+0nrtvdPced+/p6uo668J0T2sRkQnltKyvA95jZruBTcBNZvZ3kVbFxG1S1bIWESkjrN39D9x9pbuvBu4A/snd/03UhXU2ZwA4PDgS9a5ERGIvxuOsU6QSprAWEQFSc1nZ3X8G/CySSqYwMzpbMvQPKKxFRGLbsgaCsFbLWkQk3mG9tDVL/+BwrcsQEam5WId1Z0tGfdYiItRDWKvPWkQk3mG9tDXDieE8w3ndzElEGlusw7qzJQtorLWISKzDeklrcGGMhu+JSKOLd1i3hGGtlrWINLhYh3Vny9gl5xq+JyKNLdZhvaQ16LNWN4iINLpYh3V7LkU6aeoGEZGGF+uwHrs/iMZai0iji3VYQzB8T5eci0iji31YL9HNnERE6iCsW3V/EBGR2Ie17mktIlIHYb2kJcPAcJ6hUd0fREQaV/zDulX3BxERiX1YT1zFqLAWkcYV+7Be1ha0rA+eGKpxJSIitRP7sO7uaAJg/zGFtYg0rtiHdVdblmTC2H9UYS0ijSv2YZ1MGMvbsmpZi0hDi31YA6zoyHHg+KlalyEiUjN1EdbdHU1qWYtIQ5s1rM0sZ2aPm9lTZrbNzP64GoWVWtGRY//RIdy92rsWEYmFclrWw8BN7n4lcBVwi5m9JdKqpujuyHFqtMDxU/lq7lZEJDZmDWsPDIQ/psOvqjZxx4fvqd9aRBpUWX3WZpY0s63AQeDH7v7YNOtsMLNeM+vt6+uraJErOnKAxlqLSOMqK6zdveDuVwErgTeZ2eXTrLPR3Xvcvaerq6uiRXaPhbXGWotIg5rTaBB3Pwo8CNwSSTUzWNaWJWFw4Ji6QUSkMZUzGqTLzBaF003AzcALEdc1SSqZYFlbTt0gItKwUmWs0w181cySBOF+j7v/Y7RlnW5Fh8JaRBrXrGHt7k8DV1ehljPq7six/fUTtS5DRKQm6uIKRpi4ilEXxohII6qjsM5xcqTAiWFdGCMijaduwnqFhu+JSAOrm7BeuTi4ivHVwydrXImISPXVTVivWtICwCsKaxFpQHUT1oub07RmUwprEWlIdRPWZsZ5nc0KaxFpSHUT1gCrFNYi0qDqKqzfsKSZVw+fpFjUWGsRaSz1FdadzQznixw4ruF7ItJY6iqsL1rWCsCLuuxcRBpMXYX1hWFYv9w3WONKRESqq67CurMlQ2s2xZ5+hbWINJa6CmszY01XC9tfH5h9ZRGRBaSuwhrgkhXt6rMWkYZTd2F98Yo2Dg+OcGhguNaliIhUTd2F9drlbQBsP6DWtYg0jroL67ERITsP6SSjiDSOugvr5e1ZWrMpXlK/tYg0kLoLazPj0u42nt9/vNaliIhUTd2FNcCl3e08v/+E7hEiIg2jLsN6XXc7A8N5Xj2iO/CJSGOoy7C+tLsdQF0hItIw6jKs165oI2Hw3D6FtYg0hlnD2szOM7MHzew5M9tmZndWo7AzyaWTXNDVynNqWYtIgyinZZ0HPuXu64C3AB8zs3XRljW7deFJRhGRRjBrWLv7fnd/Mpw+ATwPnBt1YbO5eHkr+46d4sTQaK1LERGJ3Jz6rM1sNXA18Ng0yzaYWa+Z9fb19VWovJldfm4H7rD11aOR70tEpNbKDmszawX+Hviku5/WWezuG929x917urq6KlnjtN50fiephPHIzv7I9yUiUmtlhbWZpQmC+uvufl+0JZWnOZPisnPa6d1zpNaliIhErpzRIAZ8GXje3f9X9CWVr2d1J0+9epSRfLHWpYiIRKqclvV1wL8FbjKzreHXrRHXVZaeVYsZzhd5dt+xWpciIhKp1GwruPvPAatCLXN2zerFAGzefYT1b1hc42pERKJTl1cwjlnWlmPVkmZ69xyudSkiIpGq67AGuGbVYnp3H8Fdd+ATkYWr7sO6Z1Un/YMj7NInx4jIAlb3YX3tmiUA/GLHoRpXIiISnboP61VLmlm5uImHtyusRWThqvuwNjNuuLiLR3Ye0nhrEVmw6j6sAW64qIvBkQJbXtHVjCKyMC2IsL7uwiWkEsZD26O/gZSISC0siLBuy6VZv2ox33tmf61LERGJxIIIa4B3rFvOnv6TvHhAH0ggIgvPggnrW6/oBuC+J1+rcSUiIpW3YML6nEVN3Li2i+8+tY9iUVczisjCsmDCGuDX169k37EhHtmlDyQQkYVlQYX1zeuW05ZLce9mdYWIyMKyoMI6l05y+1Xn8P1n9tN3YrjW5YiIVMyCCmuAD197PsP5Ipsef6XWpYiIVMyCC+sLl7Vyw8VdfO3RPQyNFmpdjohIRSy4sAbYcP0F9J0Y5jtb9ta6FBGRiliQYX3dhUu47Jx2Nv7zLg3jE5EFYUGGtZmx4YYL2NU3yE9fOFjrckREztqCDGuA267o5txFTfz1QztrXYqIyFlbsGGdSib47evPp3fPETbv0a1TRaS+LdiwBnh/z3l0NKX5nz98sdaliIiclQUd1i3ZFO9bv5JHdvXzxO7DtS5HRGTeFnRYA3zqHRdz7qIm/vO9T3NyJF/rckRE5mXWsDazu83soJk9W42CKq0lm+K/vfcydh0a5EsPv1zrckRE5qWclvVXgFsiriNSN12ynNuu6OYLD+5gx0F9OIGI1J9Zw9rdHwbqvsP3D9+9jmw6wae+/bQuQxeRulOxPmsz22BmvWbW29cXvw+uXd6e43O/8UaeevUo/+W+Z3DXlY0iUj8qFtbuvtHde9y9p6urq1KbrahbLu/m9371Yu7bspd7el+tdTkiImVb8KNBpvr4TRdy7Zol/NfvbOMxfaKMiNSJhgvrZMK464PXsLKzid+8+3G+9/T+WpckIjKrcobufRN4BFhrZq+Z2UejLytaHc1pNv3OW7j83A7u3LSF7z61r9YliYicUTmjQT7g7t3unnb3le7+5WoUFrVl7Tm+8pF/wVXnLeI/bNrCFx/aqZOOIhJbDdcNUqotl+bvfvvN3HpFN//jBy/w6Xs1rE9E4ilV6wJqLZdO8hd3XM2qzmb+6mc7eWbvMb70mz2c19lc69JERMY1dMt6TCJhfPqWS/jyh3rYd/QU7/7Ln/P/tu5Vt4iIxIbCusTbL13O/R+7jnM6mrhz01bed9cv2X1osNZliYgorKda09XKdz/xNv77v7qcZ/cd5+b//RCf/8l29WWLSE0prKeRTBgffPMq/ulTv8I7L1vB53/yEm//s4f4zpa9DOcV2iJSfRZFv2xPT4/39vZWfLu18sjOfv74u9t44cAJutqybLj+At53zUo6WzK1Lk1EFggz2+zuPTMuV1iXJ18o8uCLfdz1sx08+cpRsqkEN65dxm1v7OZX1nbRnkvXukQRqWOzhXXDD90rVyqZ4OZ1y7l53XKe33+cbzz2Ct97Zj8PbDtAKmG89+pzec+V57B+1WJaszqsIlJZalmfhWLReWL3YX7w7AE2PfEKQ6NFkgnjjSs7uHbNEt56wVKuWbWYpkyy1qWKSMypG6RKBobzbHnlCI/u6ueXO/t5+rVjFIpOJpngqvMWcfUbFnHhslYu7W5n7Yo20kmd2xWRCeoGqZLWbIrrL+ri+ouCe3kPDOd54uXDPLKrn0d39fO3v9jNSKEIQHMmybVrlvLm8zu5ZvVi1nW3k0ur9S0iM1NYR6Q1m+LGS5Zx4yXLgOAE5Z7DJ9m27ziP7urn5y8d4ifPvz6+/qolzVy0rI01XS0sbc2yvCPHuYtyrFzczLK2LGZWq4ciIjGgsK6SVDLBmq5W1nS18p4rzwHg4Ikhnnj5CC8dPMEL+0+ws2+Ah7f3jbfAx+TSCVYubqazJcP5S1q4aHkrHU1plrZm6WzJ0NmSoaM5TVs2pVAXWaAU1jW0rC3HbW/sBrrH57k7J4bz7D86xL5jp3il/yR7+k+y/9gp+gdHeGDbAb7VOzrt9tqyKbrasrQ3pVnUnGZxc4a2XIqWbIrmdJKmTJKWbIrWbCoI+KY0TZkkzZkkzekUTZkkmZT60kXiSGEdM2ZGey5N+4o0a1e0nba8WHQGRvIcGRzh8OAIhwZGODI4wrFTo7x25CT94fThwRF2HBxgYDjPwFCefLG8E8mphE0EeCZFUzqYbsokacmkJqazE8uasylas8HyXDoI/HQyQSaZIJ0yMskE2XSSTDJBJhXMTyWNVML0TkCkTArrOpNIhGGeS7NqSUvZvzdaKHJypMDgcJ6B4Tz9AyMcHxrl1EiBkyMFTo7kg+nRQjgvz8mRwvjy40N5Xj8+FK4bbGc4X5x9x7MYC+50Mgj4VMJIhl+phJEIv4/9nEomSJqRSAS3BUjYxPKEGamkkUwkSFpwrJIWLgunM6lgf4aRMEiYYRa8SBoTPyfG5hnj69r4+kbSgv2bBfst3VYirC8RLmvLpUglEuG2JrZbui/G9zG5jvH9h9sLfj9Yv3R7iXC9sde+0sdU+hgoWW+8ltL1w/mlj2VsexP7n6hVqkdh3SDSyQQdTQk6msIrLZef/TaLRefUaIHBkTyDwwUGhvKMFAqM5J3RQpHRQpHhfJGR8Gs4X2A4XyRfdEbzwfLRkumRglMoFikUCb578D1fcIrujBacfLFIoegUi8ELUKEYLCsUg698cWK6dNnY96HRIkV33Am+w/jPMj+Tg3zyC0BpwNvYC9z4702EvZVsa/KciXmlLw0T82Zb7/QXlNIXtIm92TTzZq6TGfbV2Zzhnt9962n7rASFtcxbImG0ZIM+cU7vsak7PkOIu4PjFMeWFaHgwQtAafAXPXgBm/jZGc4XGRzOB9srBtsNtjl5H2P79JJ9Tp1XGFsWzoOJ2oL1J7ZLyXxn8mPAT6+jdLuT9x1Mjx2fok+/raJP2VdJ7WO/M3ZMxuoeP+5Mnlf6ujmxnp8270zbKP2N6dZj2vV8mnkzrzfp9T38oS0XXaQqrEVC490T6O29xI9O/YuI1AGFtYhIHVBYi4jUAYW1iEgdKCuszewWM3vRzHaY2WeiLkpERCabNazNLAl8AXgXsA74gJmti7owERGZUE7L+k3ADnff5e4jwCbg9mjLEhGRUuWE9bnAqyU/vxbOExGRKqnYRTFmtgHYEP44YGYvznNTS4FDlamqolTX3KiuuVFdc7MQ61p1poXlhPVe4LySn1eG8yZx943AxjmVNg0z6z3TR9vUiuqaG9U1N6prbhqxrnK6QZ4ALjKz880sA9wB/EMUxYiIyPRmbVm7e97MPg78EEgCd7v7tsgrExGRcWX1Wbv794HvR1zLmLPuSomI6pob1TU3qmtuGq4uK70toIiIxJMuNxcRqQMKaxGROhCbsK72/UfM7Dwze9DMnjOzbWZ2Zzj/j8xsr5ltDb9uLfmdPwjre9HM3hlV7Wa228yeCfffG87rNLMfm9lL4ffF4Xwzsz8P9/20ma0v2c6HwvVfMrMPnWVNa0uOyVYzO25mn6zF8TKzu83soJk9WzKvYsfHzK4Jj/+O8HfL+jSCGer6nJm9EO77fjNbFM5fbWanSo7bF2fb/0yPcZ51Vex5s2Ck2GPh/G9ZMGpsvnV9q6Sm3Wa2tQbHa6ZsqO3fWPAxPrX9IhhlshO4AMgATwHrIt5nN7A+nG4DthPc++SPgN+fZv11YV1Z4Pyw3mQUtQO7gaVT5v0p8Jlw+jPAn4TTtwI/IPg4uLcAj4XzO4Fd4ffF4fTiCj5fBwgG8Vf9eAE3AOuBZ6M4PsDj4boW/u67zqKudwCpcPpPSupaXbrelO1Mu/+ZHuM866rY8wbcA9wRTn8R+HfzrWvK8j8D/rAGx2umbKjp31hcWtZVv/+Iu+939yfD6RPA85z5MvrbgU3uPuzuLwM7wrqrVfvtwFfD6a8C7y2Z/zUPPAosMrNu4J3Aj939sLsfAX4M3FKhWt4O7HT3PbPUG8nxcveHgcPT7O+sj0+4rN3dH/Xgv+prJduac13u/iN3z4c/PkpwUdmMZtn/TI9xznWdwZyet7BFeBNwbyXrCrf7fuCbZ9pGRMdrpmyo6d9YXMK6pvcfMbPVwNXAY+Gsj4dvZ+4uees0U41R1O7Aj8xsswWX8QMsd/f94fQBJj6fvJp1jbmDyf9EtT5eULnjc244Xen6AH6LoBU15nwz22JmD5nZ9SX1zrT/mR7jfFXieVsCHC15QarU8boeeN3dXyqZV/XjNSUbavo3FpewrhkzawX+Hvikux8H7gLWAFcB+wneilXb29x9PcFtaT9mZjeULgxfjWsy5jLsj3wP8O1wVhyO1yS1PD4zMbPPAnng6+Gs/cAb3P1q4D8C3zCz9nK3V4HHGLvnbYoPMLlBUPXjNU02nNX2zlZcwrqs+49UmpmlCZ6Mr7v7fQDu/rq7F9y9CHyJ4O3fmWqseO3uvjf8fhC4P6zh9fDt09hbv4PVriv0LuBJd389rLHmxytUqeOzl8ldFWddn5l9GPg14IPhPzlhN0N/OL2ZoD/44ln2P9NjnLMKPm/9BG/7U1Pmz1u4rV8HvlVSb1WP13TZcIbtVedvrJwO96i/CK6k3EVwQmPs5MVlEe/TCPqKPj9lfnfJ9O8R9N8BXMbkEy+7CE66VLR2oAVoK5n+JUFf8+eYfHLjT8Pp25h8cuNxnzi58TLBiY3F4XRnBY7bJuAjtT5eTDnhVMnjw+knf249i7puAZ4Duqas1wUkw+kLCP5Zz7j/mR7jPOuq2PNG8C6r9ATjv59vXSXH7KFaHS9mzoaa/o1FFobz+Oe7leCs607gs1XY39sI3sY8DWwNv24F/i/wTDj/H6b8UX82rO9FSs7eVrL28A/xqfBr29j2CPoGfwq8BPyk5Ek3gk/y2RnW3VOyrd8iOEG0g5KAPYvaWghaUh0l86p+vAjeHu8HRgn6+z5ayeMD9ADPhr/zl4RX+s6zrh0E/ZZjf2NfDNd9X/j8bgWeBN492/5neozzrKtiz1v4N/t4+Fi/DWTnW1c4/yvA705Zt5rHa6ZsqOnfmC43FxGpA3HpsxYRkTNQWIuI1AGFtYhIHVBYi4jUAYW1iEgdUFiLiNQBhbWISB34/yxX0xef7Qt8AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(range(20000), best_length)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c94468da",
   "metadata": {},
   "source": [
    "we can see after 10000 epochs, the data converged(the Y axis is a single digit because the list of numbers has been very large)\n",
    "\n",
    "now let's see best route and its length..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "d28ca0f2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-11-09T20:04:29.370185Z",
     "start_time": "2021-11-09T20:04:29.357242Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "286603.6453676496\n",
      "[579, 580, 578, 577, 576, 575, 573, 572, 574, 588, 589, 590, 594, 593, 595, 596, 597, 599, 598, 600, 601, 797, 796, 795, 794, 793, 789, 790, 791, 792, 732, 731, 730, 736, 737, 708, 709, 713, 710, 711, 712, 723, 728, 729, 727, 724, 725, 726, 663, 664, 665, 668, 667, 666, 670, 669, 672, 671, 674, 677, 675, 676, 682, 681, 680, 679, 678, 673, 719, 718, 720, 722, 714, 715, 721, 717, 716, 695, 694, 696, 707, 706, 697, 705, 698, 699, 700, 701, 969, 972, 971, 970, 693, 692, 691, 690, 689, 688, 687, 686, 685, 683, 684, 988, 989, 990, 984, 983, 985, 986, 987, 982, 981, 980, 979, 978, 977, 976, 975, 974, 973, 968, 967, 966, 965, 964, 963, 702, 703, 704, 740, 739, 738, 735, 734, 744, 745, 742, 741, 743, 747, 748, 746, 733, 749, 750, 751, 752, 753, 754, 755, 1000, 763, 764, 765, 962, 961, 993, 956, 955, 954, 953, 952, 951, 950, 949, 948, 947, 946, 945, 944, 943, 942, 941, 940, 939, 957, 958, 959, 960, 769, 767, 766, 768, 770, 771, 772, 774, 775, 773, 935, 934, 936, 938, 937, 933, 932, 931, 930, 929, 928, 927, 884, 885, 921, 922, 923, 924, 925, 926, 916, 917, 918, 902, 901, 900, 919, 920, 887, 891, 890, 889, 888, 886, 883, 882, 881, 880, 879, 878, 877, 876, 870, 871, 872, 869, 867, 868, 873, 875, 874, 847, 892, 893, 894, 895, 846, 848, 849, 845, 844, 850, 851, 843, 842, 897, 896, 898, 899, 907, 908, 906, 903, 904, 905, 909, 910, 911, 912, 915, 914, 913, 777, 776, 778, 779, 780, 762, 761, 760, 759, 758, 757, 756, 788, 787, 786, 785, 784, 783, 781, 782, 803, 802, 801, 798, 799, 800, 804, 805, 806, 1001, 807, 808, 809, 810, 813, 818, 814, 815, 841, 840, 839, 858, 852, 853, 857, 854, 855, 856, 862, 863, 864, 865, 866, 861, 860, 859, 1002, 838, 837, 836, 835, 834, 833, 832, 831, 830, 829, 826, 827, 828, 817, 816, 819, 820, 812, 811, 821, 822, 823, 824, 825, 552, 551, 550, 553, 554, 555, 556, 557, 558, 560, 559, 592, 591, 571, 570, 568, 566, 565, 564, 563, 561, 562, 549, 548, 542, 543, 547, 546, 545, 540, 544, 541, 539, 538, 537, 536, 535, 533, 534, 532, 531, 529, 528, 527, 526, 525, 530, 524, 523, 522, 516, 517, 521, 520, 519, 518, 567, 569, 514, 515, 512, 513, 487, 486, 485, 484, 492, 483, 493, 494, 495, 491, 490, 488, 489, 500, 499, 498, 507, 508, 509, 511, 510, 999, 506, 505, 504, 503, 502, 501, 213, 216, 217, 212, 211, 210, 209, 208, 207, 205, 206, 204, 203, 996, 202, 201, 200, 199, 198, 197, 196, 195, 187, 188, 194, 193, 189, 192, 190, 191, 218, 219, 215, 214, 220, 222, 223, 224, 496, 497, 225, 226, 227, 272, 273, 274, 275, 276, 277, 281, 282, 283, 301, 302, 303, 304, 113, 111, 110, 112, 114, 115, 280, 278, 279, 117, 116, 118, 119, 106, 105, 104, 103, 994, 107, 108, 109, 306, 305, 991, 297, 298, 300, 299, 284, 285, 286, 287, 288, 404, 403, 402, 408, 409, 380, 381, 385, 382, 383, 384, 395, 340, 339, 391, 390, 392, 394, 393, 389, 388, 387, 386, 379, 378, 368, 366, 367, 362, 361, 360, 352, 351, 350, 353, 354, 357, 358, 359, 363, 364, 365, 642, 643, 644, 641, 640, 639, 638, 637, 636, 635, 374, 375, 376, 373, 372, 371, 370, 369, 377, 412, 411, 413, 414, 415, 417, 416, 410, 407, 406, 405, 418, 420, 419, 427, 426, 425, 424, 422, 421, 423, 464, 463, 462, 461, 428, 460, 465, 466, 467, 468, 469, 470, 480, 479, 481, 482, 998, 478, 477, 471, 472, 476, 475, 474, 473, 459, 458, 457, 456, 455, 453, 454, 450, 451, 452, 432, 431, 430, 429, 997, 435, 436, 437, 433, 434, 447, 446, 444, 445, 448, 449, 585, 584, 583, 582, 581, 587, 586, 602, 603, 604, 613, 612, 605, 606, 607, 608, 609, 610, 611, 629, 630, 632, 631, 443, 442, 441, 440, 438, 439, 634, 633, 992, 625, 626, 628, 627, 614, 615, 616, 617, 618, 619, 620, 624, 623, 621, 622, 649, 650, 651, 648, 645, 646, 647, 652, 653, 654, 659, 658, 657, 655, 656, 662, 661, 660, 356, 355, 348, 347, 346, 349, 345, 344, 343, 341, 342, 338, 337, 336, 335, 398, 397, 396, 400, 401, 399, 292, 291, 290, 289, 296, 295, 293, 294, 321, 322, 323, 320, 317, 318, 319, 324, 326, 325, 316, 315, 314, 313, 312, 311, 310, 309, 308, 307, 46, 47, 48, 45, 44, 43, 42, 49, 41, 50, 40, 51, 84, 83, 80, 81, 52, 53, 57, 54, 55, 56, 67, 66, 58, 59, 65, 61, 60, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 26, 29, 331, 330, 329, 327, 328, 334, 333, 332, 28, 27, 20, 19, 18, 21, 25, 24, 23, 22, 17, 16, 15, 13, 14, 10, 9, 8, 7, 11, 12, 63, 62, 64, 68, 69, 70, 72, 73, 71, 5, 4, 6, 3, 2, 1, 74, 75, 77, 93, 94, 96, 97, 98, 99, 91, 92, 90, 89, 87, 85, 86, 88, 82, 78, 79, 76, 95, 134, 133, 100, 101, 102, 128, 129, 130, 131, 132, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 149, 148, 146, 145, 147, 126, 127, 125, 124, 123, 122, 120, 121, 257, 256, 255, 254, 253, 259, 258, 270, 271, 269, 268, 267, 266, 265, 229, 228, 230, 232, 231, 264, 263, 243, 244, 245, 246, 262, 261, 260, 248, 247, 249, 250, 251, 252, 995, 150, 151, 152, 153, 154, 155, 165, 166, 167, 168, 169, 172, 171, 170, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 159, 160, 161, 163, 162, 158, 164, 156, 157, 186, 241, 242, 240, 235, 233, 234, 221, 236, 237, 239, 238]\n"
     ]
    }
   ],
   "source": [
    "length_pr1002 = best_length[-1]\n",
    "route_pr1002 = best_routes[-1]\n",
    "print(length_pr1002)\n",
    "print(route_pr1002)"
   ]
  }
 ],
 "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.8.0"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}