Genetic_Algorithm_Traveling_Salesman.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Genetic Algorithm - Traveling Salesman.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "HqGUlxrxw0pN"
      },
      "source": [
        "import numpy as np\n",
        "import random\n",
        "import heapq"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hnl_KzJ5dPke"
      },
      "source": [
        "class Genetic():\n",
        "     def __init__(self, node, edge):         \n",
        "         self.population_size = int(np.math.factorial(len(node)) / len(node))\n",
        "\n",
        "         self.node = node\n",
        "         self.edge = edge\n",
        "         \n",
        "         self.population = self.generate_start_population()\n",
        "         self.calculate_fitness()\n",
        "\n",
        "     def generate_start_population(self):\n",
        "         return [np.random.permutation(self.node) for i in range(self.population_size)]         \n",
        "\n",
        "     def calculate_fitness(self) :\n",
        "         fitness = []\n",
        "         \n",
        "         for pop in self.population :\n",
        "             dist = 0\n",
        "             \n",
        "             for i in range(len(pop) - 1):\n",
        "                 path = \"\".join(pop[i: i+2])\n",
        "                 dist += self.edge[path]\n",
        "             \n",
        "             path = pop[len(pop)-1] + pop[0]   \n",
        "             dist += self.edge[path]\n",
        "             \n",
        "             fitness.append(dist)   \n",
        "         \n",
        "         return fitness\n",
        "\n",
        "     def Reproduction_population(self):\n",
        "        \n",
        "        new_population = []\n",
        "        fitness = self.calculate_fitness()\n",
        "\n",
        "        best_fitness = heapq.nsmallest(int(self.population_size/3), fitness)\n",
        "        index = [fitness.index(i) for i in best_fitness]\n",
        "        best_population = [self.population[i] for i in index]\n",
        "        \n",
        "        new_population.extend(best_population)\n",
        "        \n",
        "        while len(new_population) < self.population_size :\n",
        "            selected_individual = self.parent_selection(fitness)   \n",
        "            if random.random() > 0.8 : \n",
        "                new_child = self.mutation(selected_individual[0])\n",
        "            else : \n",
        "                new_child = self.cross_over(selected_individual)\n",
        "            new_population.append(new_child)\n",
        "\n",
        "        # print(\"new_population\", new_population)\n",
        "        self.population = new_population.copy()\n",
        "\n",
        "     def parent_selection(self, fitness):\n",
        "        selected_parent_size = 2\n",
        "        selected_parent = []\n",
        "        \n",
        "        for i in range(selected_parent_size) :\n",
        "            random_number  = [np.random.randint(0, self.population_size - 1) for i in range(selected_parent_size)]\n",
        "            selected = self.population[random_number[0]] if fitness[random_number[0]] < fitness[random_number[1]] else self.population[random_number[1]]\n",
        "            selected_parent.append(selected)\n",
        "        return selected_parent\n",
        "\n",
        "     def cross_over(self, parent) :\n",
        "        child = parent[0].copy()\n",
        "        index = np.random.randint(0, len(parent[0]) - 1, 2)\n",
        "\n",
        "        start = np.min(index)\n",
        "        end   = np.max(index)\n",
        "\n",
        "        prime = [item for item in parent[1] if item not in child[start : end + 1]]\n",
        "        prime_index = 0\n",
        "\n",
        "        for i in range(len(parent[0])):\n",
        "            if i < start  or i > end:\n",
        "                child[i] = prime[prime_index].copy()\n",
        "                prime_index += 1\n",
        "\n",
        "        return child\n",
        "\n",
        "     def mutation(self, parent) : \n",
        "        rand =  np.random.randint(0, len(parent) - 1, 2)\n",
        "        x = parent.copy()\n",
        "        x[rand[1]], x[rand[0]] = x[rand[0]], x[rand[1]]\n",
        "        return x\n",
        "                 "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RH18fq9iuI_h"
      },
      "source": [
        "def main():\n",
        "    node = [\"A\", \"B\", \"C\", \"D\"]\n",
        "    edge = {'AB': 30 ,'BA': 30, 'AC' :50 ,'CA': 50, 'AD': 40, 'DA': 40, 'BC': 30, 'CB': 30, 'BD': 35, 'DB':35, 'CD':25, 'DC': 25 }\n",
        "    \n",
        "    epoch = 5\n",
        "    g = Genetic(node, edge)\n",
        "    \n",
        "    for i in range(epoch):\n",
        "        g.Reproduction_population()\n",
        "\n",
        "    fitness = g.calculate_fitness()\n",
        "    index = np.argmin(fitness)\n",
        "    print(\"best path : \", \"\".join(g.population[index])+g.population[index][0] ,\" distance : \",  fitness[index])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g_Exzb_kwu9A",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "fbe1899a-c258-4761-e5ae-c362d48d029b"
      },
      "source": [
        "main()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "best path :  DABCD  distance :  125\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}