traveling-salesman.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "233f7899-2f7d-471f-90f8-eaef3953a781",
   "metadata": {},
   "outputs": [],
   "source": [
    "using Evolutionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "79705dd8-8fb1-451b-b9a4-3a62be386bc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Vector{Vector{Float64}}:\n",
       " [0.0, 0.0]\n",
       " [2.0, 1.0]\n",
       " [3.0, 2.0]\n",
       " [4.0, 2.0]\n",
       " [5.0, 5.0]\n",
       " [1.0, 2.0]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "datapoints = [\n",
    "    [0.0, 0.0],\n",
    "    [2.0, 1.0],\n",
    "    [3.0, 2.0],\n",
    "    [4.0, 2.0],\n",
    "    [5.0, 5.0],\n",
    "    [1.0, 2.0]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5f617dc3-770c-48b0-a66d-a10f37208e64",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "euclidean (generic function with 1 method)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Euclidean distance function\n",
    "euclidean(u, v) = (u .- v) .|> (x -> x * x) |> sum |> sqrt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "8b6421cd-e387-4958-a1e4-ce9c9b5acecc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euclidean([1.0, 0.0], [0.0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0bdba3a6-2818-4d25-86e8-8f9ed5dca4b8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "cost (generic function with 1 method)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Cost function that receives an individual of permutation such like\n",
    "# [1, 5, 4, 3, 2, 6].\n",
    "# The function first calculates dist(1, 5), then dist(5, 4), then dist(4, 3),\n",
    "# then dist(3, 2), then dist(2, 6), and finaly (6, 1) just because the salesman\n",
    "# returns the starting point. \n",
    "function cost(s)\n",
    "    mycost = 0.0\n",
    "    for i = 1:(length(datapoints)-1)\n",
    "        mycost += euclidean(datapoints[s[i]], datapoints[s[i + 1]])\n",
    "    end\n",
    "    mycost += mycost + euclidean(datapoints[length(s)], datapoints[s[1]])\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "c12eff66-5c91-4a94-b61c-946c03b6803e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GA[P=100,x=0.8,μ=0.1,ɛ=0]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Configuation of GA with PMX crossover and swap2 mutation.\n",
    "myconf = Evolutionary.GA(populationSize = 100, crossover = Evolutionary.PMX, mutation = Evolutionary.swap2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c4f74937-08c2-4aae-afa4-e5b5a06ac955",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       " * Status: success\n",
       "\n",
       " * Candidate solution\n",
       "    Minimizer:  [6, 1, 2,  ...]\n",
       "    Minimum:    20.097254355082107\n",
       "    Iterations: 26\n",
       "\n",
       " * Found with\n",
       "    Algorithm: GA[P=100,x=0.8,μ=0.1,ɛ=0]\n",
       "\n",
       " * Convergence measures\n",
       "    |f(x) - f(x')| = 0.0 ≤ 1.0e-12\n",
       "\n",
       " * Work counters\n",
       "    Seconds run:   0.0053 (vs limit Inf)\n",
       "    Iterations:    26\n",
       "    f(x) calls:    2700\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Calculate\n",
    "result = Evolutionary.optimize(cost, [1,2,3,4,5,6], myconf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "d8625894-1c93-42ea-b9bc-61ceab872b69",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Vector{Int64}:\n",
       " 6\n",
       " 1\n",
       " 2\n",
       " 3\n",
       " 4\n",
       " 5"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result.minimizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a06fa907-adf4-476d-847d-6d466ee83a7f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.7.2",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}