{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Travelling Sales Ants\n",
    "A solution to the Traveling Salesman Problem using swarm intelligence\n",
    "<img src=\"salesant.jpg\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Algorithm\n",
    "I primarily followed the ACS Algorithm outlined during class, since it has a handful of variables that can be tuned to change the behavior of the simulated ants. I designed my python program to be as mutable as possible, so as to make analyzing the results straightforward, and to make it easy to modify for later use."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generating Cities\n",
    "I translated the provided generator into python to make collecting test data easier. The random seed can be set to generate the same city every time for test purposes, or left out to generate a different graph every time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from generator import SparseInstance, Loader, Node\n",
    "from antcolony import Colony, Ant\n",
    "\n",
    "# the generator takes in the number of cities, and an optional seed\n",
    "gen = SparseInstance(12, seed = 5)\n",
    "cities = gen.generateCities()\n",
    "\n",
    "def printPath(path, length):\n",
    "    s = ''\n",
    "    for node in path:\n",
    "        s +=  str(node[0]) + ' '\n",
    "    print \"path:\", s\n",
    "    print \"total length:\", length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nearest Neighbors Heuristic\n",
    "The ACS algorithm requires a heuristic to approximate the initial Pheremone value for the graph. I implemented a nearest neighbor algorithm to approximate this value. Unfortunately, there were many times where the algorithm would not finish with a complete path, so I simply returned double the current value. I think this causes the algorithm to converge slightly more slowly than it should, but my algorithm tends to find a good path given more iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "754.0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "colony = Colony(12, 'iterations', 100)\n",
    "colony.nnheuristic(cities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "path: 4 8 6 11 3 11 7 9 2 9 1 10 0 5 \n",
      "total length: 348.0\n"
     ]
    }
   ],
   "source": [
    "path, length = colony.ACS(cities)\n",
    "printPath(path, length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the heuristic value can be wildly off, but the ant solution looks quite good."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convergence\n",
    "How quickly does the algorithm find a decent solution? I ran a series of tests on my 12-city graph and a 100 city graph. The 100 city graph took a long time to run so I cut it off at 50 iterations, which does show that the solution is converging."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Run on a graph with 12 cities\n",
    "tests = [1, 10, 25, 50, 100, 250]# 500, 1000]\n",
    "data = [[] for k in range(len(tests))]\n",
    "for i in range(len(tests)):\n",
    "    colony = Colony(12, 'iterations', tests[i])\n",
    "    for k in range(10):\n",
    "        path, length = colony.ACS(cities)\n",
    "        data[i].append(length)\n",
    "    plt.scatter([tests[i] for k in range(10)], data[i])\n",
    "plt.ylim([0, 1000])\n",
    "plt.show()\n",
    "\n",
    "# Run on a graph with 100 cities\n",
    "gen = SparseInstance(100, seed = 5)\n",
    "cities = gen.generateCities()\n",
    "tests = [1, 10, 25, 50, 100,]\n",
    "data = [[] for k in range(len(tests))]\n",
    "for i in range(len(tests)):\n",
    "    colony = Colony(12, 'iterations', tests[i])\n",
    "    for k in range(3):\n",
    "        path, length = colony.ACS(cities)\n",
    "        data[i].append(length)\n",
    "    plt.scatter([tests[i] for k in range(10)], data[i])\n",
    "# plt.ylim([0, 1000])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"12cities.png\">\n",
    "\n",
    "It looks like it finds a decent solution within around 100 iterations for n = 12, so I will cap future runs at that."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loading Given Graphs\n",
    "Here I created a loader class to generate graphs for the given test data files. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Four Cities: Optimal is 143\n",
      "path: 1 2 0 3 1 \n",
      "total length: 143.0\n",
      "Time taken:  0.134999990463\n",
      "----------\n",
      "Six Cities: Optimal is 261\n",
      "path: 5 0 3 2 4 1 5 \n",
      "total length: 261.0\n",
      "Time taken:  0.819999933243\n",
      "----------\n",
      "Eight Cities: Optimal is 296\n",
      "path: 5 7 5 4 6 3 1 2 0 5 \n",
      "total length: 272.0\n",
      "Time taken:  2.9319999218\n",
      "----------\n",
      "Ten Cities: Optimal is 275\n",
      "path: 2 5 7 4 9 0 3 6 8 1 8 2 \n",
      "total length: 318.0\n",
      "Time taken:  7.44400000572\n",
      "----------\n",
      "Twlve Cities: Optimal is 269\n",
      "path:"
     ]
    }
   ],
   "source": [
    "import time\n",
    "def testFile(filename, numberofAnts, iterations):\n",
    "    loader = Loader()\n",
    "    cities = loader.load(filename)\n",
    "    colony = Colony(numberofAnts, iterations)\n",
    "    tstart = time.time()\n",
    "    path, length = colony.ACS(cities)\n",
    "    printPath(path, length)\n",
    "    print \"Time taken: \", time.time() - tstart\n",
    "    print \"----------\"\n",
    "\n",
    "\n",
    "print \"Four Cities: Optimal is 143\"\n",
    "testFile('four.txt', 4, 20)\n",
    "print \"Six Cities: Optimal is 261\"\n",
    "testFile('six.txt', 6, 20)\n",
    "print \"Eight Cities: Optimal is 296\"\n",
    "testFile('eight.txt', 8, 20)\n",
    "print \"Ten Cities: Optimal is 275\"\n",
    "testFile('ten.txt', 10, 20)\n",
    "print \"Twelve Cities: Optimal is 269\"\n",
    "testFile('twelve.txt', 12, 20)\n",
    "print \"Thirty Cities: Optimal is 1265\"\n",
    "testFile('thirty.txt', 30, 20)\n",
    "print \"Thirty Cities Sparse: Optimal is 1265\"\n",
    "testFile('thirtySparse.txt', 30, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data Results\n",
    "Comparing my results to the given solutions, my ants seem to do better than optimal for some examples. The algorithm does find the optimal solution for smaller graphs, however. I realized that this is because I designed my algorithm for a slightly different problem than the solutions'; I solved for the total shortest path, but not for the shortest hamiltonian cycle. This was also why I had issues writing my nearest-neighbor heuristic, since some of the generated graphs did not have hamiltonian cycles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parameter Tuning\n",
    "#### Exploration\n",
    "To view how much changing a parameter affects the rate of convergence, I ran the algorithm with a small number of iterations on a relatively large graph. q (chance to take only the best path ) values below 0.1 and above 0.9 resulted in terrible paths, so I will not calculate them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEACAYAAAC+gnFaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGAJJREFUeJzt3X+Q3HV9x/HnqyQ3nIYE1IOMQW+DGHNYokY5sbZlgwaM\nU0NGnRB0RCWlFagyah0T205upp1BbJ2inR4zzJwBOpIQdQZCjQGpWTupYK6oPTTBnOPskaQlrgqZ\niQa5yLt/7PdgOZLs7/vu3vf1mNnhu5/97Hfft2z2td/v5/v9fBURmJlZdv1B2gWYmVm6HARmZhnn\nIDAzyzgHgZlZxjkIzMwyzkFgZpZxVYNA0rmSviPpJ5IelfSJpP0sSQ9I+qmk+yUtqHjORknjkvZJ\nuqyifbmkMUn7Jd3Snj/JzMzqUcsWwXHgUxHxeuBtwA2SlgIbgAcj4nXAd4CNAJIuANYCA8AqYFiS\nknXdCqyPiCXAEkmXt/SvMTOzulUNgoh4IiJ+lCwfBfYB5wJXAHck3e4A1iTLq4GtEXE8IorAODAo\naSFwRkSMJv3urHiOmZmlpK4xAkk54I3Aw8A5EXEYymEBnJ10WwQcqHjaoaRtEXCwov1g0mZmZimq\nOQgkzQO+DtyYbBlMn5vCc1WYmXWhObV0kjSHcgj8W0TcmzQflnRORBxOdvv8Imk/BLyq4unnJm0n\naz/R6zlUzMwaEBGq3uuFat0i+AqwNyK+VNG2HfhIsvxh4N6K9nWSeiQtBs4H9iS7j45IGkwGj6+u\neM6LRETX3jZt2pR6DVms3fWnf3P96d4aVXWLQNLbgQ8Cj0r6IeVdQJ8Dbga2SboGmKB8pBARsVfS\nNmAvMAlcH89XeANwO3A6sCMidjZcuZmZtUTVIIiI/wJOO8nD7zzJc24CbjpB+yPAhfUUaGZm7eUz\ni9sgn8+nXULDurl2cP1pc/3dSc3sV2oXSdGJdZmZdTJJRBsHi83MbJZyEJiZZZyDwMws4xwEZmYZ\n5yAwM8s4B4GZWcY5CMzMMs5BYGaWcQ4CM7OMcxCYmWWcg8DMLOMcBGZmGecgMDPLOAeBmVkDSqUS\no6OjlEqltEtpmoPAzKxOW7bcTX//Ulau/Bj9/UvZsuXutEtqiq9HYGZWh1KpRH//Uo4d2wUsA8bo\n7V3BxMRj9PX1pVqbr0dgZjYDisUiPT05yiEAsIy5c/spFovpFdUkB4GZWR1yuRzPPFMExpKWMSYn\nJ8jlcukV1SQHgZlZHfr6+hgZGaa3dwXz5y+nt3cFIyPDqe8WaobHCMzMGlAqlSgWi+RyuY4JgUbH\nCBwEZmazRNsGiyWNSDosaayi7Q2SHpL0Q0l7JL2l4rGNksYl7ZN0WUX7ckljkvZLuqXeQs3MrD1q\nGSPYDFw+re0LwKaIeBOwCfhHAEkXAGuBAWAVMCxpKp1uBdZHxBJgiaTp6zQzsxRUDYKI2A08Oa35\nWWBBsnwmcChZXg1sjYjjEVEExoFBSQuBMyJiNOl3J7CmydrNzKwF5jT4vE8C90v6IiDgj5L2RcBD\nFf0OJW3HgYMV7QeTdjMzS1mjQXAdcGNE3CPp/cBXgJWtKwuGhoaeW87n8+Tz+Vau3sys6xUKBQqF\nQtPrqemoIUn9wH0RsSy5/1REnFnx+FMRcaakDUBExM1J+07KYwgTwK6IGEja1wGXRMR1J3k9HzVk\nZlandk8xoeQ25ZCkS5IXfgflsQCA7cA6ST2SFgPnA3si4gngiKTBZPD4auDeeos1M7PWq7prSNJd\nQB54uaTHKf/Cvxb4sqTTgKeBvwCIiL2StgF7gUng+oqf9jcAtwOnAzsiYmdr/xQzM2uETygzM5sl\nPPuomZk1xEFgZpZxDgIzs4xzEJiZZZyDwMws4xwEZmYNKJVKjI6OUiqV0i6laQ4CM7M6bdlyN/39\nS1m58mP09y9ly5a70y6pKT6PwMysDqVSif7+pRw7tovyBezH6O1dwcTEY6lfqcznEZiZzYBisUhP\nT45yCAAsY+7cforFYnpFNclBYGZWh1wuxzPPFIGpizaOMTk5QS6XS6+oJjkIzMzq0NfXx8jIML29\nK5g/fzm9vSsYGRlOfbdQMzxGYGbWgFKpRLFYJJfLdUwINDpG4CAwM5slPFhsZmYNcRCYmWWcg8DM\nLOMcBGZmGecgMDPLOAeBmVnGOQjMzDLOQWBmlnEOAjOzjHMQmJllXNUgkDQi6bCksWntH5e0T9Kj\nkj5f0b5R0njy2GUV7csljUnaL+mW1v4ZZmbWqFq2CDYDl1c2SMoD7wEujIgLgX9K2geAtcAAsAoY\nljQ178WtwPqIWAIskfSCdZqZWTqqBkFE7AaenNZ8HfD5iDie9Pll0n4FsDUijkdEERgHBiUtBM6I\niNGk353AmhbUb2ZmTWp0jGAJ8KeSHpa0S9Kbk/ZFwIGKfoeStkXAwYr2g0mbmZmlbE4TzzsrIi6W\ndBHwNeC81pUFQ0NDzy3n83ny+XwrV29m1vUKhQKFQqHp9dR0PQJJ/cB9EbEsub8DuDkivpvcHwcu\nBq4FiIjPJ+07gU3ABLArIgaS9nXAJRFx3Ulez9cjMDOrU7uvR6DkNuUe4NLkhZcAPRHxK2A7cKWk\nHkmLgfOBPRHxBHBE0mAyeHw1cG+9xZqZWetV3TUk6S4gD7xc0uOUf+F/Bdgs6VHgd5S/2ImIvZK2\nAXuBSeD6ip/2NwC3A6cDOyJiZ2v/FDMza4QvVWlmNkv4UpVmZtYQB4GZWcY5CMzMMs5BYGaWcQ4C\nM7OMcxCYmWWcg8DMLOMcBGZmGecgMDPLOAeBmVnGOQjMzDLOQWBm1oBSqcTo6CilUintUprmIDAz\nq9OWLXfT37+UlSs/Rn//UrZsuTvtkpri2UfNzOpQKpXo71/KsWO7gGXAGL29K5iYeIy+vr5Ua/Ps\no2ZmM6BYLNLTk6McAgDLmDu3n2KxmF5RTXIQmJnVIZfL8cwzRWAsaRljcnKCXC6XXlFNchCYmdWh\nr6+PkZFhentXMH/+cnp7VzAyMpz6bqFmeIzAzKwBpVKJYrFILpfrmBBodIzAQWBmNkt4sNjMzBri\nIDAzyzgHgZlZxjkIzMwyrmoQSBqRdFjS2Ake+7SkZyW9rKJto6RxSfskXVbRvlzSmKT9km5p3Z9g\nZmbNqGWLYDNw+fRGSecCK4GJirYBYC0wAKwChiVNjWDfCqyPiCXAEkkvWqeZmc28qkEQEbuBJ0/w\n0D8Dn5nWdgWwNSKOR0QRGAcGJS0EzoiI0aTfncCahqs2M7OWaWiMQNJq4EBEPDrtoUXAgYr7h5K2\nRcDBivaDSZuZmaVsTr1PkNQLfI7ybqG2GRoaem45n8+Tz+fb+XJmZl2nUChQKBSaXk9NZxZL6gfu\ni4hlkv4QeBD4LSDgXMq//AeBawAi4vPJ83YCmyiPI+yKiIGkfR1wSURcd5LX85nFZl2mE6dcyJp2\nn1ms5EZE/DgiFkbEeRGxmPJunjdFxC+A7cCVknokLQbOB/ZExBPAEUmDyeDx1cC99RZrZp1ptl2o\nJWuqbhFIugvIAy8HDgObImJzxeM/B94SEb9O7m8E1gOTwI0R8UDS/mbgduB0YEdE3HiK1/QWgVmX\n6OQLtWRNo1sEVccIIuIDVR4/b9r9m4CbTtDvEeDCegs0s842daGWY8defKEWB0F38JnFZtaU2Xih\nlqxxEJhZU2bjhVqyxtcjMLOW8FFD6fOFaczMMs4XpjEzs4Y4CMzMMs5BYGaWcQ4CM7OMcxCYmWWc\ng8DMLOMcBGbWEqVSidHRUUqlUtqlWJ0cBGbWNM8+2t18QpmZNcWzj3YOn1BmZqmYmn20HAJQOfuo\ndQcHgZk1xbOPdj8HgZk1xbOPdj+PEZhZS3j20fR59lEzs4zzYLGZmTXEQWBmlnEOAjOzjHMQmJll\nnIPAzCzjqgaBpBFJhyWNVbR9QdI+ST+S9A1J8yse2yhpPHn8sor25ZLGJO2XdEvr/xQzM2tELVsE\nm4HLp7U9ALw+It4IjAMbASRdAKwFBoBVwLCkqUOZbgXWR8QSYImk6es0M7MUVA2CiNgNPDmt7cGI\neDa5+zBwbrK8GtgaEccjokg5JAYlLQTOiIjRpN+dwJoW1G9mZk1qxRjBNcCOZHkRcKDisUNJ2yLg\nYEX7waTNzMxSNqeZJ0v6G2AyIra0qJ7nDA0NPbecz+fJ5/Otfgkzs65WKBQoFApNr6emKSYk9QP3\nRcSyiraPANcCl0bE75K2DUBExM3J/Z3AJmAC2BURA0n7OuCSiLjuJK/nKSbMzOrU7ikmlNymXuxd\nwGeA1VMhkNgOrJPUI2kxcD6wJyKeAI5IGkwGj68G7q23WDPrXL5UZfeq5fDRu4DvUT7S53FJHwX+\nBZgHfFvSDyQNA0TEXmAbsJfyuMH1FT/tbwBGgP3AeETsbPlfY2ap8KUqu5tnHzWzpvhSlZ3Ds4+a\nWSp8qcru5yAws6b4UpXdz0FgZk3xpSq7n8cIzKwlfKnK9PlSlWZmGefBYjMza4iDwMws4xwEZmYZ\n5yAwaxNPuWDdwkFg1gaecsG6iY8aMmsxT7lgafFRQ2YdwlMuWLdxEJi1mKdcsG7jIDBrMU+5YN3G\nYwRmbeIpF2ymeYoJM7OM82CxmZk1xEFgZpZxDgIzs4xzEJiZZZyDwMws4xwEZmYZ5yAwM8u4qkEg\naUTSYUljFW1nSXpA0k8l3S9pQcVjGyWNS9on6bKK9uWSxiTtl3RL6/8UMzNrRC1bBJuBy6e1bQAe\njIjXAd8BNgJIugBYCwwAq4BhSVMnN9wKrI+IJcASSdPXaWZmKagaBBGxG3hyWvMVwB3J8h3AmmR5\nNbA1Io5HRBEYBwYlLQTOiIjRpN+dFc8xM7MUNTpGcHZEHAaIiCeAs5P2RcCBin6HkrZFwMGK9oNJ\nm5mZpWxOi9bT8omBhoaGnlvO5/Pk8/lWv4SZWVcrFAoUCoWm11PTpHOS+oH7ImJZcn8fkI+Iw8lu\nn10RMSBpAxARcXPSbyewCZiY6pO0rwMuiYjrTvJ6s2bSOc9AaWYzpd2Tzim5TdkOfCRZ/jBwb0X7\nOkk9khYD5wN7kt1HRyQNJoPHV1c8Z9bydWvNrBtU3SKQdBeQB14OHKb8C/8e4GvAqyj/2l8bEU8l\n/TcC64FJ4MaIeCBpfzNwO3A6sCMibjzFa3b9FoGvW2tmM63RLYKqYwQR8YGTPPTOk/S/CbjpBO2P\nABfWVV0Xm7pu7bFjL75urYMgG7xb0LqFzyxuE1+3Ntu8W9C6ia9Q1kZbttzN+vXXM3duP5OTE4yM\nDHPVVVemXZa1mXcLWlratmvIGnfVVVfyznde6t0DGePdgtZtHARt1tfX53/8GfPC3YLlLQLvFrRO\n5jECsxbr6+tjZGSY3t4VzJ+/nN7eFYyMDPsHgXUsjxGYtYmPGrKZ1ugYgYPAzGyWaPeZxWZmNks5\nCMzMMs5B0GalUonR0VFKpVLapZiZnZCDoI18dqmZdQMPFreJzy41HzVkM82DxR1m6uzScghA5dml\nNvt5a9C6ibcI2sRbBNnl//eWFm8RdBifXfpiWRk499agdRtvEbSZ9xOXTc3E2tNTnodnNs/E6i0C\nS4vPLLaO9fwX4zeAlwK/obf3fbP6i9FTkFsaPA21dazyLpEzgfcBOaBIxPxZPS2zpyC3buIgaDPv\nGoJ58+Zx7Nj/AQ8ztavk6acvZt68eSlX1l6egty6hQeL28iHEJYdPXqU3t7zqRw87e19DUePHk2z\nLDNLeIygTTxg+Dy/F2Yzw4ePdhgfQvg8H0pr1tm8RdAm/hX8Yh4vMWuvVLYIJH1S0o8ljUn6qqQe\nSWdJekDSTyXdL2lBRf+NksYl7ZN0WTOv3en8K/jF+vr6uOiiizL9Hph1ooa3CCS9EtgNLI2IZyTd\nDewALgB+FRFfkPRZ4KyI2CDpAuCrwEXAucCDwGtP9NN/NmwRTPGvYDObKWmNEZwGvFTSHKAXOARc\nAdyRPH4HsCZZXg1sjYjjEVEExoHBJl+/4/lXsJl1uoaDICL+F/gi8DjlADgSEQ8C50TE4aTPE8DZ\nyVMWAQcqVnEoabOMyMpcQ2bdpuETyiSdSfnXfz9wBPiapA8C0/fpNLSPZ2ho6LnlfD5PPp9vqE7r\nDFmaa8hsphQKBQqFQtPraWaM4P3A5RFxbXL/Q8DFwKVAPiIOS1oI7IqIAUkbgIiIm5P+O4FNEfH9\nE6x71owRmI+gMpspaYwRPA5cLOl0SQLeAewFtgMfSfp8GLg3Wd4OrEuOLFoMnA/saeL1rUv4nAqz\nztbwrqGI2CPp68APgcnkv7cBZwDbJF0DTABrk/57JW2jHBaTwPX+2Z8NuVx5dxCMMbVFMDk5QS6X\nS7UuMyvzCWU2Izwts1n7+XoE1vF8ToVZezkIzMwyzpPOmZlZQxwEZmYZ5yAwM8s4B4GZWcY5CMzM\nMs5BYGaWcQ4CM7OMcxCYmWWcg8DMLOMcBGZmGecgMDPLOAeBmVnGOQjMzDLOQWBmlnEOAjOzjHMQ\nmJllnIPAzCzjHARmZhnnIDAzyzgHgZlZxjUVBJIWSPqapH2SfiLprZLOkvSApJ9Kul/Sgor+GyWN\nJ/0va758MzNrVrNbBF8CdkTEAPAG4DFgA/BgRLwO+A6wEUDSBcBaYABYBQxLUpOv35EKhULaJTSs\nm2sH158219+dGg4CSfOBP4mIzQARcTwijgBXAHck3e4A1iTLq4GtSb8iMA4MNvr6naybP0zdXDu4\n/rS5/u7UzBbBYuCXkjZL+oGk2yS9BDgnIg4DRMQTwNlJ/0XAgYrnH0razMwsRc0EwRxgOfCvEbEc\n+A3l3UIxrd/0+2Zm1kEU0dj3tKRzgIci4rzk/h9TDoLXAPmIOCxpIbArIgYkbQAiIm5O+u8ENkXE\n90+wboeHmVkDIqLusdeGgwBA0neBayNiv6RNwEuSh34dETdL+ixwVkRsSAaLvwq8lfIuoW8Dr41m\nCjAzs6bNafL5nwC+Kmku8HPgo8BpwDZJ1wATlI8UIiL2StoG7AUmgesdAmZm6Wtqi8DMzLpfamcW\nS3qXpMck7U92IZ2oz5eTE9B+JOmNM13jqVSrX9LrJH1P0tOSPpVGjadSQ/0fkPQ/yW23pAvTqPNk\naqh/dVL7DyXtkfT2NOo8mVo+/0m/iyRNSnrvTNZ3KjW895dIeio5mvAHkv42jTpPpsbvnnzy2fmx\npF0zXeOp1PD+/3VS+w8kPSrpuKQzT7nSiJjxG+UA+hnQD8wFfgQsndZnFfDNZPmtwMNp1NpE/a8A\n3gz8PfCptGtuoP6LgQXJ8ru68P1/ScXyhcC+tOuup/6Kfv8B/Dvw3rTrruO9vwTYnnatTdS/APgJ\nsCi5/4q06673s1PR/88on+B7yvWmtUUwCIxHxERETAJbKZ+IVukK4E6AKB9ZtCA5UqkTVK0/In4Z\nEY8Ax9MosIpa6n84yicIAjxMZ53zUUv9v624Ow94dgbrq6aWzz/Ax4GvA7+YyeKqqLX2Tp01oJb6\nPwB8IyIOQfnf8gzXeCq1vv9TrgK2VFtpWkEw/eSyg7z4i6aTT0Crpf5OVm/9fw58q60V1aem+iWt\nkbQPuA+4ZoZqq0XV+iW9ElgTEbfSWV+qtX523pbs0v1mcsRgp6il/iXAyyTtkjQq6UMzVl11Nf/b\nldRLeWv+G9VW2uxRQzbLSVpB+WiwP067lnpFxD3APck5Lv8ArEy5pHrcAlTu/+2kMKjmEeDVEfFb\nSauAeyh/uXaLqZNlLwVeCjwk6aGI+Fm6ZdXtPcDuiHiqWse0guAQ8OqK++cmbdP7vKpKn7TUUn8n\nq6l+ScuA24B3RcSTM1RbLep6/yNit6TzJL0sIn7d9uqqq6X+twBbk4kZXwGskjQZEdtnqMaTqVp7\nRBytWP6WpOEue+8PAr+MiKeBpyX9J+VJNTshCOr57K+jht1CQGqDxafx/IBHD+UBj4Fpfd7N84PF\nF9NZg5VV66/ouwn4dNo1N/D+v5ryxIAXp11vg/W/pmJ5OXAg7bob+fwk/TfTOYPFtbz351QsDwLF\ntOuus/6llE94PY3ySbKPAhekXXs9nx3KA96/AnprWW8qWwQR8XtJfwU8QHmcYiQi9kn6y/LDcVtE\n7JD0bkk/ozyP0UfTqPVEaqk/Gdj+b+AM4FlJN1L+MB09+ZpnRi31A38HvIznpwufjIiOmC22xvrf\nJ+lq4BngGMmJjZ2gxvpf8JQZL/Ikaqz9/ZKuo3zi6DHgyvQqfqEav3sek3Q/MAb8HrgtIvamWPZz\n6vjsrAHuj4hjtazXJ5SZmWWcL1VpZpZxDgIzs4xzEJiZZZyDwMws4xwEZmYZ5yAwM8s4B4GZWcY5\nCMzMMu7/AUvO2bo5LYT3AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7c0ea58>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Run on a graph with 30 cities\n",
    "gen = SparseInstance(30, seed = 5)\n",
    "cities = gen.generateCities()\n",
    "tests = [0.11, 0.25, 0.375, 0.5, 0.625, 0.75, 0.89]\n",
    "data = [[] for k in range(len(tests))]\n",
    "for i in range(len(tests)):\n",
    "    colony = Colony(30, 'iterations', 10)\n",
    "    for k in range(3):\n",
    "        path, length = colony.ACS(cities, perception = tests[i])\n",
    "        data[i].append(length)\n",
    "    for datum in data[i]:\n",
    "        if datum > 99999:\n",
    "            dontplot = True\n",
    "    if dontplot:\n",
    "        continue\n",
    "    plt.scatter([tests[i] for k in range(3)], data[i])\n",
    "# plt.ylim([0, 1000])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It seems that ants with around a 25% chance to take the best path perform the best. The slides also mentioned that this value could be increased as the algorithm runs, to solidify those found paths."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "Although I do not optimize for the best Hamiltonian Cycle, My results are still useful. Small graphs can be optimized very well, and the optimal solution can be found in many cases. The algorithm has a runtime of around O(N^4) with a fairly large overhead during ant movements. The algorithm takes a significant amount of time to run for larger graphs, but the memory usage does not increase more than O(N^2) since I maintain a global copy of the graph to store pheremone values. This could be parallelized so that every 'ant' can run at the same time, and would be made easier by removing the local update constraint of ACS."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}