GeneticAlgorithmExample.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/GeneticAlgorithmExample.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Or99-_Bl0T4X"
      },
      "source": [
        "In this notebook, I will be training a genetic algorithm to reproduce a single image. I have never used genetic algorithms before, so I thought I would start with a toy problem. The resources posts I found helpful in learning the theory and implementation of these algorithms are below, but the code is my own.\n",
        "* [Genetic Algorithms: A Tutorial](http://svitvasad.ac.in/svit/data/mca/cosmos/ga.pdf)\n",
        "* [Introduction to Genetic Algorithms](https://blog.floydhub.com/introduction-to-genetic-algorithms/)  \n",
        "* [Introduction to Genetic Algorithm & their application in data science](https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/)\n",
        "* [Reproducing Images using a Genetic Algorithm with Python](https://heartbeat.fritz.ai/reproducing-images-using-a-genetic-algorithm-with-python-91fc701ff84)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "paW4vFSjLAcH"
      },
      "source": [
        "# Background  \n",
        "\n",
        "Genetic Algorithms (GAs) are a subset of Evolutionary Algorithms, which are a subset of Guided Random Search Techniques. They are a very rough approximation of the mechanisms and principles that govern biological reproduction and evolution. They an attractive candidate for many different types of optimization problems because they have been shown to balance exploration -- via the fitness and selection functions -- and exploitation -- through the randomness introduced by mutations and crossover -- quite elegantly, in contrast to other optimization algorithms such as neural networks. In particular, the randomness incorporated into these algorithms allows it to escape local minima. The pseudo-code of a very basic genetic algorithm is written below.\n",
        "  \n",
        "## Pseudo-code  \n",
        "**function** GeneticAlgorithm(n_individuals, n_genes, desired_fitness)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *returns* an individual with fitness >= desired_fitness\n",
        "  \n",
        "&nbsp;   \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; generation = 0    \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; population = init_population(n_individuals, n_genes)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; fitness_vals = evaluate_fitness(population)  \n",
        "&nbsp;  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **while** max(fitness_vals) < desired_fitness  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; parents = select(population, fitness_vals)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; children = reproduction(parents)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; children = mutate(children, mutation_rate)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; population = make_next_generation(children, parents)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; fitness_vals = evaluate_fitness(population)  \n",
        "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; generation = generation + 1"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uoqL417seP6o"
      },
      "source": [
        "# Defining the Functions  \n",
        "Now that the rough structure of a basic GA has been illustrated, and we have loaded in an image we want to reproduce and imported python libraries, we are now ready to define the functions needed for the GA."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KTe7ccAle4Nu"
      },
      "source": [
        "### Initializing the Population  \n",
        "Typically each individual is initialized with random values from some set of numbers. Since we are trying to reproduce an image, we chose random values from the range [0, 255]."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tFPy7EDLfFzS"
      },
      "source": [
        "def init_population(n_individuals, n_genes):\n",
        "    return np.random.rand(n_individuals, n_genes) * 255  # population is an array where each row is an individual"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "u4rdj-sTY6Zi"
      },
      "source": [
        "### Fitness Function\n",
        "Perhaps the most important aspect of a GA is the choice of fitness function. As the mathematician and creator of Error-Correcting Codes Richard Hamming once said, \"You get what you measure.\", where he was basically highlighting the fact that scientists and engineers need to be greatly aware of the influences our choice of metric will have on our results. Since we are trying to reproduce a single image with our algorithm, we will need some way of measuring the difference between the actual image and each individual's reproduction of the image. Possible methods to compute the similarity between images are Signal-to-Noise Ratio (SNR), Peak SNR (PSNR), Euclidean Distance, L1-Distance, and Structural Similarity Index (SSIM), to name a few. Here we use the SSIM metric based on a number of reasons: 1) its values are interpretable and range from -1 to 1, which makes it easy to determine a threshold for stopping the model, 2) it is based off of visual perception and incorporates different perceptual phenomena such as luminance masking, and 3) captures differences in local parts of the image well because it compares small patches with a sliding window.  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ndAvYDP12-Kd"
      },
      "source": [
        "# goint to scale each individual's values between 0 and 255 each time its fitness is evaluated\n",
        "def scale(img):\n",
        "    return (img - np.amin(img)) / (np.amax(img) - np.amin(img) + 1e-6) * 255"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "STGVTpu7XZW1"
      },
      "source": [
        "def evaluate_fitness(population, real_img):\n",
        "    fitness_vals = []\n",
        "    real_imgh, real_imgw = real_img.shape\n",
        "\n",
        "    # loop through each individual and get its SSIM value\n",
        "    for individual in population:\n",
        "        individual_img = individual.reshape([real_imgh, real_imgw])\n",
        "        individual_img = scale(individual_img)\n",
        "        fitness = ssim(real_img, individual_img, win_size=7, data_range=255)\n",
        "        fitness_vals.append(fitness)\n",
        "\n",
        "    return fitness_vals"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RdAunA20rNxa"
      },
      "source": [
        "### Parent Selection  \n",
        "Central to the idea of evolution is the fact that the species with low fitness values (as determined by the environment in actual evolution) do not survive and reproduce. Thus, we must have a heuristic to select which individuals from our population will reproduce after their fitness has been evaluated. Here, perhaps in a naive fashion, we keep half of the individuals with the highest fitness values and discard the rest. There are a number of different ways to do this selection process that have been introduced over the years."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Lln5iEDTgHWy"
      },
      "source": [
        "def select(population, fitness_vals):\n",
        "    n_inds = population.shape[0]  # number of individuals\n",
        "    n_discard = n_inds // 2  # lower half of population to discard\n",
        "\n",
        "    # sort the population based on the corresponding fitness values\n",
        "    sorted_inds = [ind for _, ind in sorted(zip(fitness_vals, list(range(len(fitness_vals)))), key=lambda pair: pair[0])]\n",
        "\n",
        "    # return the population with those rows removed\n",
        "    return np.delete(population, sorted_inds[:n_discard], axis=0)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e_AlDioHtSAb"
      },
      "source": [
        "### Reproduction  \n",
        "Now that we have selected a number of parents allowed to reproduce, we can allow the remaining parents to reproduce with each other. Here, we select all possible combinations of the remaining parents, which will reproduce by randomly taking 50% of the genes from one parent and the other 50% from the other to create a child."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9mMGn1P0gai3"
      },
      "source": [
        "def reproduction(parents):\n",
        "    n_parents, n_genes = parents.shape[0], parents.shape[1]\n",
        "\n",
        "    # get all combinations of parents\n",
        "    combinations = [[p1, p2] for p1 in range(n_parents-1, 0, -1) for p2 in range(p1-1, -1, -1)]\n",
        "    #combinations += [[p1, p2] for p1 in range(n_parents-1) for p2 in range(p1+1, n_parents)]\n",
        "\n",
        "    # select some of these combinations randomly for reproduction\n",
        "    comb_sample = list(np.random.choice(len(combinations), size=(n_parents), replace=True))\n",
        "    combinations = [comb for i, comb in enumerate(combinations) if i in comb_sample]\n",
        "\n",
        "    # initialize an array to fill the children with\n",
        "    children = np.zeros(parents.shape)\n",
        "\n",
        "    for i_comb, comb in enumerate(combinations):\n",
        "        parent1, parent2 = parents[comb[0], :], parents[comb[1], :]\n",
        "\n",
        "        # mask each parent's genes randomly with an equal probability\n",
        "        mask1 = np.float32(np.random.rand(n_genes) > 0.5)\n",
        "        mask2 = np.float32(mask1 == 0)\n",
        "        parent1, parent2 = parent1 * mask1, parent2 * mask2\n",
        "\n",
        "        # make the new child and add it to the children array\n",
        "        children[i_comb, :] = parent1 + parent2\n",
        "\n",
        "    return children"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lb-6rudv06bA"
      },
      "source": [
        "### Mutation  \n",
        "Most mutations in biology are detrimental to the individual who has them. There are a number of mechanisms that allows a cell to detect and fix mutations. However, there are still some that go undetected or that can't be repaired. In the grand scale of evolutionary time, mutations are sometimes helpful by introducing an advantageous trait into the population. Here, we use two different methods of mutation: 1) we add random values taken from the normal distribution to each gene, and 2) we randomly drop out a very small percentage of genes each generation."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HclsXfr1gald"
      },
      "source": [
        "def mutate(children):\n",
        "    n_children, n_genes = children.shape\n",
        "\n",
        "    # add random noise mutation\n",
        "    mutations = np.random.randn(n_children, n_genes) * np.random.randint(0, 32, 1)[0]\n",
        "    children = children + mutations\n",
        "\n",
        "    # make the dropped-out ones the minimum value in the individual since they will be scaled later\n",
        "    min_vals = np.amin(children, 1)\n",
        "    mutation_map = np.float32(np.random.rand(n_children, n_genes) < 0.9999)\n",
        "    children *= mutation_map  # zero-out all the ones selected by mutation map\n",
        "    children += (min_vals * np.float32(mutation_map == 0).transpose()).transpose()\n",
        "\n",
        "    return children"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bKlWCdTW3Tb_"
      },
      "source": [
        "### Add Children to the Population  \n",
        "Here we add the children to the population with the remaining parents."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gWhq0ZudgaoL"
      },
      "source": [
        "def make_next_generation(parents, children):\n",
        "    return np.concatenate((parents, children), 0)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V6kZt62mXaSt"
      },
      "source": [
        "# Setting Up the Program  \n",
        "  \n",
        "First, let's import some python libraries and functions we will need."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cF5I3ETcX-ts"
      },
      "source": [
        "import numpy as np\n",
        "from skimage.metrics import structural_similarity as ssim\n",
        "import imageio\n",
        "import matplotlib.pyplot as plt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x8Hzmk3ZcW6R"
      },
      "source": [
        "Now we will load in the image we are trying to reproduce. For this exercise, I have chosen a very popular image used in image processing, which is called \"Cameraman\"."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2R8_EIW6cWE4"
      },
      "source": [
        "url = 'https://www.researchgate.net/profile/Paul_Rodriguez16/publication/265988128/figure/fig1/AS:459614656438273@1486592081799/Input-test-images-a-Cameraman-grayscale-b-grayscale-Lena-and-c-color-Lena-All.png'\n",
        "img = imageio.imread(url)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HxCdiiuwdD2o"
      },
      "source": [
        "We can view the image and print out the shape."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Qfocm18KdcSV"
      },
      "source": [
        "print(img.shape)\n",
        "\n",
        "plt.imshow(img, cmap = 'gray')\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gj6QDgaLdy2b"
      },
      "source": [
        "By printing out the shape, we can see that the image is 512 x 512 pixels and is grayscale. We are going to downsample it to 128 x 128 for easier computation and view it after downsampling. We can also print out the minimum and maximum pixel values."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Q8QKnOLad93P"
      },
      "source": [
        "img = img[::4, ::4]\n",
        "print(img.shape)\n",
        "\n",
        "print(np.amin(img), np.amax(img))\n",
        "\n",
        "plt.imshow(img, cmap='gray')\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2ZFzYNup4Z_z"
      },
      "source": [
        "# Putting It All Together"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DWqs60Yu4b3n"
      },
      "source": [
        "generation = 0\n",
        "best_fitness = []  # going to track the max fitness values in this list\n",
        "desired_fitness = 0.90  # keep going until the max fitness equals or exceeds 0.9\n",
        "\n",
        "# initialize population and compute initial fitness values\n",
        "population = init_population(20, img.size)\n",
        "fitness_vals = evaluate_fitness(population, img)\n",
        "\n",
        "while max(fitness_vals) < desired_fitness:\n",
        "    parents = select(population, fitness_vals)\n",
        "    children = reproduction(parents)\n",
        "    children = mutate(children)\n",
        "    population = make_next_generation(parents, children)\n",
        "    fitness_vals = evaluate_fitness(population, img)\n",
        "\n",
        "    # plotting metrics and progress\n",
        "    if generation % 100 == 0:\n",
        "        best_fitness.append([generation, max(fitness_vals)])\n",
        "\n",
        "    if generation % 2000 == 0:\n",
        "        print('Generation: {}; Max Fitness: {}'.format(generation, max(fitness_vals)))\n",
        "\n",
        "        max_fitness_indx = [i for i in range(len(fitness_vals)) if fitness_vals[i] == max(fitness_vals)]\n",
        "        fig = plt.figure()\n",
        "        sub1, sub2 = fig.add_subplot(121), fig.add_subplot(122)\n",
        "        sub1.imshow(scale(population[max_fitness_indx].reshape([img.shape[0], img.shape[1]])), cmap='gray')\n",
        "        sub2.imshow(img, cmap='gray')\n",
        "        sub1.set_title(\"Best Image\")\n",
        "        sub2.set_title(\"Actual Image\")\n",
        "        plt.show()\n",
        "\n",
        "        plt.bar(x = list(range(len(fitness_vals))), height = sorted(fitness_vals, reverse=True))\n",
        "        plt.xlabel(\"Individual\")\n",
        "        plt.ylabel(\"Fitness Value\")\n",
        "        plt.show()\n",
        "\n",
        "        plt.plot([x[0] for x in best_fitness], [x[1] for x in best_fitness])\n",
        "        plt.xlabel(\"Generation\")\n",
        "        plt.ylabel(\"Best Fitness Value\")\n",
        "        plt.show()\n",
        "\n",
        "    generation += 1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kFzgMfZJJkpD"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    }
  ]
}