search3e-GeneticAlgorithm_2023_2024 - ConPermutaciones.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Solving problems by Searching\n",
    "\n",
    "This notebook serves as supporting material for topics covered in **Chapter 3 - Solving Problems by Searching** and **Chapter 4 - Beyond Classical Search** from the book *Artificial Intelligence: A Modern Approach.* This notebook uses implementations from [search.py](https://github.com/aimacode/aima-python/blob/master/search.py) module. Let's start by importing everything from search module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "import random\n",
    "import bisect\n",
    "# Needed to hide warnings in the matplotlib sections\n",
    "import warnings\n",
    "#from numpy import *\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For visualisations, we use networkx and matplotlib to show the map in the notebook and we use ipywidgets to interact with the map to see how the searching algorithm works. These are imported as required in `notebook.py`."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CONTENTS\n",
    "\n",
    "* Genetic Algorithm\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GENETIC ALGORITHM\n",
    "\n",
    "Genetic algorithms (or GA) are inspired by natural evolution and are particularly useful in optimization and search problems with large state spaces.\n",
    "\n",
    "Given a problem, algorithms in the domain make use of a *population* of solutions (also called *states*), where each solution/state represents a feasible solution. At each iteration (often called *generation*), the population gets updated using methods inspired by biology and evolution, like *crossover*, *mutation* and *natural selection*."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PERMUTATION ENCODING\n",
    "\n",
    "GA Parameters:\n",
    "We now need to define the maximum size of each population. Larger populations have more variation but are computationally more  expensive to run algorithms on.\n",
    "As our population is not very large, we can afford to keep a relatively large mutation rate.\n",
    "Termination after a predefined number of generations.\n",
    "N is the size of the chromosmes, and [0,..,N-1] is the alphabet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "max_population = 100\n",
    "mutation_rate = 0.07 # 7% of the chromosones are mutated\n",
    "ngen = 100 # maximum number of generations\n",
    "N = 8 # chormosome size\n",
    "gene_pool = list(range(N)) # alphabet\n",
    "#gene_pool.remove(0)\n",
    "print(gene_pool)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Now, we need to define the most important metric for the genetic algorithm, i.e the fitness function. This will simply return the number of matching characters between the generated sample and the target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness_fn(sample):\n",
    "    # initialize fitness to 0\n",
    "    fitness = 0\n",
    "    for i in range(len(sample)):\n",
    "        # increment fitness by 1 for every matching character\n",
    "        if sample[i] == target[i]:\n",
    "           fitness += 1\n",
    "    return fitness\n",
    "# target\n",
    "target = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "To generate `ngen` number of generations, we run a `for` loop `ngen` number of times. After each generation, we calculate the fitness of the best individual of the generation and compare it to the value of `f_thres` using the `fitness_threshold` function. After every generation, we print out the best individual of the generation and the corresponding fitness value. Lets now write a function to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genetic_algorithm_stepwise(population, fitness_fn, gene_pool, ngen=1200, pmut=0.1):\n",
    "    for generation in range(int(ngen)):\n",
    "        # Elitism may be here - ADDED\n",
    "        previous_best = max(population, key=fitness_fn)\n",
    "        population = [mutate2(uniform_crossover(*select(2, population, fitness_fn)), pmut) for i in range(len(population)-1)]\n",
    "        population.append(previous_best)\n",
    "        # stores the individual genome with the highest fitness in the current population\n",
    "        current_best = max(population, key=fitness_fn)\n",
    "        #print(f'Current best: {current_best}\\t\\tGeneration: {str(generation)}\\t\\tFitness: {fitness_fn(current_best)}\\r', end='')\n",
    "        print(f'Current best: {current_best}\\t\\tGeneration: {str(generation)}\\t\\tFitness: {fitness_fn(current_best)}\\r')\n",
    "    return max(population, key=fitness_fn)       \n",
    "\n",
    "def init_population(pop_number, gene_pool):\n",
    "    # a chromosome is a random permutation of the alphabet\n",
    "    population = []\n",
    "    for _ in range(pop_number):\n",
    "        # Shuffle the gene pool and take the first pool_size elements as an individual\n",
    "        v = gene_pool[:]\n",
    "        random.shuffle(v)\n",
    "        population.append(v)\n",
    "    return population\n",
    "\n",
    "def select(r, population, fitness_fn):\n",
    "    fitnesses = map(fitness_fn, population)\n",
    "    #scaling here\n",
    "    sampler = weighted_sampler(population, fitnesses)\n",
    "    return [sampler() for i in range(r)]\n",
    "\n",
    "def weighted_sampler(seq, weights):\n",
    "    \"\"\"Return a random-sample function that picks from seq weighted by weights.\"\"\"\n",
    "    totals = []\n",
    "    for w in weights:\n",
    "        totals.append(w + totals[-1] if totals else w)\n",
    "    return lambda: seq[bisect.bisect(totals, random.uniform(0, totals[-1]))]\n",
    "    # bisect(a,x) -> insertion position of a in a sorted list x - AL REVES\n",
    "\n",
    "def uniform_crossover(x, y):\n",
    "    # x, y permutations of the alphabet\n",
    "    n = 0\n",
    "    child = [-1] * N\n",
    "    indexes = [0] * N\n",
    "    # de x se copian los valores de las posiciones con indexex[i] == 1 en las mismas posiciones en child\n",
    "    for i in  range(N):\n",
    "        indexes[i] = random.randint(0,1) \n",
    "        if indexes[i] == 1:\n",
    "            child[i] = x[i]\n",
    "            n += 1\n",
    "    # El resto (N-n) se copia de y en su orden relativo, desde el principio\n",
    "    i = 0 # indice en y\n",
    "    k = 0 # indice en child\n",
    "    for t in range(N-n):\n",
    "        while y[i] in child[:]:\n",
    "            i += 1\n",
    "        while child[k] != -1:\n",
    "            k += 1\n",
    "        child[k] = y[i]\n",
    "        i += 1   \n",
    "    return child\n",
    "\n",
    "def mutate2(x, pmut):\n",
    "    if random.uniform(0, 1) >= pmut:\n",
    "        return x\n",
    "    i, j = random.sample(range(N), 2)\n",
    "    x[i], x[j] = x[j], x[i]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function defined above is essentially the same as the one defined in `search.py` with the added functionality of printing out the data of each generation."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have defined all the required functions and variables. Let's now create a new population and test the function we wrote above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current best: [1, 2, 3, 7, 4, 6, 0, 5]\t\tGeneration: 0\t\tFitness: 4\n",
      "Current best: [1, 2, 3, 7, 4, 6, 0, 5]\t\tGeneration: 1\t\tFitness: 4\n",
      "Current best: [1, 2, 3, 5, 0, 6, 4, 7]\t\tGeneration: 2\t\tFitness: 4\n",
      "Current best: [1, 2, 3, 7, 4, 6, 0, 5]\t\tGeneration: 3\t\tFitness: 4\n",
      "Current best: [1, 2, 3, 7, 5, 6, 0, 4]\t\tGeneration: 4\t\tFitness: 5\n",
      "Current best: [1, 2, 3, 4, 5, 6, 0, 7]\t\tGeneration: 5\t\tFitness: 6\n",
      "Current best: [1, 2, 3, 4, 5, 6, 0, 7]\t\tGeneration: 6\t\tFitness: 6\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 7\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 8\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 9\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 10\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 11\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 12\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 13\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 14\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 15\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 16\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 17\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 18\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 19\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 20\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 21\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 22\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 23\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 24\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 25\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 26\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 27\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 28\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 29\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 30\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 31\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 32\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 33\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 34\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 35\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 36\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 37\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 38\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 39\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 40\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 41\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 42\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 43\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 44\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 45\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 46\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 47\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 48\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 49\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 50\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 51\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 52\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 53\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 54\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 55\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 56\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 57\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 58\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 59\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 60\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 61\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 62\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 63\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 64\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 65\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 66\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 67\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 68\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 69\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 70\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 71\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 72\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 73\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 74\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 75\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 76\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 77\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 78\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 79\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 80\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 81\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 82\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 83\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 84\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 85\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 86\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 87\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 88\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 89\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 90\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 91\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 92\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 93\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 94\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 95\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 96\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 97\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 98\t\tFitness: 7\n",
      "Current best: [1, 2, 3, 4, 5, 6, 7, 0]\t\tGeneration: 99\t\tFitness: 7\n",
      "Target: \n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
      "Solution: \n",
      "[1, 2, 3, 4, 5, 6, 7, 0]\n",
      "Fitness: \n",
      "7\n"
     ]
    }
   ],
   "source": [
    "population = init_population(max_population, gene_pool)\n",
    "#print(population)\n",
    "solution = genetic_algorithm_stepwise(population, fitness_fn, gene_pool, ngen, mutation_rate)\n",
    "print(\"Target: \")\n",
    "print(target)\n",
    "print(\"Solution: \")\n",
    "print(solution)\n",
    "print(\"Fitness: \")\n",
    "print(fitness_fn(solution))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The genetic algorithm was able to converge!\n",
    "We implore you to rerun the above cell and play around with `target, max_population, f_thres, ngen` etc parameters to get a better intuition of how the algorithm works. To summarize, if we can define the problem states in simple array format and if we can create a fitness function to gauge how good or bad our approximate solutions are, there is a high chance that we can get a satisfactory solution using a genetic algorithm. \n",
    "- There is also a better GUI version of this program `genetic_algorithm_example.py` in the GUI folder for you to play around with."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eight Queens\n",
    "\n",
    "Let's take a look at a more complicated problem.\n",
    "\n",
    "In the *Eight Queens* problem, we are tasked with placing eight queens on an 8x8 chessboard without any queen threatening the others (aka queens should not be in the same row, column or diagonal). In its general form the problem is defined as placing *N* queens in an NxN chessboard without any conflicts.\n",
    "\n",
    "First we need to think about the representation of each solution. We can go the naive route of representing the whole chessboard with the queens' placements on it. That is definitely one way to go about it, but for the purpose of this tutorial we will do something different. We have eight queens, so we will have a gene for each of them. The gene pool will be numbers from 0 to 7, for the different columns. The *position* of the gene in the state will denote the row the particular queen is placed in.\n",
    "\n",
    "For example, we can have the state \"03304577\". Here the first gene with a value of 0 means \"the queen at row 0 is placed at column 0\", for the second gene \"the queen at row 1 is placed at column 3\" and so forth.\n",
    "\n",
    "We now need to think about the fitness function. On the graph coloring problem we counted the valid edges. The same thought process can be applied here. Instead of edges though, we have positioning between queens. If two queens are not threatening each other, we say they are at a \"non-attacking\" positioning. We can, therefore, count how many such positionings are there.\n",
    "\n",
    "Let's dive right in and initialize our population:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4, 2, 7, 6, 3, 1, 0, 5], [6, 1, 4, 5, 2, 7, 0, 3], [6, 4, 5, 1, 7, 0, 3, 2], [7, 2, 5, 6, 1, 0, 3, 4], [5, 7, 1, 2, 4, 6, 0, 3]]\n"
     ]
    }
   ],
   "source": [
    "population = init_population(100, gene_pool)\n",
    "print(population[:5])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have a population of 100 and each individual has 8 genes. The gene pool is the integers from 0 to 7, in string form. Above you can see the first five individuals.\n",
    "\n",
    "Next we need to write our fitness function. Remember, queens threaten each other if they are at the same row, column or diagonal.\n",
    "\n",
    "Since positionings are mutual, we must take care not to count them twice. Therefore for each queen, we will only check for conflicts for the queens after her.\n",
    "\n",
    "A gene's value in an individual `q` denotes the queen's column, and the position of the gene denotes its row. We can check if the aforementioned values between two genes are the same. We also need to check for diagonals. A queen *a* is in the diagonal of another queen, *b*, if the difference of the rows between them is equal to either their difference in columns (for the diagonal on the right of *a*) or equal to the negative difference of their columns (for the left diagonal of *a*). Below is given the fitness function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness(q):\n",
    "    non_attacking = 0\n",
    "    for row1 in range(len(q)):\n",
    "        for row2 in range(row1+1, len(q)):\n",
    "            col1 = int(q[row1])\n",
    "            col2 = int(q[row2])\n",
    "            row_diff = row1 - row2\n",
    "            col_diff = col1 - col2\n",
    "\n",
    "            if col1 != col2 and row_diff != col_diff and row_diff != -col_diff:\n",
    "                non_attacking += 1\n",
    "\n",
    "    return non_attacking"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the best score achievable is 28. That is because for each queen we only check for the queens after her. For the first queen we check 7 other queens, for the second queen 6 others and so on. In short, the number of checks we make is the sum 7+6+5+...+1. Which is equal to 7\\*(7+1)/2 = 28.\n",
    "\n",
    "Because it is very hard and will take long to find a perfect solution, we will set the fitness threshold at 25. If we find an individual with a score greater or equal to that, we will halt. Let's see how the genetic algorithm will fare."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current best: [4, 6, 0, 2, 7, 5, 3, 1]\t\tGeneration: 0\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 1\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 2\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 3\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 4\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 5\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 6\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 7\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 8\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 9\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 10\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 11\t\tFitness: 28\n",
      "Current best: [2, 7, 3, 6, 0, 5, 1, 4]\t\tGeneration: 12\t\tFitness: 28\n",
      "Current best: [5, 2, 4, 7, 0, 3, 1, 6]\t\tGeneration: 13\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 14\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 15\t\tFitness: 28\n",
      "Current best: [2, 5, 1, 4, 7, 0, 6, 3]\t\tGeneration: 16\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 17\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 18\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 19\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 20\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 21\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 22\t\tFitness: 28\n",
      "Current best: [4, 2, 0, 6, 1, 7, 5, 3]\t\tGeneration: 23\t\tFitness: 28\n",
      "Current best: [5, 3, 6, 0, 7, 1, 4, 2]\t\tGeneration: 24\t\tFitness: 28\n",
      "Current best: [5, 3, 6, 0, 7, 1, 4, 2]\t\tGeneration: 25\t\tFitness: 28\n",
      "Current best: [6, 2, 0, 5, 7, 4, 1, 3]\t\tGeneration: 26\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 27\t\tFitness: 28\n",
      "Current best: [6, 2, 0, 5, 7, 4, 1, 3]\t\tGeneration: 28\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 29\t\tFitness: 28\n",
      "Current best: [2, 5, 1, 4, 7, 0, 6, 3]\t\tGeneration: 30\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 31\t\tFitness: 28\n",
      "Current best: [2, 5, 1, 4, 7, 0, 6, 3]\t\tGeneration: 32\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 33\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 34\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 35\t\tFitness: 28\n",
      "Current best: [4, 1, 3, 5, 7, 2, 0, 6]\t\tGeneration: 36\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 37\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 38\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 39\t\tFitness: 28\n",
      "Current best: [2, 4, 1, 7, 0, 6, 3, 5]\t\tGeneration: 40\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 3, 6, 4, 1]\t\tGeneration: 41\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 4, 6, 1, 3]\t\tGeneration: 42\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 4, 6, 1, 3]\t\tGeneration: 43\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 4, 6, 1, 3]\t\tGeneration: 44\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 4, 6, 1, 3]\t\tGeneration: 45\t\tFitness: 28\n",
      "Current best: [2, 5, 7, 0, 4, 6, 1, 3]\t\tGeneration: 46\t\tFitness: 28\n",
      "Current best: [5, 1, 6, 0, 3, 7, 4, 2]\t\tGeneration: 47\t\tFitness: 28\n",
      "Current best: [5, 1, 6, 0, 3, 7, 4, 2]\t\tGeneration: 48\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 49\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 50\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 51\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 52\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 53\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 54\t\tFitness: 28\n",
      "Current best: [6, 3, 1, 7, 5, 0, 2, 4]\t\tGeneration: 55\t\tFitness: 28\n",
      "Current best: [4, 6, 1, 5, 2, 0, 7, 3]\t\tGeneration: 56\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 57\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 58\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 59\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 60\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 61\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 62\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 63\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 64\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 65\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 66\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 67\t\tFitness: 28\n",
      "Current best: [5, 3, 1, 7, 4, 6, 0, 2]\t\tGeneration: 68\t\tFitness: 28\n",
      "Current best: [1, 6, 4, 7, 0, 3, 5, 2]\t\tGeneration: 69\t\tFitness: 28\n",
      "Current best: [1, 6, 4, 7, 0, 3, 5, 2]\t\tGeneration: 70\t\tFitness: 28\n",
      "Current best: [1, 6, 4, 7, 0, 3, 5, 2]\t\tGeneration: 71\t\tFitness: 28\n",
      "Current best: [1, 4, 6, 3, 0, 7, 5, 2]\t\tGeneration: 72\t\tFitness: 28\n",
      "Current best: [6, 1, 5, 2, 0, 3, 7, 4]\t\tGeneration: 73\t\tFitness: 28\n",
      "Current best: [6, 1, 5, 2, 0, 3, 7, 4]\t\tGeneration: 74\t\tFitness: 28\n",
      "Current best: [1, 4, 6, 0, 2, 7, 5, 3]\t\tGeneration: 75\t\tFitness: 28\n",
      "Current best: [5, 1, 6, 0, 3, 7, 4, 2]\t\tGeneration: 76\t\tFitness: 28\n",
      "Current best: [5, 1, 6, 0, 3, 7, 4, 2]\t\tGeneration: 77\t\tFitness: 28\n",
      "Current best: [4, 6, 3, 0, 2, 7, 5, 1]\t\tGeneration: 78\t\tFitness: 28\n",
      "Current best: [4, 6, 3, 0, 2, 7, 5, 1]\t\tGeneration: 79\t\tFitness: 28\n",
      "Current best: [4, 6, 3, 0, 2, 7, 5, 1]\t\tGeneration: 80\t\tFitness: 28\n",
      "Current best: [4, 6, 3, 0, 2, 7, 5, 1]\t\tGeneration: 81\t\tFitness: 28\n",
      "Current best: [4, 6, 3, 0, 2, 7, 5, 1]\t\tGeneration: 82\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 83\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 84\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 85\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 86\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 87\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 88\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 89\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 90\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 91\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 92\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 93\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 94\t\tFitness: 28\n",
      "Current best: [4, 0, 7, 5, 2, 6, 1, 3]\t\tGeneration: 95\t\tFitness: 28\n",
      "Current best: [3, 0, 4, 7, 1, 6, 2, 5]\t\tGeneration: 96\t\tFitness: 28\n",
      "Current best: [3, 0, 4, 7, 1, 6, 2, 5]\t\tGeneration: 97\t\tFitness: 28\n",
      "Current best: [3, 0, 4, 7, 1, 6, 2, 5]\t\tGeneration: 98\t\tFitness: 28\n",
      "Current best: [3, 5, 7, 2, 0, 6, 4, 1]\t\tGeneration: 99\t\tFitness: 28\n",
      "[3, 5, 7, 2, 0, 6, 4, 1]\n"
     ]
    }
   ],
   "source": [
    "solution = genetic_algorithm_stepwise(population, fitness, gene_pool, ngen=100)\n",
    "print(solution)\n",
    "#print(fitness(solution))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above you can see the solution and its fitness score, which should be no less than 25."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is where we conclude Genetic Algorithms."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "This concludes the notebook.\n",
    "Hope you learned something new!"
   ]
  }
 ],
 "metadata": {
  "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.11.5"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  },
  "widgets": {
   "state": {
    "1516e2501ddd4a2e8e3250bffc0164db": {
     "views": [
      {
       "cell_index": 59
      }
     ]
    },
    "17be64c89a9a4a43b3272cb018df0970": {
     "views": [
      {
       "cell_index": 59
      }
     ]
    },
    "ac05040009a340b0af81b0ee69161fbc": {
     "views": [
      {
       "cell_index": 59
      }
     ]
    },
    "d9735ffe77c24f13ae4ad3620ce84334": {
     "views": [
      {
       "cell_index": 59
      }
     ]
    }
   },
   "version": "1.2.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}