Algoritmos genéticos – um resumo e um exemplo

Quando você tem um problema com um número muito grande de candidatos a solução (mas muito grande mesmo), o que você precisa é de um algoritmo de busca. Não de busca no sentido Google, mas de busca de solução. Hoje em dia, em tempos de guerra de “search engines” o nome talvez confunda um pouco, mas algoritmos de busca são fundamentais em computação. Basicamente o que você quer com um algoritmo de busca é navegar pelo mar de possíveis respostas, de preferência de uma forma esperta para te ajudar a encontrar a melhor solução.

“E que problemas eu resolvo com essas bagaças? Resolve minha dívida no bar do bigode?” Os algoritmos de busca em geral são bem genéricos, então podem resolver um número muito grande de problemas. O trabalho do computólogo (ou computeiro, sei lá) é modelar o problema para que ele possa ser resolvido pelo algoritmo, o que geralmente não é um trabalho muito simples. Você não paga sua dívida no bar do bigode diretamente usando esses algoritmos, talvez, mas você pode escrever um algoritmo para calcular quais são as melhores jogadas que você deve fazer nas partidas de dominó para tirar um troco. Ou você pode criar um algoritmo para gerar projetos mais econômicos de circuitos eletrônicos, vender para uma IBM da vida, e comprar o bar do bigode com esse dinheiro.

A situação ideal é quando o algoritmo te dá uma solução sem levar muito tempo computando e a solução é a melhor possível (ou quando você passa um final de semana com a Megan Fox). E existem diversos algoritmos que são capazes de fazer isso (encontrar uma solução, não a parada da Megan Fox), mas isso depende muito do problema específico e de seu tamanho. Mas e quando você precisa mesmo da solução e esses algoritmos não são capazes de computar algo em um tempo razoável? É aí que você pode usar um algoritmo heurístico de busca, como por exemplo algoritmos genéticos. E por coincidência, este é o título deste post.

Heurística? É de comer?

A grosso modo, uma heurística é um chute mais esperto, um critério ou estratégia que pode te ajudar a encontrar uma solução boa. Pode ajudar, às vezes não vai te ajudar. Você pode por exemplo bolar uma estratégia para pegar a Megan Fox (de novo?) e de vez em quando isso funcionar. Mas de vez em quando você acabar com a Amy Winehouse. Enfim, no mínimo com este artigo você aprendeu uma palavra nova para usar na “night”.

Algoritmos genéticos

Algoritmos genéticos são algoritmos heurísticos de busca inspirados na teoria da evolução, seleção natural e nos processos biológicos envolvidos. Se você ainda lembra de conceitos como meiose, mutação, cross-over, vai ver que o algoritmo praticamente simula a idéia de como as coisas ocorrem com os cromossomos e DNA, mas utilizando os dados do problema que você quer resolver. Se você gosta muito de computação E de biologia, a ponto de ter um pôster do Richard Dawkins no seu quarto, vai ter um orgasmo cerebral de saber que um negócio desses funciona.

Eu não tenho um pôster do Richard Dawkins

Eu não tenho um pôster do Richard Dawkins

Vou tentar explicar rapidamente a idéia do algoritmo, mas provavelmente você entenderá melhor olhando para o exemplo mais abaixo. Mas já deixo claro que esta explicação abaixo tem como objetivo ser uma introdução rápida, por isso não vou ficar me desculpando no meio do texto por causa de detalhes técnicos e outros “poréns”.

A primeira coisa que você precisa ter é uma forma de representar os candidatos de preferência como uma sequência de elementos, assim como o DNA é uma sequência de bases (lembra, adenina, guanina, citosina e timina? Eu não lembrava, procurei no Google). E da mesma forma que na natureza, os primeiros patos tinham sua sequência de DNA, você precisa de um primeiro conjunto de candidatos a solução do seu problema. Esses primeiros candidatos você gera à vontade, afinal, como no caso dos patos, os primeiros não precisam ser muito bons. A seleção natural é que vai transformá-los nos super patos que existem hoje, e te ajudar a encontrar uma boa solução para o seu problema.

A natureza desempenha a seleção natural para os patos. Para o seu problema, você vai ter que bolar um critério de seleção, criando uma função de fitness que possa calcular o quanto aquele candidato a solução é um bom candidato. Esse é o seu trabalho, que depende bastante do seu problema. E usando essa função, você decide na sorte quais indivíduos sobrevivem para a próxima fase, dando mais chances para os que tiveram uma boa nota na sua funçaõ de fitness. É mais ou menos como o programa Tentação do Silvio Santos, onde só os melhores e mais sortudos passam para a próxima fase.

Depois é a hora de misturar DNA. A forma como os patos fazem isso você deve saber: ao som de Barry White ao lado da lareira. E pegando um teco de material genético do papai e misturando com o da mamãe, o que a gente chama de crossover. E isso é o que você vai fazer para ajudar a resolver seu problema, pegar um pedaço de duas das soluções sorteadas na etapa anterior e misturar para gerar uma nova solução. E aí você faz isso para gerar diversas soluções filhas, para usar no próximo passo do algoritmo.

