agreg/Algorithme_genetique_pour_generer_des_eclairages_modelisation_agreg.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Algorithme-génétique-pour-générer-des-éclairages---texte-de-modélisation-agrég\" data-toc-modified-id=\"Algorithme-génétique-pour-générer-des-éclairages---texte-de-modélisation-agrég-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Algorithme génétique pour générer des éclairages - texte de modélisation agrég</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2018-19\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2018-19-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2018-19</a></div><div class=\"lev2 toc-item\"><a href=\"#À-propos-de-ce-document\" data-toc-modified-id=\"À-propos-de-ce-document-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>À propos de ce document</a></div><div class=\"lev2 toc-item\"><a href=\"#Graphes,-éclairages-et-structures-de-données\" data-toc-modified-id=\"Graphes,-éclairages-et-structures-de-données-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Graphes, éclairages et structures de données</a></div><div class=\"lev2 toc-item\"><a href=\"#Fonctions-nécessaires-pour-l'algorithme-génétique\" data-toc-modified-id=\"Fonctions-nécessaires-pour-l'algorithme-génétique-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Fonctions nécessaires pour l'algorithme génétique</a></div><div class=\"lev3 toc-item\"><a href=\"#Validité-d'un-éclairage\" data-toc-modified-id=\"Validité-d'un-éclairage-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Validité d'un éclairage</a></div><div class=\"lev3 toc-item\"><a href=\"#Minimalité-d'un-éclairage\" data-toc-modified-id=\"Minimalité-d'un-éclairage-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Minimalité d'un éclairage</a></div><div class=\"lev3 toc-item\"><a href=\"#Conversion-entre-liste-de-valeurs-ternaires-et-éclairage\" data-toc-modified-id=\"Conversion-entre-liste-de-valeurs-ternaires-et-éclairage-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Conversion entre liste de valeurs ternaires et éclairage</a></div><div class=\"lev3 toc-item\"><a href=\"#Fonction-de-coût\" data-toc-modified-id=\"Fonction-de-coût-144\"><span class=\"toc-item-num\">1.4.4&nbsp;&nbsp;</span>Fonction de coût</a></div><div class=\"lev3 toc-item\"><a href=\"#Génération-aléatoire-d'un-individu\" data-toc-modified-id=\"Génération-aléatoire-d'un-individu-145\"><span class=\"toc-item-num\">1.4.5&nbsp;&nbsp;</span>Génération aléatoire d'un individu</a></div><div class=\"lev3 toc-item\"><a href=\"#Génération-aléatoire-d'une-population\" data-toc-modified-id=\"Génération-aléatoire-d'une-population-146\"><span class=\"toc-item-num\">1.4.6&nbsp;&nbsp;</span>Génération aléatoire d'une population</a></div><div class=\"lev3 toc-item\"><a href=\"#Squelette-générique-pour-l'algorithme-génétique\" data-toc-modified-id=\"Squelette-générique-pour-l'algorithme-génétique-147\"><span class=\"toc-item-num\">1.4.7&nbsp;&nbsp;</span>Squelette générique pour l'algorithme génétique</a></div><div class=\"lev3 toc-item\"><a href=\"#Mutations-et-croisements\" data-toc-modified-id=\"Mutations-et-croisements-148\"><span class=\"toc-item-num\">1.4.8&nbsp;&nbsp;</span>Mutations et croisements</a></div><div class=\"lev2 toc-item\"><a href=\"#Génération-d'éclairage-par-algorithme-génétique\" data-toc-modified-id=\"Génération-d'éclairage-par-algorithme-génétique-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Génération d'éclairage par algorithme génétique</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Conclusion</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithme génétique pour générer des éclairages - texte de modélisation agrég\n",
    "## Préparation à l'agrégation - ENS de Rennes, 2018-19\n",
    "- *Date* : 12 mars 2019\n",
    "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n",
    "- *Texte*: Annale 2012, [\"Éclairage graphe\" (public2012-D1)](http://agreg.org/Textes/public2012-D1.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## À propos de ce document\n",
    "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n",
    "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n",
    "- L'implémentation sera faite en Python 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphes, éclairages et structures de données\n",
    "\n",
    "On donne tout de suite un exemple de graphe, en prenant le 3ème exemple de la Figure 1 du texte.\n",
    "\n",
    "![Graphes de la Figure 1 du texte](images/ville_eclairee_1.png)\n",
    "\n",
    "On va définir ce graphe, comme une liste d'arêtes, et plusieurs éclairages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphe1 = [(1,3), (3,2), (2,4), (2,6), (2,7), (4,5), (5,6), (6,7), (6,9), (7,8), (8,9)]\n",
    "graphe1 = [ (u-1, v-1) for (u,v) in graphe1 ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nbsommets(graphe):\n",
    "    n = 0\n",
    "    for (u, v) in graphe:\n",
    "        if u > n or v > n: n = max(u, v)\n",
    "    return n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nbsommets(graphe1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quatre exemples d'éclairages, deux satisfaisant donc l'un trivialement, et les deux autres non satisfaisants :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "eclairage1_sat = [0, 1, 2, 3, 4, 5, 6, 7, 8]  # trivialement valide car on éclaire tout \n",
    "eclairage2_sat = [1, 2, 3, 5, 6, 8]  # valide mais on éclaire pas tout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "eclairage1_nonsat = [2, 4, 8]\n",
    "eclairage2_nonsat = [1, 2, 3, 5, 6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fonctions nécessaires pour l'algorithme génétique\n",
    "\n",
    "On va devoir implémenter des fonctions réalisants les tâches suivantes :\n",
    "\n",
    "- vérifier qu'un ensemble de sommets éclairés est un éclairage valide,\n",
    "- vérifier qu'un éclairage donné sous forme de tableau de `gauche`, `droite`, `lesdeux` est un éclairage valide,\n",
    "- compter le nombre de places éclairés pour un éclairage donné sous la forme précédente (c'est la fonction de coût, ou \"fitness\" de l'algorithme génétique).\n",
    "\n",
    "Ensuite pour l'initialisation de l'algorithm génétique il nous faudra :\n",
    "\n",
    "- générer un éclairage aléatoirement,\n",
    "- faire ça 100 fois pour avoir une population initiale.\n",
    "\n",
    "Et puis pour chaque étape de l'algorithme génétique, on transformera les 100 individus\n",
    "\n",
    "- trier une population d'éclairages suivant un critère (= le nombre de lampadaires utilisés),\n",
    "- faire muter aléatoirement 4 éclairages parmi les 48 meilleurs,\n",
    "- se faire reproduire les 48 moins bons individus restants par \"crossing over\", ou mutation croisée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Validité d'un éclairage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_eclairage(graphe, places_eclairees):\n",
    "    \"\"\" Cette fonction est en O(M + L) = O(M) où M est le nombre d'arêtes, et L le nombre de places éclairées (<= N <= M par connexité).\n",
    "    \"\"\"\n",
    "    n = nbsommets(graphe)\n",
    "    sont_eclairees = [ False for _ in range(n) ]\n",
    "    for p in places_eclairees:\n",
    "        sont_eclairees[p] = True\n",
    "    for (u, v) in graphe:\n",
    "        if not sont_eclairees[u] and not sont_eclairees[v]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_eclairage(graphe1, eclairage1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_eclairage(graphe1, eclairage2_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_eclairage(graphe1, eclairage1_nonsat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_eclairage(graphe1, eclairage2_nonsat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimalité d'un éclairage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def places_moins_une(places_eclairees, place_a_enlever):\n",
    "    \"\"\" En O(L) si L est le nombre de places éclairées.\"\"\"\n",
    "    return [place for place in places_eclairees if place != place_a_enlever]\n",
    "\n",
    "def est_minimal(graphe, places_eclairees):\n",
    "    \"\"\" Cette fonction est en O(M L) où M est le nombre d'arêtes, et L le nombre de places éclairées.\n",
    "    \"\"\"\n",
    "    return est_eclairage(graphe, places_eclairees) and not(all([\n",
    "        est_eclairage(graphe, places_moins_une(places_eclairees, place_a_enlever))\n",
    "        for place_a_enlever in places_eclairees\n",
    "    ]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_minimal(graphe1, eclairage1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_minimal(graphe1, eclairage2_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_minimal(graphe1, eclairage1_nonsat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_minimal(graphe1, eclairage2_nonsat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion entre liste de valeurs ternaires et éclairage\n",
    "\n",
    "Si le graphe $G=(V,E)$ est donné par un tableau de ses rues $E = \\{(u,v)\\}$, on représente une liste de places éclairées $V'$ par un tableau de valeurs ternaires `gauche`, `droite` ou `lesdeux`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "gauche, droite, lesdeux = \"G\", \"D\", \"2\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eclairage_vers_ternaires(graphe, places_eclairees):\n",
    "    \"\"\" O(M)\"\"\"\n",
    "    n = nbsommets(graphe)\n",
    "    ternaires = []\n",
    "    sont_eclairees = [ False for _ in range(n) ]\n",
    "    for p in places_eclairees:\n",
    "        sont_eclairees[p] = True\n",
    "    for (u,v) in graphe:\n",
    "        if sont_eclairees[u] and sont_eclairees[v]:\n",
    "            ternaires.append(lesdeux)\n",
    "        elif sont_eclairees[u]:\n",
    "            ternaires.append(gauche)\n",
    "        elif sont_eclairees[v]:\n",
    "            ternaires.append(droite)\n",
    "    return ternaires"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ternaires_vers_eclairage(graphe, ternaires):\n",
    "    \"\"\" O(M)\"\"\"\n",
    "    n = nbsommets(graphe)\n",
    "    places_eclairees = [ False for _ in range(n) ]\n",
    "    for (u,v), ternaire in zip(graphe, ternaires):\n",
    "        if ternaire == gauche or ternaire == lesdeux:\n",
    "            places_eclairees[u] = True\n",
    "        if ternaire == droite or ternaire == lesdeux:\n",
    "            places_eclairees[v] = True\n",
    "    # O(N)\n",
    "    eclairage = []\n",
    "    for i, p in enumerate(places_eclairees):\n",
    "        if p: eclairage.append(i)\n",
    "    return eclairage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_valide_ternaires(graphe, ternaires):\n",
    "    \"\"\" O(M)\"\"\"\n",
    "    return est_eclairage(graphe, ternaires_vers_eclairage(graphe, ternaires))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 2),\n",
       " (2, 1),\n",
       " (1, 3),\n",
       " (1, 5),\n",
       " (1, 6),\n",
       " (3, 4),\n",
       " (4, 5),\n",
       " (5, 6),\n",
       " (5, 8),\n",
       " (6, 7),\n",
       " (7, 8)]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graphe1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ternaires1_sat = eclairage_vers_ternaires(graphe1, eclairage1_sat)\n",
    "ternaires1_sat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(eclairage1_sat)\n",
    "ternaires_vers_eclairage(graphe1, eclairage_vers_ternaires(graphe1, eclairage1_sat))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['D', '2', '2', '2', '2', 'G', 'D', '2', '2', 'G', 'D']"
      ]
     },
     "execution_count": 141,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ternaires2_sat = eclairage_vers_ternaires(graphe1, eclairage2_sat)\n",
    "ternaires2_sat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 6, 8]\n",
      "['D', '2', '2', '2', '2', 'G', 'D', '2', '2', 'G', 'D']\n",
      "[1, 2, 3, 5, 6, 8]\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(eclairage2_sat)\n",
    "print(eclairage_vers_ternaires(graphe1, eclairage2_sat))\n",
    "print(ternaires_vers_eclairage(graphe1, eclairage_vers_ternaires(graphe1, eclairage2_sat)))\n",
    "print(est_valide_ternaires(graphe1, eclairage_vers_ternaires(graphe1, eclairage2_sat)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fonction de coût\n",
    "On a donc la \"fonction de coût\" recherchée :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nb_places_eclairees(graphe, ternaires):\n",
    "    \"\"\" O(M)\"\"\"\n",
    "    eclairage = ternaires_vers_eclairage(graphe, ternaires)\n",
    "    return len(eclairage)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Génération aléatoire d'un individu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def un_ternaire_aleatoire():\n",
    "    \"\"\" O(1)\"\"\"\n",
    "    return random.choice([gauche, droite, lesdeux])\n",
    "\n",
    "def un_ternaire_aleatoire_different(valeur):\n",
    "    \"\"\" O(1)\"\"\"\n",
    "    if valeur == gauche:\n",
    "        return random.choice([droite, lesdeux])\n",
    "    elif valeur == droite:\n",
    "        return random.choice([gauche, lesdeux])\n",
    "    else:\n",
    "        return random.choice([gauche, droite])\n",
    "\n",
    "def un_individu(graphe):\n",
    "    \"\"\" O(M)\"\"\"\n",
    "    return [un_ternaire_aleatoire() for (u,v) in graphe]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut facilement générer dix individus différents, qui sont tous des éclairages valides, et afficher leur coût :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L'éclairage ['D', '2', '2', '2', 'D', 'D', '2', 'G', 'D', '2', '2'] a un coût = 8\n",
      "L'éclairage ['2', 'D', 'G', 'G', 'G', 'D', '2', 'G', 'G', 'D', '2'] a un coût = 7\n",
      "L'éclairage ['D', 'G', 'G', 'G', 'G', '2', 'G', 'D', '2', '2', '2'] a un coût = 8\n",
      "L'éclairage ['D', 'G', 'D', '2', 'G', 'D', 'G', 'D', '2', 'G', 'G'] a un coût = 8\n",
      "L'éclairage ['D', 'D', '2', 'G', '2', 'G', 'G', 'D', 'D', 'D', '2'] a un coût = 7\n",
      "L'éclairage ['2', '2', 'D', 'D', 'D', '2', 'G', 'D', 'D', 'D', 'D'] a un coût = 9\n",
      "L'éclairage ['D', 'G', '2', 'G', '2', '2', 'D', '2', 'G', 'D', '2'] a un coût = 8\n",
      "L'éclairage ['2', 'D', 'D', '2', 'D', '2', 'G', 'G', 'D', 'G', '2'] a un coût = 9\n",
      "L'éclairage ['D', 'D', 'D', '2', 'G', '2', 'D', '2', 'G', '2', 'G'] a un coût = 7\n",
      "L'éclairage ['D', 'D', '2', '2', '2', 'D', '2', '2', 'D', '2', 'D'] a un coût = 8\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    ternaires = un_individu(graphe1)\n",
    "    assert est_valide_ternaires(graphe1, ternaires)\n",
    "    cout = nb_places_eclairees(graphe1, ternaires)\n",
    "    print(\"L'éclairage\", ternaires, \"a un coût =\", cout)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Génération aléatoire d'une population"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def population_initiale(graphe, taille_population):\n",
    "    return [ un_individu(graphe) for _ in range(taille_population) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, une population initiale de taille 5 est :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L'éclairage ['D', 'D', 'G', 'G', 'G', 'G', '2', 'G', '2', 'D', 'D'] a un coût = 7\n",
      "L'éclairage ['D', 'D', '2', 'D', 'G', 'G', 'D', '2', 'G', '2', '2'] a un coût = 7\n",
      "L'éclairage ['2', 'D', '2', '2', 'G', 'D', 'D', 'G', 'G', '2', 'G'] a un coût = 8\n",
      "L'éclairage ['D', '2', 'G', 'D', 'G', 'G', 'D', 'D', '2', 'G', 'G'] a un coût = 7\n",
      "L'éclairage ['D', 'G', 'D', '2', 'G', 'G', 'G', '2', 'G', 'G', 'G'] a un coût = 7\n"
     ]
    }
   ],
   "source": [
    "pop = population_initiale(graphe1, 5)\n",
    "for individu in pop:\n",
    "    print(\"L'éclairage\", individu, \"a un coût =\", nb_places_eclairees(graphe1, individu))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['D', 'D', 'G', 'G', 'G', 'G', '2', 'G', '2', 'D', 'D'],\n",
       " ['D', 'D', '2', 'D', 'G', 'G', 'D', '2', 'G', '2', '2'],\n",
       " ['D', '2', 'G', 'D', 'G', 'G', 'D', 'D', '2', 'G', 'G'],\n",
       " ['D', 'G', 'D', '2', 'G', 'G', 'G', '2', 'G', 'G', 'G'],\n",
       " ['2', 'D', '2', '2', 'G', 'D', 'D', 'G', 'G', '2', 'G']]"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(pop, key=lambda individu: nb_places_eclairees(graphe1, individu))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut donc facilement trier des "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Squelette générique pour l'algorithme génétique\n",
    "\n",
    "On va écrire une fonction générique. Pour visualiser l'évolution de la population, plutôt que d'afficher une liste de 100 coûts, je préfère afficher un décompte du nombre d'individus ayant un certain coût, en Python cela se fait très facilement avec `collections.Counter` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 5, 2: 3, 3: 1})"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "collections.Counter([1,1,1,1,1,2,2,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [],
   "source": [
    "def algorithme_genetique(\n",
    "    pop_init,\n",
    "    fct_cout,\n",
    "    muter_un,\n",
    "    croiser_deux,\n",
    "    taille_pop=100,\n",
    "    tau_meilleurs=0.48,\n",
    "    tau_cross=0.48,\n",
    "    nb_generations=1000,\n",
    "):\n",
    "    \"\"\" Complexité en O(nb_generations * [\n",
    "        taille_pop * log(taille_pop) * C_cout\n",
    "        + taille_pop * C_croisement\n",
    "        + taille_pop * C_mutation\n",
    "        ) où :\n",
    "        \n",
    "        - C_cout est le coût de calcul de la fonction d'évaluation fct_cout,\n",
    "        - C_croisement est le coût de calcul de la fonction de croisement croiser_deux,\n",
    "        - C_mutation est le coût de calcul de la fonction de mutation muter_un,\n",
    "    \"\"\"\n",
    "    nb_meilleurs = int(tau_meilleurs * taille_pop)\n",
    "    nb_enfants = 2 * (int(tau_cross * taille_pop)//2)  # nb paire !\n",
    "    nb_mutes = taille_pop - nb_meilleurs - nb_enfants\n",
    "    # première population\n",
    "    pop = pop_init(taille_pop)\n",
    "    # nb_generations étapes, toutes identiques\n",
    "    for generation in range(nb_generations):\n",
    "        couts = [fct_cout(sol) for sol in pop]\n",
    "        # bonus: affichage de la liste des couts\n",
    "        print(\"La génération numéro\", generation, \"a les coûts suivants :\", collections.Counter(couts))\n",
    "        pop_triees = sorted(pop, key=fct_cout)\n",
    "        # 1) on prend les 48% meilleurs, laissés tels quels\n",
    "        meilleurs = pop_triees[:nb_meilleurs]\n",
    "        # 2) on prend les 48% moins bons, on les croise\n",
    "        moins_bons = pop_triees[-nb_enfants:]\n",
    "        enfants = [ ]\n",
    "        for i in range(len(moins_bons) // 2):\n",
    "            parent_1 = moins_bons[2*i]\n",
    "            parent_2 = moins_bons[2*i + 1]\n",
    "            enfant_1, enfant_2 = croiser_deux(parent_1, parent_2)\n",
    "            enfants.append(enfant_1)\n",
    "            enfants.append(enfant_2)\n",
    "        # 3) on prend les 4% meilleurs, et on les mute un peu\n",
    "        mutes = [ ]\n",
    "        for i in range(nb_mutes):\n",
    "            sain = meilleurs[i]\n",
    "            un_xmen = muter_un(sain)\n",
    "            mutes.append(un_xmen)\n",
    "        # on combine les trois listes en une nouvelle population\n",
    "        nouvelle_pop = meilleurs + enfants + mutes\n",
    "        pop = nouvelle_pop\n",
    "    # a la fin, on renvoie la meilleure solution\n",
    "    meilleure_solution = max(pop, key=fct_cout)\n",
    "    return meilleure_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mutations et croisements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On doit encore écrire les deux fonctions clés, `muter_un` et `croiser_deux`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [],
   "source": [
    "def une_mutation(graphe, ternaires):\n",
    "    position = random.randint(0, len(ternaires) - 1)\n",
    "    mute = [ t for t in ternaires ]\n",
    "    mute[position] = un_ternaire_aleatoire_different(mute[position])\n",
    "    return mute\n",
    "\n",
    "def mutation(graphe, ternaires):\n",
    "    M = len(graphe)\n",
    "    nb_mutation = random.randint(1, M)\n",
    "    mute = une_mutation(graphe, ternaires)\n",
    "    for _ in range(nb_mutation - 1):\n",
    "        mute = une_mutation(graphe, mute)\n",
    "    return mute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 2),\n",
       " (2, 1),\n",
       " (1, 3),\n",
       " (1, 5),\n",
       " (1, 6),\n",
       " (3, 4),\n",
       " (4, 5),\n",
       " (5, 6),\n",
       " (5, 8),\n",
       " (6, 7),\n",
       " (7, 8)]"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "['2', '2', '2', '2', '2', '2', '2', '2', '2', '2', '2']"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graphe1\n",
    "ternaires1_sat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '2', '2', '2', '2', '2', 'D', '2', '2', '2', '2']"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "une_mutation(graphe1, ternaires1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['D', '2', 'D', 'D', '2', 'G', 'G', '2', '2', '2', 'D']"
      ]
     },
     "execution_count": 183,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mutation(graphe1, ternaires1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '2', 'G', '2', '2', '2', 'D', '2', '2', 'G', 'G']"
      ]
     },
     "execution_count": 184,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mutation(graphe1, ternaires1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '2', '2', 'G', '2', 'D', 'D', '2', 'D', '2', '2']"
      ]
     },
     "execution_count": 185,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mutation(graphe1, ternaires1_sat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "def croiser_deux_ternaires(graphe, ternaires_1, ternaires_2):\n",
    "    M1 = len(ternaires_1) // 2\n",
    "    M2 = len(ternaires_2) // 2\n",
    "    enfant_1 = ternaires_1[:M1] + ternaires_2[M2:]\n",
    "    enfant_2 = ternaires_1[M1:] + ternaires_2[:M2]\n",
    "    return enfant_1, enfant_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Les deux parents suivants :\n",
      "['2', 'D', '2', '2', '2', '2', '2', '2', '2', '2', 'G']\n",
      "['2', '2', '2', 'D', 'G', '2', 'D', 'D', '2', '2', '2']\n",
      "peuvent par exemple donner les deux enfants suivants :\n",
      "['2', 'D', '2', '2', '2', '2', 'D', 'D', '2', '2', '2']\n",
      "['2', '2', '2', '2', '2', 'G', '2', '2', '2', 'D', 'G']\n"
     ]
    }
   ],
   "source": [
    "print(\"Les deux parents suivants :\")\n",
    "ternaires_1 = mutation(graphe1, ternaires1_sat)\n",
    "print(ternaires_1)\n",
    "ternaires_2 = mutation(graphe1, ternaires1_sat)\n",
    "print(ternaires_2)\n",
    "enfant_1, enfant_2 = croiser_deux_ternaires(graphe1, ternaires_1, ternaires_2)\n",
    "print(\"peuvent par exemple donner les deux enfants suivants :\")\n",
    "print(enfant_1)\n",
    "print(enfant_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Génération d'éclairage par algorithme génétique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On assemble le tout :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eclairage_genetique(graphe,\n",
    "    taille_pop=100,\n",
    "    tau_meilleurs=0.48,\n",
    "    tau_cross=0.48,\n",
    "    nb_generations=50,\n",
    "):\n",
    "    \"\"\" Complexité en O(nb_generations * [\n",
    "        taille_pop * log(taille_pop) * O(M)\n",
    "        + taille_pop * O(M)\n",
    "        + taille_pop * O(M)\n",
    "        )  = O (nb_generations * taille_pop * log(taille_pop) * M) où :\n",
    "        \n",
    "        - M est le nombre d'arêtes dans le graphe.\n",
    "        \n",
    "        Donc si nb_generations et taille_pop sont constantes, cette fonction est en O(M).\n",
    "    \"\"\"\n",
    "    # on définit les quatre fonctions, pour ce graphe\n",
    "    def pop_init(taille_pop):\n",
    "        return population_initiale(graphe, taille_pop)\n",
    "    def fct_cout(individu):\n",
    "        return nb_places_eclairees(graphe, individu)\n",
    "    def muter_un(individu):\n",
    "        return mutation(graphe, individu)\n",
    "    def croiser_deux(parent_1, parent_2):\n",
    "        return croiser_deux_ternaires(graphe, parent_1, parent_2)\n",
    "    # on appelle la fonction générique\n",
    "    return algorithme_genetique(\n",
    "        pop_init,\n",
    "        fct_cout,\n",
    "        muter_un,\n",
    "        croiser_deux,\n",
    "        taille_pop=taille_pop,\n",
    "        tau_meilleurs=tau_meilleurs,\n",
    "        tau_cross=tau_cross,\n",
    "        nb_generations=nb_generations,\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et on donne un exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "La génération numéro 0 a les coûts suivants : Counter({9: 36, 8: 34, 7: 26, 6: 4})\n",
      "La génération numéro 1 a les coûts suivants : Counter({8: 34, 7: 32, 9: 29, 6: 5})\n",
      "La génération numéro 2 a les coûts suivants : Counter({7: 35, 9: 30, 8: 28, 6: 7})\n",
      "La génération numéro 3 a les coûts suivants : Counter({7: 38, 9: 29, 8: 23, 6: 10})\n",
      "La génération numéro 4 a les coûts suivants : Counter({7: 45, 9: 28, 8: 17, 6: 10})\n",
      "La génération numéro 5 a les coûts suivants : Counter({7: 48, 9: 27, 8: 13, 6: 12})\n",
      "La génération numéro 6 a les coûts suivants : Counter({7: 45, 9: 24, 8: 18, 6: 13})\n",
      "La génération numéro 7 a les coûts suivants : Counter({7: 41, 9: 23, 8: 22, 6: 14})\n",
      "La génération numéro 8 a les coûts suivants : Counter({7: 39, 8: 25, 9: 22, 6: 14})\n",
      "La génération numéro 9 a les coûts suivants : Counter({7: 40, 9: 26, 8: 19, 6: 15})\n",
      "La génération numéro 10 a les coûts suivants : Counter({7: 39, 9: 23, 8: 21, 6: 17})\n",
      "La génération numéro 11 a les coûts suivants : Counter({7: 40, 9: 26, 6: 20, 8: 14})\n",
      "La génération numéro 12 a les coûts suivants : Counter({7: 41, 6: 23, 9: 22, 8: 14})\n",
      "La génération numéro 13 a les coûts suivants : Counter({7: 33, 6: 26, 8: 20, 9: 20, 5: 1})\n",
      "La génération numéro 14 a les coûts suivants : Counter({7: 30, 6: 28, 9: 23, 8: 17, 5: 2})\n",
      "La génération numéro 15 a les coûts suivants : Counter({7: 30, 6: 29, 9: 26, 8: 13, 5: 2})\n",
      "La génération numéro 16 a les coûts suivants : Counter({6: 31, 8: 25, 7: 24, 9: 18, 5: 2})\n",
      "La génération numéro 17 a les coûts suivants : Counter({6: 33, 7: 24, 9: 24, 8: 17, 5: 2})\n",
      "La génération numéro 18 a les coûts suivants : Counter({6: 34, 8: 22, 9: 21, 7: 20, 5: 3})\n",
      "La génération numéro 19 a les coûts suivants : Counter({6: 35, 9: 22, 7: 21, 8: 19, 5: 3})\n",
      "La génération numéro 20 a les coûts suivants : Counter({6: 37, 7: 21, 9: 21, 8: 18, 5: 3})\n",
      "La génération numéro 21 a les coûts suivants : Counter({6: 39, 9: 23, 8: 20, 7: 15, 5: 3})\n",
      "La génération numéro 22 a les coûts suivants : Counter({6: 41, 9: 24, 8: 19, 7: 13, 5: 3})\n",
      "La génération numéro 23 a les coûts suivants : Counter({6: 43, 9: 23, 8: 16, 7: 14, 5: 4})\n",
      "La génération numéro 24 a les coûts suivants : Counter({6: 43, 8: 19, 9: 19, 7: 15, 5: 4})\n",
      "La génération numéro 25 a les coûts suivants : Counter({6: 46, 9: 19, 8: 16, 7: 15, 5: 4})\n",
      "La génération numéro 26 a les coûts suivants : Counter({6: 44, 8: 25, 9: 15, 7: 12, 5: 4})\n",
      "La génération numéro 27 a les coûts suivants : Counter({6: 47, 9: 22, 8: 15, 7: 12, 5: 4})\n",
      "La génération numéro 28 a les coûts suivants : Counter({6: 44, 9: 21, 8: 19, 7: 11, 5: 5})\n",
      "La génération numéro 29 a les coûts suivants : Counter({6: 45, 9: 22, 8: 15, 7: 13, 5: 5})\n",
      "La génération numéro 30 a les coûts suivants : Counter({6: 46, 9: 23, 8: 14, 7: 12, 5: 5})\n",
      "La génération numéro 31 a les coûts suivants : Counter({6: 44, 9: 21, 8: 18, 7: 12, 5: 5})\n",
      "La génération numéro 32 a les coûts suivants : Counter({6: 46, 9: 23, 8: 18, 7: 8, 5: 5})\n",
      "La génération numéro 33 a les coûts suivants : Counter({6: 44, 8: 24, 9: 20, 7: 7, 5: 5})\n",
      "La génération numéro 34 a les coûts suivants : Counter({6: 43, 9: 29, 8: 12, 7: 11, 5: 5})\n",
      "La génération numéro 35 a les coûts suivants : Counter({6: 45, 9: 23, 8: 18, 7: 9, 5: 5})\n",
      "La génération numéro 36 a les coûts suivants : Counter({6: 47, 9: 26, 8: 15, 7: 7, 5: 5})\n",
      "La génération numéro 37 a les coûts suivants : Counter({6: 44, 9: 22, 8: 20, 7: 9, 5: 5})\n",
      "La génération numéro 38 a les coûts suivants : Counter({6: 44, 8: 22, 9: 20, 7: 9, 5: 5})\n",
      "La génération numéro 39 a les coûts suivants : Counter({6: 45, 9: 21, 8: 21, 7: 8, 5: 5})\n",
      "La génération numéro 40 a les coûts suivants : Counter({6: 47, 9: 25, 8: 13, 7: 10, 5: 5})\n",
      "La génération numéro 41 a les coûts suivants : Counter({6: 45, 9: 26, 8: 17, 7: 7, 5: 5})\n",
      "La génération numéro 42 a les coûts suivants : Counter({6: 45, 9: 25, 8: 14, 7: 9, 5: 7})\n",
      "La génération numéro 43 a les coûts suivants : Counter({6: 44, 9: 21, 8: 16, 7: 11, 5: 8})\n",
      "La génération numéro 44 a les coûts suivants : Counter({6: 42, 9: 22, 8: 18, 7: 10, 5: 8})\n",
      "La génération numéro 45 a les coûts suivants : Counter({6: 44, 9: 23, 8: 16, 7: 9, 5: 8})\n",
      "La génération numéro 46 a les coûts suivants : Counter({6: 43, 8: 21, 9: 18, 7: 10, 5: 8})\n",
      "La génération numéro 47 a les coûts suivants : Counter({6: 41, 8: 22, 9: 19, 7: 10, 5: 8})\n",
      "La génération numéro 48 a les coûts suivants : Counter({6: 43, 9: 25, 8: 15, 7: 9, 5: 8})\n",
      "La génération numéro 49 a les coûts suivants : Counter({6: 42, 9: 21, 8: 17, 7: 12, 5: 8})\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['2', '2', '2', 'G', 'G', 'G', 'G', '2', 'D', 'D', 'G']"
      ]
     },
     "execution_count": 205,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eclairage_genetique(graphe1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a trouvé un éclairage valide avec seulement 5 places éclairées, en partant d'une population qui avait des coûts entre 7 et 9."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Si vous êtes curieux, je vous laisse travailler davantage sur ça."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "292px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": false,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "317.333px",
    "left": "917.99px",
    "right": "20px",
    "top": "8px",
    "width": "384px"
   },
   "toc_section_display": "block",
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}