Skip to content
GitLab
Rechercher un fichier Normal viewHistoryPermalink
search.ipynb 662 ko
Newer Older
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 
       "<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": 53,
   "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": 54,
   "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\">init_population</span><span class=\"p\">(</span><span class=\"n\">pop_number</span><span class=\"p\">,</span> <span class=\"n\">gene_pool</span><span class=\"p\">,</span> <span class=\"n\">state_length</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;Initializes population for genetic algorithm</span>\n",
       "<span class=\"sd\">    pop_number  :  Number of individuals in population</span>\n",
       "<span class=\"sd\">    gene_pool   :  List of possible values for individuals</span>\n",
       "<span class=\"sd\">    state_length:  The length of each individual&quot;&quot;&quot;</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\">population</span> <span class=\"o\">=</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=\"n\">pop_number</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">new_individual</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">gene_pool</span><span class=\"p\">[</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> <span class=\"k\">for</span> <span class=\"n\">j</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">state_length</span><span class=\"p\">)]</span>\n",
       "        <span class=\"n\">population</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_individual</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">return</span> <span class=\"n\">population</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(init_population)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function takes as input the number of individuals in the population, the gene pool and the length of each individual/state. It creates individuals with random genes and returns the population when done."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explanation\n",
    "\n",
    "Before we solve problems using the genetic algorithm, we will explain how to intuitively understand the algorithm using a trivial example.\n",
    "\n",
    "#### Generating Phrases\n",
    "\n",
    "In this problem, we use a genetic algorithm to generate a particular target phrase from a population of random strings. This is a classic example that helps build intuition about how to use this algorithm in other problems as well. Before we break the problem down, let us try to brute force the solution. Let us say that we want to generate the phrase \"genetic algorithm\". The phrase is 17 characters long. We can use any character from the 26 lowercase characters and the space character. To generate a random phrase of length 17, each space can be filled in 27 ways. So the total number of possible phrases is\n",
    "\n",
    "$$ 27^{17} = 2153693963075557766310747 $$\n",
    "\n",
    "which is a massive number. If we wanted to generate the phrase \"Genetic Algorithm\", we would also have to include all the 26 uppercase characters into consideration thereby increasing the sample space from 27 characters to 53 characters and the total number of possible phrases then would be\n",
    "\n",
    "$$ 53^{17} = 205442259656281392806087233013 $$\n",
    "\n",
    "If we wanted to include punctuations and numerals into the sample space, we would have further complicated an already impossible problem. Hence, brute forcing is not an option. Now we'll apply the genetic algorithm and see how it significantly reduces the search space. We essentially want to *evolve* our population of random strings so that they better approximate the target phrase as the number of generations increase. Genetic algorithms work on the principle of Darwinian Natural Selection according to which, there are three key concepts that need to be in place for evolution to happen. They are:\n",
    "\n",
    "* **Heredity**: There must be a process in place by which children receive the properties of their parents. <br> \n",
    "For this particular problem, two strings from the population will be chosen as parents and will be split at a random index and recombined as described in the `recombine` function to create a child. This child string will then be added to the new generation.\n",
    "\n",
    "\n",
    "* **Variation**: There must be a variety of traits present in the population or a means with which to introduce variation. <br>If there is no variation in the sample space, we might never reach the global optimum. To ensure that there is enough variation, we can initialize a large population, but this gets computationally expensive as the population gets larger. Hence, we often use another method called mutation. In this method, we randomly change one or more characters of some strings in the population based on a predefined probability value called the mutation rate or mutation probability as described in the `mutate` function. The mutation rate is usually kept quite low. A mutation rate of zero fails to introduce variation in the population and a high mutation rate (say 50%) is as good as a coin flip and the population fails to benefit from the previous recombinations. An optimum balance has to be maintained between population size and mutation rate so as to reduce the computational cost as well as have sufficient variation in the population.\n",
    "\n",
    "\n",
    "* **Selection**: There must be some mechanism by which some members of the population have the opportunity to be parents and pass down their genetic information and some do not. This is typically referred to as \"survival of the fittest\". <br>\n",
    "There has to be some way of determining which phrases in our population have a better chance of eventually evolving into the target phrase. This is done by introducing a fitness function that calculates how close the generated phrase is to the target phrase. The function will simply return a scalar value corresponding to the number of matching characters between the generated phrase and the target phrase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before solving the problem, we first need to define our target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "target = 'Genetic Algorithm'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We then need to define our gene pool, i.e the elements which an individual from the population might comprise of. Here, the gene pool contains all uppercase and lowercase letters of the English alphabet and the space character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The ASCII values of uppercase characters ranges from 65 to 91\n",
    "u_case = [chr(x) for x in range(65, 91)]\n",
    "# The ASCII values of lowercase characters ranges from 97 to 123\n",
    "l_case = [chr(x) for x in range(97, 123)]\n",
    "\n",
    "gene_pool = []\n",
    "gene_pool.extend(u_case) # adds the uppercase list to the gene pool\n",
    "gene_pool.extend(l_case) # adds the lowercase list to the gene pool\n",
    "gene_pool.append(' ')    # adds the space character to the gene pool"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now need to define the maximum size of each population. Larger populations have more variation but are computationally more  expensive to run algorithms on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_population = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As our population is not very large, we can afford to keep a relatively large mutation rate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mutation_rate = 0.07 # 7%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Now, we need to define the most important metric for the genetic algorithm, i.e the fitness function. This will simply return the number of matching characters between the generated sample and the target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitness_fn(sample):\n",
    "    # initialize fitness to 0\n",
    "    fitness = 0\n",
    "    for i in range(len(sample)):\n",
    "        # increment fitness by 1 for every matching character\n",
    "        if sample[i] == target[i]:\n",
    "            fitness += 1\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we run our genetic algorithm, we need to initialize a random population. We will use the `init_population` function to do this. We need to pass in the maximum population size, the gene pool and the length of each individual, which in this case will be the same as the length of the target phrase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "population = init_population(max_population, gene_pool, len(target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now define how the individuals in the population should change as the number of generations increases. First, the `select` function will be run on the population to select *two* individuals with high fitness values. These will be the parents which will then be recombined using the `recombine` function to generate the child."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "parents = select(2, population, fitness_fn) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The recombine function takes two parents as arguments, so we need to unpack the previous variable\n",
    "child = recombine(*parents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we need to apply a mutation according to the mutation rate. We call the `mutate` function on the child with the gene pool and mutation rate as the additional arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "child = mutate(child, gene_pool, mutation_rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above lines can be condensed into\n",
    "\n",
    "`child = mutate(recombine(*select(2, population, fitness_fn)), gene_pool, mutation_rate)`\n",
    "\n",
    "And, we need to do this `for` every individual in the current population to generate the new population."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "population = [mutate(recombine(*select(2, population, fitness_fn)), gene_pool, mutation_rate) for i in range(len(population))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The individual with the highest fitness can then be found using the `max` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "current_best = max(population, key=fitness_fn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's print this out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['J', 'y', 'O', 'e', ' ', 'h', 'c', 'r', 'C', 'W', 'H', 'o', 'r', 'R', 'y', 'P', 'U']\n"
     ]
    }
   ],
   "source": [
    "print(current_best)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that this is a list of characters. This can be converted to a string using the join function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JyOe hcrCWHorRyPU\n"
     ]
    }
   ],
   "source": [
    "current_best_string = ''.join(current_best)\n",
    "print(current_best_string)"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4582 4583 4584 4585 4586 4587 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4588 4589 4590 
    "We now need to define the conditions to terminate the algorithm. This can happen in two ways\n",
    "1. Termination after a predefined number of generations\n",
    "2. Termination when the fitness of the best individual of the current generation reaches a predefined threshold value.\n",
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4591 
    "\n",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4592 
    "We define these variables below"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4593 4594 4595 4596 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4597 4598 4599 4600 4601 
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4602 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 
    "ngen = 1200 # maximum number of generations\n",
    "# we set the threshold fitness equal to the length of the target phrase\n",
    "# i.e the algorithm only terminates whne it has got all the characters correct \n",
    "# or it has completed 'ngen' number of generations\n",
    "f_thres = len(target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "To generate `ngen` number of generations, we run a `for` loop `ngen` number of times. After each generation, we calculate the fitness of the best individual of the generation and compare it to the value of `f_thres` using the `fitness_threshold` function. After every generation, we print out the best individual of the generation and the corresponding fitness value. Lets now write a function to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genetic_algorithm_stepwise(population, fitness_fn, gene_pool=[0, 1], f_thres=None, ngen=1200, pmut=0.1):\n",
    "    for generation in range(ngen):\n",
    "        population = [mutate(recombine(*select(2, population, fitness_fn)), gene_pool, pmut) for i in range(len(population))]\n",
    "        # stores the individual genome with the highest fitness in the current population\n",
    "        current_best = ''.join(max(population, key=fitness_fn))\n",
    "        print(f'Current best: {current_best}\\t\\tGeneration: {str(generation)}\\t\\tFitness: {fitness_fn(current_best)}\\r', end='')\n",
    "        \n",
    "        # compare the fitness of the current best individual to f_thres\n",
    "        fittest_individual = fitness_threshold(fitness_fn, f_thres, population)\n",
    "        \n",
    "        # if fitness is greater than or equal to f_thres, we terminate the algorithm\n",
    "        if fittest_individual:\n",
    "            return fittest_individual, generation\n",
    "    return max(population, key=fitness_fn) , generation       "
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4641 4642 4643 4644 4645 4646 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4647 
    "The function defined above is essentially the same as the one defined in `search.py` with the added functionality of printing out the data of each generation."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4648 4649 4650 4651 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4652 
   "execution_count": 70,
Aman Deep Singh's avatar
Refactored N-Queens problem (#848)  
Aman Deep Singh a validé
4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 
   "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",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4744 4745 4746 4747 4748 
       "<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",
Aman Deep Singh's avatar
Refactored N-Queens problem (#848)  
Aman Deep Singh a validé
4749 
       "\n",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4750 4751 4752 4753 4754 4755 
       "        <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",
Aman Deep Singh's avatar
Refactored N-Queens problem (#848)  
Aman Deep Singh a validé
4756 4757 4758 4759 4760 4761 4762 4763 
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4764 4765 4766 4767 
     "metadata": {},
     "output_type": "display_data"
    }
   ],
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
4768 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4769 
    "psource(genetic_algorithm)"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4770 4771 4772 4773 
   ]
  },
  {
   "cell_type": "markdown",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4774 
   "metadata": {},
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4775 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4776 
    "We have defined all the required functions and variables. Let's now create a new population and test the function we wrote above."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4777 4778 4779 4780 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current best: Genetic Algorithm\t\tGeneration: 985\t\tFitness: 17\r"
     ]
    }
   ],
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4792 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4793 4794 
    "population = init_population(max_population, gene_pool, len(target))\n",
    "solution, generations = genetic_algorithm_stepwise(population, fitness_fn, gene_pool, f_thres, ngen, mutation_rate)"
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
4795 4796 4797 4798 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
4799 
   "metadata": {},
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
4800 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4801 4802 4803 
    "The genetic algorithm was able to converge!\n",
    "We implore you to rerun the above cell and play around with `target, max_population, f_thres, ngen` etc parameters to get a better intuition of how the algorithm works. To summarize, if we can define the problem states in simple array format and if we can create a fitness function to gauge how good or bad our approximate solutions are, there is a high chance that we can get a satisfactory solution using a genetic algorithm. \n",
    "- There is also a better GUI version of this program `genetic_algorithm_example.py` in the GUI folder for you to play around with."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4804 4805 4806 
   ]
  },
  {
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4807 4808 
   "cell_type": "markdown",
   "metadata": {},
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4809 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 
    "### Usage\n",
    "\n",
    "Below we give two example usages for the genetic algorithm, for a graph coloring problem and the 8 queens problem.\n",
    "\n",
    "#### Graph Coloring\n",
    "\n",
    "First we will take on the simpler problem of coloring a small graph with two colors. Before we do anything, let's imagine how a solution might look. First, we have to represent our colors. Say, 'R' for red and 'G' for green. These make up our gene pool. What of the individual solutions though? For that, we will look at our problem. We stated we have a graph. A graph has nodes and edges, and we want to color the nodes. Naturally, we want to store each node's color. If we have four nodes, we can store their colors in a list of genes, one for each node. A possible solution will then look like this: ['R', 'R', 'G', 'R']. In the general case, we will represent each solution with a list of chars ('R' and 'G'), with length the number of nodes.\n",
    "\n",
    "Next we need to come up with a fitness function that appropriately scores individuals. Again, we will look at the problem definition at hand. We want to color a graph. For a solution to be optimal, no edge should connect two nodes of the same color. How can we use this information to score a solution? A naive (and ineffective) approach would be to count the different colors in the string. So ['R', 'R', 'R', 'R'] has a score of 1 and ['R', 'R', 'G', 'G'] has a score of 2. Why that fitness function is not ideal though? Why, we forgot the information about the edges! The edges are pivotal to the problem and the above function only deals with node colors. We didn't use all the information at hand and ended up with an ineffective answer. How, then, can we use that information to our advantage?\n",
    "\n",
    "We said that the optimal solution will have all the edges connecting nodes of different color. So, to score a solution we can count how many edges are valid (aka connecting nodes of different color). That is a great fitness function!\n",
    "\n",
    "Let's jump into solving this problem using the `genetic_algorithm` function."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4823 4824 4825 4826 4827 4828 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4829 
    "First we need to represent the graph. Since we mostly need information about edges, we will just store the edges. We will denote edges with capital letters and nodes with integers:"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4830 4831 4832 4833 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4834 
   "execution_count": 72,
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4835 4836 4837 4838 4839 
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4840 4841 4842 4843 4844 4845 
    "edges = {\n",
    "    'A': [0, 1],\n",
    "    'B': [0, 3],\n",
    "    'C': [1, 2],\n",
    "    'D': [2, 3]\n",
    "}"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4846 4847 4848 4849 4850 4851 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4852 4853 4854 
    "Edge 'A' connects nodes 0 and 1, edge 'B' connects nodes 0 and 3 etc.\n",
    "\n",
    "We already said our gene pool is 'R' and 'G', so we can jump right into initializing our population. Since we have only four nodes, `state_length` should be 4. For the number of individuals, we will try 8. We can increase this number if we need higher accuracy, but be careful! Larger populations need more computating power and take longer. You need to strike that sweet balance between accuracy and cost (the ultimate dilemma of the programmer!)."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4855 4856 4857 4858 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['R', 'G', 'G', 'G'], ['G', 'R', 'R', 'G'], ['G', 'G', 'G', 'G'], ['G', 'R', 'G', 'G'], ['G', 'G', 'G', 'R'], ['G', 'R', 'R', 'G'], ['G', 'R', 'G', 'G'], ['G', 'G', 'R', 'G']]\n"
     ]
    }
   ],
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4870 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4871 4872 
    "population = init_population(8, ['R', 'G'], 4)\n",
    "print(population)"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4873 4874 4875 4876 4877 4878 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4879 4880 4881 
    "We created and printed the population. You can see that the genes in the individuals are random and there are 8 individuals each with 4 genes.\n",
    "\n",
    "Next we need to write our fitness function. We previously said we want the function to count how many edges are valid. So, given a coloring/individual `c`, we will do just that:"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4882 4883 4884 4885 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4886 
   "execution_count": 74,
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4887 4888 4889 4890 4891 
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4892 4893 
    "def fitness(c):\n",
    "    return sum(c[n1] != c[n2] for (n1, n2) in edges.values())"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4894 4895 4896 4897 4898 4899 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4900 
    "Great! Now we will run the genetic algorithm and see what solution it gives."
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4901 4902 4903 4904 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['R', 'G', 'R', 'G']\n"
     ]
    }
   ],
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4916 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4917 4918 
    "solution = genetic_algorithm(population, fitness, gene_pool=['R', 'G'])\n",
    "print(solution)"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4919 4920 4921 
   ]
  },
  {
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4922 4923 
   "cell_type": "markdown",
   "metadata": {},
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4924 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4925 
    "The algorithm converged to a solution. Let's check its score:"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4926 4927 4928 
   ]
  },
  {
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4929 4930 
   "cell_type": "code",
   "execution_count": 76,
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4931 
   "metadata": {},
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4932 4933 4934 4935 4936 4937 4938 4939 4940 
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4941 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4942 
    "print(fitness(solution))"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4943 4944 4945 
   ]
  },
  {
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4946 4947 
   "cell_type": "markdown",
   "metadata": {},
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4948 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4949 4950 4951 
    "The solution has a score of 4. Which means it is optimal, since we have exactly 4 edges in our graph, meaning all are valid!\n",
    "\n",
    "*NOTE: Because the algorithm is non-deterministic, there is a chance a different solution is given. It might even be wrong, if we are very unlucky!*"
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4952 4953 4954 4955 4956 4957 
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4958 
    "#### Eight Queens\n",
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
4959 
    "\n",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4960 
    "Let's take a look at a more complicated problem.\n",
Aman Deep Singh's avatar
Explanation of genetic algorithm functions with an example. Fixed #696 (#702)  
Aman Deep Singh a validé
4961 
    "\n",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4962 4963 4964 4965 4966 4967 4968 4969 4970 
    "In the *Eight Queens* problem, we are tasked with placing eight queens on an 8x8 chessboard without any queen threatening the others (aka queens should not be in the same row, column or diagonal). In its general form the problem is defined as placing *N* queens in an NxN chessboard without any conflicts.\n",
    "\n",
    "First we need to think about the representation of each solution. We can go the naive route of representing the whole chessboard with the queens' placements on it. That is definitely one way to go about it, but for the purpose of this tutorial we will do something different. We have eight queens, so we will have a gene for each of them. The gene pool will be numbers from 0 to 7, for the different columns. The *position* of the gene in the state will denote the row the particular queen is placed in.\n",
    "\n",
    "For example, we can have the state \"03304577\". Here the first gene with a value of 0 means \"the queen at row 0 is placed at column 0\", for the second gene \"the queen at row 1 is placed at column 3\" and so forth.\n",
    "\n",
    "We now need to think about the fitness function. On the graph coloring problem we counted the valid edges. The same thought process can be applied here. Instead of edges though, we have positioning between queens. If two queens are not threatening each other, we say they are at a \"non-attacking\" positioning. We can, therefore, count how many such positionings are there.\n",
    "\n",
    "Let's dive right in and initialize our population:"
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
4971 4972 4973 4974 
   ]
  },
  {
   "cell_type": "code",
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 6, 2, 0, 2, 3, 4, 7], [7, 2, 0, 6, 3, 3, 0, 6], [2, 3, 0, 6, 6, 2, 5, 5], [2, 6, 4, 2, 3, 5, 5, 5], [3, 1, 5, 1, 5, 1, 0, 3]]\n"
     ]
    }
   ],
Antonis Maronikolakis's avatar
Notebook: Genetic Algorithms (#503)  
Antonis Maronikolakis a validé
4986 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4987 4988 
    "population = init_population(100, range(8), 8)\n",
    "print(population[:5])"
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
4989 4990 4991 4992 
   ]
  },
  {
   "cell_type": "markdown",
Antonis Maronikolakis's avatar
Search Notebook: Fixing Latex (#522)  
Antonis Maronikolakis a validé
4993 
   "metadata": {},
ESHAN PANDEY's avatar
Implementation of GA in notebook search.ipyinb (#489)  
ESHAN PANDEY a validé
4994 
   "source": [
Aman Deep Singh's avatar
Search notebook update (#933)  
Aman Deep Singh a validé
4995 4996 4997 4998 4999 5000 
    "We have a population of 100 and each individual has 8 genes. The gene pool is the integers from 0 to 7, in string form. Above you can see the first five individuals.\n",
    "\n",
    "Next we need to write our fitness function. Remember, queens threaten each other if they are at the same row, column or diagonal.\n",
    "\n",
    "Since positionings are mutual, we must take care not to count them twice. Therefore for each queen, we will only check for conflicts for the queens after her.\n",
    "\n",
Afficher toutes les annotations