Search-Based Test Generation - Part 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Search-Based Test Generation - Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "\n",
    "import inspect\n",
    "import ast\n",
    "import astor\n",
    "\n",
    "import sys\n",
    "\n",
    "# For presenting as slides\n",
    "#plt.rcParams['figure.figsize'] = [12, 8]\n",
    "#plt.rcParams.update({'font.size': 22})\n",
    "#plt.rcParams['lines.linewidth'] = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## The Test Data Generation Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The problem we will consider in this chapter is the following: Given an entry point to a program (a function), we want to find values for the parameters of this function such that the execution of the function reaches a particular point in the program. In other words, we aim to find a test input to the program that covers a target statement. We will then generalise this problem to finding test inputs to cover _all_ statements in the program."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Assume we are aiming to test the following function under test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def test_me(x, y):\n",
    "    if x == 2 * (y + 1):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The `test_me` function has two input parameters, `x`and `y`, and it returns `True` or `False` depending on how the parameters relate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_me(10, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_me(22, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to address the test generation problem as a search problem, we need to decide on an encoding, and derive appropriate search operators. It is possible to use bitvectors like we did on previous problems; however, a simpler interpretation of the parameters of a function is a list of the actual parameters. That is, we encode a test input as a list of parameters; we will start by assuming that all parameters are numeric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The representation for inputs of this function is lists of length two, one element for `x` and one for `y`. As numeric values in Python are unbounded, we need to decide on some finite bounds for these values, e.g.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "MAX = 1000\n",
    "MIN = -MAX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For generating inputs we can now uniformly sample in the range (MIN, MAX). The length of the vector shall be the number of parameters of the function under test. Rather than hard coding such a parameter, we can also make our approach generalise better by using inspection to determine how many parameters the function under test has:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from inspect import signature\n",
    "sig = signature(test_me)\n",
    "num_parameters = len(sig.parameters)\n",
    "num_parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As usual, we will define the representation implicitly using a function that produces random instances."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_random_individual():\n",
    "    return [random.randint(MIN, MAX) for _ in range(num_parameters)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_random_individual()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need to define search operators matching this representation. To apply local search, we need to define the neighbourhood. For example, we could define one upper and one lower neighbour for each parameter:\n",
    "\n",
    "- `x-1, y`\n",
    "- `x+1, y`\n",
    "- `x, y+1`\n",
    "- `x, y-1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_neighbours(individual):\n",
    "    neighbours = []\n",
    "    for p in range(len(individual)): \n",
    "        if individual[p] > MIN:\n",
    "            neighbour = individual[:]\n",
    "            neighbour[p] = individual[p] - 1\n",
    "            neighbours.append(neighbour)\n",
    "        if individual[p] < MAX:\n",
    "            neighbour = individual[:]\n",
    "            neighbour[p] = individual[p] + 1\n",
    "            neighbours.append(neighbour)\n",
    "            \n",
    "    return neighbours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "x = get_random_individual()\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_neighbours(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Before we can apply search, we also need to define a fitness function.  Suppose that we are interested in covering the `True` branch of the if-condition in the `test_me()` function, i.e. `x == 2 * (y + 1)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def test_me(x, y):\n",
    "    if x == 2 * (y + 1):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "How close is a given input tuple for this function from reaching the target (true) branch of `x == 2 * (y + 1)`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's consider an arbitrary point in the search space, e.g. `(274, 153)`. The if-condition compares the following values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "x = 274\n",
    "y = 153\n",
    "x, 2 * (y + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to make the branch true, both values need to be the same. Thus, the more they differ, the further we are away from making the comparison true, and the less they differ, the closer we are from making the comparison true. Thus, we can quantify \"how false\" the comparison is by calculating the difference between `x` and `2 * (y + 1)`. Thus, we can calculate this distance as `abs(x - 2 * (y + 1))`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def calculate_distance(x, y):\n",
    "    return abs(x - 2 * (y + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "calculate_distance(274, 153)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can use this distance value as our fitness function, since we can nicely measure how close we are to an optimal solution. Note, however, that \"better\" doesn't mean \"bigger\" in this case; the smaller the distance the better. This is not a problem, since any algorithm that can maximize a value can also be made to minimize it instead.\n",
    "\n",
    "For each value in the search space of integer tuples, this distance value defines the elevation in our search landscape. Since our example search space is two-dimensional, the search landscape is three-dimensional and we can plot it to see what it looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "x = np.outer(np.linspace(-10, 10, 30), np.ones(30))\n",
    "y = x.copy().T\n",
    "z = calculate_distance(x, y)\n",
    "\n",
    "fig = plt.figure(figsize=(12, 12))\n",
    "ax  = plt.axes(projection='3d')\n",
    "\n",
    "ax.plot_surface(x, y, z, cmap=plt.cm.jet, rstride=1, cstride=1, linewidth=0);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The optimal values, i.e. those that make the if-condition true, have fitness value 0 and can be clearly seen at the bottom of the plot. The further away from the optimal values, the higher elevated the points in the search space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This distance can serve as our fitness function if we aim to cover the true branch of the program in our example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(individual):\n",
    "    x = individual[0]\n",
    "    y = individual[1]\n",
    "    return abs(x - 2 * (y + 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can now use any local search algorithm we have defined previously, with only one modification: In the prior examples where we applied local search we were always maximising fitness values; now we are minimising, so a hillclimber, for example, should only move to neighbours with _smaller_ fitness values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "max_steps = 10000\n",
    "fitness_values = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's use a steepest ascent hillclimber:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def hillclimbing():\n",
    "    current = get_random_individual()\n",
    "    fitness = get_fitness(current)\n",
    "    best, best_fitness = current[:], fitness\n",
    "    print(f\"Starting at fitness {best_fitness}: {best}\")\n",
    "\n",
    "    step = 0\n",
    "    while step < max_steps and best_fitness > 0:\n",
    "        neighbours = [(x, get_fitness(x)) for x in get_neighbours(current)]\n",
    "        best_neighbour, neighbour_fitness = min(neighbours, key=lambda i: i[1])\n",
    "        step += len(neighbours)        \n",
    "        fitness_values.extend([best_fitness] * len(neighbours))\n",
    "        if neighbour_fitness < fitness:\n",
    "            current = best_neighbour\n",
    "            fitness = neighbour_fitness\n",
    "            if fitness < best_fitness:\n",
    "                best = current[:]\n",
    "                best_fitness = fitness\n",
    "        else:\n",
    "            # Random restart if no neighbour is better\n",
    "            current = get_random_individual()\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",
    "\n",
    "    print(f\"Solution fitness after {step} fitness evaluations: {best_fitness}: {best}\")\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "max_steps = 10000\n",
    "fitness_values = []\n",
    "hillclimbing()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since there are no local optima, the hillclimber will easily find the solution, even without restarts. However, this can take a while, in particular if we use a larger input space:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "MAX = 100000\n",
    "MIN = -MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "hillclimbing()\n",
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Unless the randomly chosen initial point is already close to an optimal solution, the hillclimber is going to be hopeless in moving through the search space within a reasonable number of iterations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Alternating Variable Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The search problem represented by the `test_me` function has an easy fitness landscape with no local optima. However, it still takes quite long to reach the optimum, depending on where the random starting point lies in the search space. This is because the neighbourhood for real program inputs can be quite large, depending on the number of parameters, and even just the search space for each parameter individually can already be very large. In our example we restricted `MAX` and `MIN` to a very narrow range, but imagine doing this for 32 bit integers. Both these problems are addressed with an adapted version of our hillclimber known as the _Alternating Variable Method_, which differs from the hillclimber in two ways: \n",
    "1. Rather than considering the neighbourhood of all input parameters at once, we apply search to each parameter individually in turn\n",
    "2. Rather than taking only small steps of size 1, we allow larger jumps in the search space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's first consider the second aspect, larger jumps in the search space. The idea is to apply a _pattern_ search where we first decide on a direction in the search space to move, and then apply increasingly larger steps in that direction as long as the fitness improves. We only consider a single parameter, thus the \"direction\" simply refers to whether one increases or decreases this value. The function thus takes (1) the individual on which to perform the search, (2) a particular parameter we are considering, (3) the direction of the search, and (4) the starting fitness values. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def pattern_search(individual, parameter, direction, fitness):\n",
    "    print(f\"  {individual}, direction {direction}, fitness {fitness}\")\n",
    "\n",
    "    individual[parameter] = individual[parameter] + direction\n",
    "    new_fitness = get_fitness(individual)\n",
    "    if new_fitness < fitness:\n",
    "        fitness_values.append(new_fitness)\n",
    "        return pattern_search(individual, parameter, 2 * direction, new_fitness)\n",
    "    else:\n",
    "        # If fitness is not better we overshot. Undo last move, and return\n",
    "        fitness_values.append(fitness)\n",
    "        individual[parameter] = individual[parameter] - direction\n",
    "        return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For example, let's assume `y` is a large value (1000), and `x` is considerably smaller. For our example function, the optimal value for `x` would thus be at 2002. Applying the search to `x` we thus need to move in the positive direction (`1`), and the function will do this with increasing steps until it \"overshoots\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "x = [0, 1000]\n",
    "f = get_fitness(x)\n",
    "pattern_search(x, 0, 1, get_fitness(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If `x` is larger than `y` we would need to move in the other direction, and the search does this until it undershoots the target of 2002:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "x = [10000, 1000]\n",
    "f = get_fitness(x)\n",
    "pattern_search(x, 0, -1, get_fitness(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The AVM algorithm applies the pattern search as follows:\n",
    "1. Start with the first parameter\n",
    "2. Probe the neighbourhood of the parameter to find the direction of the search\n",
    "3. Apply pattern search in that direction\n",
    "4. Repeat probing + pattern search until no more improvement can be made\n",
    "5. Move to the next parameter, and go to step 2\n",
    "\n",
    "Like a regular hillclimber, the search may get stuck in local optima and needs to use random restarts. The algorithm is stuck if it probed all parameters in sequence and none of the parameters allowed a move that improved fitness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def probe_and_search(individual, parameter, fitness):\n",
    "    new_parameters = individual[:]\n",
    "    value = new_parameters[parameter]\n",
    "    new_fitness = fitness\n",
    "    # Try +1\n",
    "    new_parameters[parameter] = individual[parameter] + 1\n",
    "    print(f\"Trying +1 at fitness {fitness}: {new_parameters}\")\n",
    "    new_fitness = get_fitness(new_parameters)\n",
    "    if new_fitness < fitness:\n",
    "        fitness_values.append(new_fitness)\n",
    "        new_fitness = pattern_search(new_parameters, parameter, 2, new_fitness)\n",
    "    else:\n",
    "        # Try -1\n",
    "        fitness_values.append(fitness)\n",
    "        new_parameters[parameter] = individual[parameter] - 1\n",
    "        print(f\"Trying -1 at fitness {fitness}: {new_parameters}\")\n",
    "        new_fitness = get_fitness(new_parameters)\n",
    "        if new_fitness < fitness:\n",
    "            fitness_values.append(new_fitness)\n",
    "            new_fitness = pattern_search(new_parameters, parameter, -2, new_fitness)\n",
    "        else:\n",
    "            fitness_values.append(fitness)\n",
    "            new_parameters[parameter] = individual[parameter]\n",
    "            new_fitness = fitness\n",
    "            \n",
    "    return new_parameters, new_fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def avm():\n",
    "    current = get_random_individual()\n",
    "    fitness = get_fitness(current)\n",
    "    best, best_fitness = current[:], fitness\n",
    "    fitness_values.append(best_fitness)    \n",
    "    print(f\"Starting at fitness {best_fitness}: {current}\")\n",
    "\n",
    "    changed = True\n",
    "    while len(fitness_values) < max_steps and best_fitness > 0:\n",
    "        # Random restart\n",
    "        if not changed: \n",
    "            current = get_random_individual()\n",
    "            fitness = get_fitness(current)\n",
    "            fitness_values.append(fitness)\n",
    "        changed = False\n",
    "            \n",
    "        parameter = 0\n",
    "        while parameter < len(current):\n",
    "            print(f\"Current parameter: {parameter}\")\n",
    "            new_parameters, new_fitness = probe_and_search(current, parameter, fitness)\n",
    "            if current != new_parameters:\n",
    "                # Keep on searching\n",
    "                changed = True\n",
    "                current = new_parameters\n",
    "                fitness = new_fitness\n",
    "                if fitness < best_fitness:\n",
    "                    best_fitness = fitness\n",
    "                    best = current[:]\n",
    "            else:\n",
    "                parameter += 1\n",
    "\n",
    "    print(f\"Solution fitness {best_fitness}: {best}\")\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "avm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The pattern search even works efficiently if we increase the size of the search space to 64-bit numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "MAX = 2**32\n",
    "MIN = -MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "avm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Program Instrumentation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Deriving fitness functions is not quite so easy. Of course we could come up with an equation that captures the relation between the sides of the triangle, but then essentially we would need to reproduce the entire program logic again in a function, which certainly does not help generalising to other programs. For example, consider how the fitness function would look like if the comparison was not made on the input parameters, but on values derived through computation within the function under test. Ideally, what we would want is to be able to pick a point in the program and come up with a fitness function automatically that describes how close we are to reaching this point."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There are two central ideas in order to achieve this:\n",
    "\n",
    "- First, rather than trying to guess how close a program inputs gets to a target statement, we simply _run_ the program with the input and observe how close it actually gets.\n",
    "\n",
    "- Second, during the execution we keep track of distance estimates like the one we calculated for the `test_me` function whenever we come across conditional statements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to observe what an execution does, we need to *instrument* the program: We add new code immediately before or after the branching condition to keep track of the values observed and calculate the distance using these values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's first consider what is done here conceptually. We first define a global variable in which we will store the distance, so that we can access it after the execution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "distance = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now the instrumented version just has to update the global variable immediately before executing the branching condition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def test_me_instrumented(x, y):\n",
    "    global distance\n",
    "    distance = abs(x - 2 * (y + 1))\n",
    "    if x == 2 * (y + 1):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's try this out for a couple of example values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_me_instrumented(0, 0)\n",
    "distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "test_me_instrumented(22, 10)\n",
    "distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Using this instrumented version of `test_me()`, we can define a fitness function which simply calculates the distance for the condition being true:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(individual):\n",
    "    global distance\n",
    "    test_me_instrumented(*individual)\n",
    "    fitness = distance\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's try this on some example inputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness([0, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "When we have reached the target branch, the distance will be 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness([22, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "When implementing the instrumentation, we need to consider that the branching condition may have side-effects. For example, suppose that the branching condition were `x == 2 * foo(y)`, where `foo()` is a function that takes an integer as input. Naively instrumenting would lead to the following code:\n",
    "\n",
    "```\n",
    "    distance = abs(x - 2 * foo(y))\n",
    "\tif x == 2 * foo(y):\n",
    "\t...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Thus, the instrumentation would lead to `foo()` being executed *twice*. Suppose `foo()` changes the state of the system (e.g., by printing something, accessing the file system, changing some state variables, etc.), then clearly invoking `foo()` a second time is a bad idea. One way to overcome this problem is to _transform_ the conditions, rather than _adding_ tracing calls. For example, one can create temporary variables that hold the values necessary for the distance calculation and then use these in the branching condition:\n",
    "\n",
    "```\n",
    "\ttmp1 = x\n",
    "\ttmp2 = 2 * foo(y)\n",
    "\tdistance = compute_distance(tmp1, tmp2)\n",
    "\tif tmp1 == tmp2:\n",
    "\t...\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def evaluate_equals(op1, op2):\n",
    "    global distance\n",
    "    distance = abs(op1 - op2)\n",
    "    if distance == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now the aim would be to transform the program automatically such that it looks like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def test_me_instrumented(x, y):\n",
    "    tmp1 = x\n",
    "    tmp2 = 2 * (y + 1)    \n",
    "    if evaluate_equals(tmp1, tmp2):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Replacing comparisons automatically is actually quite easy in Python, using the abstract syntax tree (AST) of the program. In the AST, a comparison will typically be a tree node with an operator attribute and two children for the left-hand and right-hand operators. To replace such comparisons with a call to `calculate_distance()` one simply needs to replace the comparison node in the AST with a function call node, and this is what the `BranchTransformer` class does using a NodeTransformer from Python's `ast` module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import ast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class BranchTransformer(ast.NodeTransformer):\n",
    "\n",
    "    def visit_FunctionDef(self, node):\n",
    "        node.name = node.name + \"_instrumented\"\n",
    "        return self.generic_visit(node)\n",
    "\n",
    "    def visit_Compare(self, node):\n",
    "        if not isinstance(node.ops[0], ast.Eq):\n",
    "            return node\n",
    "\n",
    "        return ast.Call(func=ast.Name(\"evaluate_equals\", ast.Load()),\n",
    "                        args=[node.left,\n",
    "                              node.comparators[0]],\n",
    "                        keywords=[],\n",
    "                        starargs=None,\n",
    "                        kwargs=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The `BranchTransformer` parses a target Python program using the built-in parser `ast.parse()`, which returns the AST. Python provides an API to traverse and modify this AST. To replace the comparison with a function call we use an `ast.NodeTransformer`, which uses the visitor pattern where there is one `visit_*` function for each type of node in the AST. As we are interested in replacing comparisons, we override `visit_Compare`, where instead of the original comparison node we return a new node of type `ast.Func`, which is a function call node. The first parameter of this node is the name of the function `calculate_distance`, and the arguments are the two operands that our `calculate_distance` function expects.\n",
    "\n",
    "You will notice that we also override `visit_FunctionDef`; this is just to change the name of the method by appending `_instrumented`, so that we can continue to use the original function together with the instrumented one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The following code parses the source code of the `test_me()` function to an AST, then transforms it, and prints it out again (using the `to_source()` function from the `astor` library):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import inspect\n",
    "import ast\n",
    "import astor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "source = inspect.getsource(test_me)\n",
    "node = ast.parse(source)\n",
    "BranchTransformer().visit(node)\n",
    "\n",
    "# Make sure the line numbers are ok before printing\n",
    "node = ast.fix_missing_locations(node)\n",
    "print(astor.to_source(node))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To calculate a fitness value with the instrumented version, we need to compile the instrumented AST again, which is done using Python's `compile()` function. We then need to make the compiled function accessible, for which we first retrieve the current module from `sys.modules`, and then add the compiled code of the instrumented function to the list of functions of the current module using `exec`. After this, the `cgi_decode_instrumented()` function can be accessed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def create_instrumented_function(f):\n",
    "    source = inspect.getsource(f)\n",
    "    node = ast.parse(source)\n",
    "    node = BranchTransformer().visit(node)\n",
    "\n",
    "    # Make sure the line numbers are ok so that it compiles\n",
    "    node = ast.fix_missing_locations(node)\n",
    "\n",
    "    # Compile and add the instrumented function to the current module\n",
    "    current_module = sys.modules[__name__]\n",
    "    code = compile(node, filename=\"<ast>\", mode=\"exec\")\n",
    "    exec(code, current_module.__dict__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(test_me)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_me_instrumented(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test_me_instrumented(22, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The estimate for any relational comparison of two values is defined in terms of the _branch distance_. Our `evaluate_equals` function indeed implements the branch distance function for an equality comparison. To generalise this we need similar estimates for other types of relational comparisons. Furthermore, we also have to consider the distance to such conditions evaluating to false, not just to true. Thus, each if-condition actually has two distance estimates, one to estimate how close it is to being true, and one how close it is to being false. If the condition is true, then the true distance is 0; if the condition is false, then the false distance is 0. That is, in a comparison `a == b`, if `a` is smaller than `b`, then the false distance is `0` by definition. \n",
    "\n",
    "The following table shows how to calculate the distance for different types of comparisons:\n",
    "\n",
    "| Condition | Distance True | Distance False |\n",
    "| ------------- |:-------------:| -----:|\n",
    "| a == b      | abs(a - b) | 1 |\n",
    "| a != b      | 1          | abs(a - b) |\n",
    "| a < b       | b - a + 1  | a - b      |\n",
    "| a <= b      | b - a      | a - b + 1  |\n",
    "| a > b       | a - b + 1  | b - a      |\n",
    "\n",
    "\n",
    "Note that several of the calculations add a constant `1`. The reason for this is quite simple: Suppose we want to have `a < b` evaluate to true, and let `a = 27` and `b = 27`. The condition is not true, but simply taking the difference would give us a result of `0`. To avoid this, we have to add a constant value. It is not important whether this value is `1` -- any positive constant works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We generalise our `evaluate_equals` function to an `evaluate_condition` function that takes the operator as an additional parameter, and then implements the above table. In contrast to the previous `calculate_equals`, we will now calculate both, the true and the false distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def evaluate_condition(op, lhs, rhs):\n",
    "    distance_true = 0\n",
    "    distance_false = 0\n",
    "    if op == \"Eq\":\n",
    "        if lhs == rhs:\n",
    "            distance_false = 1\n",
    "        else:\n",
    "            distance_true = abs(lhs - rhs)\n",
    "\n",
    "    # ... code for other types of conditions\n",
    "\n",
    "    if distance_true == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's consider a slightly larger function under test. We will use the well known triangle example, originating in Glenford Meyer's classical Art of Software Testing book "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def triangle(a, b, c):\n",
    "    if a <= 0 or b <= 0 or c <= 0:\n",
    "        return 4 # invalid\n",
    "    \n",
    "    if a + b <= c or a + c <= b or b + c <= a:\n",
    "        return 4 # invalid\n",
    "    \n",
    "    if a == b and b == c:\n",
    "        return 1 # equilateral\n",
    "    \n",
    "    if a == b or b == c or a == c:\n",
    "        return 2 # isosceles\n",
    "    \n",
    "    return 3 # scalene"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The function takes as input the length of the three sides of a triangle, and returns a number representing the type of triangle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "triangle(4,4,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Adapting our representation is easy, we just need to correctly set the number of parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sig = signature(triangle)\n",
    "num_parameters = len(sig.parameters)\n",
    "num_parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For the `triangle` function, however, we have multiple if-conditions; we have to add instrumentation to each of these using `evaluate_condition`. We also need to generalise from our global `distance` variable, since we now have two distance values per branch, and potentially multiple branches. Furthermore, a condition might be executed multiple times within a single execution (e.g., if it is in a loop), so rather than storing all values, we will only keep the _minimum_ value observed for each condition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "distances_true = {}\n",
    "distances_false = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def update_maps(condition_num, d_true, d_false):\n",
    "    global distances_true, distances_false\n",
    "\n",
    "    if condition_num in distances_true.keys():\n",
    "        distances_true[condition_num] = min(distances_true[condition_num], d_true)\n",
    "    else:\n",
    "        distances_true[condition_num] = d_true\n",
    "\n",
    "    if condition_num in distances_false.keys():\n",
    "        distances_false[condition_num] = min(distances_false[condition_num], d_false)\n",
    "    else:\n",
    "        distances_false[condition_num] = d_false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we need to finish implementing the `evaluate_condition` function. We add yet another parameter to denote the ID of the branch we are instrumenting:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def evaluate_condition(num, op, lhs, rhs):\n",
    "    distance_true = 0\n",
    "    distance_false = 0\n",
    "\n",
    "    # Make sure the distance can be calculated on number and character\n",
    "    # comparisons (needed for cgi_decode later)\n",
    "    if isinstance(lhs, str):\n",
    "        lhs = ord(lhs)\n",
    "    if isinstance(rhs, str):\n",
    "        rhs = ord(rhs)\n",
    "\n",
    "    if op == \"Eq\":\n",
    "        if lhs == rhs:\n",
    "            distance_false = 1\n",
    "        else:\n",
    "            distance_true = abs(lhs - rhs)\n",
    "\n",
    "    elif op == \"Gt\":\n",
    "        if lhs > rhs:\n",
    "            distance_false = lhs - rhs\n",
    "        else:\n",
    "            distance_true = rhs - lhs + 1\n",
    "    elif op == \"Lt\":\n",
    "        if lhs < rhs:\n",
    "            distance_false = rhs - lhs\n",
    "        else:\n",
    "            distance_true = lhs - rhs + 1\n",
    "    elif op == \"LtE\":\n",
    "        if lhs <= rhs:\n",
    "            distance_false = rhs - lhs + 1\n",
    "        else:\n",
    "            distance_true = lhs - rhs\n",
    "    # ...\n",
    "    # handle other comparison operators\n",
    "    # ...\n",
    "\n",
    "    elif op == \"In\":\n",
    "        minimum = sys.maxsize\n",
    "        for elem in rhs.keys():\n",
    "            distance = abs(lhs - ord(elem))\n",
    "            if distance < minimum:\n",
    "                minimum = distance\n",
    "\n",
    "        distance_true = minimum\n",
    "        if distance_true == 0:\n",
    "            distance_false = 1\n",
    "    else:\n",
    "        assert False\n",
    "\n",
    "    update_maps(num, normalise(distance_true), normalise(distance_false))\n",
    "\n",
    "    if distance_true == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need to normalise branch distances since different comparisons will be on different scales, and this would bias the search. We will use the normalisation function defined in the previous chapter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def normalise(x):\n",
    "    return x / (1.0 + x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We also need to extend our instrumentation function to take care of all comparisons, and not just equality comparisons:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import ast\n",
    "class BranchTransformer(ast.NodeTransformer):\n",
    "\n",
    "    branch_num = 0\n",
    "\n",
    "    def visit_FunctionDef(self, node):\n",
    "        node.name = node.name + \"_instrumented\"\n",
    "        return self.generic_visit(node)\n",
    "\n",
    "    def visit_Compare(self, node):\n",
    "        if node.ops[0] in [ast.Is, ast.IsNot, ast.In, ast.NotIn]:\n",
    "            return node\n",
    "\n",
    "        self.branch_num += 1\n",
    "        return ast.Call(func=ast.Name(\"evaluate_condition\", ast.Load()),\n",
    "                        args=[ast.Num(self.branch_num - 1),\n",
    "                              ast.Str(node.ops[0].__class__.__name__),\n",
    "                              node.left,\n",
    "                              node.comparators[0]],\n",
    "                        keywords=[],\n",
    "                        starargs=None,\n",
    "                        kwargs=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can now take a look at the instrumented version of `triangle`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "source = inspect.getsource(triangle)\n",
    "node = ast.parse(source)\n",
    "transformer = BranchTransformer()\n",
    "transformer.visit(node)\n",
    "\n",
    "# Make sure the line numbers are ok before printing\n",
    "node = ast.fix_missing_locations(node)\n",
    "num_branches = transformer.branch_num\n",
    "\n",
    "print(astor.to_source(node))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To define an executable version of the instrumented triangle function, we can use our `create_instrumented_function` function again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(triangle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "triangle_instrumented(4, 4, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "distances_true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "distances_false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The branch distance functions above are defined only for atomic comparisons. However, in the `triangle` program all of the atomic comparisons are part of larger predicates, joined together by `and` and `or` connectors. \n",
    "\n",
    "For conjunctions the branch distance is defined such that the distance to make `A and B` true equals the sum of the branch distances for `A` and `B`, as both of the two conditions would need to be true. Similarly, the branch distance to make `A or B` true would be the _minimum_ of the two branch distances of `A` and `B`, as it suffices if one of the two conditions is true to make the entire expression true (and the false distance would be the sum of false distances of the conditions). For a negation `not A`, we can simply switch from the true distance to the false distance, or vice versa. Since predicates can consist of nested conditions, one would need to recursively calculate the branch distance.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Assume we want to find an input that covers the third if-condition, i.e., it produces a triangle where all sides have equal length. Considering the instrumented version of the triangle function we printed above, in order for this if-condition to evaluate to true we require conditions 0, 1, 2, 3, 4, and 5 to evaluate to false, and 6 and 7 to evaluate to true. Thus, the fitness function for this branch would be the sum of false distances for branches 0-5, and true distances for branches 6 and 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(x):\n",
    "    # Reset any distance values from previous executions\n",
    "    global distances_true, distances_false\n",
    "    distances_true  = {x: 1.0 for x in range(num_branches)}\n",
    "    distances_false = {x: 1.0 for x in range(num_branches)}\n",
    "\n",
    "    # Run the function under test\n",
    "    triangle_instrumented(*x)\n",
    "\n",
    "    # Sum up branch distances for our specific target branch\n",
    "    fitness = 0.0\n",
    "    for branch in [6, 7]:\n",
    "        fitness += distances_true[branch]\n",
    "\n",
    "    for branch in [0, 1, 2, 3, 4, 5]:\n",
    "        fitness += distances_false[branch]\n",
    "\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness([5,5,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "get_fitness(get_random_individual())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "MAX = 10000\n",
    "MIN = -MAX\n",
    "fitness_values = []\n",
    "max_gen = 1000\n",
    "hillclimbing()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "avm()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Besides the local search algorithms, we can also use evolutionary search in order to find solutions to our test generation problem. We therefore need to define the usual search operators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tournament_size = 3\n",
    "def tournament_selection(population):\n",
    "    candidates = random.sample(population, tournament_size)        \n",
    "    winner = min(candidates, key = lambda x: get_fitness(x))\n",
    "    return winner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "elite_size = 2\n",
    "def elitism_standard(population):\n",
    "    population.sort(key = lambda k: get_fitness(k))\n",
    "    return population[:elite_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def mutate(solution):\n",
    "    P_mutate = 1/len(solution)\n",
    "    mutated = solution[:]\n",
    "    for position in range(len(solution)):\n",
    "        if random.random() < P_mutate:\n",
    "            mutated[position] = int(random.gauss(mutated[position], 20))\n",
    "    return mutated"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "population_size = 20\n",
    "P_xover = 0.7\n",
    "max_gen = 100\n",
    "selection = tournament_selection\n",
    "crossover = singlepoint_crossover\n",
    "elitism = elitism_standard\n",
    "MAX = 1000\n",
    "MIN = -MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def ga():\n",
    "    population = [get_random_individual() for _ in range(population_size)]\n",
    "    best_fitness = sys.maxsize\n",
    "    for p in population:\n",
    "        fitness = get_fitness(p)\n",
    "        if fitness < best_fitness:\n",
    "            best_fitness = fitness\n",
    "            best_solution = p\n",
    "    print(f\"Iteration 0, best fitness: {best_fitness}\")\n",
    "\n",
    "    for iteration in range(max_gen):\n",
    "        fitness_values.append(best_fitness)\n",
    "        new_population = elitism(population)\n",
    "        while len(new_population) < len(population):\n",
    "            parent1 = selection(population)\n",
    "            parent2 = 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 = mutate(offspring1)\n",
    "            offspring2 = mutate(offspring2)\n",
    "            \n",
    "            new_population.append(offspring1)\n",
    "            new_population.append(offspring2)\n",
    "\n",
    "        population = new_population\n",
    "        for p in population:\n",
    "            fitness = get_fitness(p)\n",
    "            if fitness < best_fitness:\n",
    "                best_fitness = fitness\n",
    "                best_solution = p\n",
    "        print(f\"Iteration {iteration}, best fitness: {best_fitness}, size {len(best_solution)}\")\n",
    "\n",
    "    return best_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "ga()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We set `MAX` to a value as low as 1000, because the optimisation with our small mutational steps may take long to achieve that multiple values are equal, which some of the branches of the triangle program require (such as the one we are optimising for currently)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "MAX = 100000\n",
    "MIN = -MAX\n",
    "fitness_values = []\n",
    "ga()\n",
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Different mutation operators may yield different results: For example, rather than just adding random noise to the individual parameters, we can also probabilistically copy values from other parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mutate(solution):\n",
    "    P_mutate = 1/len(solution)\n",
    "    mutated = solution[:]\n",
    "    for position in range(len(solution)):\n",
    "        if random.random() < P_mutate:\n",
    "            if random.random() < 0.9:\n",
    "                mutated[position] = int(random.gauss(mutated[position], 20))\n",
    "            else:\n",
    "                mutated[position] = random.choice(solution)\n",
    "    return mutated"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's see the performance of the resulting algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "fitness_values = []\n",
    "MAX = 100000\n",
    "MIN = -MAX\n",
    "ga()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In our fitness function, we manually determined which branches need to evaluate which way, and how to sum up the fitness functions. In practice, this can be automated by combining the branch distance metric with the _approach level_, which was introduced (originally named approximation level) in this paper:\n",
    "\n",
    "Wegener, J., Baresel, A., & Sthamer, H. (2001). Evolutionary test environment for automatic structural testing. Information and software technology, 43(14), 841-854.\n",
    "\n",
    "The approach level calculates the distances of an execution from a target node in terms of graph distances on the control dependence graph. However, we will not cover the approach level in this chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Whole Test Suite Optimisation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Besides the question of how the best fitness function for a coverage goal looks like, there are some related questions: How much time should we spend on optimising for each coverage goal? It is possible that some coverage goals are infeasible (e.g., dead code, or infeasible branches), so any time spent on these is wasted, while it may be missing for other goals that are feasible but would need more time. Test cases typically cover multiple goals at the same time; even if a test is optimised for one specific line or branch, it may coincidentally cover others along the execution. Thus, the order in which we select coverage goals for optimisation may influence the overall result, and the number of tests we require. In principle, one way to address these issues would be by casting test generation as a multi-objective optimisation problem, and aiming to produce tests for _all_ coverage goals at the same time. However, there is an issue with this: Multi-objective algorithms like the ones we considered in the previous chapter typically work well on 2-3 objectives, but code will generally have many more coverage objectives, rendering classical multi-objective algorithms infeasible (Pareto-dominance happens rarely with higher numbers of objectives). We will therefore now consider some alternatives."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first alternative we consider is to switch our representation: Rather than optimising individual test cases for individual coverage objectives, we optimise entire test _suites_ to cover _all_ coverage objectives at the same time. Our encoding thus should describe multiple tests. But how many? This is very much problem specific. Thus, rather than hard coding the number of tests, we will only define an upper bound, and let the search decide what is the necessary number of tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "num_tests = 30"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_random_individual():\n",
    "    num = random.randint(1, num_tests)\n",
    "    return [[random.randint(MIN, MAX) for _ in range(num_parameters)] for _ in range(num)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "When applying mutation, we need to be able to modify individual tests as before. To keep things challenging, we will not use our optimised mutation that copies parameters, but aim to achieve the entire optimisation just using small steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def mutate_test(solution):\n",
    "    P_mutate = 1/len(solution)\n",
    "    mutated = solution[:]\n",
    "    for position in range(len(solution)):\n",
    "        if random.random() < P_mutate:\n",
    "            mutated[position] = min(MAX, max(MIN, int(random.gauss(mutated[position], MAX*0.01))))\n",
    "            \n",
    "    return mutated"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "However, modifying tests is only one of the things we can do when mutating our actual individuals, which consist of multiple tests. Besides modifying existing tests, we could also delete or add tests, for example like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def mutate_set(solution):\n",
    "    P_mutate = 1/len(solution)\n",
    "    mutated = []\n",
    "    for position in range(len(solution)):\n",
    "        if random.random() >= P_mutate:\n",
    "            mutated.append(solution[position][:])\n",
    "            \n",
    "    if not mutated:\n",
    "        mutated = solution[:]\n",
    "    for position in range(len(mutated)):\n",
    "        if random.random() < P_mutate:\n",
    "            mutated[position] = mutate_test(mutated[position])\n",
    " \n",
    "    ALPHA = 1/3\n",
    "    count = 1\n",
    "    while random.random() < ALPHA ** count:\n",
    "        count += 1\n",
    "        mutated.append([random.randint(MIN, MAX) for _ in range(num_parameters)])\n",
    "    \n",
    "    return mutated"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "With a certain probability, each of the tests can be removed from a test suite; similarly, each remaining test may be mutated like we mutated tests previously. Finally, with a probability `ALPHA` we insert a new test; if we do so, we insert another one with probability `ALPHA`$^2$, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "When crossing over two individuals, they might have different length, which makes choosing a crossover point difficult. For example, we might pick a crossover point that is longer than one of the parent chromosomes, and then what do we do? A simple solution would be to pick two different crossover points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def variable_crossover(parent1, parent2):\n",
    "    pos1 = random.randint(1, len(parent1))\n",
    "    pos2 = random.randint(1, len(parent2))\n",
    "    offspring1 = parent1[:pos1] + parent2[pos2:]\n",
    "    offspring2 = parent2[:pos2] + parent1[pos1:]\n",
    "    return (offspring1, offspring2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To see this works, we need to define the fitness function. Since we want to cover _everything_ we simply need to make sure that every single branch is covered at least once in a test suite. A branch is covered if its minimum branch distance is 0; thus, if everything is covered, then the sum of minimal branch distances should be 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There is one special case: If an if-statement is executed only once, then optimising the true/false distance may lead to a suboptimal, oscillising evolution. We therefore also count how often each if-condition was executed. If it was only executed once, then the fitness value for that branch needs to be higher than if it was executed twice. For this, we extend our `update_maps` function to also keep track of the execution count:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "condition_count = {}\n",
    "def update_maps(condition_num, d_true, d_false):\n",
    "    global distances_true, distances_false, condition_count\n",
    "\n",
    "    if condition_num in condition_count.keys():\n",
    "        condition_count[condition_num] = condition_count[condition_num] + 1\n",
    "    else:\n",
    "        condition_count[condition_num] = 1\n",
    "        \n",
    "    if condition_num in distances_true.keys():\n",
    "        distances_true[condition_num] = min(\n",
    "            distances_true[condition_num], d_true)\n",
    "    else:\n",
    "        distances_true[condition_num] = d_true\n",
    "\n",
    "    if condition_num in distances_false.keys():\n",
    "        distances_false[condition_num] = min(\n",
    "            distances_false[condition_num], d_false)\n",
    "    else:\n",
    "        distances_false[condition_num] = d_false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The actual fitness function now is the sum of minimal distances after all tests have been executed. If an if-condition was not executed at all, then the true distance and the false distance will be 1, resulting in a sum of 2 for the if-condition. If the condition was covered only once, we set the fitness to exactly 1. If the condition was executed more than once, then at least either the true or false distance has to be 0, such that in sum, true and false distances will be less than 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_fitness(x):\n",
    "    # Reset any distance values from previous executions\n",
    "    global distances_true, distances_false, condition_count\n",
    "    distances_true =  {x: 1.0 for x in range(num_branches)}\n",
    "    distances_false = {x: 1.0 for x in range(num_branches)}\n",
    "    condition_count = {x:   0 for x in range(num_branches)}\n",
    "\n",
    "    # Run the function under test\n",
    "    for test in x:\n",
    "        triangle_instrumented(*test)\n",
    "\n",
    "    # Sum up branch distances\n",
    "    fitness = 0.0\n",
    "    for branch in range(num_branches):\n",
    "        if condition_count[branch] == 1:\n",
    "            fitness += 1\n",
    "        else:\n",
    "            fitness += distances_true[branch]\n",
    "            fitness += distances_false[branch]\n",
    "\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Before we run some experiments on this, let's make a small addition to our genetic algorithm: Since the size of individuals is variable it will be interesting to observe how this evolves. We'll capture the average population size in a separate list. Since the costs of evaluating fitness are no longer constant per individual but depend on the number of tests executed, we will also change our stopping criterion to the number of executed tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from statistics import mean\n",
    "\n",
    "length_values = []\n",
    "max_executions = 10000\n",
    "\n",
    "def ga():\n",
    "    population = [get_random_individual() for _ in range(population_size)]\n",
    "    best_fitness = sys.maxsize\n",
    "    tests_executed = 0\n",
    "    for p in population:\n",
    "        fitness = get_fitness(p)\n",
    "        tests_executed += len(p)\n",
    "        if fitness < best_fitness:\n",
    "            best_fitness = fitness\n",
    "            best_solution = p\n",
    "    while tests_executed < max_executions:\n",
    "        fitness_values.append(best_fitness)\n",
    "        length_values.append(mean([len(x) for x in population]))\n",
    "        new_population = elitism(population)\n",
    "        while len(new_population) < len(population):\n",
    "            parent1 = selection(population)\n",
    "            parent2 = 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 = mutate(offspring1)\n",
    "            offspring2 = mutate(offspring2)\n",
    "            \n",
    "            new_population.append(offspring1)\n",
    "            new_population.append(offspring2)\n",
    "            tests_executed += len(offspring1) + len(offspring2)\n",
    "\n",
    "        population = new_population\n",
    "        for p in population:\n",
    "            fitness = get_fitness(p)\n",
    "            if fitness < best_fitness:\n",
    "                best_fitness = fitness\n",
    "                best_solution = p\n",
    "    print(f\"Best fitness: {best_fitness}, size {len(best_solution)}\")\n",
    "\n",
    "    return best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since we now have all the operators we need in place, let's run a first experiment aiming to achieve 100% coverage on the triangle example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "max_executions = 1000000\n",
    "MAX = 1000\n",
    "MIN = -MAX\n",
    "crossover = variable_crossover\n",
    "selection = tournament_selection\n",
    "elitism   = elitism_standard \n",
    "mutate    = mutate_set\n",
    "tournament_size = 4\n",
    "population_size = 50\n",
    "fitness_values = []\n",
    "length_values = []\n",
    "ga()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(fitness_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The plot shows iterations of the genetic algorithm on the x-axis. Very likely, the result likely isn't great. But why? Let's look at the average population length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(length_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "What you can see here is a phenomenon called _bloat_: Individuals grow in size through mutation and crossover, and the search has no incentive to reduce their size (adding a test can never decrease coverage; removing a test can). As a result the individuals just keep growing, and quickly eat up all the available resources for the search. How to deal with this problem will be covered in the next chapter."
   ]
  }
 ],
 "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"
  },
  "rise": {
   "enable_chalkboard": true,
   "scroll": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}