{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as mpimg\n",
    "import random\n",
    "import math\n",
    "\n",
    "class TSP():\n",
    "    cities = 0\n",
    "    distances = []\n",
    "    locations = []\n",
    "    \n",
    "    def distance(self, c1, c2):\n",
    "        loc1, loc2 = self.locations[c1], self.locations[c2]\n",
    "        return math.sqrt((loc1[0]-loc2[0])**2 + (loc1[1]-loc2[1])**2)\n",
    "    \n",
    "    def __init__(self, cities, seed=1):\n",
    "        random.seed(seed)\n",
    "        self.cities = cities\n",
    "        \n",
    "        self.locations = []\n",
    "        for i in range(cities):\n",
    "            self.locations.append((random.random(), random.random()))\n",
    "        \n",
    "        self.distances = []\n",
    "        for i in range(cities):\n",
    "            self.distances.append([])\n",
    "            for j in range(cities):\n",
    "                self.distances[i].append(self.distance(i, j))\n",
    "                \n",
    "    def random_solution(self):\n",
    "        s = [i for i in range(self.cities)]\n",
    "        random.shuffle(s)\n",
    "        return s\n",
    "    \n",
    "    def evaluate(self, s):\n",
    "        fit = 0\n",
    "        for i in range(len(s)):\n",
    "            fit += self.distances[s[i]][s[i+1 if i+1<len(s) else 0]]\n",
    "        return fit\n",
    "    \n",
    "    def mutate(self, s):\n",
    "        sol = s[:]\n",
    "        c1, c2 = random.sample(range(0, self.cities), 2)\n",
    "        if c2 < c1:\n",
    "            ctmp = c1\n",
    "            c1 = c2\n",
    "            c2 = ctmp\n",
    "        rev = sol[c1:c2+1]\n",
    "        rev.reverse()\n",
    "        sol[c1:c2+1] = rev\n",
    "        return sol\n",
    "    \n",
    "    def crossover(self, s1, s2):\n",
    "        sol1, sol2 = s1[:], s2[:]\n",
    "        c1, c2 = random.sample(range(0, self.cities), 2)\n",
    "        if c2 < c1:\n",
    "            ctmp = c1\n",
    "            c1 = c2\n",
    "            c2 = ctmp\n",
    "        sol1[c1:c2+1] = list(filter(lambda x: x in sol1[c1:c2+1], s2))\n",
    "        sol2[c1:c2+1] = list(filter(lambda x: x in sol2[c1:c2+1], s1))\n",
    "        \n",
    "        return sol1, sol2\n",
    "    \n",
    "    def display_solution_param(self, solution):\n",
    "        fig, ax = plt.subplots(figsize=(8, 8))\n",
    "\n",
    "        x = [i[1] for i in [self.locations[c] for c in solution]]\n",
    "        y = [i[0] for i in [self.locations[c] for c in solution]]\n",
    "        x.append(x[0])\n",
    "        y.append(y[0])\n",
    "        line, = ax.plot(x, y, 'go-',linewidth=2)\n",
    "            \n",
    "        plt.xlim((-0.03,1.03))\n",
    "        plt.ylim((-0.03,1.03))\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 1:** Implement the generational evolutionary algorithm with tournament selection. Let it be parametrized with four parameters: the size of the population $N$, the size of the tournament $t$, the probability of mutation $p_m$ and the probability of crossover $p_c$. The algorithm should terminate automatically after 50 generations with no improvement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2:**\n",
    "\n",
    "* What is the role of a mutation operator in evolutionary algorithms?\n",
    "* What are the properties of a good mutation operator?\n",
    "* What is the role of a crossover operator in evolutionary algorithms?\n",
    "* What are the properties of a good crossover operator?\n",
    "* What is the role of a cloning operator in evolutionary algorithms?\n",
    "* What are the properties of a good genetic representation?\n",
    "* How can you tell that the population has converged?\n",
    "* How do the parameters of the evolutionary algorithm affect the speed of its convergence?\n",
    "* Does the speed of the algorithm's convergence correlate with the quality of the solutions? What is the reason?\n",
    "* Can a population escape from a local optimum once it has converged?\n",
    "\n",
    "\n",
    "* What are the strengths of the evolutionary algorithms?\n",
    "* What are the weaknesses of the evolutionary algorithms?\n",
    "* What changes would you introduce to the evolutionary algorithms?\n",
    "* Which problems are evolutionary algorithms best suited for?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 3:** Implement the QAP (https://en.wikipedia.org/wiki/Quadratic_assignment_problem). Use EA to solve it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class QAP():\n",
    "    \n",
    "    def __init__(self, seed=1):\n",
    "        random.seed(seed)\n",
    "        #TODO\n",
    "                \n",
    "    def random_solution(self):\n",
    "        s = []\n",
    "        #TODO\n",
    "        \n",
    "        return s\n",
    "    \n",
    "    def evaluate(self, s):\n",
    "        fit = 0\n",
    "        #TODO\n",
    "        \n",
    "        return fit\n",
    "    \n",
    "    def mutate(self, s):\n",
    "        sol = s[:]\n",
    "        #TODO\n",
    "        \n",
    "        return sol\n",
    "    \n",
    "    def crossover(self, s1, s2):\n",
    "        sol1, sol2 = s1[:], s2[:]\n",
    "        #TODO\n",
    "        \n",
    "        return sol1, sol2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 4:** Choose one of the problems (TSP or QAP). Assume a constant number of fitness evaluations per each evolutionary run. For a sufficiently big (nontrivial) problem:\n",
    "\n",
    "a) Assume $N = 200$, $t = 5$. Prepare a heatmap illustrating the influence of values of $p_m$ and $p_c$ on the quality of the solution.\n",
    "\n",
    "b) Assume $p_m = 0.5$, $p_c = 0.5$. Prepare a heatmap illustrating the influence of values of $N$ and $t$ on the quality of the solution.\n",
    "\n",
    "Discuss the results. Can we expect to see similar results under different search termination conditions (e.g. a number of iterations with no improvement)? Can we expect to see similar results for different optimization problems?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}