1_introduction/evolutionary_algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<img src=\"https://github.com/d9w/evolution/raw/master/imgs/logo.png\" width=\"20%\" align=\"right\" style=\"margin:0px 20px\">\n",
    "\n",
    "\n",
    "# Evolutionary Computation\n",
    "\n",
    "## 1.3 Evolutionary Algorithms\n",
    "\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-sa/4.0/\"><img alt=\"Creative Commons License\" align=\"left\" src=\"https://i.creativecommons.org/l/by-sa/4.0/80x15.png\" /></a>&nbsp;| Dennis G. Wilson | <a href=\"https://d9w.github.io/evolution/\">https://d9w.github.io/evolution/</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Outline\n",
    "\n",
    "1. [Individuals](#individuals)\n",
    "2. [Objectives](#objectives)\n",
    "3. [(1+1) EA](#one_plus_one)\n",
    "4. [$(1+\\lambda)$ EA](#one_plus_lambda)\n",
    "5. [Algorithm parameters](#parameters)\n",
    "\n",
    "\n",
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/d9w/evolution/blob/master/1_introduction/evolutionary_algorithms.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "import numpy as np\n",
    "from tqdm import tqdm\n",
    "np.random.seed(1234)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <a id=\"individuals\"></a>Individuals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The base unit of an evolutionary algorithm is the individual. An individual represents a single solution to the problem we want to solve. We'll start simple with binary individuals, where genes are represented by bits. DNA in biological organisms is mostly base 4, being represented by 4 different amino acids. We'll use a base 2 representation of 1s and 0s, but the interpretation of these binary strings could lead to any complex organism. Using binary strings allows us to discuss the theoretical analysis of evolutionary algorithms, which have mostly been studied on binary genomes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Individual:\n",
    "    \n",
    "    def __init__(self, n: int):\n",
    "        self.genes = np.random.randint(0, 2, (n,))\n",
    "        self.fitness = -np.inf\n",
    "        \n",
    "    def __str__(self):\n",
    "        return f'(Ind: {self.genes}, {self.fitness})'\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return str(self)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here we've defined a new type, `Individual` which has binary genes and an integer fitness. When we construct a new individual, we use random genes and set the default fitness to 0. For these examples we'll be using objective functions which have positive fitness values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ind = Individual(10)\n",
    "ind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <a id=\"objectives\"></a>Objectives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "An objective function is a function which gives a value to our individual. A strength of evolutionary algorithms is that this objective function can be anything as long as it evaluates the individual. Unlike other optimization methods, this function does not need to be differentiable or continuous. The first objective function we'll look at is the OneMax function, which simply adds all of the bits of the genotype. The optimal fitness for this function is therefore when the entire genotype is 1. This simple function has been well-studied and generalizes well to the search of any specific bit string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def onemax(i: Individual):\n",
    "    return np.sum(i.genes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ind.fitness = onemax(ind)\n",
    "ind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "As we can see, the fitness of our individual is the number of 1s in the function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In order to be more general later, we'll write an `evaluate` function which can take any `objective` function. The `!` exclamation point in `evaluate!` indicates that this function modifies the object which is passed. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def evaluate(ind: Individual, objective):\n",
    "    ind.fitness = objective(ind)\n",
    "\n",
    "evaluate(ind, onemax)\n",
    "ind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Now that we have our individuals defined and we have an objective function, we're ready to write our first evolutionary algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <a id=\"one_plus_one\"></a>(1+1) Evolutionary Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The first algorithm we'll implement is the simplest evolutionary algorithm, the (1+1) Evolutionary Algorithm:\n",
    "\n",
    "1. Choose randomly an initial bit string $x∈ \\{0;1\\} $\n",
    "2. Repeat the following mutation step:\n",
    "    1. Compute $x′$ by flipping independently each bit $x_i$ with probability $p$\n",
    "    2. Replace $x$ by $x′$ if $f(x′) \\geq f(x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We'll start by defining the number of dimensions for our problem, then define the first individual, the starting point of search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "parent = Individual(n)\n",
    "evaluate(parent, onemax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's define the mutation step as a function. This will make our code more organized and has the advantage in Julia that compilation will optimize this part of the code. We'll use the probability of $p=\\frac{1}{n}$, where $n$ is the number of bits. We'll discuss that choice soon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def mutate(ind: Individual, mutation_rate=1.0/len(ind.genes)):\n",
    "    new_genes = np.copy(ind.genes)\n",
    "    for i in range(len(new_genes)):\n",
    "        if np.random.rand() < mutation_rate:\n",
    "            new_genes[i] = not ind.genes[i]\n",
    "    child = Individual(len(ind.genes))\n",
    "    child.genes = new_genes\n",
    "    return child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "child = mutate(parent)\n",
    "print(\"Parent :\", parent)\n",
    "print(\"Child :\", child)\n",
    "print(\"Genes :\", parent.genes == child.genes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Try running this a few times and you'll see that most of the time, only one gene changes. That makes sense due to the $p=\\frac{1}{n}$ mutation rate we set. This means that evolution will move rather slowly towards the optimal bitstring, on average only 1 change at a time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Now that we have the new individual, we can do the last part of our algorithm: Replace $x$ by $x′$ if $f(x′) \\geq f(x)$. To do this, we must first evaluate the new individual."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "evaluate(child, onemax)\n",
    "print(parent.fitness)\n",
    "print(child.fitness)\n",
    "if child.fitness >= parent.fitness:\n",
    "    parent = child\n",
    "parent.fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "That's all there is to the (1+1) EA. We simply run this mutation step over and over until we reach the solution we want or stop the computation. Let's look at just a few iterations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "parent = Individual(n)\n",
    "for i in range(20):\n",
    "    child = mutate(parent)\n",
    "    evaluate(child, onemax)\n",
    "    if child.fitness >= parent.fitness:\n",
    "        parent = child\n",
    "    # print(i, \" \", parent.fitness)\n",
    "\n",
    "print(parent.fitness, \" / \", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "So in a few generations, we can see improvement. To study how long it will take for this to reach the OneMax solution, let's first define everything we've done until now as a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def one_plus_one(ind_length: int, num_generations: int, objective):\n",
    "    fits = np.zeros(num_generations)\n",
    "    parent = Individual(ind_length)\n",
    "    evaluate(parent, objective)\n",
    "    \n",
    "    for i in tqdm(range(len(fits))):\n",
    "        child = mutate(parent)\n",
    "        evaluate(child, objective)\n",
    "\n",
    "        if child.fitness >= parent.fitness:\n",
    "            parent = child\n",
    "            \n",
    "        fits[i] = parent.fitness\n",
    "    return fits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Since evolutionary algorithms are stochastic, it's hard to guarantee their exact computational complexity. You can prove the worst case, but a more useful metric is the expected number of generations to reach the optimal solution. For linear objective functions such as the OneMax problem, the expected runtime for the (1+1) EA has been [proven](https://core.ac.uk/download/pdf/82100186.pdf) to to be $0(n \\log n)$, where $n$ is the number of independent binary variables (ie, the length of the genome). This proof is beyond the scope of this class, but I recommend looking at the linked publications in this notebook. Note that this is only for the case of a mutation rate of $\\frac{1}{n}$, which is why we used it as our default value before. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's run our (1+1) EA with $n \\log n$ as our number of generations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 1000\n",
    "fits = one_plus_one(n, int(np.round(n * np.log(n)))*2, onemax)\n",
    "print(fits[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fits, 'b')\n",
    "plt.xlabel(\"Generations\")\n",
    "plt.ylabel(\"Fitness\")\n",
    "plt.title(f\"One-Max on {n} Dimensions\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This isn't yet $n$ but its very close, which is what the expected time guarantees: $n \\log n$ is the average value of when the (1+1) EA converges. The worst case for a binary (1+1) EA on any function is to converge in $O(n^n)$, but we don't need to run it for that long to see convergence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The Leading Ones problem is another well-studied binary problem which counts the number of leading ones from left to right, stopping when the first zero-bit is found. In other words, the fitness of this function is:\n",
    "\n",
    "$f(x) := \\sum_{i=1}^n \\prod_{j=1}^i x_j$\n",
    "\n",
    "In our implementation, we'll just count the indices and stop when we reach a 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def leading_ones(ind: Individual):\n",
    "    f = 0\n",
    "    for i in range(len(ind.genes)):\n",
    "        if not ind.genes[i]:\n",
    "            f = i\n",
    "            break\n",
    "    return f\n",
    "print(ind)\n",
    "leading_ones(ind)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <b>Exercise</b>\n",
    "    <br/>\n",
    "    Run the (1+1) EA on the Leading Ones problem. Does it converge near $0(n \\log n)$, or $O(n^2)$?\n",
    "    <br/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <a id=\"one_plus_lambda\"></a>$(1+\\lambda)$ Evolutionary Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The next algorithm that we'll see is a small change on the (1+1) EA. Instead of generating one individual each iteration (generation) we'll make $\\lambda$. This can be considered our population. This small change means the $(1+\\lambda)$ algorithm is still very simple, but this simple algorithm is used in state-of-the-art Genetic Programming methods to do perform complex tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The $(1+\\lambda) EA$ introduces a new parameter: population size. What should we choose for this parameter? [Recent theoretical work](https://www.sciencedirect.com/science/article/pii/S0304397514002060) has demonstrated that the expected running time of the $(1+\\lambda)$ EA on any linear function is $O(\\frac{1}{λ} n \\log n + n)$ under the condition that $\\lambda = O(\\log n \\log \\log n / \\log \\log \\log n)$. We could try that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 1000\n",
    "𝜆 = int(round(np.log(n)*np.log(np.log(n))/np.log(np.log(np.log(n)))))\n",
    "print(𝜆)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We'll rewrite our `one_plus_one` function, this time using a population of individuals. We'll keep track of the best new individual in order to compare it with the expert for replacement in the next generation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 1\n",
    "a = [0]\n",
    "for i in range(1, m+1):\n",
    "    a.append(i)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def one_plus_lambda(ind_length: int, num_generations: int, objective, 𝜆: int):\n",
    "    fits = np.zeros(num_generations)\n",
    "    expert = Individual(ind_length)\n",
    "    evaluate(expert, objective)\n",
    "    \n",
    "    for i in tqdm(range(len(fits))):\n",
    "        population = [expert,]\n",
    "        best = 0\n",
    "        for j in range(1, 𝜆):\n",
    "            population.append(mutate(expert))\n",
    "            evaluate(population[j], objective) \n",
    "            if population[j].fitness > population[best].fitness:\n",
    "                best = j\n",
    "        if population[best].fitness >= expert.fitness:\n",
    "            expert = population[best]\n",
    "        fits[i] = expert.fitness\n",
    "    return fits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's see how these two methods compare on the OneMax problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 100\n",
    "n_gens = 1000\n",
    "fits_1 = one_plus_one(n, n_gens, onemax)\n",
    "fits_𝜆 = one_plus_lambda(n, n_gens, onemax, 𝜆)\n",
    "fits_1[-1], fits_𝜆[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fits_1, label=\"1+1\", color='b')\n",
    "plt.plot(fits_𝜆, label=\"1+lambda\", color='g')\n",
    "plt.xlabel(\"Generations\")\n",
    "plt.ylabel(\"Fitness\")\n",
    "plt.title(f\"One-Max on {n} Dimensions\")\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "At first glance, it appears that the $(1+\\lambda)$ EA performs much better than the (1+1) EA. However, this is an unfair comparison. The $(1+\\lambda)$ EA runs the evaluation function $\\lambda$ times per generation, meaning there are many more evaluations. We can see this by plotting based on evaluation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fits_1, label=\"1+1\", color='b')\n",
    "plt.plot(np.arange(1,n_gens*𝜆,𝜆), fits_𝜆, label=\"1+lambda\", color='g')\n",
    "plt.xlabel(\"Evaluations\")\n",
    "plt.ylabel(\"Fitness\")\n",
    "plt.title(f\"One-Max on {n} Dimensions\")\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A more fair comparison would be to give each algorithm the same number of function evaluations, like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 1000\n",
    "n_gens = 10000\n",
    "fits_1 = one_plus_one(n, n_gens, onemax)\n",
    "fits_𝜆 = one_plus_lambda(n, int(n_gens/𝜆), onemax, 𝜆)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fits_1, label=\"1+1\", color='b')\n",
    "plt.plot(np.arange(1,n_gens,𝜆), fits_𝜆, label=\"1+lambda\", color='g')\n",
    "plt.xlabel(\"Evaluations\")\n",
    "plt.ylabel(\"Fitness\")\n",
    "plt.title(f\"One-Max on {n} Dimensions\")\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Because evolutionary algorithms are entirely based on randomness, it is a good practice to run them multiple times to have an idea about their performance. We'll run this 10 times, but more is often a good idea, depending on the distribution of final results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n_trials = 10\n",
    "n = 100\n",
    "n_gens = 1000\n",
    "\n",
    "fits_1 = np.zeros((n_gens, n_trials))\n",
    "fits_𝜆 = np.zeros((int(n_gens/𝜆), n_trials))\n",
    "\n",
    "for i in range(n_trials):\n",
    "    fits_1[:, i] = one_plus_one(n, n_gens, onemax)\n",
    "    fits_𝜆[:, i] = one_plus_lambda(n, int(n_gens/𝜆), onemax, 𝜆)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "μ_1 = np.mean(fits_1, axis=1)\n",
    "σ_1 = np.std(fits_1, axis=1)\n",
    "μ_𝜆 = np.mean(fits_𝜆, axis=1)\n",
    "σ_𝜆 = np.std(fits_𝜆, axis=1)\n",
    "print(np.shape(μ_1), np.shape(σ_1))\n",
    "print(np.shape(μ_𝜆), np.shape(σ_𝜆))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(μ_1, label=\"1+1\", color='b')\n",
    "plt.fill_between(np.arange(0, n_gens), μ_1+σ_1, μ_1-σ_1, facecolor='b', alpha=0.1)\n",
    "plt.plot(np.arange(1,n_gens,𝜆), μ_𝜆, label=\"1+lambda\", color='g')\n",
    "plt.fill_between(np.arange(0, n_gens, 𝜆), μ_𝜆+σ_𝜆, μ_𝜆-σ_𝜆, facecolor='b', alpha=0.1)\n",
    "plt.xlabel(\"Evaluations\")\n",
    "plt.ylabel(\"Fitness\")\n",
    "plt.title(f\"One-Max on {n} Dimensions\")\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <b>Exercise</b>\n",
    "    <br/>\n",
    "    Compare the (1+1) EA and $(1+\\lambda)$ EA on the Leading Ones problem\n",
    "    <br/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <a id=\"parameters\"></a>Algorithm parameters\n",
    "\n",
    "In this tutorial, we used fixed parameter values based on theoretical results. However, in practice, the choice of mutation rate and population size can greatly impact experimental results. Recent work has also demonstrated the value in [self-adjusting parameters](https://arxiv.org/pdf/1704.02191.pdf), which is similar to what a different stochastic optimization method, simulated annealing, uses. The policy of parameter adjustment is still an active field of research."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div class=\"alert alert-info\">\n",
    "    <b>Bonus Exercise</b>\n",
    "    <br/>\n",
    "    Study the effect of population size $\\lambda$ and mutation rate on $(1+1)$ EA and $(1+\\lambda)$ EA. Do they change the results a lot? Try implementing a dynamic mutation rate, such as one that decreases over time.\n",
    "    <br/>\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}