Evolutionary Search - Part 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Evolutionary Algorithms (Part 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The general scheme of an evolutionary algorithm is as follows:\n",
    "- We need to decide on some (genetic) _encoding_ for our search problem\n",
    "- The algorithm acts on a _population_ of individuals, initially usually generated randomly\n",
    "- From that population a strategy of _parent selection_ decides which individuals may reproduce\n",
    "- Selection is usually influenced by the _fitness_ of individuals\n",
    "- _Recombination operators_ describe how parents are recombined, thereby merging genetic material from multiple parents\n",
    "- As part of recombination, _mutation_ on the offspring may occur\n",
    "- Which of the parents and offspring represent the next generation is determined by a _survivor selection_ strategy\n",
    "- There needs to be some criterion to decide on _termination_ of the algorithm (e.g., fixed time or number of fitness evaluations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Historically, there are different branches of evolutionary computation, and the different flavours of evolutionary algorithms have been associated with different data types to represent solutions. For example, _Genetic Algorithms_ are traditionally associated with binary strings, while _Evolution Strategies_ were mainly concerned with real-valued vectors. These differences are largely irrelevant for our purposes. An overall strategy to derive a suitable evolutionary algorithm or a problem at hand is to:\n",
    "1. Choose a representation that suits the problem at hand\n",
    "2. Choose variation operators based on that representation\n",
    "3. Choose selection operators, which are independent of representation\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will start by considering the one-max problem again, where a solution is a vector of length _n_, consisting of binary numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In terms of _genetic encoding_, a _chromosome_ would in this case be the list, each number in the list is a _gene_, and the alleles would be the actual values _0_ and _1_. This _bitstring_ representation also happens to be the classical representation often used for Genetic Algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_random_solution():\n",
    "    return random.choices([0,1], k=n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Like all metaheuristics, evolutionary algorithms are guided by a fitness function -- in the case of evolutionary algorithms these mainly inform the selection operators about the fitness of candidate individuals. The fitness function is independent of the metaheuristic search algorithm, but specific to the problem we are attempting to solve, so it is the same fitness function we used for local search algorithms when solving the one max problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(solution):\n",
    "    return sum(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Evolution Strategies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Evolution Strategies were developed in the 1960s and 1970s by Ingo Rechenberg and Hans-Paul Schwefel. We will start considering canonical evolution strategies which mainly use selection and mutation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "- Ingo Rechenberg (1971): Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Frommann-Holzboog (1973).\n",
    "- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Classical evolution strategies were applied to real-valued vectors, where mutation was performed by adding a normally distributed random vector. In our one max example, however, we are optimising a bitvector and not a vector of real numbers. We can define a basic mutation as randomly flipping bits in a chromosome (as is the standard way to mutate bitstrings). An important question here is how many bits to flip in a vector: If the changes are too small, this inhibits the exploration aspect of the algorithm; if the changes are too large, this may inhibit exploitation. A common approach is therefore to make a probabilistic number of changes depending on the length of chromosomes used. Given a vector of length _n_, each element is changed with probability _1/n_. On average, one element will thus be changed. However, it may also happen that more or fewer elements are changed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def mutate(individual):\n",
    "    P_mutate = 1/len(individual)\n",
    "    copy = individual[:]\n",
    "    for position in range(len(individual)):\n",
    "        if random.random() < P_mutate:\n",
    "            copy[position] = 1 - copy[position]\n",
    "    return copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "mutate([0,0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need to set some parameters again; first, we'll store the best solution found along the search in the list `fitness_values` again, and we will use the number of fitness evaluations as the stopping condition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "max_steps = 1000\n",
    "fitness_values = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To start with, we consider the simplest possible evolution strategy which operates on a population of size two: the current point (parent) and the result of its mutation (offspring). The parent selection is therefore easy -- there is only one parent. Survivor selection chooses the mutant as the next parent if its fitness is at least as good as the parent's fitness, otherwise the parent survives and the mutant is disregarded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def oneplusone():\n",
    "    current = get_random_solution()\n",
    "    fitness = get_fitness(current)\n",
    "    fitness_values.append(fitness)\n",
    "    iteration = 1\n",
    "\n",
    "    while iteration < max_steps:\n",
    "        iteration += 1\n",
    "        candidate = mutate(current)\n",
    "        candidate_fitness = get_fitness(candidate)\n",
    "        if candidate_fitness >= fitness:\n",
    "            current = candidate\n",
    "            fitness = candidate_fitness\n",
    "        fitness_values.append(fitness)\n",
    "\n",
    "    return current"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As `current` always refers to an individual with the best fitness value encountered so far, we can simply return that and do not need to store a copy of the best individual encountered so far."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "oneplusone()\n",
    "opo_values = fitness_values[:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To see the progress of the evolution, we can plot the fitness values again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(opo_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The fitness plot is probably slightly less steep than the one we saw for the hillclimber in the last chapter, or at least somewhat more edged. However, this particular evolutionary algorithm is actually a variant of hillclimbing: It is a _randomised_ (or _stochastic_) hillclimber, where the exploration operator chooses random neighbours. As the mutation operator may change more than one bit, however, we may also be making larger jumps in the search space, rather than just considering immediate neighbours."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The name \"one plus one\" summarises three different parameters of this evolution strategy. First, the number of offspring may differ from the number of parents. In evolution strategies, the _lambda_ parameter typically denotes how many offspring each parent produces. This generalises the (1+1)-ES to a (1+λ)-ES, where the parent produces λ offspring. The survivor selection then considers the parent as well as all mutants, and picks the best of these as the new parent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lmbda = 9\n",
    "def onepluslambda():\n",
    "    current = get_random_solution()\n",
    "    best_fitness = get_fitness(current)\n",
    "    steps = 1\n",
    "    fitness_values.append(best_fitness)\n",
    "    while steps < max_steps:\n",
    "        candidates = [mutate(current) for _ in range(lmbda)]\n",
    "        candidates.append(current)\n",
    "        steps += lmbda\n",
    "\n",
    "        current = max(candidates, key = lambda x: get_fitness(x))\n",
    "        fitness = get_fitness(current)\n",
    "        if fitness > best_fitness:\n",
    "            best_fitness = fitness\n",
    "            \n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "onepluslambda()\n",
    "opl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Increasing λ leads to more exploration of the local neighbourhood of the current solution; intuitively, the effects will be similar like switching between steepest ascent and first ascent hillclimbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The second parameter is the selection strategy, which in the `onepluslambda` strategy is encoded in the name, `plus`, as it considers the parent _plus_ the offspring during selection. An alternative selection is _comma_-selection, where survivors are only selected from the offspring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def onecommalambda():\n",
    "    current = get_random_solution()\n",
    "    fitness = get_fitness(current)\n",
    "    best = current[:]\n",
    "    best_fitness = fitness\n",
    "    fitness_values.append(best_fitness)\n",
    "    steps = 1\n",
    "    while steps < max_steps:\n",
    "        candidates = [mutate(current) for _ in range(lmbda)]\n",
    "        steps += lmbda\n",
    "\n",
    "        current = max(candidates, key = lambda x: get_fitness(x))\n",
    "        fitness = get_fitness(current)        \n",
    "        if fitness > best_fitness:\n",
    "            best_fitness = fitness\n",
    "            best = current\n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "onecommalambda()\n",
    "ocl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will next generalise our `one-` strategies to larger populations than just one, which represents the third parameter encoded in the name. In evolution strategies, the population size is typically denoted as μ, and we can easily generalise our (1+λ)-ES to a (μ+λ)-ES, where the μ parents produce a total of λ offspring, and then survivor selection considers all parents together with (_plus_) all their offspring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "mu = 3\n",
    "def mupluslambda():\n",
    "    population = [get_random_solution() for _ in range(mu)]\n",
    "    best = max(population, key = lambda x: get_fitness(x))\n",
    "    best_fitness = get_fitness(best)\n",
    "    fitness_values.extend([best_fitness] * mu)\n",
    "    steps = mu\n",
    "    while steps < max_steps:\n",
    "        candidates = [mutate(current) for current in random.choices(population, k=lmbda)]\n",
    "        candidates.extend(population)\n",
    "        steps += lmbda\n",
    "\n",
    "        candidates.sort(key = lambda x: get_fitness(x), reverse = True)\n",
    "        candidate = candidates[0]\n",
    "        if get_fitness(candidate) > best_fitness:\n",
    "            best = candidate\n",
    "            best_fitness = get_fitness(best)\n",
    "        population = candidates[:mu]\n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "mupluslambda()\n",
    "mpl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "While the fitness curve likely is less steep than in the former versions of the evolution strategy, note that in the plot we are only increasing once we have completed the evaluation of an entire generation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For the sake of completeness, let's also consider the (μ,λ)-ES, where the survivor selection only considers the offspring, but not the parents. The (μ,λ)-selection is often preferred in practice because it is better at leaving local optima as well as following moving optima. Note that for (μ,λ) selection μ < λ must hold."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mucommalambda():\n",
    "    population = [get_random_solution() for _ in range(mu)]\n",
    "    best = max(population, key = lambda x: get_fitness(x))\n",
    "    best_fitness = get_fitness(best)\n",
    "    fitness_values.extend([best_fitness] * mu)\n",
    "    steps = mu\n",
    "    while steps < max_steps:\n",
    "        candidates = [mutate(current) for current in random.choices(population, k=lmbda)]\n",
    "        steps += lmbda\n",
    "\n",
    "        candidates.sort(key = lambda x: get_fitness(x), reverse = True)\n",
    "        candidate = candidates[0]\n",
    "        if get_fitness(candidate) > best_fitness:\n",
    "            best = candidate\n",
    "            best_fitness = get_fitness(best)\n",
    "        population = candidates[:mu]\n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "mucommalambda()\n",
    "mcl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.plot(mcl_values, label = \"(μ,λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The evolution strategies we have considered so far did not include recombination: We simply copied the parents. There is another parameter which we need to consider, and which was hidden from the name so far: The number of individuals involved in recombination ρ. So far, we had implicitly assumed ρ=1, which is known as _cloning_. The parameter is typically included in the name of the evolution strategy using the scheme (μ/ρ,λ). Let's consider the case of ρ=2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "rho = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to combine to parents, we need to combine two parents to one offspring. Crossover takes the genetic material of two or more parent individuals, and recombines them. A basic crossover operator is single-point crossover, where, for two parent chromosomes of length n, we pick a point 0 < x < n, and then take the first x genes from the first parent, and the remaining n - x genes from the second parent. Crossover can be implemented to return a single combined individual, or we can return both variants (and if we only need one, we can randomly choose one)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def singlepoint_crossover(parent1, parent2):\n",
    "    pos = random.randint(0, len(parent1))\n",
    "    offspring1 = parent1[:pos] + parent2[pos:]\n",
    "    offspring2 = parent2[:pos] + parent1[pos:]\n",
    "    return offspring1, offspring2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Integrating crossover (ρ=2) into our evolution strategies gives us a (μ/2+λ) algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mu2pluslambda():\n",
    "    population = [get_random_solution() for _ in range(mu)]\n",
    "    best = max(population, key = lambda x: get_fitness(x))\n",
    "    best_fitness = get_fitness(best)\n",
    "    fitness_values.extend([best_fitness] * mu)\n",
    "    steps = mu\n",
    "    while steps < max_steps:\n",
    "        candidates = []\n",
    "        for x in range(lmbda):\n",
    "            parents = random.choices(population, k = 2)\n",
    "            child = random.choice(singlepoint_crossover(parents[0], parents[1]))\n",
    "            child = mutate(child)\n",
    "            candidates.append(child)\n",
    "            steps += 1\n",
    "\n",
    "        # Plus selection\n",
    "        candidates.extend(population)\n",
    "        candidates.sort(key = lambda x: get_fitness(x), reverse = True)\n",
    "        candidate = candidates[0]\n",
    "        if get_fitness(candidate) > best_fitness:\n",
    "            best = candidate\n",
    "            best_fitness = get_fitness(best)\n",
    "        population = candidates[:mu]\n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "mu2pluslambda()\n",
    "m2pl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.plot(mcl_values, label = \"(μ,λ)ES\")\n",
    "plt.plot(m2pl_values, label = \"(μ/2+λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Of course we also have a comma-selection variant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mu2commalambda():\n",
    "    population = [get_random_solution() for _ in range(mu)]\n",
    "    best = max(population, key=lambda x: get_fitness(x))\n",
    "    best_fitness = get_fitness(best)\n",
    "    fitness_values.extend([best_fitness] * mu)\n",
    "    steps = mu\n",
    "    while steps < max_steps:\n",
    "        candidates = []\n",
    "        for x in range(lmbda):\n",
    "            parents = random.choices(population, k=mu)\n",
    "            child = random.choice(singlepoint_crossover(parents[0], parents[1]))\n",
    "            child = mutate(child)\n",
    "            candidates.append(child)\n",
    "            steps += 1\n",
    "\n",
    "        # Comma selection\n",
    "        candidates.sort(key=lambda x: get_fitness(x), reverse=True)\n",
    "        candidate = candidates[0]\n",
    "        if get_fitness(candidate) > best_fitness:\n",
    "            best = candidate\n",
    "            best_fitness = get_fitness(best)\n",
    "        population = candidates[:mu]\n",
    "        fitness_values.extend([best_fitness] * lmbda)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "mu2commalambda()\n",
    "m2cl_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.plot(mcl_values, label = \"(μ,λ)ES\")\n",
    "plt.plot(m2pl_values, label = \"(μ/2+λ)ES\")\n",
    "plt.plot(m2cl_values, label = \"(μ/2,λ)ES\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "An important element of evolution strategies in general we haven't touched upon yet is self-adaptation -- which is a topic we will consider in a later lecture."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Simple Genetic Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Traditionally, a main difference between evolution strategies and genetic algorithms is that evolution strategies manipulate the phenotype directly, since they were originally applied to real-valued functions. In contrast, genetic algorithms traditionally act on a genetic encoding (usually binary encoding), and the fitness is evaluated on the decoded phenotype. For our one max example, the difference is rather irrelevant, since our phenotype _is_ a bitstring.\n",
    "\n",
    "A second major difference lies in the selection strategy: In a canonical, simple Genetic Algorithm the deterministic parent selection is usually replaced with a probabilistic selection strategy, typically applied to larger populations. As a simple first example, we will use tournament selection: For a given number of individuals (the tournament size) we randomly select individuals from the population (with or without replacement), and the best of these individuals wins the tournament, and is a parent for reproduction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tournament_size = 5\n",
    "def tournament_selection(population, replacement = False):\n",
    "    if replacement:\n",
    "        candidates = random.choices(population, k = tournament_size)\n",
    "    else:\n",
    "        candidates = random.sample(population, tournament_size)\n",
    "        \n",
    "    return max(candidates, key = lambda x: get_fitness(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Note: We are redundantly calculating fitness here. However, we will not count these fitness evaluations as it would be trivial to cache fitness values to avoid recalculation, but that would clutter up the examples. (We will cache fitness values in later iterations of the algorithms we are considering)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For survivor selection, there are different models: In a _generational_ genetic algorithm, an entire new offspring population is bred, and then replaces the parent population. In a _steady-state_ genetic algorithm, one offspring (or pair of offspring) is generated per generation and one member of population is replaced by that offspring. We will start with a generational genetic algorithm, but include another twist on survivor selection: In _elitism_ a certain share of the best individuals of one generation survives _unchanged_ to the next generation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def elitism(population):\n",
    "    population.sort(key = lambda k: get_fitness(k), reverse = True)\n",
    "    return population[:elite_size]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Before we implement the genetic algorithm, there are a couple of parameters we need to decide on: How large shall the population be? How many of these shall always survive based on elitism? What should the probability for mutation be? While we have avoided the question of the mutation rate by encoding that into the mutation operator, we need to choose sensible values for all other parameters. We will use some common default values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "population_size = 20\n",
    "elite_size = int(population_size * 0.05)\n",
    "P_xover = 0.7\n",
    "selection = tournament_selection\n",
    "crossover = singlepoint_crossover\n",
    "fitness_values = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def ga():\n",
    "    population = [get_random_solution() for _ in range(population_size)]\n",
    "\n",
    "    best_fitness = -1\n",
    "    steps = 0\n",
    "    for p in population: # We are iterating over the population only so that our plot is more fine-grained\n",
    "        fitness = get_fitness(p)\n",
    "        if fitness > best_fitness:\n",
    "            best_fitness, best_solution = fitness, p[:]\n",
    "        steps += 1\n",
    "        fitness_values.append(best_fitness)\n",
    "\n",
    "    while steps < max_steps:\n",
    "        new_population = elitism(population)\n",
    "        while len(new_population) < len(population):\n",
    "            parent1, parent2 = selection(population), selection(population)\n",
    "\n",
    "            if random.random() < P_xover:\n",
    "                offspring1, offspring2 = crossover(parent1, parent2)\n",
    "            else:\n",
    "                offspring1, offspring2 = parent1[:], parent2[:]\n",
    "\n",
    "            offspring1, offspring2 = mutate(offspring1), mutate(offspring2)\n",
    "            new_population += [offspring1, offspring2]\n",
    "\n",
    "        population = new_population\n",
    "        for p in population:\n",
    "            fitness = get_fitness(p)\n",
    "            steps += 1\n",
    "            if fitness > best_fitness:\n",
    "                best_fitness, best_solution = fitness, p\n",
    "            fitness_values.append(best_fitness)\n",
    "\n",
    "    return best_solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "ga()\n",
    "ga_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.plot(mcl_values, label = \"(μ,λ)ES\")\n",
    "plt.plot(m2pl_values, label = \"(μ/2+λ)ES\")\n",
    "plt.plot(m2cl_values, label = \"(μ/2,λ)ES\")\n",
    "plt.plot(ga_values, label = \"GA\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Steady State Genetic Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our simple genetic algorithm uses a _generational model_, where each iteration produces a new offspring population. An alternative is a _steady state_ genetic algorithm: In each iteration, we only pick a small number of individuals (e.g., 2), produce offspring, and then replace the parents with the offspring. During this replacement we can apply differnet survivor strategies; for example, the offspring can always replace the parents, or we could always use the best out of the set of parents and their offspring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def steadystatega():\n",
    "    population = [get_random_solution() for _ in range(population_size)]\n",
    "    steps = 0\n",
    "    \n",
    "    best_fitness = -1\n",
    "    best = None\n",
    "\n",
    "    for p in population:\n",
    "        fitness = get_fitness(p)\n",
    "        steps += 1\n",
    "        if fitness > best_fitness:\n",
    "            best_fitness, best = fitness, p\n",
    "        fitness_values.append(best_fitness)\n",
    "\n",
    "    while steps < max_steps:\n",
    "        parent1, parent2 = selection(population), selection(population)        \n",
    "        p1, p2 = population.index(parent1), population.index(parent2)\n",
    "\n",
    "        if random.random() < P_xover:\n",
    "            offspring1, offspring2 = crossover(parent1, parent2)\n",
    "        else:\n",
    "            offspring1, offspring2 = parent1[:], parent2[:]\n",
    "\n",
    "        offspring1, offspring2 = mutate(offspring1), mutate(offspring2)\n",
    "        \n",
    "        best1, best2 = sorted([parent1, parent2, offspring1, offspring2], key = lambda item: get_fitness(item), reverse = True)[:2]\n",
    "        population[p1] = best1\n",
    "        population[p2] = best2\n",
    "        steps += 2\n",
    "\n",
    "        if get_fitness(best1) > best_fitness:\n",
    "            best_fitness, best = get_fitness(best1), best1[:]\n",
    "\n",
    "        fitness_values.append(best_fitness)\n",
    "        fitness_values.append(best_fitness)\n",
    "\n",
    "    return best\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "steadystatega()\n",
    "ssga_values = fitness_values[:]\n",
    "plt.plot(opo_values, label = \"(1+1)ES\")\n",
    "plt.plot(opl_values, label = \"(1+λ)ES\")\n",
    "plt.plot(ocl_values, label = \"(1,λ)ES\")\n",
    "plt.plot(mpl_values, label = \"(μ+λ)ES\")\n",
    "plt.plot(mcl_values, label = \"(μ,λ)ES\")\n",
    "plt.plot(m2pl_values, label = \"(μ/2+λ)ES\")\n",
    "plt.plot(m2cl_values, label = \"(μ/2,λ)ES\")\n",
    "plt.plot(ga_values, label = \"GA\")\n",
    "plt.plot(ssga_values, label = \"SS-GA\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Comparison of the algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We defined a rather large space of possible algorithms and variations, and the usual question is: Which of these works best? We already saw some trends emerging from the plots above, for example the (1+1)ES tends to do well. Let's evaluate some variants in more detail."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To simplify experiments, we will define a helper function that runs an algorithm for a number of repetitions and gives us a list of resulting fitness values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.utils import io\n",
    "\n",
    "def run_times(algorithm, repetitions):\n",
    "    global fitness_values\n",
    "    result = []\n",
    "    for i in range(repetitions):\n",
    "        fitness_values = []\n",
    "        with io.capture_output() as captured: \n",
    "            algorithm()\n",
    "        result.append(fitness_values[-1])\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we have to call this for each of the algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "crossover = singlepoint_crossover\n",
    "selection = tournament_selection\n",
    "max_steps = 1000\n",
    "\n",
    "results = {\"GA\"      : run_times(ga, 30), \n",
    "           \"SS-GA\"   : run_times(steadystatega, 30),\n",
    "           \"(μ/2+λ)ES\" : run_times(mu2pluslambda, 30),\n",
    "           \"(μ/2,λ)ES\" : run_times(mu2commalambda, 30),\n",
    "           \"(μ+λ)ES\" : run_times(mupluslambda, 30),\n",
    "           \"(μ,λ)ES\" : run_times(mucommalambda, 30),\n",
    "           \"(1+1)ES\" : run_times(oneplusone, 30), }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can compare the results by plotting the distributions of the final fitness values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.boxplot(results.values())\n",
    "ax.set_xticklabels(results.keys(), rotation=45)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If we want to know whether there is a statistical difference between two configurations, we can use the statistics we learned in the previous chapter, e.g. a Mann-Whitney U test to compare (1+1)ES with (μ/2+λ)ES:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from scipy.stats import mannwhitneyu\n",
    "result = mannwhitneyu(results[\"(μ/2+λ)ES\"], results[\"(1+1)ES\"])\n",
    "result[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Most likely, the results suggest that (1+1)ES finds the solution for one max more efficiently (but whether it does so significantly we would have to test for using statistical tests and effect size measures). We only looked at one particular configuration of search operators for the GA, and varying the parameters and operators may lead to entirely different results. We will look at other operators in a later chapter. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In the previous chapter we considered local search algorithms, which appeared to work quite well on the one-max problem. Let's see how they compare against our new global search algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "All local search algorithms required a definition of neighbourhood:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_neighbours(candidate):\n",
    "    neighbours = []\n",
    "    for pos in range(len(candidate)):\n",
    "        copy = candidate[:]\n",
    "        copy[pos] = 1 - copy[pos]\n",
    "        neighbours.append(copy)\n",
    "    return neighbours"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We'll use a first ascent hillclimber with restarts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def hillclimbing():\n",
    "\n",
    "    current = get_random_solution()\n",
    "    fitness = get_fitness(current)\n",
    "    best = current[:]\n",
    "    best_fitness = fitness\n",
    "\n",
    "    step = 0\n",
    "    while step < max_steps:\n",
    "\n",
    "        replaced = False\n",
    "        for neighbour in get_neighbours(current):\n",
    "            neighbour_fitness = get_fitness(neighbour)\n",
    "            step += 1\n",
    "            if neighbour_fitness > fitness:\n",
    "                current = neighbour\n",
    "                fitness = neighbour_fitness\n",
    "                replaced = True\n",
    "                if fitness > best_fitness:\n",
    "                    best = current[:]\n",
    "                    best_fitness = fitness\n",
    "\n",
    "                fitness_values.append(best_fitness)\n",
    "                break\n",
    "            else:\n",
    "                fitness_values.append(best_fitness)\n",
    "\n",
    "        # Random restart if no neighbour is better\n",
    "        if not replaced:\n",
    "            current = get_random_solution()\n",
    "            fitness = get_fitness(current)\n",
    "            step += 1\n",
    "            if fitness > best_fitness:\n",
    "                best = current[:]\n",
    "                best_fitness = fitness\n",
    "            fitness_values.append(best_fitness)\n",
    "\n",
    "    return best"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The second local search algorithm was tabu search:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tabu_size = 500\n",
    "def tabusearch():\n",
    "    current = get_random_solution()\n",
    "    fitness = get_fitness(current)\n",
    "\n",
    "    tabu = [current]\n",
    "\n",
    "    best_solution = current\n",
    "    best_fitness = fitness\n",
    "\n",
    "    iteration = 0\n",
    "    step = 0\n",
    "    while step < max_steps:\n",
    "        best_neighbour = None\n",
    "\n",
    "        neighbour_fitness = 0\n",
    "        for neighbour in get_neighbours(current):\n",
    "            if neighbour not in tabu:\n",
    "                new_fitness = get_fitness(neighbour)\n",
    "                step += 1\n",
    "                if new_fitness > neighbour_fitness:\n",
    "                    best_neighbour = neighbour\n",
    "                    neighbour_fitness = new_fitness\n",
    "                    if neighbour_fitness > best_fitness:\n",
    "                        best_fitness = neighbour_fitness\n",
    "                        best_solution = best_neighbour\n",
    "                fitness_values.append(best_fitness)\n",
    "                \n",
    "\n",
    "        # Append at the end of the tabu list\n",
    "        tabu.append(best_neighbour)\n",
    "        current = best_neighbour\n",
    "        \n",
    "        # Remove elements from the front of the tabu list\n",
    "        while len(tabu) > tabu_size:\n",
    "            tabu.pop(0)\n",
    "        \n",
    "        iteration += 1\n",
    "\n",
    "    return best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, there is simulated annealing and its helper functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def acceptance_probability(fitness, new_fitness, temperature):\n",
    "    if new_fitness > fitness:\n",
    "        return 1\n",
    "    else:\n",
    "        p = math.exp( (new_fitness - fitness) / temperature)\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def temperature(fraction):\n",
    "    return max(0.01, min(1, 1 - fraction))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def simulatedannealing():\n",
    "    current = get_random_solution()\n",
    "    fitness = get_fitness(current)\n",
    "\n",
    "    best_solution = current\n",
    "    best_fitness = fitness\n",
    "\n",
    "    step = 0\n",
    "    while step < max_steps:\n",
    "        fraction = step / float(max_steps)\n",
    "        T = temperature(fraction)\n",
    "\n",
    "        neighbour = random.choice(get_neighbours(current))\n",
    "        neighbour_fitness = get_fitness(neighbour)\n",
    "        step += 1\n",
    "\n",
    "        if acceptance_probability(fitness, neighbour_fitness, T) > random.random():\n",
    "            current, fitness = neighbour, neighbour_fitness\n",
    "\n",
    "            if fitness > best_fitness:\n",
    "                best_fitness = fitness\n",
    "                best_solution = current\n",
    "        fitness_values.append(best_fitness)\n",
    "\n",
    "    return best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We already have the results of our experiment stored in `results`, so we just need to extend our data with some runs of these three local search algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "results.update({\n",
    "    \"HC\"      : run_times(hillclimbing, 30),\n",
    "    \"Tabu\"    : run_times(tabusearch, 30),\n",
    "    \"SA\"      : run_times(simulatedannealing, 30),\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, we are ready to compare local search with our global search algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.boxplot(results.values())\n",
    "ax.set_xticklabels(results.keys(), rotation=45)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This result is of course specific to the particular value of `n` and the chosen number of steps for the algorithm, but does it reflect what you expected?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Leading Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's consider an alternative problem, based on the identical representation and search operators, but with a slightly different fitness function. The Leading Ones problem is a variation of the One Max problem, and often used to study search algorithms. The fitness function for Leading Ones represents the number of leading ones in an individual:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(solution):\n",
    "    fitness = 0\n",
    "    for i in solution:\n",
    "        if i == 1:\n",
    "            fitness += 1\n",
    "        else:\n",
    "            break\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness([1,1,1,0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness([1,0,0,1,1,1,1,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The fitness value can always be increased by appending a single one to the leading\n",
    "ones, therefore like One Max this is a _unimodal_ problem, i.e., there is only a single local optimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since the fitness function is the only thing that changes, we can immediately run some new experiments to compare our search algorithms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "crossover = singlepoint_crossover\n",
    "selection = tournament_selection\n",
    "max_steps = 1000\n",
    "\n",
    "results = {\"GA\"      : run_times(ga, 30), \n",
    "           \"SS-GA\"   : run_times(steadystatega, 30),\n",
    "           \"(μ/2+λ)ES\" : run_times(mu2pluslambda, 30),\n",
    "           \"(μ/2,λ)ES\" : run_times(mu2commalambda, 30),\n",
    "           \"(μ+λ)ES\" : run_times(mupluslambda, 30),\n",
    "           \"(μ,λ)ES\" : run_times(mucommalambda, 30),\n",
    "           \"(1+1)ES\" : run_times(oneplusone, 30),\n",
    "           \"HC\"      : run_times(hillclimbing, 30),\n",
    "           \"Tabu\"    : run_times(tabusearch, 30),\n",
    "           \"SA\"      : run_times(simulatedannealing, 30),\n",
    "          }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.boxplot(results.values())\n",
    "ax.set_xticklabels(results.keys(), rotation=45)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "These results are likely somewhat different from the ones on the one max problem. In particular, the global search algorithms will perform many mutations that show no difference in the resulting fitness values -- fitness can only be improved by mutating the first `0` in the list. There is always such a neighbour that a hill climber can find, while global search algorithms are largely 'blind'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Evolutionary Search on the n-queens problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As alternative example problem, we will consider the n-queens problem again, which you already know from the previous chapter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_random_solution():\n",
    "    return [random.randint(0, n-1) for _ in range(n)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To keep the runtimes of the algorithms small, we should reduce the value of `n` compared to what we used for one max:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The fitness calculation still considers the number of pairs of queens that do not check each other:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(solution):\n",
    "    fitness = 0\n",
    "    for i in range(len(solution) - 1):\n",
    "        for j in range(i + 1, len(solution)):\n",
    "            if solution[i] != solution[j] \\\n",
    "                and solution[i] != solution[j] + (j - i) \\\n",
    "                and solution[j] != solution[i] + (j - i):\n",
    "                fitness += 1\n",
    "\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to apply search to a different problem, we also need to make sure that the search operators match the problem encoding. Selection operators are independent of the representation, so we only need to worry about variation operators here. For crossover, we are just cutting and merging lists, so the single-point crossover operator we defined is just fine for the n-queens problem. We will have to change our mutation operator, however, since for one max that simply consists of flipping bits. As a basic mutation operator, we can simply probabilistically replace individual genes with new random values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mutate(individual):\n",
    "    P_mutate = 1/len(individual)\n",
    "    copy = individual[:]\n",
    "    for position in range(len(individual)):\n",
    "        if random.random() < P_mutate:\n",
    "            copy[position] = random.randint(0, n-1)\n",
    "    return copy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will also need to redefine the local neighbourhood to make the local search algorithms work. (In a future revision of this notebook I'll just import them, but for now they are cloned below)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_neighbours(solution):\n",
    "    neighbours = []\n",
    "    for i in range(len(solution)):\n",
    "        if solution[i] > 0:\n",
    "            copy = solution[:]\n",
    "            copy[i] = copy[i] - 1\n",
    "            neighbours.append(copy)\n",
    "        if solution[i] < n - 1:\n",
    "            copy = solution[:]\n",
    "            copy[i] = copy[i] + 1\n",
    "            neighbours.append(copy)\n",
    "\n",
    "    return neighbours"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we can run some experiments using all the different search algorithms defined so far:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "max_steps = 1000\n",
    "tabu_size = 500\n",
    "\n",
    "results = {\"GA\"        : run_times(ga, 30), \n",
    "           \"SS-GA\"     : run_times(steadystatega, 30),\n",
    "           \"(μ/2+λ)ES\" : run_times(mu2pluslambda, 30),\n",
    "           \"(μ/2,λ)ES\" : run_times(mu2commalambda, 30),\n",
    "           \"(μ+λ)ES\"   : run_times(mupluslambda, 30),\n",
    "           \"(μ,λ)ES\"   : run_times(mucommalambda, 30),\n",
    "           \"(1+1)ES\"   : run_times(oneplusone, 30), \n",
    "           \"HC\"        : run_times(hillclimbing, 30),\n",
    "           \"Tabu\"      : run_times(tabusearch, 30),\n",
    "           \"SA\"        : run_times(simulatedannealing, 30)\n",
    "          }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.boxplot(results.values())\n",
    "ax.set_xticklabels(results.keys(), rotation=45)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "At this point, we could also dig into more statistics on the comparisons. But did we really choose the right operators and parameters? This is a question for a future chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Outlook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In this chapter, we considered some basic variation and selection operators. In the next chapter we will consider a couple of alternatives. Besides all the possible variations in parameters and search operators, there are also many variations of the algorithms themselves. Some specific variants we will consider in later lectures in this course are the following:\n",
    "\n",
    "- Parallel GAs, in which independent island populations are evolved and sporadically exchange individuals\n",
    "- Cellular GAs, in which a topology is imposed on the population, and decides on candidates for reproduction\n",
    "- Memetic Algorithms, which extend GAs with local search\n",
    "- Adaptive GAs, in which the parameters evolve together with the solutions.\n",
    "\n",
    "Besides these fundamental variations of the canonical GA, each variant further has many different options. What population size to use? Which selection operator? Which replacement operator? What probabilities to apply the different variation operators? We will consider in a future lecture how to choose these parameters.\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}