Skip to content
GitLab
Rechercher un fichier Normal viewHistoryPermalink
search.ipynb 191 ko
Newer Older
Anthony Marakis's avatar
Update search.ipynb (#726)  
Anthony Marakis a validé
2001 2002 2003 2004 
      "[0, 2, 3, 1, 4, 6, 7, 5, 8]\n",
      "[1, 2, 3, 0, 4, 6, 7, 5, 8]\n",
      "[1, 2, 3, 4, 0, 6, 7, 5, 8]\n",
      "[1, 2, 3, 4, 5, 6, 7, 0, 8]\n",
surya saini's avatar
add Astar heuristics (#685)  
surya saini a validé
2005 2006 2007 2008 2009 
      "[1, 2, 3, 4, 5, 6, 7, 8, 0]\n"
     ]
    }
   ],
   "source": [
surya saini's avatar
Solve Issue of Loading search.ipynb (#689)  
surya saini a validé
2010 2011 2012 
    "# 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",
Anthony Marakis's avatar
Update search.ipynb (#726)  
Anthony Marakis a validé
2013 2014 2015 2016 
    "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"
surya saini's avatar
add Astar heuristics (#685)  
surya saini a validé
2017 2018 
   ]
  },
Aman Deep Singh's avatar
Added section on Hill Climbing (#787)  
Aman Deep Singh a validé
2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HILL CLIMBING\n",
    "\n",
    "Hill Climbing is a heuristic search used for optimization problems.\n",
    "Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem. \n",
    "This solution may or may not be the global optimum.\n",
    "The algorithm is a variant of generate and test algorithm. \n",
    "<br>\n",
    "As a whole, the algorithm works as follows:\n",
    "- Evaluate the initial state.\n",
    "- If it is equal to the goal state, return.\n",
    "- Find a neighboring state (one which is heuristically similar to the current state)\n",
    "- Evaluate this state. If it is closer to the goal state than before, replace the initial state with this state and repeat these steps.\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "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\">hill_climbing</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;From the initial node, keep choosing the neighbor with highest value,</span>\n",
       "<span class=\"sd\">    stopping when no neighbor is better. [Figure 4.2]&quot;&quot;&quot;</span>\n",
       "    <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
       "    <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
       "        <span class=\"n\">neighbors</span> <span class=\"o\">=</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">expand</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">neighbors</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">break</span>\n",
       "        <span class=\"n\">neighbor</span> <span class=\"o\">=</span> <span class=\"n\">argmax_random_tie</span><span class=\"p\">(</span><span class=\"n\">neighbors</span><span class=\"p\">,</span>\n",
       "                                     <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">node</span><span class=\"p\">:</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">neighbor</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span> <span class=\"o\">&lt;=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">break</span>\n",
       "        <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">neighbor</span>\n",
       "    <span class=\"k\">return</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(hill_climbing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will find an approximate solution to the traveling salespersons problem using this algorithm.\n",
    "<br>\n",
    "We need to define a class for this problem.\n",
    "<br>\n",
    "`Problem` will be used as a base class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class TSP_problem(Problem):\n",
    "\n",
    "    \"\"\" subclass of Problem to define various functions \"\"\"\n",
    "\n",
    "    def two_opt(self, state):\n",
    "        \"\"\" Neighbour generating function for Traveling Salesman Problem \"\"\"\n",
    "        neighbour_state = state[:]\n",
    "        left = random.randint(0, len(neighbour_state) - 1)\n",
    "        right = random.randint(0, len(neighbour_state) - 1)\n",
    "        if left > right:\n",
    "            left, right = right, left\n",
    "        neighbour_state[left: right + 1] = reversed(neighbour_state[left: right + 1])\n",
    "        return neighbour_state\n",
    "\n",
    "    def actions(self, state):\n",
    "        \"\"\" action that can be excuted in given state \"\"\"\n",
    "        return [self.two_opt]\n",
    "\n",
    "    def result(self, state, action):\n",
    "        \"\"\"  result after applying the given action on the given state \"\"\"\n",
    "        return action(state)\n",
    "\n",
    "    def path_cost(self, c, state1, action, state2):\n",
    "        \"\"\" total distance for the Traveling Salesman to be covered if in state2  \"\"\"\n",
    "        cost = 0\n",
    "        for i in range(len(state2) - 1):\n",
    "            cost += distances[state2[i]][state2[i + 1]]\n",
    "        cost += distances[state2[0]][state2[-1]]\n",
    "        return cost\n",
    "\n",
    "    def value(self, state):\n",
    "        \"\"\" value of path cost given negative for the given state \"\"\"\n",
    "        return -1 * self.path_cost(None, None, None, state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use cities from the Romania map as our cities for this problem.\n",
    "<br>\n",
    "A list of all cities and a dictionary storing distances between them will be populated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Arad', 'Bucharest', 'Craiova', 'Drobeta', 'Eforie', 'Fagaras', 'Giurgiu', 'Hirsova', 'Iasi', 'Lugoj', 'Mehadia', 'Neamt', 'Oradea', 'Pitesti', 'Rimnicu', 'Sibiu', 'Timisoara', 'Urziceni', 'Vaslui', 'Zerind']\n"
     ]
    }
   ],
   "source": [
    "distances = {}\n",
    "all_cities = []\n",
    "\n",
    "for city in romania_map.locations.keys():\n",
    "    distances[city] = {}\n",
    "    all_cities.append(city)\n",
    "    \n",
    "all_cities.sort()\n",
    "print(all_cities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to populate the individual lists inside the dictionary with the manhattan distance between the cities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "for name_1, coordinates_1 in romania_map.locations.items():\n",
    "        for name_2, coordinates_2 in romania_map.locations.items():\n",
    "            distances[name_1][name_2] = np.linalg.norm(\n",
    "                [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])\n",
    "            distances[name_2][name_1] = np.linalg.norm(\n",
    "                [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The way neighbours are chosen currently isn't suitable for the travelling salespersons problem.\n",
    "We need a neighboring state that is similar in total path distance to the current state.\n",
    "<br>\n",
    "We need to change the function that finds neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def hill_climbing(problem):\n",
    "    \n",
    "    \"\"\"From the initial node, keep choosing the neighbor with highest value,\n",
    "    stopping when no neighbor is better. [Figure 4.2]\"\"\"\n",
    "    \n",
    "    def find_neighbors(state, number_of_neighbors=100):\n",
    "        \"\"\" finds neighbors using two_opt method \"\"\"\n",
    "        \n",
    "        neighbors = []\n",
    "        \n",
    "        for i in range(number_of_neighbors):\n",
    "            new_state = problem.two_opt(state)\n",
    "            neighbors.append(Node(new_state))\n",
    "            state = new_state\n",
    "            \n",
    "        return neighbors\n",
    "\n",
    "    # as this is a stochastic algorithm, we will set a cap on the number of iterations\n",
    "    iterations = 10000\n",
    "    \n",
    "    current = Node(problem.initial)\n",
    "    while iterations:\n",
    "        neighbors = find_neighbors(current.state)\n",
    "        if not neighbors:\n",
    "            break\n",
    "        neighbor = argmax_random_tie(neighbors,\n",
    "                                     key=lambda node: problem.value(node.state))\n",
    "        if problem.value(neighbor.state) <= problem.value(current.state):\n",
    "            current.state = neighbor.state\n",
    "        iterations -= 1\n",
    "        \n",
    "    return current.state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An instance of the TSP_problem class will be created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tsp = TSP_problem(all_cities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now generate an approximate solution to the problem by calling `hill_climbing`.\n",
    "The results will vary a bit each time you run it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Fagaras',\n",
       " 'Neamt',\n",
       " 'Iasi',\n",
       " 'Vaslui',\n",
       " 'Hirsova',\n",
       " 'Eforie',\n",
       " 'Urziceni',\n",
       " 'Bucharest',\n",
       " 'Giurgiu',\n",
       " 'Pitesti',\n",
       " 'Craiova',\n",
       " 'Drobeta',\n",
       " 'Mehadia',\n",
       " 'Lugoj',\n",
       " 'Timisoara',\n",
       " 'Arad',\n",
       " 'Zerind',\n",
       " 'Oradea',\n",
       " 'Sibiu',\n",
       " 'Rimnicu']"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hill_climbing(tsp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution looks like this.\n",
    "It is not difficult to see why this might be a good solution.\n",
    "<br>\n",
    "![title](images/hillclimb-tsp.png)"
   ]
  },
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2401 2402 
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2403 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2404 
   "source": [
Anthony Marakis's avatar
Contents for RL and Search Notebooks (#567)  
Anthony Marakis a validé
2405 
    "## GENETIC ALGORITHM\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2406 2407 2408 
    "\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",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2409 
    "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*."
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2410 2411 2412 2413 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2414 
   "metadata": {},
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 
   "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."
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2431 2432 2433 2434 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2435 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2436 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2437 2438 2439 2440 
    "### Glossary\n",
    "\n",
    "Before we continue, we will lay the basic terminology of the algorithm.\n",
    "\n",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2441 
    "* Individual/State: A list of elements (called *genes*) that represent possible solutions.\n",
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2442 
    "\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2443 2444 2445 2446 2447 2448 2449 
    "* 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."
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2450 2451 2452 2453 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2454 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2455 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2456 2457 2458 2459 2460 2461 2462 2463 
    "### 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",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2464 
    "* 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",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2465 2466 
    "\n",
    "![uniform crossover](images/uniform_crossover.png)"
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2467 2468 2469 2470 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2471 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2472 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2473 2474 2475 2476 
    "### 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",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2477 
    "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."
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2478 2479 2480 2481 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2482 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2483 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2484 
    "### Selection\n",
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2485 
    "\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2486 
    "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",
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2487 
    "\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2488 
    "The selection process is this:\n",
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2489 
    "\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2490 2491 2492 2493 
    "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",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2494 
    "$$ chance(i) = \\dfrac{fitness(i)}{\\sum_{k \\, in \\, P}{fitness(k)}} $$"
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2495 2496 2497 2498 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2499 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2500 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2501 2502 2503 2504 2505 
    "### 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:"
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2506 2507 2508 2509 
   ]
  },
  {
   "cell_type": "code",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2510 
   "execution_count": 2,
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 
   "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"
    }
   ],
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2626 
   "source": [
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
2627 
    "psource(genetic_algorithm)"
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2628 2629 2630 2631 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2632 
   "metadata": {},
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2633 2634 2635 2636 2637 2638 2639 
   "source": [
    "The algorithm takes the following input:\n",
    "\n",
    "* `population`: The initial population.\n",
    "\n",
    "* `fitness_fn`: The problem's fitness function.\n",
    "\n",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2640 
    "* `gene_pool`: The gene pool of the states/individuals. By default 0 and 1.\n",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2641 
    "\n",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2642 
    "* `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",
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2643 2644 2645 2646 2647 2648 
    "\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."
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2649 2650 2651 2652 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
2653 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2654 
   "source": [
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
2655 2656 
    "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",
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
2657 
    "The function of mating is accomplished by the method `recombine`:"
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
2658 2659 2660 2661 
   ]
  },
  {
   "cell_type": "code",
Antonis Maronikolakis's avatar
Search Notebook: Update GA (#524)  
Antonis Maronikolakis a validé
2662 
   "execution_count": 3,
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 
   "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",
       "    <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\">g</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">gene_pool</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=\"n\">r</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\">g</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"n\">new_gene</span> <span class=\"o\">=</span> <span class=\"n\">gene_pool</span><span class=\"p\">[</span><span class=\"n\">r</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=\"p\">[</span><span class=\"n\">new_gene</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"n\">x</span><span class=\"p\">[</span><span class=\"n\">c</span><span class=\"o\">+</span><span class=\"mi\">1</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(mutate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We pick a gene in `x` to mutate and a gene from the gene pool to replace it with.\n",
    "\n",
    "To help initializing the population we have the helper function `init_population`\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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",
Afficher toutes les annotations