Por último entra um processo muito conhecido pelos X-Men: a mutação. Graças a isso você pode ter características novas nas populações existentes, como patos que atiram laser pelos olhos. Ou uma solução melhor para seu problema. Também podem surgir patos de duas cabeças ou soluções piores para seu problema. Por isso é uma etapa em que você não realiza muitas mudanças, podendo muitas vezes nem mudar nada. Sorteie um ou mais dos pedaços do seu candidato a solução e dê uma mudadinha nele (ou não). Pronto, você tem uma solução mutante.

Pato após mutação

Pato após mutação

Depois é só aplicar todos esses passos (fitness, crossover e mutação) várias vezes, gerando várias soluções, que se tudo estiver direitinho e se sua modelagem do problema for boa, você pode encontrar uma solução para seu problema. Você pode definir algum critério para esse algoritmo parar, como por exemplo rodar até encontrar uma solução boa o suficiente de acordo com a sua função de fitness, ou rodar 1000 vezes.

Não entendi. Desenha pra mim?

Acho que o problema mais simples para usar como exemplo é o problema das N-Rainhas. Se você não sabe, no xadrez a rainha é a peça mais poderosa, que pode se movimentar em qualquer direção, incluindo diagonais, e qualquer número de casas. Ela é ferrada. E normalmente, em um jogo normal, você tem só duas rainhas, uma para cada adversário. Mas no problema das n-rainhas, você tem n rainhas e um tabuleiro com n linhas e n colunas (por exemplo, no problema das 4-rainhas você tem um tabuleiro de 4×4 e 4 rainhas). O desafio consiste em posicionar as n rainhas no tabuleiro sem que nenhuma delas esteja se atacando. Para um n pequeno, o problema é meio bobo, mas se você tiver um n como 4378564378543, aí a coisa complica. Óbvio que resolvendo isto você não vai comprar o bar do bigode, mas acho que te ajudará a aprender como funcionam os algoritmos genéticos.


nrainha1

Exemplo A: aqui o problema não foi resolvido, porque as rainhas das duas últimas colunas podem se atacar pelas diagonais.


nrainha2

Exemplo B: Uma solução para o problema.

Pelos dois exemplos acima você já deve ter sacado que é uma coisa esperta você tentar não colocar mais de uma peça por coluna por exemplo. E isso nos ajuda a modelar a forma como podemos representar esses candidatos a solução. Lembra quando falei que seria legal se o candidato a solução pudesse ser representado por uma sequência de elementos? Podemos representar os exemplos acima, com um vetor de números, em que a primeira posição do vetor indica a linha em que colocamos a rainha da primeira coluna, a segunda posição no vetor a linha da rainha da segunda coluna, e assim por diante. Com isso, o exemplo A seria representado por (1, 4, 2, 3) e o exemplo B por (2, 4, 1, 3). Essas representações são como o DNA do seu problema.

Com essa representação, você está pronto para começar o algoritmo, gerando alguns candidatos a solução que vão ser a primeira geração. Como gerá-los e quantos gerar fica a seu critério. Você pode ter por exemplo uns 20 candidatos gerados de forma aleatória (sorteando cada valor em cada posição).

Agora o que a gente precisa é uma função de fitness, que vai ser usada para fazer a seleção dos candidatos para a próxima fase. Você quer que a função de fitness dê uma probabilidade maior para uma solução quase resolvida do que para uma solução com muitas rainhas se atacando. Neste problema, podemos dizer que o melhor candidato é aquele com menor número de rainhas se atacando e usar isso para construir a função de fitness. Então você pode por exemplo estabelecer que se um candidato a solução tem 4 rainhas se atacando, a probabilidade dele passar para a próxima fase seja de 10%, se tiver 3 rainhas se atacando seja de 30%, e assim por diante. Então para cada candidato a solução você calcula seu fitness e joga o seu dado de 100 lados para cima para ver se esse candidato sobrevive para a próxima fase. Se o dado gerar um número menor que a probabilidade dada pela função de fitness, deixe o candidato continuar.

Chega a etapa de crossover, de misturar as soluções. Primeiro agrupe os candidatos em pares (papai e mamãe). Você pode sortear um número para saber o tamanho do pedaço inicial da solução papai que será substituída no candidato mamãe, e fazer essa substituição para gerar um novo candidato. Por exemplo, se você tiver um papai (2, 3, 4, 4) e uma mãe (1, 3, 2, 1), você pode decidir pegar as duas primeiras colunas do pai e as duas últimas da mãe para gerar o novo (2, 3, 2, 1). Continue com essa orgia de candidatos até gerar o mesmo número de candidatos que você tinha inicialmente.

A mutação também é uma etapa simples. Primeiro decida aleatoriamente se vai ocorrer mutação para aquele candidato (de preferência com uma probabilidade baixa, para que isso não seja tão frequente). Se for decidido que deve haver mutação, sorteie uma das colunas do candidato e mude esse valor para um valor aleatório. Por exemplo, o candidato (1, 4, 3, 3) pode sofrer uma mutação na última coluna e se transformar em (1, 4, 3, 1), por exemplo.

