tsp-ga.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json, operator, random, pandas as pd, numpy as np\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as mpimg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "map = mpimg.imread('map.png')\n",
    "\n",
    "with open('capitals.json', 'r') as capitals_file:\n",
    "    capitals = json.load(capitals_file)\n",
    "capitalsList = list(capitals.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "def showPath(path, starting_city, w=15, h=15):\n",
    "    x, y = list(zip(*path))\n",
    "    _, (x0, y0) = starting_city\n",
    "\n",
    "    plt.imshow(map)\n",
    "    plt.plot(x + x[:1], y + y[:1], 'g--')\n",
    "    plt.plot(x + x[:1], y + y[:1], 'r*', markersize=20)\n",
    "    plt.plot(x0, y0, 'y*', markersize=25)\n",
    "    plt.axis(\"off\")\n",
    "\n",
    "    fig = plt.gcf()\n",
    "    fig.set_size_inches([w, h])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coords(capitals):\n",
    "    _, coords = zip(*capitals)\n",
    "    return coords"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateIndividual(cityList, popSize):\n",
    "    population = []\n",
    "\n",
    "    for i in range(0, popSize):\n",
    "        population.append(random.sample(cityList, len(cityList)))\n",
    "\n",
    "    return population"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(city1, city2):\n",
    "    x1, _ = city1\n",
    "    x2, _ = city2\n",
    "    _, y1 = city1\n",
    "    _, y2 = city2\n",
    "\n",
    "    xDis = abs(x1 - x2)\n",
    "    yDis = abs(y1 - y2)\n",
    "\n",
    "    distance = np.sqrt((xDis * xDis) + (yDis * yDis))\n",
    "\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fitness(route):\n",
    "    score = 0\n",
    "\n",
    "    for i in range(1, len(route)):\n",
    "        k = route[i - 1]\n",
    "        l = route[i]\n",
    "        score = score + distance(k, l)\n",
    "\n",
    "    return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "def popScore(population):\n",
    "    fitnessResults = {}\n",
    "\n",
    "    for i in range(0, len(population)):\n",
    "        fitnessResults[i] = fitness(population[i])\n",
    "\n",
    "    return sorted(fitnessResults.items(), key=operator.itemgetter(1), reverse=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection(popRanked, eliteSize):\n",
    "    selectionResults = []\n",
    "\n",
    "    df = pd.DataFrame(np.array(popRanked), columns=[\"Index\", \"Fitness\"])\n",
    "    df['cum_sum'] = df.Fitness.cumsum()\n",
    "    df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()\n",
    "\n",
    "    for i in range(0, eliteSize):\n",
    "        selectionResults.append(popRanked[i][0])\n",
    "\n",
    "    for i in range(0, len(popRanked) - eliteSize):\n",
    "        pick = 100 * random.random()\n",
    "        for i in range(0, len(popRanked)):\n",
    "            if pick <= df.iat[i, 3]:\n",
    "                selectionResults.append(popRanked[i][0])\n",
    "                break\n",
    "\n",
    "    return selectionResults"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matingPool(population, selectionResults):\n",
    "    matingpool = []\n",
    "    \n",
    "    for i in range(0, len(selectionResults)):\n",
    "        index = selectionResults[i]\n",
    "        matingpool.append(population[index])\n",
    "\n",
    "    return matingpool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossover(parent1, parent2):\n",
    "    child = []\n",
    "    childP1 = []\n",
    "    childP2 = []\n",
    "\n",
    "    geneA = int(random.random() * len(parent1))\n",
    "    geneB = int(random.random() * len(parent1))\n",
    "\n",
    "    startGene = min(geneA, geneB)\n",
    "    endGene = max(geneA, geneB)\n",
    "\n",
    "    for i in range(startGene, endGene):\n",
    "        childP1.append(parent1[i])\n",
    "\n",
    "    childP2 = [item for item in parent2 if item not in childP1]\n",
    "\n",
    "    child = childP1 + childP2\n",
    "    return child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evolvePopulation(matingpool, eliteSize):\n",
    "    children = []\n",
    "    length = len(matingpool) - eliteSize\n",
    "    pool = random.sample(matingpool, len(matingpool))\n",
    "\n",
    "    for i in range(0, eliteSize):\n",
    "        children.append(matingpool[i])\n",
    "\n",
    "    for i in range(0, length):\n",
    "        child = crossover(pool[i], pool[len(matingpool) - i - 1])\n",
    "        children.append(child)\n",
    "    return children"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(individual, mutationRate):\n",
    "    for swapped in range(len(individual)):\n",
    "        if random.random() < mutationRate:\n",
    "            swapWith = int(random.random() * len(individual))\n",
    "\n",
    "            city1 = individual[swapped]\n",
    "            city2 = individual[swapWith]\n",
    "\n",
    "            individual[swapped] = city2\n",
    "            individual[swapWith] = city1\n",
    "\n",
    "    return individual"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutatePopulation(children, mutationRate):\n",
    "    newGeneration = []\n",
    "\n",
    "    for i in children:\n",
    "        mutatedChild = mutate(i, mutationRate)\n",
    "        newGeneration.append(mutatedChild)\n",
    "\n",
    "    return newGeneration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nextGeneration(currentGen, eliteSize, mutationRate):\n",
    "    popRanked = popScore(currentGen)\n",
    "\n",
    "    selectionResults = selection(popRanked, eliteSize)\n",
    "\n",
    "    matingpool = matingPool(currentGen, selectionResults)\n",
    "\n",
    "    children = evolvePopulation(matingpool, eliteSize)\n",
    "\n",
    "    nextGeneration = mutatePopulation(children, mutationRate)\n",
    "\n",
    "    return nextGeneration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [],
   "source": [
    "def geneticAlgorithm(capitalsList, popSize, eliteSize, mutationRate, generations):\n",
    "    cityList = coords(capitalsList)\n",
    "    progress = []\n",
    "\n",
    "    pop = generateIndividual(cityList, popSize)\n",
    "\n",
    "    print(f'Initial distance={popScore(pop)[0][1]}')\n",
    "\n",
    "    progress.append(popScore(pop)[0][1])\n",
    "\n",
    "    for i in range(0, generations):\n",
    "        pop = nextGeneration(pop, eliteSize, mutationRate)\n",
    "        progress.append(popScore(pop)[0][1])\n",
    "\n",
    "    print(f'Final distance={popScore(pop)[0][1]}')\n",
    "\n",
    "    bestRouteIndex = popScore(pop)[0][0]\n",
    "\n",
    "    bestRoute = pop[bestRouteIndex]\n",
    "\n",
    "    plt.plot(progress)\n",
    "    plt.ylabel('Distance')\n",
    "    plt.xlabel('Generation')\n",
    "    plt.show()\n",
    "    return bestRoute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numCities = 15\n",
    "\n",
    "bestRoute = geneticAlgorithm(\n",
    "    capitalsList[:numCities],\n",
    "    popSize=100,\n",
    "    eliteSize=30,\n",
    "    mutationRate=0.01,\n",
    "    generations=300,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f'Best route={bestRoute}')\n",
    "\n",
    "showPath(bestRoute, capitalsList[0])"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
  },
  "kernelspec": {
   "display_name": "Python 3.9.2 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}