Arquivo da tag: algoritmo

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.

Monges, torres e porque não adianta apenas comprar mais hardware

Se você já visitou a casa de algum pai que goste de presentear seus filhos com brinquedos educacionais (ou você é um desses pais), já deve ter visto uma torre de Hanoi. É aquele brinquedo que é composto de várias peças de tamanhos diferentes e três pauzinhos onde as peças se encaixam.

Este jogo não existe para Playstation 3

Este jogo não existe para Playstation 3

O que poucas pessoas sabem (principalmente as crianças que ganham esses brinquedos) é que esse é um quebra cabeças, com regras bem definidas e cuja solução algorítmica até já foi estudada por vários pesquisadores de matemática e computação.

Existe uma lenda sobre a torre de Hanoi, que diz que existem monges em um templo tentando resolver uma torre de Hanoi para o caso de 64 discos de ouro. E que quando eles conseguirem resolver, o mundo vai acabar. Agora você deve ter ficado preocupado, porque provavelmente se você conseguiu resolver a torre de Hanoi que seu filho tem em casa, daqui a pouco esses monges que não tem mais nada para fazer vão terminar esse negócio e o mundo vai acabar. E você já pagou suas férias de dezembro!!

Calma, se tudo der certo, você ainda vai poder viajar em dezembro. Pelo menos dificilmente os monges vão atrapalhar suas férias. O número mínimo de operações para se resolver uma torre de Hanoi de 64 discos é 264-1 movimentos. Ou seja, mesmo que os monges nunca errassem e pudessem realizar cada movimento em 1 segundo, a solução do problema inteiro levaria mais de 580 bilhões de anos para terminar. Sem pausa para a novela.

E se os monges fizessem um upgrade e usassem uma máquina tão rápida quanto o supercomputador mais potente atualmente? Olhando no TOP500, o campeão atual é o Roadrunner, um cluster da IBM, que realizou no benchmark até 1456704 GFlops (bilhões de operações de ponto flutuante por segundo). Como o problema da torre de Hanoi não pode ser paralelizado (sempre tenho que mover uma peça por vez) para simplificar vamos pegar um de seus processadores, que faz 12.8 GFlops. Se os monges pudessem realizar 12800000000 movimentos por segundo será que o fim do mundo aconteria antes da próxima copa do mundo? Melhoraria bastante (só uns 45 anos) mas ainda ocorreriam muitas copas até lá. 

Para quem já resolveu uma torre de Hanoi de brinquedo, com 8 discos, deve ser muito estranho uma torre que nem tem tantos discos a mais necessitar de um número tão grande de operações para ser resolvida. Isso em computação é muito comum e e conhecido como explosão exponencial. Às vezes o problema parece bobo quando você aplica o algoritmo para versões pequenas do problema, mas o número de operações para resolver versões só um pouco maiores cresce para um tamanho probitivo, em que simplesmente não valeria a pena tentar resolver por levar tempo demais.

O exemplo desse fenômeno é encontrado na resolução da torre de Hanoi. A versão infantil, com 8 discos, exige no mínimo 255 operações. Dobrando-se o número de discos, 65535 operações. Com 24 discos, 16777215 operações. Moral da história: se quiser deixar seu filho bem ocupado, dê uma torre de Hanoi com uns 20 discos.

É raro uma empresa se deparar com um problema desses e tentar resolvê-lo (na ignorância de que o problema gera uma explosão exponencial). E você nem precisa trabalhar em uma empresa que resolve torres de Hanoi. Depois de algum tempo tentando resolver o problema, a empresa pode se frustrar e desistir, ou culpar o coitado do programador que fica marcado como incompetente.

Obs.: Este post foi livremente inspirado nas aulas do professor Coelho do IME-USP. O original obviamente é melhor.