Genetic_Algorithms_with_DEAP_ipynb.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/JosephBless/Deep-Learning-Colab/blob/main/Genetic_Algorithms_with_DEAP_ipynb.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0V9I6y4g9zrj"
      },
      "source": [
        "# Genetic Algorithms with DEAP\n",
        "\n",
        "From [The One Max Problem](https://deap.readthedocs.io/en/master/examples/ga_onemax.html)\n",
        "\n",
        "Updated by Kevin Sikorski for Python 3.6 and [Base2 MLI](https://github.com/base2solutions/mli)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SNWdHmYGcHxs"
      },
      "source": [
        "# Genetic Algorithms\n",
        "Genetic Algorithms have been used for years, but they have never really been the HOT NEW thing in AI.  They tend to fare better relative to other approaches where you don't have an easily computable derivative, such as you would have with gradient descent, and with discrete parameters.  They are parallelizable, and they are pretty easy to code and understand.\n",
        "\n",
        "Genetic Algorithms are a sort of random search, where you start with a random population of individuals with random \"genetic code\".  By iterating the learning algorithm, the individuals' genetic code undergoes mutation and crossover resulting in - on average - a slightly more fit next generation of individuals.  There are countless variations on how this is done (Do we keep some of the most fit individuals from the last generation?  What is your mutation rate?  Who gets to mate with whom?  Do we vary the number of individuals?).  These mutation and crossover operations serve to pull our solutions out of local minima and visit far flung areas of the solution space, all while hopefully conserving the parts of the solution that perform well.\n",
        "\n",
        "\n",
        "<figure>\n",
        "<table border = 5 align = center>\n",
        "<tr>\n",
        "<td width=22%>\n",
        "    <img src=\"https://raw.githubusercontent.com/KevinSikorskiBase2S/machine-learning-intro-workshop/master/images/zebroo.jpg\" />\n",
        "</td>\n",
        "<td width=22%>\n",
        "    <img src=\"https://raw.githubusercontent.com/KevinSikorskiBase2S/machine-learning-intro-workshop/master/images/searrot.png\" />\n",
        "</td>\n",
        "<td width=22%>\n",
        "    <img src=\"https://raw.githubusercontent.com/KevinSikorskiBase2S/machine-learning-intro-workshop/master/images/squsky.jpg\" />\n",
        "</td>\n",
        "<td width=22%>\n",
        "    <img src=\"https://raw.githubusercontent.com/KevinSikorskiBase2S/machine-learning-intro-workshop/master/images/rhinen.jpg\" />\n",
        "</td>\n",
        "</table>\n",
        "<center>\n",
        "  <figcaption>Non-optimal individuals from Genetic Algorithm experiments found on a google image search.</figcaption>     \n",
        "  </center>\n",
        "</figure>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BSZa4hf3qyRO"
      },
      "source": [
        "# Terminology\n",
        "\n",
        "### Individual\n",
        "Genetic Algorithms make use of an analogy to genetics, where we use a population of randomly generated individuals, each with some genetic code.  This code represents a potential solution to the problem.  The representation of the solution depends on the particular problem we are addressing, but it generally consists of a data structure.  It could contain one or more strings like \"ACGTCACTCGGATGC\" if we are dealing with DNA, real-valued data if we are dealing with vectors, arbitrary and mutually-exclusive concepts like \"January\", \"February\", and \"December\", or anything else.\n",
        "\n",
        "### Fitness\n",
        "Since these solutions are chosen at random, some are better than others.  We need to be able to evaluate how good a particular solution is.  We do this by defining a fitness function (called an evaulation function in the example below).  This takes in an individual or its genetic code, and outputs a scalar number that allows us to compare fitness between individuals.\n",
        "\n",
        "### Mutation\n",
        "In the real world, genetic code mutates due to random events like cosmic rays and nuclear decay, or due to random transcription errors.  We simulate this in genetic algorithms with a mutation rate.  Here with a low probability, we randomly change one or more elements of the genetic code of an individual.  This might be changing a number encoded in it (either a little or a lot), flipping a bit in a string, or randomizing the month in a date-time field.\n",
        "\n",
        "### Crossover\n",
        "In the real world, mating between individuals produces offspring with genetic code that is a combination of the parents.  This is simulated with crossover.  In the first diagram below we show two parents at the top, each with different genetic material.  Two offspring are shown below, each the product of crossover.  The parent's genetic code is broken at a randomly selected point.  The right half of the red parent is attached to the left half of the blue parent to produce one offspring's genes; the remaining pieces are similarly concatenated to make the other offspring's genes.\n",
        "\n",
        "Geometrically, you can think of crossover as a projection of one parent's genetic code to a random plane in the search space that contains the other parent's genetic code.  (This plane will also be aligned with one of the basis vectors of the genetic code.)  The Crossover as projection diagram below shows an example involving two parents in magenta with genetic code (0,0) and (1,1).  When crossover occurs, we produce the cyan individuals with genetic code (0,1) and (1,0) by taking the first element from one parent and the second element from the second parent.  Or phrased geometrically, by projecting one parent's point to the Y-axis (the basis vector for the second element of the genetic code), and the the other parent's point to the X-axis."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NCUOiAsN2uhD"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "\n",
        "plt.subplot(1,2,1)\n",
        "plt.title(\"Crossover\")\n",
        "fig=plt.plot((0, 1), (5, 5), linewidth=5, color='b')\n",
        "fig=plt.plot((0, 1), (4, 4), linewidth=5, color='r')\n",
        "fig=plt.plot((0, 0.6), (2, 2), linewidth=5, color='b')\n",
        "fig=plt.plot((0, 0.6), (1, 1), linewidth=5, color='r')\n",
        "fig=plt.plot((0.6, 1), (1, 1), linewidth=5, color='b')\n",
        "fig=plt.plot((0.6, 1), (2, 2), linewidth=5, color='r')\n",
        "\n",
        "plt.subplot(1,2,2)\n",
        "plt.scatter([0, 1], [0,1], color='m', lw=3)\n",
        "plt.scatter([1, 0], [0,1], color='c', lw=3)\n",
        "plt.title(\"Crossover as projection\")\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "shLyVA2oQhsS"
      },
      "source": [
        "Depending on the type of information being stored in your genetic code, you may need to take special care.  For example, consider the Traveling Salesman Problem.  This problem involes finding the shortest path by which a salesman can visit a list of cities, visiting each precisely once.  Mutations that cause the same city to appear twice are of course illegal.  Crossovers similarly need to be done with care."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MQo4tsn4-PoP"
      },
      "source": [
        "# One Max Problem\n",
        "This example will help new users to overview some of the DEAP framework’s possibilities and illustrate the potential of evolutionary algorithms in general. The problem itself is both very simple and widely used in the evolutionary computational community. We will create a population of individuals consisting of integer vectors randomly filled with 0 and 1. Then we let our population evolve until one of its members contains only 1 and no 0 anymore.\n",
        "\n",
        "## Setting Things Up\n",
        "In order to solve the One Max problem, we need a bunch of ingredients. First we have to define our individuals, which will be lists of integer values, and to generate a population using them. Then we will add some functions and operators taking care of the evaluation and evolution of our population and finally put everything together in script.\n",
        "\n",
        "But first of all, we need to import some modules."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "n1TlDbXM9YBy"
      },
      "source": [
        "import random\n",
        "\n",
        "!pip install deap\n",
        "from deap import base\n",
        "from deap import creator\n",
        "from deap import tools\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5j5Cu17P-Wf9"
      },
      "source": [
        "## Creator\n",
        "Since the actual structure of the required individuals in genetic algorithms does strongly depend on the task at hand, DEAP does not contain any explicit structure. It will rather provide a convenient method for creating containers of attributes, associated with fitnesses, called the deap.creator. Using this method we can create custom individuals in a very simple way.\n",
        "\n",
        "The creator is a class factory that can build new classes at run-time. It will be called with first the desired name of the new class, second the base class it will inherit, and in addition any subsequent arguments you want to become attributes of your class. This allows us to build new and complex structures of any type of container from lists to n-ary trees."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZFeTYVBn-XCY"
      },
      "source": [
        "creator.create(\"FitnessMax\", base.Fitness, weights=(1.0,))\n",
        "creator.create(\"Individual\", list, fitness=creator.FitnessMax)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vi1UTZS1-cdv"
      },
      "source": [
        "First we will define the class FitnessMax. It will inherit the Fitness class of the deap.base module and contain an additional attribute called weights. Please mind the value of weights to be the tuple (1.0,). This way we will be maximizing a single objective fitness. We can’t repeat it enough, in DEAP single objectives is a special case of multi objectives.\n",
        "\n",
        "Next we will create the class Individual, which will inherit the class list and contain our previously defined FitnessMax class in its fitness attribute. Note that upon creation all our defined classes will be part of the creator container and can be called directly.\n",
        "\n",
        "## Toolbox\n",
        "Now we will use our custom classes to create types representing our individuals as well as our whole population.\n",
        "\n",
        "All the objects we will use on our way, an individual, the population, as well as all functions, operators, and arguments will be stored in a DEAP container called Toolbox. It contains two methods for adding and removing content, register() and unregister()."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HS3iXNSW-gS8"
      },
      "source": [
        "toolbox = base.Toolbox()\n",
        "# Attribute generator\n",
        "toolbox.register(\"attr_bool\", random.randint, 0, 1)\n",
        "# Structure initializers\n",
        "toolbox.register(\"individual\", tools.initRepeat, creator.Individual,\n",
        "    toolbox.attr_bool, 100)\n",
        "toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JO9v6Wx_-jam"
      },
      "source": [
        "In this code block we register a generation function toolbox.attr_bool() and two initialization ones individual() and population(). toolbox.attr_bool(), when called, will draw a random integer between 0 and 1. The two initializers, on the other hand, will instantiate an individual or population.\n",
        "\n",
        "The registration of the tools to the toolbox only associates aliases to the already existing functions and freezes part of their arguments. This allows us to fix an arbitrary amount of argument at certain values so we only have to specify the remaining ones when calling the method. For example, the attr_bool() generator is made from the randint() function that takes two arguments a and b, with a <= n <= b, where n is the returned integer. Here, we fix a = 0 and b = 1.\n",
        "\n",
        "Our individuals will be generated using the function initRepeat(). Its first argument is a container class, in our example the Individual one we defined in the previous section. This container will be filled using the method attr_bool(), provided as second argument, and will contain 100 integers, as specified using the third argument. When called, the individual() method will thus return an individual initialized with what would be returned by calling the attr_bool() method 100 times. Finally, the population() method uses the same paradigm, but we don’t fix the number of individuals that it should contain.\n",
        "\n",
        "##The Evaluation Function\n",
        "The evaluation function is pretty simple in our example. We just need to count the number of ones in an individual."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "s9XjIzai-lvs"
      },
      "source": [
        "def evalOneMax(individual):\n",
        "    return sum(individual),\n",
        "\n",
        "print(evalOneMax([0,0,0,0]))\n",
        "print(evalOneMax([0,1,0,1]))\n",
        "print(evalOneMax([1,1,1,1]))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vhwe8gl3-nVT"
      },
      "source": [
        "## The Genetic Operators\n",
        "Within DEAP there are two ways of using operators. We can either simply call a function from the tools module or register it with its arguments in a toolbox, as we have already seen for our initialization methods. The most convenient way, however, is to register them in the toolbox, because this allows us to easily switch between the operators if desired. The toolbox method is also used when working with the algorithms module. See the [One Max Problem: Short Version](https://deap.readthedocs.io/en/master/examples/ga_onemax_short.html#short-ga-onemax) for an example.\n",
        "\n",
        "Registering the genetic operators required for the evolution in our One Max problem and their default arguments in the toolbox is done as follows."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AoLoTIuj-ppU"
      },
      "source": [
        "toolbox.register(\"evaluate\", evalOneMax)\n",
        "toolbox.register(\"mate\", tools.cxTwoPoint)\n",
        "toolbox.register(\"mutate\", tools.mutFlipBit, indpb=0.05)\n",
        "toolbox.register(\"select\", tools.selTournament, tournsize=3)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pzSud0CF-q_y"
      },
      "source": [
        "The evaluation will be performed by calling the alias evaluate. It is important to not fix its argument in here. We will need it later on to apply the function to each separate individual in our population. The mutation, on the other hand, needs an argument to be fixed (the independent probability of each attribute to be mutated indpb).\n",
        "\n",
        "## Evolving the Population\n",
        "Once the representation and the genetic operators are chosen, we will define an algorithm combining all the individual parts and performing the evolution of our population until the One Max problem is solved.\n",
        "\n",
        "## Creating the Population\n",
        "First of all, we need to actually instantiate our population. But this step is effortlessly done using the population() method we registered in our toolbox earlier on."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "F30uZtcp-u79"
      },
      "source": [
        "pop = toolbox.population(n=300)\n",
        "\n",
        "# Evaluate the entire population\n",
        "fitnesses = list(map(toolbox.evaluate, pop))\n",
        "for ind, fit in zip(pop, fitnesses):\n",
        "    ind.fitness.values = fit\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bUw_9gTr-wjK"
      },
      "source": [
        "**pop** will be a list composed of 300 individuals. Since we left the parameter **n** open during the registration of the population() method in our toolbox, we are free to create populations of arbitrary size.\n",
        "\n",
        "Before we go on, this is the time to define some constants we will use later on."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Dx5L38zU-x1H"
      },
      "source": [
        "# CXPB  is the probability with which two individuals\n",
        "#       are crossed\n",
        "#\n",
        "# MUTPB is the probability for mutating an individual\n",
        "CXPB, MUTPB = 0.5, 0.2"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V1QT9wKN-2E8"
      },
      "source": [
        "## Evaluating the Population\n",
        "The next thing to do is to evaluate our brand new population.  We map() the evaluation function to every individual and then assign their respective fitness. Note that the order in fitnesses and population is the same.\n",
        "\n",
        "The evolution of the population is the final step we have to accomplish. Recall, our individuals consist of 100 integer numbers and we want to evolve our population until we got at least one individual consisting of only 1s and no 0s. So all we have to do is to obtain the fitness values of the individuals!\n",
        "\n",
        "To check the performance of the evolution, we will calculate and print the minimal, maximal, and mean values of the fitnesses of all individuals in our population as well as their standard deviations."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PtryFa_TJxWa"
      },
      "source": [
        "def findFitness():\n",
        "    fits = [ind.fitness.values[0] for ind in pop]\n",
        "\n",
        "    length = len(pop)\n",
        "    mean = sum(fits) / length\n",
        "    sum2 = sum(x*x for x in fits)\n",
        "    std = abs(sum2 / length - mean**2)**0.5\n",
        "\n",
        "    print(\"  Min %s\" % min(fits))\n",
        "    print(\"  Max %s\" % max(fits))\n",
        "    print(\"  Avg %s\" % mean)\n",
        "    print(\"  Std %s\" % std)\n",
        "    return fits\n",
        "\n",
        "fits=findFitness()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Dfh6gnNQ-5Wy"
      },
      "source": [
        "## Mating and Mutation\n",
        "\n",
        "In genetic algorithms, evolution occurs via either mutation or crossover, both of which happen (or don't happen) randomly.  In mutation, we change one or more of the genes of one of our individuals.  In cross-over, two individuals are mated to mix their genes.\n",
        "\n",
        "The crossover (or mating) and mutation operators, provided within DEAP, usually take respectively 2 or 1 individual(s) as input and return 2 or 1 modified individual(s). In addition they modify those individuals within the toolbox container and we do not need to reassign their results.\n",
        "\n",
        "We will perform both the crossover (mating) and the mutation of the produced children with a certain probability of CXPB and MUTPB. The del statement will invalidate the fitness of the modified offspring."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M6ssqRncEIDN"
      },
      "source": [
        "def mateAndMutate(offspring):\n",
        "    for child1, child2 in zip(offspring[::2], offspring[1::2]):\n",
        "        if random.random() < CXPB:\n",
        "            toolbox.mate(child1, child2)\n",
        "            del child1.fitness.values\n",
        "            del child2.fitness.values\n",
        "\n",
        "    for mutant in offspring:\n",
        "        if random.random() < MUTPB:\n",
        "            toolbox.mutate(mutant)\n",
        "            del mutant.fitness.values\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mEOPfK92--q-"
      },
      "source": [
        "## The Main Loop\n",
        "\n",
        "This will creates an offspring list, which is an exact copy of the selected individuals. The toolbox.clone() method ensure that we don’t use a reference to the individuals but an completely independent instance. This is of utter importance since the genetic operators in toolbox will modify the provided objects in-place.\n",
        "\n",
        "We then mutate and mate the individuals to find the next generation of individuals.  We evaluate them, and continue until one of our individuals evolves to be the perfect organism (fitness of 100 or more), or until the number of generations reaches 1000.\n",
        "\n",
        "At each generation, we output some statistics about that generation's population, as well as a graph of the genetic material for an arbitrary individual.  A 0 in the genetic material is drawn in red, and a 1 is drawn in blue."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Df-rsxoX-6vj"
      },
      "source": [
        "import numpy as np\n",
        "# Variable keeping track of the number of generations\n",
        "g = 0\n",
        "\n",
        "# Begin the evolution\n",
        "while max(fits) < 100 and g < 1000:\n",
        "    # A new generation\n",
        "    g = g + 1\n",
        "    print(\"-- Generation %i --\" % g)\n",
        "    # Select the next generation individuals\n",
        "    offspring = toolbox.select(pop, len(pop))\n",
        "    # Clone the selected individuals\n",
        "    offspring = list(map(toolbox.clone, offspring))\n",
        "\n",
        "    # Apply crossover and mutation on the offspring\n",
        "    mateAndMutate(offspring)\n",
        "\n",
        "    # Evaluate the individuals with an invalid fitness\n",
        "    invalid_ind = [ind for ind in offspring if not ind.fitness.valid]\n",
        "    fitnesses = map(toolbox.evaluate, invalid_ind)\n",
        "    for ind, fit in zip(invalid_ind, fitnesses):\n",
        "        ind.fitness.values = fit\n",
        "    pop[:] = offspring\n",
        "\n",
        "    # print statistics on our updated population\n",
        "    fits=findFitness()\n",
        "\n",
        "    # plot an arbitrary organism\n",
        "    x = [i/100 for i in range(len(pop[0]))]\n",
        "    y = [1 for i in x]\n",
        "    colors = ['r' if pop[0][i]==0 else 'b' for i in range(len(pop[0]))]\n",
        "    plt.scatter(x, y, c=colors, alpha=0.5)\n",
        "    plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "STsQs-Hg_JaT"
      },
      "source": [
        "This evolution will now run until at least one of the individuals will be filled with 1s exclusively or we run out of time (generations = 1000).\n",
        "\n",
        "A [Statistics](https://deap.readthedocs.io/en/master/api/tools.html#deap.tools.Statistics) object is available within DEAP to facilitate the gathering of the evolution’s statistics. See the [One Max Problem: Short Version](https://deap.readthedocs.io/en/master/examples/ga_onemax_short.html#short-ga-onemax) for an example.\n",
        "\n",
        "The complete source code of this example: [examples/ga/onemax](https://github.com/DEAP/deap/blob/99223a884d224cfc0f5cdf779e18d4eae030e788/examples/ga/onemax.py)."
      ]
    }
  ]
}