genetic_algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Genetic Algorithm\n",
    "\n",
    "The genetic algorithm emulates Evolution by \"breeding\" solutions from previous solutions and applying mutation. The likelihood that a solution \"survives\" is based on its \"fitness\" value (as defined by some \"fitness function\").\n",
    "\n",
    "### Problem to solve\n",
    "\n",
    "Let's try using it to solve a simple equation:\n",
    "\n",
    "* x − y = −1\n",
    "* 3x + y = 9\n",
    "\n",
    "**(The real solution is x=2, y=3)**\n",
    "\n",
    "## Generic Genetic Algorithm\n",
    "\n",
    "First, let's write a basic genetic algorithm.\n",
    "\n",
    "Each \"individual\" will be a list in this form: `[fitness, val1, val2, ...]`. This way, we can simply do a `sort()` to determine fitness, since a sort of a list first considers the first value in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def generate_couples(population):\n",
    "    couples = []\n",
    "    for i in range(0, len(population)-1, 2):\n",
    "        c = (population[i], population[i+1])\n",
    "        couples.append(c)\n",
    "    return couples\n",
    "\n",
    "def genetic_algorithm(fit_func, cross_func, mutate_func, init_pop, max_iter=1000,\n",
    "                      max_pop=100, quit_at_err=0.01, mut_prob=0.1, mut_mu=0, mut_sigma=1):\n",
    "    population = init_pop\n",
    "    num_solutions_considered = 0\n",
    "    top_dog = init_pop[0]\n",
    "    \n",
    "    for i in range(max_iter):        \n",
    "        # Calculate fitness function for each individual\n",
    "        for individual in population:\n",
    "            fitness = individual[0]\n",
    "            if fitness < 0:  # Meaning it has not been calculated, since fitness is always positive or 0\n",
    "                fitness = fit_func(individual)\n",
    "                individual[0] = fitness\n",
    "\n",
    "        # Sort population by fitness - this is needed both to find the top dog (to see if we have a\n",
    "        # good-enough solution) and to put the population in order for pariing up as couples.\n",
    "        population.sort()\n",
    "        num_solutions_considered += len(population)\n",
    "        \n",
    "        # Find the \"most fit\" individual. If this solution is close enough (error less than quit_at_err),\n",
    "        # then just stop the algorithm and return this solution.\n",
    "        top_dog = population[0]\n",
    "        if top_dog[0] < quit_at_err:\n",
    "            print('Solutions considered: {}, Error: {}'.format(num_solutions_considered, top_dog[0]))\n",
    "            return top_dog\n",
    "        \n",
    "        # Make couples - they pair up according to fitness\n",
    "        couples = generate_couples(population)\n",
    "        \n",
    "        # Mate - the baby's genetics are created by taking the x from one of the parents and y from the other,\n",
    "        # and then applying mutation (to randomly tweak the 'genes')\n",
    "        babies = [mutate(have_sex(couple[0], couple[1]), mut_prob, mut_mu, mut_sigma) for couple in couples]\n",
    "        population += babies\n",
    "        \n",
    "        # Sort by fitness and cull (simulating limited resources) - only the strong survive\n",
    "        population.sort()\n",
    "        population = population[:max_pop]\n",
    "\n",
    "    print('Solutions considered: {}, Error: {}'.format(num_solutions_considered, top_dog[0]))\n",
    "    return top_dog\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Write problem-specific functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solutions considered: 5583, Error: 0.0051585675279162005\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0.0051585675279162005, 1.9800869495118212, 2.988398522965479]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fitness_function(individual):\n",
    "    fitness, x, y = individual\n",
    "    # We square the error so it's always positive\n",
    "    eq1_error = ((x - y) - (-1))**2\n",
    "    eq2_error = ((3*x + y) - 9)**2\n",
    "    return eq1_error + eq2_error\n",
    "\n",
    "def have_sex(a, b):\n",
    "    \"\"\" Given parents a and b, take the x value from a and the y value from b.\n",
    "    This is similar to how humans get half their genetic material from the father and half\n",
    "    from the mother. \"\"\"\n",
    "    x = a[1]\n",
    "    y = b[2]\n",
    "    # Set fitness at -1, indicating it hasn't been calculated yet (i.e. the babies haven't \n",
    "    # been tested in the wild yet)\n",
    "    return [-1, x, y]\n",
    "\n",
    "def mutate(a, mutation_probability, mu, sigma):\n",
    "    \"\"\" Mutate the values for x and y according to the probability of mutation - \n",
    "    if mutation_probability is 0.01, then there is a 1% chance of a value being mutated.\n",
    "    \n",
    "    If we mutate, we do so by generating a random number according to the normal distribution\n",
    "    as specified by mu (mean) and sigma (standard deviation).\n",
    "    \"\"\"\n",
    "    mutant = [-1]\n",
    "    for var in a[1:]:\n",
    "        if random.random() <= mutation_probability:\n",
    "            new_var = var + random.gauss(mu, sigma)\n",
    "            mutant.append(new_var)\n",
    "        else:\n",
    "            mutant.append(var)\n",
    "    return mutant\n",
    "\n",
    "initial_population = [[-1, 0, 0], [-1, 10, 10]]     \n",
    "most_fit_solution = genetic_algorithm(fitness_function, have_sex, mutate, initial_population)\n",
    "most_fit_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Wow, so that's a pretty close solution in not too many generations (or solutions considered).**\n",
    "\n",
    "Now, let's compare it these 2 types of random searches:\n",
    "\n",
    "* Random walk\n",
    "* Uniform random search (in a constrained window)\n",
    "\n",
    "## Comparison with random walk solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solutions considered: 1000000, Error: 2674475.7667086828\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-517.4518389625891, 14.596513748922629]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_walk_next_solution(prev_solution, mu, sigma):\n",
    "    return [prev_solution[0] + random.gauss(mu, sigma), prev_solution[1] + random.gauss(mu, sigma)]\n",
    "\n",
    "def error_function(individual):\n",
    "    x, y = individual\n",
    "    # We square the error so it's always positive\n",
    "    eq1_error = ((x - y) - (-1))**2\n",
    "    eq2_error = ((3*x + y) - 9)**2\n",
    "    return eq1_error + eq2_error\n",
    "\n",
    "def do_random_walk_search(mu, sigma, init_guess, max_iter=100*10000+1, quit_at_err=0.01):\n",
    "    current_solution = init_guess\n",
    "    \n",
    "    for i in range(max_iter):\n",
    "        current_solution = random_walk_next_solution(current_solution, 0, .5)\n",
    "        current_solution_err = error_function(current_solution)\n",
    "        if current_solution_err < quit_at_err:\n",
    "            break\n",
    "            \n",
    "    print('Solutions considered: {}, Error: {}'.format(i, current_solution_err))\n",
    "    return current_solution\n",
    "\n",
    "do_random_walk_search(0, 0.5, [0, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "That is a pretty bad solution, and a ton of error.\n",
    "\n",
    "## Comparison with random (non-walk) solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solutions considered: 258008, Error: 0.003331292698078634\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2.0172999771900813, 2.9610554044041812]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_next_solution(x_min, x_max, y_min, y_max):\n",
    "    return [random.uniform(x_min, x_max), random.uniform(y_min, y_max)]\n",
    "\n",
    "def do_random_search(x_min, x_max, y_min, y_max, max_iter=100*10000+1, quit_at_err=0.01):\n",
    "    for i in range(max_iter):\n",
    "        # Note that with this solution, we are artificially limiting the search window\n",
    "        current_solution = random_next_solution(x_min, x_max, y_min, y_max)\n",
    "        current_solution_err = error_function(current_solution)\n",
    "        if current_solution_err < quit_at_err:\n",
    "            break\n",
    "\n",
    "    print('Solutions considered: {}, Error: {}'.format(i, current_solution_err))\n",
    "    return current_solution\n",
    "\n",
    "do_random_search(-20, 20, -20, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So looks like the random uniform search is descent (though nowhere near the efficiency as the Genetic Algorithm). BUT, we had to limit the search window for x and y to (-20, 20). The Genetic Algorithm is is really nice because no such limitation of the window is necessary. With some problems, we don't have such a good idea of where the solution (or a good-enough solution) lies.\n",
    "\n",
    "Now, look how poorly the random search algorithm behaves when we expand the window to (-100, 100):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solutions considered: 1000000, Error: 13621.719576470292\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[8.392531191861323, -84.92413223145496]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do_random_search(-100, 100, -100, 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*So when we expand the search space, the results are much worse for the uniform random search.*\n",
    "\n",
    "# Conclusion\n",
    "\n",
    "Clearly, the genetic algorithm is much more efficient than either a random walk search or a random uniform search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}