search.ipynb

    "    \n",
    "    explored = set()\n",
    "    while frontier:\n",
    "        node = frontier.pop()\n",
    "        \n",
    "        node_colors[node.state] = \"red\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "        \n",
    "        if problem.goal_test(node.state):\n",
    "            node_colors[node.state] = \"green\"\n",
    "            iterations += 1\n",
    "            all_node_colors.append(dict(node_colors))\n",
    "            return(iterations, all_node_colors, node)\n",
    "        \n",
    "        explored.add(node.state)\n",
    "        for child in node.expand(problem):\n",
    "            if child.state not in explored and child not in frontier:\n",
    "                frontier.append(child)\n",
    "                node_colors[child.state] = \"orange\"\n",
    "                iterations += 1\n",
    "                all_node_colors.append(dict(node_colors))\n",
    "            elif child in frontier:\n",
    "                incumbent = frontier[child]\n",
    "                if f(child) < f(incumbent):\n",
    "                    del frontier[incumbent]\n",
    "                    frontier.append(child)\n",
    "                    node_colors[child.state] = \"orange\"\n",
    "                    iterations += 1\n",
    "                    all_node_colors.append(dict(node_colors))\n",
    "\n",
    "        node_colors[node.state] = \"gray\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "    return None\n",
    "\n",
    "def uniform_cost_search(problem):\n",
    "    \"[Figure 3.14]\"\n",
    "    iterations, all_node_colors, node = best_first_graph_search(problem, lambda node: node.path_cost)\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a667c668001e4e598478ba4a870c6aec"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "135c6bd739de4aab8fc7b2fcb6b90954"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(user_input = False, algorithm = uniform_cost_search, problem = romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A\\* SEARCH\n",
    "\n",
    "Let's change all the node_colors to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def best_first_graph_search(problem, f):\n",
    "    \"\"\"Search the nodes with the lowest f scores first.\n",
    "    You specify the function f(node) that you want to minimize; for example,\n",
    "    if f is a heuristic estimate to the goal, then we have greedy best\n",
    "    first search; if f is node.depth then we have breadth-first search.\n",
    "    There is a subtlety: the line \"f = memoize(f, 'f')\" means that the f\n",
    "    values will be cached on the nodes as they are computed. So after doing\n",
    "    a best first search you can examine the f values of the path returned.\"\"\"\n",
    "    \n",
    "    # we use these two variables at the time of visualisations\n",
    "    iterations = 0\n",
    "    all_node_colors = []\n",
    "    node_colors = dict(initial_node_colors)\n",
    "    \n",
    "    f = memoize(f, 'f')\n",
    "    node = Node(problem.initial)\n",
    "    \n",
    "    node_colors[node.state] = \"red\"\n",
    "    iterations += 1\n",
    "    all_node_colors.append(dict(node_colors))\n",
    "    \n",
    "    if problem.goal_test(node.state):\n",
    "        node_colors[node.state] = \"green\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "        return(iterations, all_node_colors, node)\n",
    "    \n",
    "    frontier = PriorityQueue(min, f)\n",
    "    frontier.append(node)\n",
    "    \n",
    "    node_colors[node.state] = \"orange\"\n",
    "    iterations += 1\n",
    "    all_node_colors.append(dict(node_colors))\n",
    "    \n",
    "    explored = set()\n",
    "    while frontier:\n",
    "        node = frontier.pop()\n",
    "        \n",
    "        node_colors[node.state] = \"red\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "        \n",
    "        if problem.goal_test(node.state):\n",
    "            node_colors[node.state] = \"green\"\n",
    "            iterations += 1\n",
    "            all_node_colors.append(dict(node_colors))\n",
    "            return(iterations, all_node_colors, node)\n",
    "        \n",
    "        explored.add(node.state)\n",
    "        for child in node.expand(problem):\n",
    "            if child.state not in explored and child not in frontier:\n",
    "                frontier.append(child)\n",
    "                node_colors[child.state] = \"orange\"\n",
    "                iterations += 1\n",
    "                all_node_colors.append(dict(node_colors))\n",
    "            elif child in frontier:\n",
    "                incumbent = frontier[child]\n",
    "                if f(child) < f(incumbent):\n",
    "                    del frontier[incumbent]\n",
    "                    frontier.append(child)\n",
    "                    node_colors[child.state] = \"orange\"\n",
    "                    iterations += 1\n",
    "                    all_node_colors.append(dict(node_colors))\n",
    "\n",
    "        node_colors[node.state] = \"gray\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "    return None\n",
    "\n",
    "def astar_search(problem, h=None):\n",
    "    \"\"\"A* search is best-first graph search with f(n) = g(n)+h(n).\n",
    "    You need to specify the h function when you call astar_search, or\n",
    "    else in your Problem subclass.\"\"\"\n",
    "    h = memoize(h or problem.h, 'h')\n",
    "    iterations, all_node_colors, node = best_first_graph_search(problem, lambda n: n.path_cost + h(n))\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "3e62c492a82044e4813ad5d84e698874"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b661fd0c0c8d495db2672aedc25b9a44"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n", 
    "display_visual(user_input = False, algorithm = astar_search, problem = romania_problem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "7f1ffa858c92429bb28f74c23c0c939c"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "7a98e98ffec14520b93ce542f5169bcc"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "094beb8cf34c4a5b87f8368539d24091"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a8f89c87de964ee69004902763e68a54"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2ccdb4aba3ee4371a78306755e5642ad"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "all_node_colors = []\n",
    "# display_visual(user_input = True, algorithm = breadth_first_tree_search)\n",
    "display_visual(user_input = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BEST FIRST SEARCH\n",
    "Let's change all the node_colors to starting position and define a different problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_first_graph_search(problem, f):\n",
    "    \"\"\"Search the nodes with the lowest f scores first.\n",
    "    You specify the function f(node) that you want to minimize; for example,\n",
    "    if f is a heuristic estimate to the goal, then we have greedy best\n",
    "    first search; if f is node.depth then we have breadth-first search.\n",
    "    There is a subtlety: the line \"f = memoize(f, 'f')\" means that the f\n",
    "    values will be cached on the nodes as they are computed. So after doing\n",
    "    a best first search you can examine the f values of the path returned.\"\"\"\n",
    "    \n",
    "    # we use these two variables at the time of visualisations\n",
    "    iterations = 0\n",
    "    all_node_colors = []\n",
    "    node_colors = dict(initial_node_colors)\n",
    "    \n",
    "    f = memoize(f, 'f')\n",
    "    node = Node(problem.initial)\n",
    "    \n",
    "    node_colors[node.state] = \"red\"\n",
    "    iterations += 1\n",
    "    all_node_colors.append(dict(node_colors))\n",
    "    \n",
    "    if problem.goal_test(node.state):\n",
    "        node_colors[node.state] = \"green\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "        return(iterations, all_node_colors, node)\n",
    "    \n",
    "    frontier = PriorityQueue(min, f)\n",
    "    frontier.append(node)\n",
    "    \n",
    "    node_colors[node.state] = \"orange\"\n",
    "    iterations += 1\n",
    "    all_node_colors.append(dict(node_colors))\n",
    "    \n",
    "    explored = set()\n",
    "    while frontier:\n",
    "        node = frontier.pop()\n",
    "        \n",
    "        node_colors[node.state] = \"red\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "        \n",
    "        if problem.goal_test(node.state):\n",
    "            node_colors[node.state] = \"green\"\n",
    "            iterations += 1\n",
    "            all_node_colors.append(dict(node_colors))\n",
    "            return(iterations, all_node_colors, node)\n",
    "        \n",
    "        explored.add(node.state)\n",
    "        for child in node.expand(problem):\n",
    "            if child.state not in explored and child not in frontier:\n",
    "                frontier.append(child)\n",
    "                node_colors[child.state] = \"orange\"\n",
    "                iterations += 1\n",
    "                all_node_colors.append(dict(node_colors))\n",
    "            elif child in frontier:\n",
    "                incumbent = frontier[child]\n",
    "                if f(child) < f(incumbent):\n",
    "                    del frontier[incumbent]\n",
    "                    frontier.append(child)\n",
    "                    node_colors[child.state] = \"orange\"\n",
    "                    iterations += 1\n",
    "                    all_node_colors.append(dict(node_colors))\n",
    "\n",
    "        node_colors[node.state] = \"gray\"\n",
    "        iterations += 1\n",
    "        all_node_colors.append(dict(node_colors))\n",
    "    return None\n",
    "\n",
    "def best_first_search(problem, h=None):\n",
    "    \"\"\"Best-first graph search is an informative searching algorithm with f(n) = h(n).\n",
    "    You need to specify the h function when you call best_first_search, or\n",
    "    else in your Problem subclass.\"\"\"\n",
    "    h = memoize(h or problem.h, 'h')\n",
    "    iterations, all_node_colors, node = best_first_graph_search(problem, lambda n: h(n))\n",
    "    return(iterations, all_node_colors, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "5ae2d521b74743afa988c462a851c269"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "559c20b044a4469db7f0ab8c3fae1022"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "all_node_colors = []\n",
    "romania_problem = GraphProblem('Arad', 'Bucharest', romania_map)\n",
    "display_visual(user_input = False, algorithm = best_first_search, problem = romania_problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A* Heuristics\n",
    "\n",
    "Different heuristics provide different efficiency in solving A* problems which are generally defined by the number of explored nodes as well as the branching factor. With the classic 8 puzzle we can show the efficiency of different heuristics through the number of explored nodes.\n",
    "\n",
    "### 8 Puzzle Problem\n",
    "\n",
    "The *8 Puzzle Problem* consists of a 3x3 tray in which the goal is to get the initial configuration to the goal state by shifting the numbered tiles into the blank space.\n",
    "\n",
    "example:- \n",
    "\n",
    "              Initial State                        Goal State\n",
    "              | 7 | 2 | 4 |                       | 0 | 1 | 2 |\n",
    "              | 5 | 0 | 6 |                       | 3 | 4 | 5 |\n",
    "              | 8 | 3 | 1 |                       | 6 | 7 | 8 |\n",
    "              \n",
    "We have a total of 9 blank tiles giving us a total of 9! initial configuration but not all of these are solvable, the solvability of a configuration can be checked by calculating the Inversion Permutation. If the total Inversion Permutation is even then the initial configuration is solvable else the initial configuration is not solvable which means that only 9!/2 initial states lead to a solution.\n",
    "\n",
    "#### Heuristics :-\n",
    "\n",
    "1.) Manhattan Distance:- For the 8 puzzle problem Manhattan distance is defined as the distance of a tile from its goal state( for the tile numbered '1' in the initial configuration Manhattan distance is 4 \"2 for left and 2 for upward displacement\").\n",
    "\n",
    "2.) No. of Misplaced Tiles:- The heuristic calculates the number of misplaced tiles between the current state and goal state.\n",
    "\n",
    "3.) Sqrt of Manhattan Distance:- It calculates the square root of Manhattan distance.\n",
    "\n",
    "4.) Max Heuristic:- It assign the score as max of Manhattan Distance and No. of misplaced tiles. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# heuristics for 8 Puzzle Problem\n",
    "\n",
    "def linear(state,goal):\n",
    "    return sum([1 if state[i] != goal[i] else 0 for i in range(8)])\n",
    "\n",
    "def manhanttan(state,goal):\n",
    "\tindex_goal = {0:[2,2], 1:[0,0], 2:[0,1], 3:[0,2], 4:[1,0], 5:[1,1], 6:[1,2], 7:[2,0], 8:[2,1]}\n",
    "\tindex_state = {}\n",
    "\tindex = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]\n",
    "\tx=0\n",
    "\ty=0\n",
    "\tfor i in range(len(state)):\n",
    "\t\tindex_state[state[i]] = index[i]\n",
    "\tmhd = 0\n",
    "\tfor i in range(8):\n",
    "\t\tfor j in range(2):\n",
    "\t\t\tmhd = abs(index_goal[i][j] - index_state[i][j]) + mhd\n",
    "\treturn mhd\n",
    "\n",
    "def sqrt_manhanttan(state,goal):\n",
    "\tindex_goal = {0:[2,2], 1:[0,0], 2:[0,1], 3:[0,2], 4:[1,0], 5:[1,1], 6:[1,2], 7:[2,0], 8:[2,1]}\n",
    "\tindex_state = {}\n",
    "\tindex = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]\n",
    "\tx=0\n",
    "\ty=0\n",
    "\tfor i in range(len(state)):\n",
    "\t\tindex_state[state[i]] = index[i]\n",
    "\tmhd = 0\n",
    "\tfor i in range(8):\n",
    "\t\tfor j in range(2):\n",
    "\t\t\tmhd = (index_goal[i][j] - index_state[i][j])**2 + mhd\n",
    "\treturn math.sqrt(mhd)\n",
    "\n",
    "def max_heuristic(state,goal):\n",
    "\tscore1 = manhanttan(state, goal)\n",
    "\tscore2 = linear(state, goal)\n",
    "\treturn max(score1, score2)\t\t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "Number of explored nodes by the following heuristic are:  126\n",
      "[2, 4, 3, 1, 5, 6, 7, 8, 0]\n",
      "[2, 4, 3, 1, 5, 0, 7, 8, 6]\n",
      "[2, 4, 3, 1, 0, 5, 7, 8, 6]\n",
      "[2, 0, 3, 1, 4, 5, 7, 8, 6]\n",
      "[0, 2, 3, 1, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 0, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 0, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Number of explored nodes by the following heuristic are:  129\n",
      "[2, 4, 3, 1, 5, 6, 7, 8, 0]\n",
      "[2, 4, 3, 1, 5, 0, 7, 8, 6]\n",
      "[2, 4, 3, 1, 0, 5, 7, 8, 6]\n",
      "[2, 0, 3, 1, 4, 5, 7, 8, 6]\n",
      "[0, 2, 3, 1, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 0, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 0, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Number of explored nodes by the following heuristic are:  126\n",
      "[2, 4, 3, 1, 5, 6, 7, 8, 0]\n",
      "[2, 4, 3, 1, 5, 0, 7, 8, 6]\n",
      "[2, 4, 3, 1, 0, 5, 7, 8, 6]\n",
      "[2, 0, 3, 1, 4, 5, 7, 8, 6]\n",
      "[0, 2, 3, 1, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 0, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 0, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n",
      "Number of explored nodes by the following heuristic are:  139\n",
      "[2, 4, 3, 1, 5, 6, 7, 8, 0]\n",
      "[2, 4, 3, 1, 5, 0, 7, 8, 6]\n",
      "[2, 4, 3, 1, 0, 5, 7, 8, 6]\n",
      "[2, 0, 3, 1, 4, 5, 7, 8, 6]\n",
      "[0, 2, 3, 1, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 0, 4, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 0, 5, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 0, 7, 8, 6]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n"
     ]
    }
   ],
   "source": [
    "# Solving the puzzle \n",
    "puzzle = EightPuzzle()\n",
    "puzzle.checkSolvability([2,4,3,1,5,6,7,8,0]) # checks whether the initialized configuration is solvable or not\n",
    "puzzle.solve([2,4,3,1,5,6,7,8,0],[1,2,3,4,5,6,7,8,0],max_heuristic) # Max_heuristic\n",
    "puzzle.solve([2,4,3,1,5,6,7,8,0],[1,2,3,4,5,6,7,8,0],linear) # Linear\n",
    "puzzle.solve([2,4,3,1,5,6,7,8,0],[1,2,3,4,5,6,7,8,0],manhanttan) # Manhattan\n",
    "puzzle.solve([2,4,3,1,5,6,7,8,0],[1,2,3,4,5,6,7,8,0],sqrt_manhanttan) # Sqrt_manhattan"
   ]
  },
  {
   "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*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overview\n",
    "\n",
    "A genetic algorithm works in the following way:\n",
    "\n",
    "1) Initialize random population.\n",
    "\n",
    "2) Calculate population fitness.\n",
    "\n",
    "3) Select individuals for mating.\n",
    "\n",
    "4) Mate selected individuals to produce new population.\n",
    "\n",
    "     * Random chance to mutate individuals.\n",
    "\n",
    "5) Repeat from step 2) until an individual is fit enough or the maximum number of iterations was reached."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Glossary\n",
    "\n",
    "Before we continue, we will lay the basic terminology of the algorithm.\n",
    "\n",
    "* Individual/State: A list of elements (called *genes*) that represent possible solutions.\n",
    "\n",
    "* Population: The list of all the individuals/states.\n",
    "\n",
    "* Gene pool: The alphabet of possible values for an individual's genes.\n",
    "\n",
    "* Generation/Iteration: The number of times the population will be updated.\n",
    "\n",
    "* Fitness: An individual's score, calculated by a function specific to the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Crossover\n",
    "\n",
    "Two individuals/states can \"mate\" and produce one child. This offspring bears characteristics from both of its parents. There are many ways we can implement this crossover. Here we will take a look at the most common ones. Most other methods are variations of those below.\n",
    "\n",
    "* Point Crossover: The crossover occurs around one (or more) point. The parents get \"split\" at the chosen point or points and then get merged. In the example below we see two parents get split and merged at the 3rd digit, producing the following offspring after the crossover.\n",
    "\n",
    "![point crossover](images/point_crossover.png)\n",
    "\n",
    "* Uniform Crossover: This type of crossover chooses randomly the genes to get merged. Here the genes 1, 2 and 5 were chosen from the first parent, so the genes 3, 4 were added by the second parent.\n",
    "\n",
    "![uniform crossover](images/uniform_crossover.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mutation\n",
    "\n",
    "When an offspring is produced, there is a chance it will mutate, having one (or more, depending on the implementation) of its genes altered.\n",
    "\n",
    "For example, let's say the new individual to undergo mutation is \"abcde\". Randomly we pick to change its third gene to 'z'. The individual now becomes \"abzde\" and is added to the population."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection\n",
    "\n",
    "At each iteration, the fittest individuals are picked randomly to mate and produce offsprings. We measure an individual's fitness with a *fitness function*. That function depends on the given problem and it is used to score an individual. Usually the higher the better.\n",
    "\n",
    "The selection process is this:\n",
    "\n",
    "1) Individuals are scored by the fitness function.\n",
    "\n",
    "2) Individuals are picked randomly, according to their score (higher score means higher chance to get picked). Usually the formula to calculate the chance to pick an individual is the following (for population *P* and individual *i*):\n",
    "\n",
    "$$ chance(i) = \\dfrac{fitness(i)}{\\sum_{k \\, in \\, P}{fitness(k)}} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation\n",
    "\n",
    "Below we look over the implementation of the algorithm in the `search` module.\n",
    "\n",
    "First the implementation of the main core of the algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">genetic_algorithm</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">fitness_fn</span><span class=\"p\">,</span> <span class=\"n\">gene_pool</span><span class=\"o\">=</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">,</span> <span class=\"mi\">1</span><span class=\"p\">],</span> <span class=\"n\">f_thres</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">ngen</span><span class=\"o\">=</span><span class=\"mi\">1000</span><span class=\"p\">,</span> <span class=\"n\">pmut</span><span class=\"o\">=</span><span class=\"mf\">0.1</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;[Figure 4.8]&quot;&quot;&quot;</span>\n",
       "    <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">ngen</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">population</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">mutate</span><span class=\"p\">(</span><span class=\"n\">recombine</span><span class=\"p\">(</span><span class=\"o\">*</span><span class=\"n\">select</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"p\">,</span> <span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">fitness_fn</span><span class=\"p\">)),</span> <span class=\"n\">gene_pool</span><span class=\"p\">,</span> <span class=\"n\">pmut</span><span class=\"p\">)</span>\n",
       "                      <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">))]</span>\n",
       "\n",
       "        <span class=\"n\">fittest_individual</span> <span class=\"o\">=</span> <span class=\"n\">fitness_threshold</span><span class=\"p\">(</span><span class=\"n\">fitness_fn</span><span class=\"p\">,</span> <span class=\"n\">f_thres</span><span class=\"p\">,</span> <span class=\"n\">population</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">fittest_individual</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">fittest_individual</span>\n",
       "\n",
       "\n",
       "    <span class=\"k\">return</span> <span class=\"n\">argmax</span><span class=\"p\">(</span><span class=\"n\">population</span><span class=\"p\">,</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"n\">fitness_fn</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(genetic_algorithm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm takes the following input:\n",
    "\n",
    "* `population`: The initial population.\n",
    "\n",
    "* `fitness_fn`: The problem's fitness function.\n",
    "\n",
    "* `gene_pool`: The gene pool of the states/individuals. By default 0 and 1.\n",
    "\n",
    "* `f_thres`: The fitness threshold. If an individual reaches that score, iteration stops. By default 'None', which means the algorithm will not halt until the generations are ran.\n",
    "\n",
    "* `ngen`: The number of iterations/generations.\n",
    "\n",
    "* `pmut`: The probability of mutation.\n",
    "\n",
    "The algorithm gives as output the state with the largest score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each generation, the algorithm updates the population. First it calculates the fitnesses of the individuals, then it selects the most fit ones and finally crosses them over to produce offsprings. There is a chance that the offspring will be mutated, given by `pmut`. If at the end of the generation an individual meets the fitness threshold, the algorithm halts and returns that individual.\n",
    "\n",
    "The function of mating is accomplished by the method `recombine`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">recombine</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">,</span> <span class=\"n\">y</span><span class=\"p\">):</span>\n",
       "    <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">)</span>\n",
       "    <span class=\"n\">c</span> <span class=\"o\">=</span> <span class=\"n\">random</span><span class=\"o\">.</span><span class=\"n\">randrange</span><span class=\"p\">(</span><span class=\"mi\">0</span><span class=\"p\">,</span> <span class=\"n\">n</span><span class=\"p\">)</span>\n",
       "    <span class=\"k\">return</span> <span class=\"n\">x</span><span class=\"p\">[:</span><span class=\"n\">c</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"n\">y</span><span class=\"p\">[</span><span class=\"n\">c</span><span class=\"p\">:]</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(recombine)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The method picks at random a point and merges the parents (`x` and `y`) around it.\n",
    "\n",
    "The mutation is done in the method `mutate`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">mutate</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">,</span> <span class=\"n\">gene_pool</span><span class=\"p\">,</span> <span class=\"n\">pmut</span><span class=\"p\">):</span>\n",
       "    <span class=\"k\">if</span> <span class=\"n\">random</span><span class=\"o\">.</span><span class=\"n\">uniform</span><span class=\"p\">(</span><span class=\"mi\">0</span><span class=\"p\">,</span> <span class=\"mi\">1</span><span class=\"p\">)</span> <span class=\"o\">&gt;=</span> <span class=\"n\">pmut</span><span class=\"p\">:</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">x</span>\n",
       "\n",