03_algoritmos_geneticos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algoritmos Genéticos\n",
    "\n",
    "<img src='https://github.com/shivamshekhar/Chrome-T-Rex-Rush/raw/master/screenshot.gif'>\n",
    "\n",
    "Algoritmos genéticos (AGs) são uma classe de algoritmos de otimização inspirada no processo evolutivo biológico, que fazem parte do que se chama de computação evolutiva. AGs são inspirados em modelos biológicos, e se fundamentam na Genética de Mendel (1965) e também na Teoria da Evolução de Darwin (1959), usando uma medida para avaliar a capacidade que os indivíduos de uma população têm para sobriver e se reproduzir.\n",
    "\n",
    "Dessa forma, espera-se que as características dos indivíduos ''mais aptos'', que se reproduzem, em uma geração sejam  transferidas para a próxima geração. Podemos definir como um pseudocódigo do AG o seguinte:\n",
    "\n",
    "\n",
    "    ENTRADA: População Inicial (aleatória)\n",
    "             Função de Fitness\n",
    "             Critério de Parada\n",
    "             \n",
    "    REPITA (até que o critério de parada seja atendido):\n",
    "    \n",
    "        PASSO 1: Aplicar a função de fitness a cada indivíduo\n",
    "        PASSO 2: Selecionar os x melhores indivíduos\n",
    "        PASSO 3: Reprodução\n",
    "                - Aplicar o crossover a um par (com prob = p)\n",
    "                - Aplicar mutação (com prob = p’)\n",
    "        PASSO 4: Formar uma nova população com os filhos gerados\n",
    "  \n",
    "  \n",
    "    SAÍDA: Melhor indivíduo presente na geração final    \n",
    "\n",
    "## O que iremos fazer?\n",
    "\n",
    "Neste *notebook*, iremos utilizar AGs para criar um modelo capaz de jogar o [chrome-trex-rush](https://github.com/fernandokm/chrome-trex-rush) -- uma versão, em Python, do *game* T-Rex embutido no Google Chrome. \n",
    "\n",
    "Assim, o nosso modelo que controlará o dinossauro poderá assumir três possíveis ações:\n",
    "    - Não fazer nada (e continuar correndo)\n",
    "    - Pular (os cactus)\n",
    "    - Agachar (dos pterossauros)\n",
    "\n",
    "\n",
    "Em geral, as nossas <mark>variáveis de entrada</mark> são parâmetros que nos <mark>dizem coisas sobre o nosso problema</mark>. No caso do dinossauro, poderia ser a **distância até o próximo obstáculo**, a **velocidade**, a **altura do próximo obstáculo**, etc. <mark>Lembrando que o jogo é dinâmico</mark>, ou seja, essas variáveis estão em constante mudança, a cada tomada de decisão, rodamos mais uma decisão com outros valores. **Esse vetor com essas variáveis é chamado de “estado do jogo”.**\n",
    "\n",
    "Nossa função de decisão não nos retornará um número, mas sim um vetor com três números (um para cada ação) e nós vamos escolher a ação cuja função nos dê o maior output dentre os três.\n",
    "\n",
    "--\n",
    "\n",
    "\n",
    "Para instalarmos o pacote do jogo, basta executar a célula abaixo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "! pip install --user git+https://github.com/fernandokm/chrome-trex-rush@master"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "import numpy as np\n",
    "import random\n",
    "from chrome_trex import DinoGame\n",
    "\n",
    "\n",
    "CHANCE_MUT = .2      # Chance de mutação de um peso qualquer\n",
    "NUM_INDIVIDUOS = 20  # Tamanho da população\n",
    "NUM_MELHORES = 5     # Número de indivíduos que são mantidos de uma geração para a próxima"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ver_individuo(individuo :np.array, ax :plt.axis=None):\n",
    "    \"\"\"Função vizualização de indivíduos\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    individuo : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    \"\"\"\n",
    "    \n",
    "    if ax is None:\n",
    "        fig, ax = plt.subplots(figsize=(8, 2))\n",
    "\n",
    "    sns.heatmap(individuo,annot=True, fmt='.2f', cmap='gray', ax=ax)\n",
    "\n",
    "    ax.set_yticklabels(['Correr', 'Pular', 'Agachar'], rotation=0)\n",
    "    ax.set_xticklabels(['$w_{p}$'.replace('p', str(x+1)) for x in range(10)], rotation=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## População\n",
    "\n",
    "> **Definição:** A populaçao é formada por um conjunto de indivíduos que irão competir pela sobrevivência e pela repodrução, objetivando perpetuar suas características.\n",
    "\n",
    "Como vimos no pseudo-código, mais em cima, uma das entradas do algorimto genético é uma população (inicialmente, gerada aleatoriamente). Para isso, vamos criar vários indivíduos com <mark>pesos</mark>.\n",
    "\n",
    "### Código Genético e Pesos (ou genes)\n",
    "\n",
    "Cada indivíduo possui seu próprio código genético, que determina suas características e desempenho no ambiente em que vive. Da mesma forma, em AGs, existem parâmetros que influenciam na tomada de decisão dos modelos e, consequentemente, seu desempenho.\n",
    "\n",
    "> Imagine que tenhamos que criar um modelo, usando AGs, para investir na bolsa de valores de modo que queremos maximizar o nosso lucro. Nossa IA pode ''aprender'' a levar em conta o valor do ativo, bem como notícias relacionadas ao mercado e outras variáveis, para poder inferir se irá ou não fazer um investimento.\n",
    "\n",
    "No exemplo acima, a taxa de valorização de cada variável para a tomada de decisão do modelo é chamada de **peso**, e determina seu sucesso. Essas taxas são obtidas através de uma <mark>função de tomada de decisão</mark> e, comparando com conceitos da biologia, essa função seria algo análogo ao genoma de uma espécie, enquanto os pesos seriam associados às diferenças que cada organismo da espécie tem em seu DNA.\n",
    "\n",
    "Se definíssemos uma função linear simples (em que multiplicamos cada variável por um peso e depois somamos tudo), uma IA gerada por esse algoritmo genético que tivesse 3 pesos teria a função de decisão abaixo:\n",
    "\n",
    "$$\n",
    "f = \\sum_{i=1}^{3} w_i \\cdot x_i = [(w_1 \\cdot x_1) + (w_2 \\cdot x_2) + (w_3 \\cdot x_3)]\n",
    "$$\n",
    "\n",
    "onde, $x_i$ são os elementos de estado e $w_i$ os pesos respectivos, para dado indivíduo. \n",
    "\n",
    "**Spoiler:** essa é a função que vamos adotar no Dino Run! \n",
    "\n",
    "Vamos agora utilizar a biblioteca `numpy` para nos ajudar a gerar uma matriz de pesos aleatórios (já iremos ver mais sobre ela):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def populacao_aleatoria(n :int) -> list:\n",
    "    \"\"\"Gera uma população aleatória\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    n : int\n",
    "        Número de indivíduos que serão criados\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    list\n",
    "        Uma população aleatória. A população é uma lista de indivíduos,\n",
    "                                                                                                                                                e cada indivíduo é uma matriz 3x10 de pesos (números).\n",
    "        Os indivíduos podem tomar 3 ações (0, 1, 2) e cada linha da matriz\n",
    "        contém os pesos associados a uma das ações, para os componentes.\n",
    "    \"\"\"\n",
    "    pop = []\n",
    "    \n",
    "    # Para cada indivíduo, gere uma matriz contendo pesos para cada componente, em cada ação\n",
    "    for i in range(n):\n",
    "        pop.append(np.random.uniform(-10, 10, size=(3, 10)))\n",
    "    \n",
    "    return pop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vizualização dos indivíduos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ver_individuo(populacao_aleatoria(1)[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Cada linha da nossa matriz, acima, é um **Gene**\n",
    "\n",
    "> Genes correspondem a uma representação de algum parâmetro de interesse, de acordo com algum alfabeto, podendo usar valores inteiros, reais e cadeis de caracteres, porém, o mais comum é usar apenas valores 0 e 1 de um alfabeto binário.\n",
    "\n",
    "- E a matriz, como um todo, é um **Cromosso** (ou indivíduo)\n",
    "\n",
    "> Cromossos correspondem a uma cadeia de genes que representam cada indivíduo da população.\n",
    "\n",
    "> Um indivíduo correspode a um cromossomo e, no caso dos algoritmos genéticos, são usados para representar as soluções a serem encontradas em um problema de otimização."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Função de Decisão\n",
    "\n",
    "Okay, agora que já montamos nossos indivíduos iniciais, como vamos fazer para nosso AG tomar uma decisão?\n",
    "\n",
    "A ideia aqui é dividir esse processo em duas funções. A primeira delas, vai aplicar aquelas nossas funções de decisão em si, nos retornando um valor para cada ação, ou seja, um vetor com três números. Já a segunda, vai pegar esse vetor e nos retornar o índice do maior número entre os três.\n",
    "\n",
    "### Primeira Função: o Valor das Ações\n",
    "\n",
    "Iremos identificar o ''valor de cada ação'' ($y_i$) através da multiplicação matricial entre o indivíduo ($W$) e o vetor de estado (*i.e.*, as variáveis do jogo, que são 10) ($x_i$).\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "    w_{1;1} & x_{1;2} & x_{1;3} & \\dots  & w_{1;10} \\\\\n",
    "    w_{2;1} & x_{2;2} & x_{2;3} & \\dots  & w_{2;10} \\\\\n",
    "    \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    w_{3;1} & w_{3;2} & w_{3;3} & \\dots  & w_{3;10}\n",
    "\\end{bmatrix} \\cdot\n",
    "\\begin{bmatrix}\n",
    "    x_{1} \\\\\n",
    "    x_{2} \\\\\n",
    "    x_{3} \\\\\n",
    "    \\vdots \\\\\n",
    "    x_{10} \\\\\n",
    "\\end{bmatrix} = \n",
    "\\begin{bmatrix}\n",
    "    y_{1} \\\\\n",
    "    y_{2} \\\\\n",
    "    y_{3} \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Desse modo, a função que calcula o valor das ações fica assim:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valor_das_acoes(individuo :np.array, estado :np.array) -> np.array:\n",
    "    \"\"\"Função para determinar o valor de cada ação\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    individuo : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    estado : np.array\n",
    "        Vetor com 10 números que representam o estado do jogo.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    np.array\n",
    "        Um vetor com os valores das ações no estado `estado`. Calcula os valores\n",
    "        das jogadas como combinações lineares dos valores do estado, ou seja,\n",
    "        multiplica a matriz de pesos pelo estado.\n",
    "    \"\"\"\n",
    "    \n",
    "    return individuo @ estado"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Segunda Função: Pegar o Índice da Melhor Ação\n",
    "\n",
    "Essa aqui não tem segredo, a gente vai usar uma função do numpy que faz justamente isso: dado um vetor, ela retorna o índice do maior valor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def melhor_jogada(individuo :np.array, estado: np.array) -> int:\n",
    "    \"\"\"Identifica a ação a ser tomada\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    individuo : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    estado : np.array\n",
    "        Vetor com 10 números que representam o estado do jogo.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    int\n",
    "        A ação de maior valor (0, 1 ou 2) calculada pela função `valor_das_acoes`.\n",
    "    \"\"\"\n",
    "    \n",
    "    acoes = valor_das_acoes(individuo, estado)\n",
    "    return np.argmax(acoes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gerações & Seleção\n",
    "\n",
    "> **Definição**: A geração corresponde a uma população em um certo período. No caso, dos algoritmos genéticos, corresponde aos valores dos indivíduos obtidos em uma dada iteração.\n",
    "\n",
    "> **Definição**: A seleção é usada para escolher os indivíduos para a reprodução, podendo ser realizada de diferentes maneiras, porém, as propostas mais comuns são: a seleção aleatória, a seleção por torneio e a seleção usando a roleta.\n",
    "\n",
    "\n",
    "<img src='https://media.nature.com/m685/nature-assets/srep/2016/161121/srep37616/images_hires/srep37616-f3.jpg'>\n",
    "\n",
    "\n",
    "Na natureza, indivíduos mais aptos sobrevivem e se reproduzem com mais frequência, proliferando seu código genético na população. No longo prazo, isso gera populações mais e mais adaptadas ao seu ambiente a cada geração. Porém, linha de códigos não estão sujeitas a adversidades como fome ou incapacidade de encontrar um@ parceir@. <mark>Assim, não se espera observar um fenômeno equivalente, a não ser que seja introduzido um processo artificial</mark>.\n",
    "\n",
    "Esse processo pode ser realizado, em computação, através de **função de avaliação do indivíduo** (*i.e.* *fitness function*). Essa função é responsável por determinar a aptidão (sucesso ou performance) de um indivíduo na atual geração.\n",
    "\n",
    "> **Elitismo:** **Seleção somente dos melhores indivíduos criados para uma próxima geração** (baseado na sua função de avaliação), da mesma forma como somente os organismos mais aptos a um habitat conseguem passar pelo crivo da natureza, gerando proles que viverão a próxima geração da espécie.\n",
    "\n",
    "Os demais indivíduos, então, acabam não sendo selecionados para a próxima geração. Entretanto, estão aptos a reproduzirem. Essa etapa ocorre através do **crossover** entre os genes de dois indivíduos, possibilitando a criação ''filhos'' com, neste caso, 50% da carga genética (ou pesos, ou informação) de cada um dos seus pais. As proles desenvolvidas nesse processo, que ainda estão sujeitas à **mutação**, compõem nova população que irá para a próxima geração, junto com os indivíduos selecionados pelo elitismo.\n",
    "\n",
    "> Se um algoritmo genético é configurado para ter uma população de tamanho $\\texttt{NUM_INDIVIDUOS}=10$ e definimos que os $\\texttt{NUM_MELHORES}=3$ indivíduos mais aptos serão repassados diretamente para a próxima geração, então os 7 indivíduos só poderão perpetuar sua espécie, na próxima geração, através *crossover* e mutação das suas proles. Esses 7 indivíduos não aptos devem procriar a quantidade remanescente de indivíduos para a próxima geração.\n",
    "\n",
    "\n",
    "### Crossing over"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cross_over(a: np.array, b: np.array, n_children :int=1) -> list:\n",
    "    \"\"\"Combina dois indivíduos\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    a : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    b : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    n_children : int, optional\n",
    "        Qunatidade de filhos a serem gerados, by default 1\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    list\n",
    "        Uma lista contendo `n_children` novo(s) indivíduo(s) resultante do \n",
    "        cruzamento entre os indivíduos `a` e `b`.\n",
    "    \"\"\"\n",
    "    \n",
    "    children = []\n",
    "    \n",
    "    for i in range(n_children):\n",
    "        sieve = np.random.choice([0, 1], size=(3, 10), p=[.5, .5])\n",
    "        not_sieve = sieve^1\n",
    "        children.append(a*sieve + b*not_sieve)\n",
    "\n",
    "    return children"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos observar um crossover baixo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ind = populacao_aleatoria(2)\n",
    "ind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(1, 2, figsize=(15, 2))\n",
    "\n",
    "fig.suptitle(\"Pais\", y=1.2, fontsize=16)\n",
    "\n",
    "ver_individuo(ind[0], ax=ax[0])\n",
    "ax[0].set_title(\"Indivíduo A\")\n",
    "\n",
    "ver_individuo(ind[1], ax=ax[1])\n",
    "ax[1].set_title(\"Indivíduo B\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filhos_qtd = 2\n",
    "filhos = filhos = cross_over(*ind, n_children=filhos_qtd)\n",
    "\n",
    "fig, ax = plt.subplots(1, filhos_qtd, figsize=(6.5*filhos_qtd, 2))\n",
    "\n",
    "fig.suptitle(\"Filhos\", y=1.2, fontsize=16)\n",
    "\n",
    "for i in range(filhos_qtd):\n",
    "    ver_individuo(filhos[i], ax=ax[i])\n",
    "    ax[i].set_title(\"Filho \" + str(i+1))\n",
    "    \n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mutação\n",
    "\n",
    "Na função de mutação nós vamos possivelmente mutar os pesos do nosso indivíduo com uma probabilidade definida lá em cima nas nossas variáveis globais"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutacao(individuo :np.array):\n",
    "    \"\"\"Essa função não tem saída. Ela apenas modifica os pesos do indivíduo,\n",
    "    com chance CHANCE_MUT para cada peso.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    individuo : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo.\n",
    "    \"\"\"\n",
    "    \n",
    "    for i in range(3):\n",
    "        for j in range(10):\n",
    "            if np.random.uniform(0, 1) < CHANCE_MUT:\n",
    "                individuo[i][j] *= np.random.uniform(-1.5, 1.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos observar os efeitos da mutação em um indivíduo aleatório:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ind = populacao_aleatoria(1)[0]\n",
    "\n",
    "fig, ax = plt.subplots(1, 2, figsize=(15, 2))\n",
    "\n",
    "ver_individuo(ind, ax=ax[0])\n",
    "ax[0].set_title(\"Antes da mutação\")\n",
    "\n",
    "mutacao(ind)\n",
    "ver_individuo(ind, ax=ax[1])\n",
    "ax[1].set_title(\"Após a mutação\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### T-Rex Rush: Um pouco sobre o jogo\n",
    "\n",
    "\n",
    "<img src='https://github.com/shivamshekhar/Chrome-T-Rex-Rush/raw/master/screenshot.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos instânciar e iniciar o game da seguinte forma:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trex = DinoGame(fps=60)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note que passamos como parâmetro `fps=60`. No momento do ''treinamento'' do algoritmo genético, podemos aumentar o *frame rate* para agilizar o processo.\n",
    "\n",
    "O objeto `DinoGame()` possui alguns métodos/atributos interessantes, vejamos:\n",
    "\n",
    "\n",
    "| Item                   | Descrição                                                                                      |\n",
    "|------------------------|------------------------------------------------------------------------------------------------|\n",
    "| `DinoGame.reset()`     | Método que reinicia o jogo                                                                     |\n",
    "| `DinoGame.game_over`   | Atributo para verificar se o jogo foi finalizado                                               |\n",
    "| `DinoGame.step()`      | Método que permite o dinossauro executar uma ação (0-Nada/Corre, 1-Pula, 2-Agacha)             |\n",
    "| `DinoGame.get_score()` | Método que obtém o score da partida                                                            |\n",
    "| `DinoGame.get_state()` | Método que obtém as 10 variáveis do jogo (por exemplo, distância do obstáculo, velocidade etc) |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma breve demonstração ''burrinha'' :p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = 5*60 \n",
    "\n",
    "while t != 0:\n",
    "    if trex.game_over:\n",
    "        trex.reset()\n",
    "    trex.step(np.random.randint(0, 3))\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fitness: função de avaliação do indivíduo\n",
    "\n",
    "Finalmente, vamos fazer nossa função de *fitness* \\o/\n",
    "\n",
    "Chegamos agora num ponto bem importante dos algoritmos genéticos, que é a função de *fitness*. Como dito anteriormente no texto, para simular o mecanismo biológico de seleção natural precisamos artificialmente criar uma pressão do meio. É aí que entra a função de *fitness*: a partir do score dado por ela para um dado indivíduo, é possível comparar a performance dele em relação aos demais.\n",
    "\n",
    "A nossa função de *fitness* mais simples a ser escolhida (que é o que faremos nesse caso) é o score do jogo, que pode ser obtido pelo método `DinoGame.get_score()`, lembra?\n",
    "\n",
    "Então, em termos de código, o que a função deve executar é: **fazer com que o indivíduo jogue o jogo e depois pegar o score dele**. Algumas ressalvas são: temos que dar reset no jogo antes de pôr nosso pequeno indivíduo à prova, para que ele comece um jogo novo (e não fique na tela de game over do indivíduo anterior).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fitness_function(individuo :np.array, game_ob :DinoGame) -> int:\n",
    "    \"\"\"Faz o indivíduo jogar uma partida e depois pegar o score que ele conseguiu\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    individuo : np.array\n",
    "        Matriz 3x10 com os pesos do indivíduo\n",
    "    game_ob : chrome_trex.dinogame.DinoGame\n",
    "        Objeto que representa o jogo\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    int\n",
    "        O fitness calculado de um indivíduo. Esse cálculo é feito simulando um\n",
    "        jogo e calculando o fitness com base nessa simulação\n",
    "    \"\"\"\n",
    "    \n",
    "    game_ob.reset()\n",
    "    \n",
    "    while not game_ob.game_over:\n",
    "        vet_estados = game_ob.get_state() # variáveis do jogo\n",
    "        acao = melhor_jogada(individuo, vet_estados) # Obtém a ação do dinossauro (corre, pula ou agacha)\n",
    "        game_ob.step(acao) # Aplica a ação\n",
    "\n",
    "    return game_ob.get_score()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vejamos uma demonstração com um indivíduo que criamos mais cedo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fitness_function(ind, trex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Próxima Geração\n",
    "\n",
    "Agora que definimos a nossa função de *fitness*, podemos aplicar o elitismo e a reprodução (crossover e mutação) para gerar a próxima população:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def proxima_geracao(populacao :list, fitness :list) -> list:\n",
    "    \"\"\"Cria a próxima geração a partir de elitismo e seleção (crossover + mutação)\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    populacao : list\n",
    "        Lista com os pesos (Matriz 3x10) dos indivíduos.\n",
    "    fitness : list\n",
    "        Lista de scores\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    list\n",
    "        Lista com os pesos (Matriz 3x10) dos indivíduos da nova geração.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Ordena a população pelo fitness, decrescentemente\n",
    "    top_individuos = [x for _, x in sorted(zip(fitness, populacao), key=lambda x: x[0], reverse=True)]\n",
    "    top_fitness = sorted(fitness, reverse=True)\n",
    "        \n",
    "    # Elitismo: Seleciona os indivíduos com os melhores scores\n",
    "    proxima_ger = top_individuos[:NUM_MELHORES]\n",
    "    \n",
    "    while len(proxima_ger) < NUM_INDIVIDUOS:\n",
    "        # Seleciona dois indivíduos, através do método roulette wheel (roleta)\n",
    "        # para realizar o crossover. Note que a selaçao ocorre apenas nos indivíduos\n",
    "        # que não participaram do elitismo.\n",
    "        ind_a, ind_b = random.choices(top_individuos, weights=top_fitness, k=2)\n",
    "        \n",
    "        children = cross_over(ind_a, ind_b, n_children=1)\n",
    "        \n",
    "        for child in children:\n",
    "            mutacao(child)\n",
    "        \n",
    "        proxima_ger.append(child)\n",
    "    \n",
    "    return proxima_ger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hora de juntar tudo e se divertir! \n",
    "\n",
    "Pronto, agora estamos com a faca e o queijo na mão. Só temos que juntar os pedaços que criamos até agora. \n",
    "\n",
    "Esse código de agora é essencialmente a transformação daquele pseudocódigo do início do texto em código python para o Dino Run.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Configurações ~~\n",
    "\n",
    "trex.high_score = 0 # Resetando o high score do jogo\n",
    "trex.fps = 900000 # Aumenta o frame rate do jogo para que o ''treinamento'' ocorra mais rápido\n",
    "num_geracoes = 5 # Determina o número de gerações que serão criadas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "print('ger | fitness\\n----+-' + '-' * 5 * NUM_INDIVIDUOS)\n",
    "\n",
    "# Iremos criar a popoulação inicial (aleatoriamente) com `NUM_INDIVIDUOS`\n",
    "populacao = populacao_aleatoria(NUM_INDIVIDUOS)\n",
    "\n",
    "for ger in range(num_geracoes):\n",
    "    # Obtém o fitness de cada indivíduo da população\n",
    "    fitness = [fitness_function(individuo, trex) for individuo in populacao]\n",
    "        \n",
    "    # Atualiza a população, criando uma nova geração\n",
    "    populacao = proxima_geracao(populacao, fitness)\n",
    "    \n",
    "    # Imprime na tela o score de cada um dos indivíduos, por geração\n",
    "    print('{:3} |'.format(ger),\n",
    "          ' '.join('{:4d}'.format(s) for s in sorted(fitness, reverse=True)))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Após o ''treino'', diversos indivíduos foram gerados e testados. Os que melhor se adaptaram, foram perpetuando suas características ao longo das gerações.\n",
    "\n",
    "Vamos verificar como ficou o melhor indivíduo da última geração:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trex.high_score = 0\n",
    "\n",
    "# Vamos aumentar o frame rate do jogo para que o treinamento ocorra mais rápido\n",
    "trex.fps = 60000000\n",
    "\n",
    "# Iremos criar a popoulação inicial (aleatoriamente) com `NUM_INDIVIDUOS`\n",
    "populacao = populacao_aleatoria(NUM_INDIVIDUOS)\n",
    "\n",
    "print('ger | fitness\\n----+-' + '-' * 5 * NUM_INDIVIDUOS)\n",
    "\n",
    "best_fit = 0\n",
    "best_ind = None\n",
    "\n",
    "num_geracoes = 400\n",
    "for ger in range(num_geracoes):\n",
    "    # Obtém o fitness de cada indivíduo da população\n",
    "    fitness = [fitness_function(individuo, trex) for individuo in populacao]\n",
    "    \n",
    "    # Salva o melhor indivíduo\n",
    "    if max(fitness) > best_fit:\n",
    "        best_fit = max(fitness)\n",
    "        best_ind = populacao[np.argmax(fitness)]\n",
    "        \n",
    "    # Atualiza a população, criando uma nova geração\n",
    "    populacao = proxima_geracao(populacao, fitness)\n",
    "    \n",
    "    print('{:3} |'.format(ger),\n",
    "          ' '.join('{:4d}'.format(s) for s in sorted(fitness, reverse=True)))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trex.fps = 60\n",
    "\n",
    "melhor_individuo = populacao[np.argmax(fitness)]\n",
    "fit = fitness_function(melhor_individuo, trex)\n",
    "\n",
    "print('Fitness/Score: {:4.1f}'.format(trex.get_score()))\n",
    "print('Indivíduo:')\n",
    "\n",
    "ver_individuo(melhor_individuo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--- \n",
    "<span style='font-family: verdana; color: gray'>Notebook baseado no artigo <a href='https://medium.com/turing-talks/turing-talks-8-algoritmos-gen%C3%A9ticos-a791c25bd7ba'>Algoritmos Genéticos: Um primeiro modelo de Machine Learning baseado na seleção natural</a>, do blog <b>TuringTalks</b>.</span>"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}