Algoritmos Genéticos
Um primeiro modelo de Machine Learning baseado na seleção natural
Esta semana faremos uma pausa em nossos estudos de Data Science para ver uma aplicação de Machine Learning na área de jogos. Para isso, usaremos um tipo de algoritmo baseado na biologia: os algoritmos genéticos. É a mesma ideia que apresentamos em nosso workshop em maio desse ano.
Para acompanhar esse artigo você precisa saber o básico de Python e Numpy. Caso você não saiba, fique tranquilo, nós temos alguns artigos sobre isso aqui no Turing Talks: Python (parte 1 e parte 2) e Numpy.
Algoritmos genéticos (AGs) são uma classe de algoritmos de otimização inspirada no processo evolutivo biológico. Eles recebem esse nome por se relacionarem intimamente a como espécies se adaptam ao ambiente ao longo de diversas gerações.
Em linhas gerais, esses algoritmos criam diversas soluções aleatoriamente para um problema, das quais serão selecionadas as que apresentarem melhor performance (ou fitness, em inglês). Mais soluções são geradas a partir das selecionadas, e esse processo é repetido diversas vezes até que se encontre uma solução satisfatória. Esse processo é análogo à seleção natural, pensando-se em uma população de soluções (cada solução seria um indivíduo).
Como o algoritmo é baseado num conceito biológico, em geral, utilizamos alguns jargões da biologia quando falamos de aspectos do AG. Na tabela a seguir, você pode verificar as analogias entre alguns termos utilizados na biologia e em AGs:
O exemplo que será explanado neste artigo é o de treinar o jogo Dino Run do Google (aquele que aparece no Google Chrome quando a sua internet cai), entretanto existem outros exemplos, como reproduzir imagens 2D em 3D (um tópico mais avançado do que o que será abordado aqui, mas você pode dar uma olhada neste video e neste artigo).
Overview do Algoritmo Genético
A ideia do algoritmo genético é selecionar as melhores soluções de um problema e fazer com que elas se perpetuem. Podemos definir como um pseudocódigo do AG o seguinte:
ENTRADA: População Inicial (aleatória)
Função de Fitness
Critério de ParadaREPITA (até que o critério de parada seja atendido):PASSO 1: Aplicar a função de fitness a cada indivíduoPASSO 2: Selecionar os x melhores indivíduosPASSO 3: Reprodução
- Aplicar o crossover a um par (com prob = p)
- Aplicar mutação (com prob = p’)PASSO 4: Formar uma nova população com os filhos geradosSAÍDA: Melhor indivíduo presente na geração final
Tipicamente, esses passos são divididos em funções dentro do código, como “reprodução”, “crossing over”, “população aleatória”, “fitness” e etc. Vamos dividir mais ou menos dessa forma o nosso estudo.
Dino Run: O Nosso Problema
Muitos problemas em algoritmos genéticos são unidimensionais, ou seja, a função de decisão é binária: tomar uma ação ou outra. Vamos pensar num exemplo bem bobo com essa propriedade: digamos que queiramos fazer um AG que nos diga se um determinado personagem deve ficar sentado ou de pé. Nesse caso, existem apenas duas escolhas possíveis, de forma que a fronteira de decisão poderia ser unidimensional. Ou seja, o nosso algoritmo iria ter algumas variáveis de entrada, uma função que utilizasse essas variáveis com determinados pesos e iria nos retornar um valor (um número real). Dependendo de quanto fosse esse valor, nós tomaríamos uma determinada ação, como por exemplo: ficar de pé se f(x) < 0 e ficar sentado se f(x) ≥ 0. Assim, nossa fronteira seria o 0, e poderíamos representar numa linha em quais valores iríamos tomar determinadas ações. Resumindo em diagramas essa lógica:
Um ponto que pode gerar dúvida é: como eu escolho essa fronteira? A ideia do AG é que ele se adapte às suas escolhas iniciais conforme o algoritmo roda. Então, simplificadamente: pode escolher qualquer fronteira. O que eventualmente pode mudar com a sua escolha é a sua taxa e limites de convergência, que podem ser prejudicados ou melhorados (isso não só para sua fronteira, mas principalmente para a função de fitness… mas isso discutiremos daqui a pouco).
No caso do Dino Run nós temos três possíveis ações (Pular, Agachar, Não fazer nada), e, por isso, é melhor que o nosso indivíduo seja multidimensional. O que queremos é que cada ação tenha sua própria função, que indique o quão boa essa ação é. Por exemplo: se, em um determinado instante, o jogador deve pular, o valor da ação pular será maior que o valor de agachar ou não fazer nada. Assim, 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). O que isso implica é que não vai existir uma fronteira de decisão unidimensional, que nem a que foi mostrada, mas sim, cada ação terá o seu próprio valor, sem limitações. Nós vamos escolher a ação cuja função nos dê o maior output dentre os três.
Por que vamos fazer isso? Bom, de fato, nós bem que podíamos esquartejar nossa pobre reta real em vários pedacinhos e arbitrar intervalos para determinadas ações, entretanto, isso poderia prejudicar bastante nossa convergência.
Um último detalhe antes de mergulharmos na implementação, que você deve estar se perguntando há um tempo, é: e as nossas variáveis de entrada??? Bom, em geral, as nossa variáveis de entrada são parâmetros que nos dizem coisas sobre o nosso problema. 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. Lembrando que o jogo é dinâmico, 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”.
Agora que discutimos toda essa teoria, vamos começar arrumando a casa, importando o jogo, as bibliotecas que vamos usar (numpy) e escolhendo nossos parâmetros globais:
Obs: a biblioteca que estamos usando é a chrome-trex-rush, que pode ser instalada com o seguinte comando:
pip install --user git+https://github.com/GrupoTuringCodes/chrome-trex-rush@masterSe você quiser instalar pelo Jupyter notebook, é só colocar um ponto de exclamação antes da linha acima ( !pip install ...).
População Aleatória
Como dito no pseudocódigo anterior, uma das coisas necessárias para o algoritmo genético é uma população aleatória para começar. Para isso, vamos criar vários indivíduos com pesos. PERA, CALMA, O QUÊ? Mas você nem me explicou direito o que que é isso! Calma leitor, vamos dar uma aprofundada antes de montarmos o código em si.
Código Genético e Pesos
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, uma inteligência artificial possui parâmetros que influenciam sua tomada de decisão e, consequentemente, seu desempenho. Considere, por exemplo, um código que pretende investir no mercado financeiro de forma a maximizar seu capital. A IA pode levar em conta desde o valor de um ativo até notícias sobre o proprietário de uma empresa para decidir se investirá ou não no negócio. O quanto esse programa valoriza cada elemento da realidade em sua tomada de decisão é chamado de peso, e determina seu sucesso. Como e quais fatores são valorizados nesse processo são descritos por uma função de tomada de decisão. Nesse paralelo, a função de tomada de decisão de um algoritmo seria 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.
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:
f = a⋅p[1] + b⋅p[2] + c⋅p[3],
em que p[1], p[2] e p[3] são elementos do vetor de estado e a, b e c são os pesos do indivíduo. (Spoiler: essa é a função que vamos adotar no Dino Run)
Note que os pesos não precisam necessariamente multiplicar variáveis da função geral de tomada de decisão, ou seja, o uso da função linear é apenas uma simplificação. O importante é que cada peso altere cada variável de alguma forma, definida pelo projetista.
No Dino Run
Bom, voltando ao Dino Run, nós vamos utilizar a biblioteca numpy para nos ajudar a gerar uma matriz de pesos aleatórios (explicaremos melhor como funciona essa matriz na próxima parte do post):
Função de Decisão
Okay, agora que já montamos nossos indivíduos iniciais, como vamos fazer com que eles tomem uma decisão? 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. Lembrando que nesse caso a nossa função de decisão é uma função linear, mas ela não precisaria ser assim. Essa função pode ser o quão complexa ou simples nós quisermos, desde uma função linear (como a que utilizaremos) até uma rede neural (que veremos mais a frente), por exemplo.
A segunda função que vamos utilizar vai pegar esse vetor e nos retornar o índice do maior número entre os três. Por que pegamos esse índice? Bom, no jogo, cada uma das ações é aplicada com um número (0,1 ou 2), que corresponde exatamente a um dos índices do vetor de decisão. E como eu garanto que eu estou pegando o índice certo da ação certa? Eu preciso saber qual ação corresponde a qual índice? Na verdade não, como já dito anteriormente, o AG vai se adaptar às suas escolhas iniciais. Então relaxa, não importa qual índice representa qual ação.
Primeira Função: o Valor das Ações
A multiplicação matricial da matriz do indivíduo pelo vetor do estado nos retornará os valores de cada ação. Por exemplo, se o estado tiver 5 componentes (s0, s1, s2, s3, s4) e as letras coloridas (de a a o) forem os pesos do indivíduo, os valores das ações seriam:
Matricialmente, a equação acima fica:
Acima usamos um estado com apenas 5 componentes. No Dino Run, o estado tem 10 componentes, ou seja, os pesos estarão organizados em uma matriz 3×10. Desse modo, a função que calcula o valor das ações fica assim:
Segunda Função: Pegar o Índice da Melhor Ação
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.
Reprodução
Antes de entrarmos na reprodução dos nossos indivíduos, vamos esclarecer alguns conceitos.
Seleção Natural e Gerações
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. No entanto, linhas de código não estão sujeitas a adversidades como fome ou incapacidade de encontrar um parceiro. Assim, não se espera observar um fenômeno equivalente a não ser que seja introduzido um processo artificial de seleção desses códigos.
No contexto da computação, esse processo é introduzido por uma função de avaliação de desempenho. Essa função é responsável por determinar o que caracteriza o sucesso de uma IA em uma certa tarefa. Consideremos, por exemplo, que o desempenho da nossa IA investidora seja definido exclusivamente por seu capital acumulado ao longo do tempo. Se criássemos diversas IAs para investirem no mercado, com parâmetros de tomada de decisão gerados aleatoriamente, é um fato que haveria exemplares com desempenho melhor do que os demais.
Seria possível que uma dessas IAs (ou indivíduos) tivesse performance boa o suficiente para ser utilizada. No entanto, a probabilidade desse evento é usualmente muito baixa. Assim, podemos repetir o processo descrito até que se encontre uma IA satisfatória. Porém, essa busca pode ser muito demorada, o que é remediado por alguns recursos dos algoritmos genéticos.
Buscar membros de alta performance (para uma dada tarefa) em um grupo cujos indivíduos têm características aleatórias é contraproducente: espera-se que a grande maioria deles, senão sua totalidade, tenha péssimo desempenho. Apesar disso, ainda existirá uma diferença entre a performance de cada um, o que é crucial para o funcionamento de algoritmos genéticos. Um AG seleciona somente os melhores indivíduos que criou 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.
A partir dessa seleção, o AG descarta os demais indivíduos, substituindo-os por IAs cujos parâmetros são gerados a partir de ligeiras variações nos pesos de um “sobrevivente” da geração anterior. Essas variações, sim, são aleatórias, de forma que seja provável que haja tanto indivíduos de melhor quanto de pior desempenho. Assim, a cada geração, espera-se que haja indivíduos com melhores resultados do que na anterior, eventualmente obtendo-se um indivíduo com desempenho satisfatório.
No Dino Run
Nessa etapa não vamos eliminar os piores indivíduos, vamos deixar pra fazer isso depois que fizermos a nossa função de fitness (aquela que avalia o desempenho dos indivíduos). Por enquanto, vamos apenas fazer os mecanismos de crossing over e mutação.
Na reprodução, a função de crossing over escolherá dois indivíduos da população existente e a partir deles criará um indivíduo novo. Depois disso a função de mutação irá possivelmente alterar esse indivíduo.
Mutação
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. CALMA CALMA CALMA! Como que eu mexo com uma probabilidade num código? Eu não sei como fazer algo acontecer com uma probabilidade dada! Calma leitor, nós pensamos nisso, vamos dar uma explicadinha de como lidar com as probabilidades.
Para fazer com que um evento ocorra com probabilidade p basta gerar um número aleatório entre 0 e 1 (nossa variável aleatória com distribuição uniforme) e verificar se ele está dentro de um intervalo do tamanho da probabilidade que queremos. Exemplificando:
Nesse caso um número sorteado entre 0 e 1 tem 20% de chance de cair no intervalo rosa.
Assim, nosso código fica assim:
Nesse caso, a mutação consiste em multiplicar o peso por um valor aleatório dentro de um intervalo, mas não necessariamente teria de ser isso.
Crossing Over
Como dito anteriormente, a função de crossing over é a que combina dois indivíduos. É nesse momento que vamos escolher dois indivíduos da população e a partir deles gerar um novo. Existem várias formas de fazer isso, você poderia, por exemplo, escolher metade dos pesos do pai e metade dos da mãe. No caso do Dino Run, o que fazemos é, primeiramente, definir a nossa “cria” como a cópia de um dos dois indivíduos selecionados e depois trocar cada um dos pesos pelo do outro indivíduo com uma chance dada.
Fitness
Bom, 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.
A função de fitness é extremamente importante para modelar um problema, ela deve ser escolhida sabiamente. Isso porque toda a força computacional será posta para maximizá-la; se ela não contempla de forma satisfatória o nosso problema, chegaremos numa solução que não nos será útil.
Mesmo que a função de fitness penalize os indivíduos conforme o esperado para o nosso problema, ainda precisamos corrigir algumas nuances e penalizar mais alguns aspectos do que outros a depender do caso. Por exemplo, se num jogo de snake a nossa função de fitness apenas premiasse o maior número de casas percorridas pela cobrinha indiscriminadamente, poderíamos induzir o algoritmo a fazer com que ela andasse em círculos (o que não é nada bom). Uma forma de prevenir isso seria penalizar os passos dados em direção contrária a da comida. Num exemplo mais real, se quiséssemos maximizar o lucro de uma empresa com base no estoque a ser mantido por ela e, para isso, utilizássemos uma simulação com algoritmos genéticos, haveríamos de considerar várias nuances em nossa função de fitness. Nada nos ajudaria a empresa maximizar o lucro no curto prazo se com isso ela prejudicasse a satisfação dos clientes (o que a faria performar mal no futuro), por isso teríamos de pesar isso no nosso fitness.
Voltando ao Dino Run, a nossa função de fitness mais simples a ser escolhida (que é o que faremos nesse caso) é o score do jogo. É claro, talvez pesar outros parâmetros poderia melhorar o nosso resultado final e a nossa taxa de convergência. Entretanto, nesse caso, preferimos utilizar apenas a pontuação do jogo para simplificar o código.
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).
O legal é que agora estamos começando a encaixar as peças, nessa função tivemos que puxar algumas de nossa funções implementadas anteriormente.
Próxima Geração
Agora que definimos a nossa função de fitness, podemos eliminar os nossos piores indivíduos e reproduzir os melhores. Ou seja, o que vamos fazer é unir o fitness com a nossa reprodução e também selecionar os melhores. Para isso, vamos definir uma função adicional que ordenará a população com base no fitness de cada individuo.
Obs: na função acima, utilizamos o método random.choices() (e não np.random.choice()) porque o método de numpy não consegue trabalhar com listas de listas (ou listas de matrizes).
Função Main
Pronto, agora estamos com a faca e o queijo na mão. Só temos que juntar os pedaços que criamos até agora. 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.
Observe que no final do código, na parte que mostra o melhor indivíduo, tivemos que diminuir a velocidade do jogo (o fps ou frames per second). Inicialmente criamos o jogo com um fps alto, para que o algoritmo rodasse mais rápido. No entanto, para que seja possível ver o dinossauro jogando, é necessário diminuir o fps.
Conclusão
Em suma, o algoritmo genético é uma ferramenta simples, mas muito poderosa. Ele pode ser utilizado em combinação com outras técnicas e é uma forma de otimização menos custosa do que muitas famosas, como o grid search, por exemplo.
Por hoje é só, caro leitor! Espero que tenha gostado do texto! Se quiser saber mais de IA, acompanhe nossos posts aqui e no Facebook, onde divulgamos os nossos eventos, como o workshop que fizemos sobre Algoritmos Genéticos.
