GA Algorithm Project .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  ❄️🌏🚗The 15 Winter Trips In The Northern Thailand \n",
    "## by Genetice Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Crossover\n",
    "In crossover phase, it implemented by Ordered Crossover (OX)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ox_crossover(parent_1, parent_2, N = 15):\n",
    "    start = randint(0, N-1)\n",
    "    end = randint(start, N-1)\n",
    "    if(end-start == N-1):\n",
    "        end = end - 1\n",
    "    subParent_1 = parent_1[start:end+1]\n",
    "    subParent_2 = parent_2[start:end+1]\n",
    "    child_1 = parent_1\n",
    "    child_2 = parent_2\n",
    "    parent_1 = [ x for x in parent_1 if x not in subParent_2]\n",
    "    parent_2 = [ x for x in parent_2 if x not in subParent_1]\n",
    "    if(end != N-1):\n",
    "        child_1[end+1:N] = parent_2[len(parent_2)-N+end+1:]\n",
    "        child_2[end+1:N] = parent_1[len(parent_1)-N+end+1:]\n",
    "    child_1[:start] = parent_2[:start]\n",
    "    child_2[:start] = parent_1[:start]\n",
    "    return [child_1, child_2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generate Chromosome\n",
    "This function required input n, number of bit in chromosome.\n",
    "And return a random chromosome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateChromosome(n):\n",
    "    x = list(range(n))\n",
    "    shuffle(x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generatePopulation(M=10, N=15):\n",
    "    # M is populationsize (default 10)\n",
    "    # N is length of chromosome (default 15)\n",
    "    populations = [] # parent\n",
    "    while len(populations) < M:\n",
    "        newChromosome = generateChromosome(N)\n",
    "        if newChromosome not in populations:\n",
    "            populations.append(newChromosome)\n",
    "    return populations\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculate Distance\n",
    "Calculate distance from dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculateDistance(distance, chromosome):\n",
    "    d = 0\n",
    "    for i in range(len(chromosome) -1):\n",
    "        d += distance[chromosome[i]][chromosome[i+1]]\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sorted_min_distance_chromosome(chromosomes):\n",
    "    length = len(chromosomes)\n",
    "    distance_each_chromosome = []\n",
    "    for n in range(length):\n",
    "        distance_each_chromosome.append((chromosomes[n],calculateDistance(data, chromosomes[n])))\n",
    "    sorted_distance = sorted(distance_each_chromosome, key=lambda tup: tup[1])\n",
    "#     selected_one = distance_each_chromosome.index(min_distance)\n",
    "    return sorted_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Genetic Algorithm\n",
    "The main algorithm to find optimize solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GA(data, N, pop_size, generation):\n",
    "    populations = generatePopulation(pop_size, N) # generate populations\n",
    "    populations = [ (x, calculateDistance(data, x)) for x in populations]\n",
    "    \n",
    "    bestChromosome = None\n",
    "\n",
    "    for gen in range(generations):\n",
    "        new_populations = []\n",
    "\n",
    "        populations = sorted(populations, key=lambda x: x[1])[:pop_size]\n",
    "        for i in range(0, len(populations)-1,2):\n",
    "            if bestChromosome == None or bestChromosome[1]>populations[i][1]:\n",
    "                bestChromosome = populations[i]\n",
    "#                 print(str(gen) + \") \" + str(bestChromosome))\n",
    "\n",
    "            chromosome1 = populations[i][0]\n",
    "            chromosome2 = populations[i+1][0]\n",
    "            child1, child2 = ox_crossover(chromosome1, chromosome2, N)\n",
    "            new_populations.append((child1, calculateDistance(data, child1)))\n",
    "            new_populations.append((child2, calculateDistance(data, child2)))\n",
    "\n",
    "        for i in range(len(populations))[::-1]:\n",
    "            del populations[i]\n",
    "\n",
    "        populations = new_populations\n",
    "\n",
    "    return bestChromosome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example Run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([7, 0, 10, 9, 4, 3, 6, 1, 5, 8, 2, 11], 2097)\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "from random import shuffle, randint\n",
    "\n",
    "data = [\n",
    "    [0,262,398,172,601,392,185,158,181,353,557,682,249,408,491], \n",
    "    [262,0,410,186,512,310,90,324,258,342,475,532,167,258,409], \n",
    "    [400,414,0,476,313,209,322,256,220,48,288,598,246,342,253], \n",
    "    [161,185,472,0,574,371,158,329,267,404,537,655,228,381,470],\n",
    "    [594,515,313,577,0,209,423,491,434,331,73,518,336,327,126],\n",
    "    [392,312,209,374,209,0,221,289,231,155,184,415,145,220,117],\n",
    "    [186,90,319,158,421,218,0,237,171,251,384,502,75,228,317],\n",
    "    [158,322,249,330,491,289,235,0,72,234,454,634,196,360,388],\n",
    "    [181,255,228,265,436,234,167,72,0,179,399,579,140,305,332],\n",
    "    [155,271,48,416,73,155,263,301,177,0,320,552,187,282,254],\n",
    "    [557,478,287,540,75,184,387,521,397,320,0,545,311,354,153],\n",
    "    [676,532,606,649,520,416,495,720,575,555,547,0,437,318,397],\n",
    "    [249,167,246,228,348,145,75,283,140,187,311,437,0,160,243],\n",
    "    [408,258,348,372,327,225,230,360,305,282,354,318,162,0,204],\n",
    "    [473,365,253,473,126,117,320,388,330,253,153,396,244,205,0] \n",
    "]\n",
    "max_N = 12\n",
    "pop_size = 10\n",
    "generations = 5000\n",
    "rounds = 5\n",
    "best = GA(data, 12, pop_size, generations)\n",
    "print(best)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### GA in Graph\n",
    "wait around 15 min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time: 860.65006s\n"
     ]
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "09bdb15c986942ddaf98a4623a517da2",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=300, description='population', max=500, min=100, step=200), IntSlider(va…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "<function __main__.f(population, generation)>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import matplotlib as npl\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual\n",
    "import ipywidgets as widgets\n",
    "data = [\n",
    "    [0,262,398,172,601,392,185,158,181,353,557,682,249,408,491], \n",
    "    [262,0,410,186,512,310,90,324,258,342,475,532,167,258,409], \n",
    "    [400,414,0,476,313,209,322,256,220,48,288,598,246,342,253], \n",
    "    [161,185,472,0,574,371,158,329,267,404,537,655,228,381,470],\n",
    "    [594,515,313,577,0,209,423,491,434,331,73,518,336,327,126],\n",
    "    [392,312,209,374,209,0,221,289,231,155,184,415,145,220,117],\n",
    "    [186,90,319,158,421,218,0,237,171,251,384,502,75,228,317],\n",
    "    [158,322,249,330,491,289,235,0,72,234,454,634,196,360,388],\n",
    "    [181,255,228,265,436,234,167,72,0,179,399,579,140,305,332],\n",
    "    [155,271,48,416,73,155,263,301,177,0,320,552,187,282,254],\n",
    "    [557,478,287,540,75,184,387,521,397,320,0,545,311,354,153],\n",
    "    [676,532,606,649,520,416,495,720,575,555,547,0,437,318,397],\n",
    "    [249,167,246,228,348,145,75,283,140,187,311,437,0,160,243],\n",
    "    [408,258,348,372,327,225,230,360,305,282,354,318,162,0,204],\n",
    "    [473,365,253,473,126,117,320,388,330,253,153,396,244,205,0] \n",
    "]\n",
    "max_N = 12\n",
    "pop_size_range = [100, 300, 500]\n",
    "generation_range = [1000, 3000, 5000]\n",
    "\n",
    "calculateData = {}\n",
    "start = time.time()\n",
    "for pop_size in pop_size_range:\n",
    "    calculateData[pop_size] = {}\n",
    "    for gen in generation_range:\n",
    "        result = []\n",
    "        for n in range(6, max_N+1):\n",
    "            best = GA(data, n, pop_size, gen)\n",
    "            result.append(best[1])\n",
    "        calculateData[pop_size][gen] = result\n",
    "end = time.time()\n",
    "# print(calculateData)\n",
    "print(\"time: %8.5fs\" % (end-start))\n",
    "\n",
    "def f(population, generation):\n",
    "    NRange = [6,7,8,9,10,11,12]\n",
    "    fig = plt.figure()\n",
    "    axes = fig.add_subplot(111)\n",
    "    bruteforce = [1163, 1177, 1234, 1285, 1197, 1245, 1660]\n",
    "    axes.plot(NRange, bruteforce, 'r')\n",
    "    axes.plot(NRange, calculateData[population][generation], 'b')\n",
    "        \n",
    "    plt.show()\n",
    "interact(f, population=(100,500,200), generation=(1000,5000,2000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using GA to solve 15! problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimize way is\n",
      "วัดศรีชุม จ.ลำปาง > ดอยผาตั้ง จ.เชียงราย > พิพิธภัณฑ์เมืองลับแล จ.อุตรดิตถ์ > ดอยอินทนนท์ จ.เชียงใหม่ > ดอยหัวหมด จ.ตาก > เขื่อนภูมิพล จ.ตาก > ดอยเสมอดาว จ.น่าน > เขาค้อ จ.เพชรบูรณ์ > วัดศรีรัตนมหาธาตุวรมหาวิหาร จ.พิษณุโลก > ภูทับเบิก จ.เพชรบูรณ์ > ปาย จ.เเม่ฮ่องสอน > กว๊านพะเยา จ.พะเยา > อุทยานแห่งชาติขุนสถาน จ.แพร่ > วัดพระธาตุหริภุญชัยวรมหาวิหาร จ.ลำพูน > ดอยอ่างขาง จ.เชียงใหม่\n",
      "Total Distance 2168.00km\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "from random import shuffle, randint, seed\n",
    "\n",
    "seed(0)\n",
    "\n",
    "data = [\n",
    "    [0,262,398,172,601,392,185,158,181,353,557,682,249,408,491], \n",
    "    [262,0,410,186,512,310,90,324,258,342,475,532,167,258,409], \n",
    "    [400,414,0,476,313,209,322,256,220,48,288,598,246,342,253], \n",
    "    [161,185,472,0,574,371,158,329,267,404,537,655,228,381,470],\n",
    "    [594,515,313,577,0,209,423,491,434,331,73,518,336,327,126],\n",
    "    [392,312,209,374,209,0,221,289,231,155,184,415,145,220,117],\n",
    "    [186,90,319,158,421,218,0,237,171,251,384,502,75,228,317],\n",
    "    [158,322,249,330,491,289,235,0,72,234,454,634,196,360,388],\n",
    "    [181,255,228,265,436,234,167,72,0,179,399,579,140,305,332],\n",
    "    [155,271,48,416,73,155,263,301,177,0,320,552,187,282,254],\n",
    "    [557,478,287,540,75,184,387,521,397,320,0,545,311,354,153],\n",
    "    [676,532,606,649,520,416,495,720,575,555,547,0,437,318,397],\n",
    "    [249,167,246,228,348,145,75,283,140,187,311,437,0,160,243],\n",
    "    [408,258,348,372,327,225,230,360,305,282,354,318,162,0,204],\n",
    "    [473,365,253,473,126,117,320,388,330,253,153,396,244,205,0] \n",
    "]\n",
    "\n",
    "dataName = [\n",
    "    \"ดอยอ่างขาง จ.เชียงใหม่\",\n",
    "    \"ดอยอินทนนท์ จ.เชียงใหม่\",\n",
    "    \"ดอยเสมอดาว จ.น่าน\",\n",
    "    \"ปาย จ.เเม่ฮ่องสอน\",\n",
    "    \"เขาค้อ จ.เพชรบูรณ์\",\n",
    "    \"พิพิธภัณฑ์เมืองลับแล จ.อุตรดิตถ์\",\n",
    "    \"วัดพระธาตุหริภุญชัยวรมหาวิหาร จ.ลำพูน\",\n",
    "    \"ดอยผาตั้ง จ.เชียงราย\",\n",
    "    \"กว๊านพะเยา จ.พะเยา\",\n",
    "    \"อุทยานแห่งชาติขุนสถาน จ.แพร่\",\n",
    "    \"ภูทับเบิก จ.เพชรบูรณ์\",\n",
    "    \"ดอยหัวหมด จ.ตาก\",\n",
    "    \"วัดศรีชุม จ.ลำปาง\",\n",
    "    \"เขื่อนภูมิพล จ.ตาก\",\n",
    "    \"วัดศรีรัตนมหาธาตุวรมหาวิหาร จ.พิษณุโลก\"\n",
    "]\n",
    "\n",
    "N = 15\n",
    "pop_size = 500\n",
    "generations = 5000\n",
    "path, distance = GA(data, N, pop_size, generations)\n",
    "pathName = ' > '.join([dataName[x] for x in path])\n",
    "print(\"Optimize way is\")\n",
    "print(pathName)\n",
    "print(\"Total Distance %.2fkm\" % distance)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}