TSP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "hidden-baghdad",
   "metadata": {},
   "source": [
    "# Traveling Salesman Problem - Genetski Algoritam\n",
    "\n",
    "## Šta je TSP (Traveling Salesman Problem)?\n",
    "\n",
    "Zadatak TSP-a je da jedan putujući trgovac prođe kroz svaki grad unutar regiona i da prođe najkraćim putem a da\n",
    "ne svrati u isti grad dva puta.\n",
    "Glavni problem TSP-a što ga čini veoma popularnim je pri većim količinama gradova kompleksnost TSP-a se značajno\n",
    "povećava.\n",
    "\n",
    "## Šta su genetski algoritmi?\n",
    "\n",
    "Genetski algoritam predstavlja rešavanje jednog problema pomoću teorije evolucije.\n",
    "\n",
    "### Inicijalizacija\n",
    "\n",
    "Genetski algoritmi rade tako što se uzima određeni broj jedinki koji predstavljaju neko _validno_ rešenje koje\n",
    "ne mora biti optimalno, pa se svakoj jedinki meri \"fitness\" pomoću heurističke funkcije. Heurističa funkcija\n",
    "i \"fitness\" predstavljaju koliko je optimalno rešenje.\n",
    "\n",
    "### Selekcija i rekombinacija\n",
    "\n",
    "Zatim se od izmerenih \"fitness\" vrednosti generiše selekcija roditelja koji će napraviti sledeću populaciju.\n",
    "kada se odrede roditelji geni im se ukrštaju i stvara se potomak sa novim genima i \"fitness\"-om.\n",
    "Proces se završava kada se napravi nova generacija sa istim brojem populacije.\n",
    "\n",
    "### Elitizam\n",
    "\n",
    "Postoji šansa da je nova generacija gora od prošle, u tom slučaju možemo da primenimo elitizam i da osiguramo da barem\n",
    "jedna najbolja jedinka iz prethodne generacije ostane.\n",
    "\n",
    "### Mutacija\n",
    "Pošto će populacija krenuti da se poboljšava u određenom pravcu postoji šansa da se dostigne lokalni maksimum što se tiče\n",
    "\"fitness\"-a gde ni jedan pravac ne poboljšava jedinke iako postoji optimalnije rešenje. Zbog ovoga se uvodi mala šansa\n",
    "mutacije među jedinki da ih izbaci iz mogućeg \"ćoška\".\n",
    "\n",
    "![lokalni maksimum](./images/lokalni_maksimum.png)\n",
    "\n",
    "Zatime se opet vrše svi ciklusi iznova onoliko generacija koliko mislimo da je dovoljno. Što više generacija, to duže će trebati da se izračuna ali se dobijaju bolji rezultati.\n",
    "\n",
    "# Rešavanje TSP-a uz pomoć genetskog algoritma\n",
    "\n",
    "## Julia\n",
    "\n",
    "Algoritam je napisan u Julia jeziku. Jezik je mešavina raznih drugih programskih jezika kao što su Python, Matlab, R, i uzima neke koncepte od funkcionalnih jezika kao što su Haskell.\n",
    "\n",
    "Julia se koristi najviše u matematičke i statističke svrhe pa je zato savršen jezik za rešavanje ovog problema.\n",
    "\n",
    "## Predstavljanje podataka\n",
    "\n",
    "Prvo je bitno kako đemo predstavljati podatke u rešenju. Najbitnije su sledeće strukture"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "joined-privacy",
   "metadata": {},
   "outputs": [],
   "source": [
    "struct Node\n",
    "    x::Int\n",
    "    y::Int\n",
    "end\n",
    "\n",
    "struct Individual\n",
    "    genome::Vector{Node}\n",
    "    fitness::Float64\n",
    "    distance::Float64\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "further-russia",
   "metadata": {},
   "source": [
    "`Node` predstavlja jednu koordinatu grada a `Individual` predstalja jedinku unutar populacije.\n",
    "Unutar `Individual` strukture `genome` predstavlja moguće rešenje u vidu neponavljajućeg niza gradova\n",
    "`fitness` predstavlja vrednost ili \"jačinu\" te jedinke (u ovom slučaju se računa kao 1/`distance`) a `distance`\n",
    "predstavlja ukupno pređenu dužinu.\n",
    "\n",
    "Zatim imamo neke korisne funkcije koje implementiramo da bih smo mogli koristiti neke specijalizovane funkcije"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "internal-montana",
   "metadata": {},
   "outputs": [],
   "source": [
    "import Base\n",
    "\n",
    "# Return the maximum of the two individuals\n",
    "Base.max(g1::Individual, g2::Individual)::Individual = g1.fitness > g2.fitness ? g1 : g2\n",
    "\n",
    "# Return true if the first individual is less than the second\n",
    "Base.isless(g1::Individual, g2::Individual)::Bool = g1.fitness < g2.fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "republican-stroke",
   "metadata": {},
   "source": [
    "I usput dodajemo neke korisne funkcije za računanje razdaljine između dva grada i ukupnu dužinu putanje"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "worthy-manitoba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "distancetotal (generic function with 1 method)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Returns the distance between nodes\n",
    "distancebetween(n1::Node, n2::Node)::Float64 =\n",
    "    sqrt(abs(n1.x - n2.x)^2 + abs(n1.y - n2.y)^2)\n",
    "\n",
    "# Returns the total distance of a path\n",
    "# SUM n1 -> n2 -> n3 -> ... -> nn\n",
    "function distancetotal(genomes::Vector{Node})::Float64\n",
    "    prev_node = genomes[1]\n",
    "    distance = 0\n",
    "    for i = 2:length(genomes)\n",
    "        curr_node = genomes[i]\n",
    "        distance += distancebetween(prev_node, curr_node)\n",
    "        prev_node = curr_node\n",
    "    end\n",
    "\n",
    "    return distance\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "gross-invitation",
   "metadata": {},
   "source": [
    "## Fitness\n",
    "\n",
    "Kod računanja fitness-a uzimamo 1 / vrednost ukupne dužine putanje. Što je duža putanja to je manji fitness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "promotional-proposal",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fitness (generic function with 1 method)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fitness(genomes::Vector{Node})::Float64 =\n",
    "    1 / distancetotal(genomes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "turkish-slovakia",
   "metadata": {},
   "source": [
    "Sada možemo napraviti funkciju koja generiše jedinke"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "terminal-trail",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "makeindividual (generic function with 1 method)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Random\n",
    "\n",
    "# Generate a random valid solution by shuffling the nodes\n",
    "# then create an individual\n",
    "# Can you afford to be one though?\n",
    "function makeindividual(nodes::Vector{Node})::Individual\n",
    "    genomes = shuffle(nodes)\n",
    "    fit = fitness(genomes)\n",
    "    dist = distancetotal(genomes)\n",
    "\n",
    "    return Individual(genomes, fit, dist)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "comic-convert",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i1: Individual(Node[Node(1, 1), Node(5, 5), Node(3, 3), Node(2, 2), Node(4, 4)], 0.07856742013183861, 12.727922061357857)\n",
      "i2: Individual(Node[Node(4, 4), Node(2, 2), Node(5, 5), Node(1, 1), Node(3, 3)], 0.0642824346533225, 15.556349186104045)\n",
      "Is i1 less than i2? false\n"
     ]
    }
   ],
   "source": [
    "cities = [Node(1, 1), Node(2, 2), Node(3, 3), Node(4, 4), Node(5, 5)];\n",
    "\n",
    "i1 = makeindividual(cities)\n",
    "i2 = makeindividual(cities)\n",
    "\n",
    "println(\"i1: \", i1)\n",
    "println(\"i2: \", i2)\n",
    "\n",
    "println(\"Is i1 less than i2? \", isless(i1, i2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "human-verse",
   "metadata": {},
   "source": [
    "## Mutacija\n",
    "\n",
    "Da bi smo izvršili mutaciju jedne jedinke možemo jednostavno zameniti pozicije da grada u nizu i rezultat će još\n",
    "biti validan\n",
    "\n",
    "<img src=\"./images/mutacija.png\" width=\"300\" />\n",
    "\n",
    "Što se tiče koda, prolazimo kroz sve gradove u nizu i testiramo da li je neki nasumičan broj manji od zadatog praga\n",
    "mutacije, ako jeste uzimamo neku drugu nasumičnu poziciju i menjamo mesta tim gradovima.\n",
    "\n",
    "> **Napomena**: ovim načinom postoji šansa da se zamene više od dva grada u jednoj mutaciji ali je veoma mala i izbalancira se\n",
    "sa šansom da se zameni isti grad sa sobom tako da se ne desi mutacija."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "contemporary-maximum",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mutate (generic function with 1 method)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function mutate(individual::Individual, mutation_rate::Float64)::Individual\n",
    "    gen = copy(individual.genome)\n",
    "    for i in 1:length(gen)\n",
    "        if rand(Float64) < mutation_rate\n",
    "            pos2 = rand(1:length(gen))\n",
    "            \n",
    "            tmp = gen[i]\n",
    "            gen[i] = gen[pos2]\n",
    "            gen[pos2] = tmp\n",
    "        end\n",
    "    end\n",
    "\n",
    "    dist = distancetotal(gen)\n",
    "    fit = fitness(gen)\n",
    "\n",
    "    return Individual(gen, fit, dist)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "answering-southeast",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before mutation: Individual(Node[Node(1, 1), Node(5, 5), Node(3, 3), Node(2, 2), Node(4, 4)], 0.07856742013183861, 12.727922061357857)\n",
      "After mutation: Individual(Node[Node(1, 1), Node(5, 5), Node(3, 3), Node(2, 2), Node(4, 4)], 0.07856742013183861, 12.727922061357857)\n"
     ]
    }
   ],
   "source": [
    "println(\"Before mutation: \", i1)\n",
    "println(\"After mutation: \", mutate(i1, 0.05))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "amber-weight",
   "metadata": {},
   "source": [
    "## Rekombinacija\n",
    "\n",
    "Kod rekombinacije postupak je malo komplikovaniji i predstavlja jedan \"teži\" deo koda.\n",
    "\n",
    "Prvi deo je da uzmemo jedan \"isečak\" putanje iz prvog roditelja i postavljamo ga u istu poziciju kod deteta:\n",
    "\n",
    "<img src=\"./images/rekombinacija1.png\" width=300 />\n",
    "\n",
    "Drugi korak je gde prolazimo kroz sve gradove redom iz drugog roditelja i kopiramo one koji već ne postoje nad toj poziciji\n",
    "u dete, vodeći računa u kom redosledu ih postavljamo:\n",
    "\n",
    "<img src=\"./images/rekombinacija2.png\" width=300 />\n",
    "\n",
    "Kod radi na sličnom principu tako što uzima jedan opseg kod prvog roditelja, zatim prolazi kroz drugog roditelja i\n",
    "postavlja gradove u slobodne pozicije kod deteta onim redosledom kojim se pojavljuju ako ne postoje već u\n",
    "prvom roditelju, tako osiguravamo da je rezultat još uvek validan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "incident-underground",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "crossover (generic function with 1 method)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function crossover(individual1::Individual, individual2::Individual)::Individual\n",
    "    # find a \"window\" to take from the first parent\n",
    "    (pos1, pos2) = minmax(rand(1:length(individual1.genome)), rand(1:length(individual1.genome)))\n",
    "\n",
    "    # Save the segment we want to transfer to the child\n",
    "    seqm = individual1.genome[pos1:pos2]\n",
    "    \n",
    "    gen = Array{Node}(undef, length(individual2.genome)) \n",
    "\n",
    "    j = 1\n",
    "    # Go through every node in the second parent and add it to the\n",
    "    # child in order of appearence if it doesn't exist in the first\n",
    "    # parents selected genes\n",
    "    for i = 1:length(individual2.genome)\n",
    "        if !(individual2.genome[i] in seqm)\n",
    "            # goes through the child until it finds a free position\n",
    "            while j <= length(gen)\n",
    "                if (j in pos1:pos2)\n",
    "                    j += 1\n",
    "                else\n",
    "                    gen[j] = individual2.genome[i]\n",
    "                    j += 1\n",
    "                    break\n",
    "                end\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "\n",
    "    # actually apply the first parents genes and create the child\n",
    "    gen[pos1:pos2] = seqm\n",
    "    fit = fitness(gen)\n",
    "    dist = distancetotal(gen)\n",
    "\n",
    "    return Individual(gen, fit, dist)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "heard-angola",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parent 1: Individual(Node[Node(1, 1), Node(5, 5), Node(3, 3), Node(2, 2), Node(4, 4)], 0.07856742013183861, 12.727922061357857)\n",
      "Parent 2: Individual(Node[Node(4, 4), Node(2, 2), Node(5, 5), Node(1, 1), Node(3, 3)], 0.0642824346533225, 15.556349186104045)\n",
      "Crossover: Individual(Node[Node(4, 4), Node(5, 5), Node(3, 3), Node(2, 2), Node(1, 1)], 0.1414213562373095, 7.0710678118654755)\n"
     ]
    }
   ],
   "source": [
    "println(\"Parent 1: \", i1)\n",
    "println(\"Parent 2: \", i2)\n",
    "println(\"Crossover: \", crossover(i1, i2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "conservative-register",
   "metadata": {},
   "source": [
    "## Selekcija\n",
    "\n",
    "Jedan od najvažnijih koraka je selekcija jedinki za pravljenje nove populacije. Sistem selekcije predstavlja jednu _lutriju_\n",
    "gde svakoj jedinki dodeljuje jedan deo na \"pikado\" tabli, veličina dela zavisi od jačine te jedinke u odnosu na ukupnu\n",
    "jačinu populacije: Npr ako imamo 4 jedinki:\n",
    "\n",
    "| Jedinka | Fitness | Procenat kontribucije |\n",
    "|:--------|---------|----------------------:|\n",
    "| 1       | 0.5     | 50%                   |\n",
    "| 2       | 0.25    | 25%                   |\n",
    "| 3       | 0.125   | 12.5%                 |\n",
    "| 4       | 0.125   | 12.5%                 |\n",
    "\n",
    "Možemo napraviti sledeću \"pikado\" tabelu:\n",
    "\n",
    "<img src=\"./images/pikado.png\" width=300 />\n",
    "\n",
    "Posle generisanja tabele možemo uzeti jedno roditelja tako što nasumično bacamo \"strelu\" u tabelu i uzimamo jedinku koju\n",
    "pogodimo.\n",
    "\n",
    "Ovu lutriju u kodu predstavljamo tako što dodeljujemo svakoj jedinki opseg pozicije od 1 do 1000 (npr. jedinka 1 ima opseg\n",
    "1:500, jedinka dva ima opseg 501:750, itd.) zatim generišemo nasumičan broj od 1 do 1000 i gledamo koja jedinka ima taj\n",
    "opseg:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "smooth-mineral",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "selectparent (generic function with 1 method)"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function selectparent(population::Vector{Individual})::Individual\n",
    "    # sum all of the fitnesses together\n",
    "    totalfitness = reduce((x, y) -> x + y.fitness, population; init=0.0)\n",
    "    lottery = []\n",
    "    maxpoints = 1000\n",
    "    minpoints = 1\n",
    "\n",
    "    # genrate a range for every individual for the lottery\n",
    "    for ind in population\n",
    "        chance = ind.fitness / totalfitness\n",
    "        points = Int(round(maxpoints * chance)) + minpoints\n",
    "        push!(lottery, minpoints:points)\n",
    "\n",
    "        minpoints = points\n",
    "    end\n",
    "\n",
    "    # the winning number\n",
    "    randselection = rand(1:maxpoints)\n",
    "\n",
    "    # find the selected parent\n",
    "    for (i, value) in enumerate(lottery)\n",
    "        if randselection in value\n",
    "            return population[i]\n",
    "        end\n",
    "    end\n",
    "\n",
    "    return population[rand(1:length(population))]\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "optional-saudi",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8-element Array{Individual,1}:\n",
       " Individual(Node[Node(4, 4), Node(3, 3), Node(5, 5), Node(1, 1), Node(2, 2)], 0.08838834764831842, 11.313708498984763)\n",
       " Individual(Node[Node(1, 1), Node(4, 4), Node(3, 3), Node(5, 5), Node(2, 2)], 0.07856742013183861, 12.727922061357855)\n",
       " Individual(Node[Node(4, 4), Node(3, 3), Node(1, 1), Node(2, 2), Node(5, 5)], 0.10101525445522107, 9.899494936611665)\n",
       " Individual(Node[Node(5, 5), Node(4, 4), Node(2, 2), Node(1, 1), Node(3, 3)], 0.1178511301977579, 8.485281374238571)\n",
       " Individual(Node[Node(2, 2), Node(4, 4), Node(5, 5), Node(1, 1), Node(3, 3)], 0.07856742013183861, 12.727922061357857)\n",
       " Individual(Node[Node(5, 5), Node(4, 4), Node(3, 3), Node(1, 1), Node(2, 2)], 0.1414213562373095, 7.0710678118654755)\n",
       " Individual(Node[Node(4, 4), Node(1, 1), Node(2, 2), Node(5, 5), Node(3, 3)], 0.07856742013183862, 12.727922061357853)\n",
       " Individual(Node[Node(3, 3), Node(4, 4), Node(2, 2), Node(1, 1), Node(5, 5)], 0.08838834764831843, 11.313708498984761)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parent 1: Individual(Node[Node(4, 4), Node(1, 1), Node(2, 2), Node(5, 5), Node(3, 3)], 0.07856742013183862, 12.727922061357853)\n",
      "Parent 2: Individual(Node[Node(5, 5), Node(4, 4), Node(3, 3), Node(1, 1), Node(2, 2)], 0.1414213562373095, 7.0710678118654755)\n"
     ]
    }
   ],
   "source": [
    "population = collect((makeindividual(cities) for _ in 1:8))\n",
    "\n",
    "display(population)\n",
    "\n",
    "parent1 = selectparent(population)\n",
    "parent2 = selectparent(population)\n",
    "\n",
    "println(\"Parent 1: \", parent1)\n",
    "println(\"Parent 2: \", parent2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exceptional-retailer",
   "metadata": {},
   "source": [
    "## Sve zajedno\n",
    "\n",
    "Sledeće je da se svi ovi koraci redosledno primene: `selekcija -> rekombinacija -> mutacija`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "executive-amsterdam",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "runcycle (generic function with 1 method)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function runcycle(population::Vector{Individual}; elitism=false, mutationrate=0.05)::Vector{Individual}\n",
    "    popcount = length(population)\n",
    "    newpop = []\n",
    "\n",
    "    if elitism\n",
    "        push!(newpop, maximum(population))\n",
    "        popcount -= 1\n",
    "    end\n",
    "\n",
    "    while popcount != 0\n",
    "        p1 = selectparent(population)\n",
    "        p2 = selectparent(population)\n",
    "\n",
    "        while p1 == p2\n",
    "            p2 = selectparent(population)\n",
    "        end\n",
    "\n",
    "        child = crossover(p1, p2)\n",
    "        push!(newpop, child)\n",
    "        popcount -= 1\n",
    "    end\n",
    "\n",
    "    map(x -> mutate(x, mutationrate), newpop)\n",
    "\n",
    "    return newpop\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "appropriate-andrews",
   "metadata": {},
   "source": [
    "> ### Elitizam\n",
    "> Postoji šansa da jedinke nove generacije bude gore od najgore jedinke iz prethodne, tako da imamo i opciju za elitizam.\n",
    "> Kada je elitizam aktivan čuva se najjača jedinka iz prethodne generacije.\n",
    "\n",
    "Sada možemo da narpavimo jednostavnu funkciju koja će simulirati određeni broj generacija i vratiti najoptimalnije rešenje"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "colored-indonesian",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "evolve (generic function with 1 method)"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function evolve(\n",
    "    nodes::Vector{Node};\n",
    "    indcount=8,\n",
    "    iterations=1000,\n",
    "    elitism=false,\n",
    "    mutationrate=0.01)::Individual\n",
    "    \n",
    "    if indcount < 2\n",
    "        throw(DomainError(indcount, \"the number of individuals must be 2 or more\"))\n",
    "    end\n",
    "\n",
    "    initpop::Vector{Individual} = []\n",
    "    for _ = 1:indcount\n",
    "        push!(initpop, makeindividual(nodes))\n",
    "    end\n",
    "\n",
    "    pop = initpop\n",
    "\n",
    "    for _ = 1:iterations\n",
    "        pop = runcycle(pop; elitism, mutationrate)\n",
    "    end\n",
    "\n",
    "    return maximum(pop)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "amended-warren",
   "metadata": {},
   "source": [
    "# Krajnji rezultat\n",
    "\n",
    "Sada možemo da nađemo potecijalno najkraći put kroz koji trgovac mora da prođe. Testiraćemo sa manjim brojem ciklusa, većim,\n",
    "elitizmom, bez elitizma.\n",
    "\n",
    "Početni podaci:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "genuine-victoria",
   "metadata": {},
   "outputs": [],
   "source": [
    "cities = [\n",
    "    Node(1, 1),\n",
    "    Node(1, 10),\n",
    "    Node(5, 6),\n",
    "    Node(8, 11),\n",
    "    Node(4, 3),\n",
    "    Node(2, 9),\n",
    "    Node(5, 12)\n",
    "];"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parliamentary-invasion",
   "metadata": {},
   "source": [
    "## Bez elitizma, malo iteracija"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "secret-generator",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Individual(Node[Node(5, 12), Node(8, 11), Node(1, 1), Node(4, 3), Node(5, 6), Node(1, 10), Node(2, 9)], 0.03423751175455418, 29.207730023399925)"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evolve(\n",
    "    cities;\n",
    "    indcount = 8,\n",
    "    iterations = 600,\n",
    "    elitism = false\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "integral-short",
   "metadata": {},
   "source": [
    "## Sa elitizmom, malo iteracija"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "returning-military",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Individual(Node[Node(5, 12), Node(1, 10), Node(2, 9), Node(8, 11), Node(5, 6), Node(4, 3), Node(1, 1)], 0.04030683876347041, 24.8096856681871)"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evolve(\n",
    "    cities;\n",
    "    indcount = 8,\n",
    "    iterations = 600,\n",
    "    elitism = true\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "desirable-negative",
   "metadata": {},
   "source": [
    "## Mnogo iteracija, bez elitizma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "golden-canadian",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Individual(Node[Node(1, 1), Node(4, 3), Node(2, 9), Node(1, 10), Node(5, 12), Node(8, 11), Node(5, 6)], 0.04030683876347041, 24.8096856681871)"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evolve(\n",
    "    cities;\n",
    "    indcount = 8,\n",
    "    iterations = 10000,\n",
    "    elitism = false\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spectacular-nelson",
   "metadata": {},
   "source": [
    "## Mnogo iteracija, sa elitizmom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "economic-plate",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Individual(Node[Node(1, 1), Node(4, 3), Node(5, 6), Node(1, 10), Node(2, 9), Node(5, 12), Node(8, 11)], 0.047072524192957196, 21.243815094785507)"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evolve(\n",
    "    cities;\n",
    "    indcount = 8,\n",
    "    iterations = 10000,\n",
    "    elitism = true\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "parental-sharp",
   "metadata": {},
   "source": [
    "## Rezultati\n",
    "\n",
    "Rezultati će naravno varirati od izvršavanja do izvršavanja pa će nekada biti bliže optimalnom rešenju nekada dalje jer\n",
    "algoritam zavisi od nasumičnosti. Ali možemo videti sa jednostavnijim primerom da najverovatnije će naći optimalno\n",
    "rešenje:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "broke-transaction",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Individual(Node[Node(1, 0), Node(2, 0), Node(3, 0), Node(4, 0), Node(5, 0)], 0.25, 4.0)"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cities_easy = [\n",
    "    Node(1, 0),\n",
    "    Node(2, 0),\n",
    "    Node(5, 0),\n",
    "    Node(4, 0),\n",
    "    Node(3, 0)\n",
    "];\n",
    "\n",
    "evolve(\n",
    "    cities_easy,\n",
    "    indcount = 8,\n",
    "    iterations = 10000,\n",
    "    elitism = true\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "behind-recording",
   "metadata": {},
   "source": [
    "Kao što vidimo rezultat će biti 1 -> 2 -> 3 -> 4 -> 5 (ili obrnuto), sem ako smo neopisivo nerećni (ili srećni u zavisnosti\n",
    "kako gledamo), tako da znamo da algoritam radi."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.2",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}