Daí em diante repita, até conseguir um candidato sem nenhum conflito.

Gostei, vou usar para resolver todos os meus problemas!

Calma, algoritmo genético não é a solução para todos os males (apesar de alguns pesquisadores com fome por número de publicações acharem que é). Ele não vai funcionar tão bem para alguns problemas, e isso você só descobre depois que teve todo o trabalho de implementar e rodar. Você pode precisar das respostas dentro de um certo tempo, e o algoritmo pode precisar rodar por muito tempo para chegar em alguma resposta razoável (o que é um problema de muitas buscas heurísticas). Ele pode não chegar a uma resposta boa o suficiente. E modelar o problema e gerar uma boa função de fitness não é um trabalho simples, e o desempenho do algoritmo depende muito do seu modelo.

Mesmo com essas restrições, existem diversas aplicações (e tentativas de aplicação) de algoritmos genéticos na indústria, no mercado financeiro e (ironicamente) em bioinformática, além de ser uma ferramenta auxiliar no ambiente acadêmico. Se duvida disso, dê uma olhada nos resultados do Google.

Espero que algum dia um algoritmo genético possa te ajudar a evoluir na resolução de um problema.

26 Respostas para “Algoritmos genéticos – um resumo e um exemplo

  1. Muito bom texto! Agora preciso de um algoritmo que, dado um programa, o faça evoluir, deixando-o mais consistente, previsível e com melhor desempenho…

  2. Gostei do texto. Mas o lance dos patos meio que caiu de páraquedas, sem uma introdução adequada. Ficou meio jogado lá, sem conexão com nada.
    “E da mesma forma que na natureza, os primeiros patos tinham sua sequência de DNA, você precisa de um primeiro conjunto de candidatos a solução do seu problema.”
    Acredito que ficaria melhor indicar antes que vai usar os patos como exemplo.

  3. Muito bacana seu artigo! Bem humorada com explicação bem clara. Gostei!

  4. Bota uma foto de um pato with lasers que fica melhor ainda.

  5. Isso não é desculpa! As fotos with lasers que conheço são todas feitas no paint da forma mais tosca imaginável.

  6. Muito intereçante o texto , me ajudou a entender o AG. Ajudou a entender um artigo que tava lendo e que usou o AG. valeu!

  7. Cara muito bom o seu artigo, bem humorado e didatico, com uma linguagem acessivel que faz com que as pessoas que leiam se interessem em aprofundar no texto parabéns.
    Você explicou bem a forma como fazer, mas por exemplo uma pessoa com pouca experiência em programação fica com problemas em implementar isso, apesar de ter sacado tudo o que você disse.
    Se você pudesse fazer um pequeno exemplo introduzindo um codigo em seja qual for a lingagem que vc utiliza acho que ajduaria mais, pra casos como o meu.
    Tipo esse exemplo ai das rainhas seria uma boa.
    Parabéns.

  8. Gostei muito do texto!! Estou começando a estudar AG agora e deu pra ter uma ideia do que é. Lógico que eu ainda tenho muito pra ler e estudar, né!

  9. Ótimo texto para quem começa no assunto. Meus parabéns!

  10. Gostei da didática, porém eu não acho em nenhum blog ou site, um exemplo pronto, para analisar… tipo um projeto simples em java, com algum algoritmo genético, funcionando corretamente… alguém tem um projeto assim ?

  11. muito bom texto
    percebi melhor o conceito de AG agora que em 3 aulas com o prof.
    obrigado

    PS: ja agora conheces alguma aplicação com este algoritmo para poder ver os resultados.

  12. O texto foi útil para uma pesquisa da faculdade, muito obrigado. vc foi mais claro do que uma lampada de 500W…

  13. Muito bom o artigo, bem elucidativo, parabéns !

  14. Parabéns pelo texto, mas vale lembrar que a peça mais importante no xadrez é o rei!

  15. Já havia lido vários textos sobre AG’s, mas nunca nenhum tão divertido. Parabéns!

  16. Aqui em São Paulo foi feita uma otimização de tráfego em uma avenida do bairro do Brooklin utilizando um simulador que faz uso de AG. A CET gostou do resultado e manteve a programação otimizada dos semáforos.

  17. Putis, nunca ri tanto com um artigo de TI. Muito bom.
    Se tivesse uma implementação eu juro que conseguiria a Megan Fox pra vc.
    kkkkkkkk….

  18. Parabéns. Me ajudou muito, o exemplo da dama foi ótimo🙂

  19. Putz! Parabéns pelo texto, pela eloquência, pela Mega bebendo cerveja no Bigode e por explicar MUITO bem o assunto!

  20. muito bom o post. continue com esse ótimo trabalho. quem ama o que faz sabe o que faz.

  21. Belo texto! Melhorou 150% minha compreensão!
    Só faltou um exemplo em código! =) Abraço!

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s