Algoritmos Genéticos

Na faculdade de Computação, fiz uma cadeira de IA (Inteligência Artificial). O professor nos apresentou algumas técnicas de programação que são usadas nesse ramo da computação, onde os problemas são muito complexos, algumas vezes de tal forma que nem dá pra pensar num algoritmo comum para resolve-los. Problemas cuja ordem de complexidade exige mais dos computadores. Vimos técnicas tais como Resfriamento/Têmpera Simulada (Simulated Annealing) e Algoritmos Genéticos (Genetic Algorithms).

Eu fiquei principalmente interessado nessa técnica de Algoritmos Genéticos que é inspirada na biologia evolutiva e usa hereditariedade, mutação, seleção natural e recombinação (crossing over) para achar soluções aproximadas de problemas de otimização e busca. Isso funciona da seguinte forma: os algoritmos genéticos são implementados como uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores (fazendo um paralelo com o papel de um indivíduo biológico, ou seja, uma tentativa de solução de problemas de sobrevivência no mundo real). A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada através de gerações. A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a próxima geração de acordo com sua aptidão em resolver o problema proposto, e recombinados ou mutados para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo. Em outras palavras, um algoritmo genético atua na resolução de um problema da mesma forma que a evolução atua, isto é, através de populações de indivíduos que geram descendentes através de várias gerações e são selecionados naturalmente de acordo com suas características. Explico melhor com um exemplo a seguir.

O professor passou um problema para implementarmos essa técnica. O problema consistia em alocarmos várias freqüências diferentes num conjunto de antenas de forma que a interferência entre elas fosse a menor possível. Ele então disse algumas regras sobre como aconteceriam as interferências. Ele disse quantos grupos de antenas deveriam existir, as distâncias possíveis entre as antenas, quantas freqüências tínhamos disponíveis, quanta interferência seria causada dependendo das distâncias, etc. Por exemplo, uma antena "A" poderia usar a freqüência 23, e outra antena "B" poderia usar a freqüência 54, e assim por diante. Mas também poderia acontecer de antenas diferentes usarem a mesma freqüência, por isso causariam interferência uma na outra dependendo da distância entre elas. E se nós tivéssemos 500 antenas, e tivéssemos que distribuir apenas 100 freqüências entre elas, isso teria que ser de forma que a interferência fosse mínima. Como tínhamos um número limitado de frequências para distribuir em centenas de antenas, logicamente que ocorreriam repetições, e uma mesma frequência teria que ser usada por mais de uma antena. Isso é conhecido como "Princípio da Casa dos Pombos" (se N pombos devem ser postos em M casas, sendo N > M, então pelo menos uma casa irá conter mais de um pombo).

A solução do problema usando algoritmos genéticos é extremamente elegante, fácil e não nos custa esforço nenhum. Simplesmente nós, os programadores, não resolvemos o problema, mas deixamos a solução evoluir sozinha. Elegante, não? Para esse problema das antenas, fazemos o seguinte. Digamos que queremos alocar 100 freqüências em 500 antenas. Primeiramente, temos que criar a nossa população inicial que é constituída de indivíduos. O que é um indivíduo? Um indivíduo é uma possível solução do problema. E neste caso, um indivíduo é um conjunto de 500 antenas, cada uma com sua freqüência específica. Podemos escolher o tamanho da população inicial de, digamos, 3 mil indivíduos, ou seja, 3 mil soluções diferentes para o problema, inicializadas de forma completamente aleatória. Nós pegamos uma função que gera valores aleatórios de 1 até 100 e alocamos um valor para cada uma das 500 antenas, fazemos isso 3 mil vezes para termos 3 mil indivíduos na população inicial. Assim estamos prontos para começar.


Já dá pra perceber algumas semelhanças com a evolução biológica. Temos uma população com centenas ou milhares de indivíduos, cada um destes com características diferentes. Os genes são as partes do código genético de cada indivíduo. Então, no nosso exemplo, cada indivíduo possui 500 genes, cada um dos quais sendo um par antena-freqüência, por exemplo, um indivíduo pode possuir um gene que seja 324-12, ou seja, ele pode ter na sua antena de número 324 a freqüência 12. A mutação é uma mudança aleatória em um gene, então digamos, se um indivíduo possui um gene dizendo que sua antena de número 324 possui a freqüência 12, o seu filho pode herdar esse gene e, caso ele sofra uma mutação, pode mudar para a freqüência 57, formando o gene 324-57. O cruzamento acontece quando dois indivíduos cruzam entre si para gerar filhos. No nosso caso, pegamos dois indivíduos (dois conjuntos de antenas com freqüências) e geramos um filho (novo conjunto de antenas com freqüências). No caso esse filho recebe metade dos genes do seu pai e metade dos genes da sua mãe. Essa doação de genes á aleatória, contanto que tenha 50% do pai e 50% da mãe.


E a seleção natural? Bem, a partir das regras que o professor deu para calcularmos a interferência entre as antenas dependendo das distâncias entre elas, podemos calcular a aptidão de cada indivíduo. Cada um possui características que o tornam mais apto ou menos apto para sobreviver, se reproduzir e passar seus genes para seus descendentes. No nosso caso a aptidão é a interferência total de um indivíduo. Tendo as regras para calcular a interferência de cada antena, podemos chegar em resultados que mostrem as aptidões dos indivíduos. No nosso exemplo, temos uma população de 3 mil indivíduos, cada um deles tendo um valor de interferência que é causado pelas suas antenas de acordo com as freqüências de cada uma e suas respectivas distâncias com as demais antenas. Lembro-me que a aptidão inicial média da população era um valor muito alto de interferência, ou seja, quando inicializamos as antenas com freqüências aleatórias, fica tudo muito confuso e existe uma interferência altíssima. Percebamos que nesse caso, um valor menor para interferência significa um indivíduo mais apto, ou seja, que possui os melhores genes para sobreviver.

Depois de gerarmos a população inicial (onde cada indivíduo é uma possível solução do problema), começamos a rodar o programa. A cada geração, calculamos a aptidão de cada indivíduo e permitimos que se reproduzam com uma probabilidade maior para aqueles que tiverem uma aptidão melhor. Dessa prole, depois do cruzamento, pegamos um pequeníssimo percentual dos indivíduos e nestes causamos mutações em um pequeníssimo percentual dos seus genes. Daí pegamos a prole inteira, tanto aqueles que sofreram mutações (uns poucos) como aqueles que não sofreram (quase todos) e calculamos a aptidão de cada um deles. Selecionamos um percentual maior daqueles que tem uma melhor aptidão e um pequeno percentual de quem tem aptidão ruim. Agora temos uma nova população, que foi "peneirada" a partir da primeira, foi cruzada e sofreu algumas poucas mutações. Como selecionamos com uma chance maior aqueles indivíduos com melhor aptidão para poderem reproduzir-se, existe uma tendência probabilística de que essa prole tenha indivíduos com aptidões melhores ainda (no caso, com menor interferência entre as antenas). Tipo, eventualmente pode surgir uma geração onde a aptidão média seja pior, mas a longo prazo, a tendência é que genes que causem uma aptidão ruim sejam eliminados do reservatório genético (pool genético) da população.


Lembro-me que no início a interferência média da população era algo em torno de 2500. Mas ao longo da simulação, víamos um gráfico dessa interferência em cada geração sendo construído e ia decrescendo. Depois de algumas dezenas de milhares de gerações (que bom que os computadores são rápidos), lembro que o melhor resultado que conseguimos foi de interferência 11. Impressionante! Aqueles indivíduos que tinham sido inicializados aleatoriamente, foram sendo cruzados de acordo com suas aptidões e esses cruzamentos seguiram as leis da probabilidade onde aqueles com melhor aptidão tinham mais chances de sobreviver e cruzar. Essa tendência estatística convergiu cada vez mais para uma população com a aptidão melhorada.

E algoritmos genéticos tem sido usados muito para resolver muitos problemas computacionais. Esse tipo de algoritmo é usado por empresas de telecomunicações para determinar a posição ótima de uma rede de torres de telefones celulares, também é usado para melhorar a área de cobertura de satélites, para descobrir novos algoritmos de ordenação, melhores rotas de transporte, etc. É uma infinidade de usos. Já li sobre um satélite da NASA onde os engenheiros não projetaram o satélite, mas ele evoluiu. Eles simplesmente pegaram vários projetos de satélite e jogaram dentro de um algoritmo genético. Daí, o programa pegava os vários projetos, ia misturando eles, cruzando, gerando automaticamente novos projetos que eram uma mistura dos vários projetos iniciais, eles sofriam mutações e depois de muitas gerações de cruzamento, mutação e seleção, surgiram novos projetos inéditos muito melhores. O poder da seleção natural é fantástico.

A ordenação de conjuntos é um problema rotineiro da computação e existem muitos algoritmos famosos para resolver esse problema. Mas com o uso de algoritmos genéticos, são obtidos novos algoritmos de ordenação que os próprios programadores não fazem a menor idéia de como eles funcionam, só sabem que conseguem ordenar conjuntos e de forma excelente. Nada como um mecânismo simples de seleção gradual e cumulativa direcionando as soluções por caminhos cada vez mais adaptados de acordo com as situações locais. O poder da seleção cumulativa é bem explicado no livro "O Relojoeiro Cego" do biólogo Richard Dawkins e ele dedica todo um capítulo para esclarecer esta questão. Ele prova que um macaco batendo aleatoriamente numa máquina de escrever nunca poderia produzir todas as obras de Shakespeare. Mas se for usado o mecânismo da seleção cumulativa e gradual, em um tempo razoável, o tal macaco datilógrafo poderia tornar-se um grande escritor.