Algoritmos genéticos explicados

A evolução produziu olhos, asas e cérebros sem um projetista, simplesmente guardando o que funciona e fazendo-o variar. Um algoritmo genético toma emprestada essa ideia para resolver problemas num computador. Não precisa de compreender o problema, apenas de distinguir uma resposta melhor de uma pior, o que faz dele uma ferramenta poderosa quando o espaço de respostas possíveis é demasiado grande e demasiado estranho para ser explorado de outra forma.

Foguetões a voar a partir da parte de baixo de um campo, contornando uma parede em direção a um alvo verde, com o melhor voo desenhado como linha tracejada
Foguetões a voar a partir da parte de baixo de um campo, contornando uma parede em direção a um alvo verde, com o melhor voo desenhado como linha tracejada

A ideia

Nas décadas de 1960 e 1970, John Holland, da Universidade do Michigan, transformou a teoria de Darwin num algoritmo, descrito no seu livro «Adaptation in Natural and Artificial Systems», de 1975. Mais ou menos na mesma altura, Ingo Rechenberg e Hans-Paul Schwefel desenvolveram na Alemanha as estratégias evolutivas para o projeto de engenharia. A receita comum: manter uma população de soluções candidatas, pontuá-las, deixar que as melhores se reproduzam com variação e repetir ao longo de muitas gerações.

John Holland, que descreveu os algoritmos genéticos no seu livro Adaptation in Natural and Artificial Systems, de 1975.
John Holland, que descreveu os algoritmos genéticos no seu livro Adaptation in Natural and Artificial Systems, de 1975.

Os genes e a população

Cada candidato é descrito por um cromossoma, uma lista de genes. No laboratório, os genes de um foguetão são os seus impulsos, um para cada momento do seu voo; noutros problemas podem ser os bits de um número, a ordem das cidades num percurso ou as dimensões das peças de um projeto. A primeira geração é aleatória, o que significa que explora amplamente o espaço de respostas, mas quase não tem nenhuma boa.

A função de aptidão

A aptidão é o número único que diz quão bom é um candidato, e é a única coisa que o algoritmo sabe sobre o problema. Para os foguetões, recompensa sobretudo chegar cedo, depois terminar perto do alvo, e penaliza as quedas. Uma função de aptidão bem escolhida guia a procura suavemente em direção a boas respostas; uma descuidada recompensa a coisa errada, e o algoritmo aproveitará qualquer brecha que ela deixe aberta.

Seleção

Os pais são escolhidos de modo que os candidatos mais aptos tenham mais filhos, mas os mais fracos continuem a ter uma oportunidade, porque os seus genes podem conter peças úteis. A seleção por roleta dá a cada candidato uma fatia de uma roda proporcional à sua aptidão; a seleção por torneio escolhe alguns ao acaso e fica com o melhor. Uma seleção mais forte acelera o progresso, mas também torna a população mais uniforme, o que pode terminar a procura demasiado cedo.

Cruzamento e mutação

O cruzamento combina dois progenitores: aqui um filho recebe a primeira parte dos seus genes de um progenitor e o resto do outro, de modo que as primeiras manobras de um foguetão se podem juntar às últimas de outro. A mutação substitui alguns genes ao acaso. O cruzamento recombina o que a população já tem; a mutação traz o que ela nunca teve. O teorema dos esquemas de Holland descreve como pequenos blocos de construção de bons genes se espalham pela população sob esta mistura de seleção e recombinação.

Elitismo, exploração e aproveitamento

Copiar sem alterações os poucos melhores candidatos para a geração seguinte, o elitismo, garante que a melhor resposta nunca se perde. Todo o algoritmo genético tem de equilibrar a exploração, experimentar novas regiões do espaço de procura, com o aproveitamento, refinar o que já é bom. Com pouca variação, a população converge para uma única resposta medíocre; com demasiada, nunca estabiliza. O tamanho da população, a taxa de mutação e a pressão de seleção são os botões que regulam esse equilíbrio.

Ótimos locais

Um algoritmo genético segue apenas a aptidão, por isso pode ser enganado. Quando o caminho para a melhor resposta passa primeiro por respostas piores, a população sobe a colina mais próxima e fica lá: um ótimo local. Atrás das paredes desfasadas do laboratório, os foguetões que se despenham por baixo do alvo obtêm melhor pontuação do que os que se desviam para encontrar a abertura, por isso a população amontoa-se contra a parede. Entre os remédios estão populações maiores, mais mutação, manter a diversidade da população e, sobretudo, uma função de aptidão melhor.

Explore

Abra o laboratório de algoritmos genéticos para fazer evoluir foguetões à volta de uma parede, de uma abertura, de pilares, de paredes desfasadas ou de paredes desenhadas por si. Altere a população, a taxa de mutação, o tempo de vida e o método de seleção, ative e desative o elitismo e acompanhe no gráfico a rapidez com que cresce a proporção de foguetões que atingem o alvo, ou porque não cresce.

Perguntas frequentes

Um algoritmo genético é uma forma de inteligência artificial?

Pertence ao campo mais vasto da IA e da aprendizagem automática, como método de procura e otimização. Não aprende com exemplos como uma rede neuronal; melhora soluções candidatas por tentativa e seleção. Os dois são muitas vezes combinados, por exemplo fazendo evoluir a estrutura ou os pesos de redes neuronais, uma abordagem chamada neuroevolução.

Um algoritmo genético encontra sempre a melhor resposta?

Não. É uma heurística: normalmente encontra boas respostas para problemas difíceis, mas não garante a melhor nem prova quão perto está dela. Para problemas em que um método exato é suficientemente rápido, esse método é melhor.

Qual é a diferença entre um algoritmo genético e as estratégias evolutivas?

Ambos são algoritmos evolutivos. Os algoritmos genéticos clássicos dão ênfase ao cruzamento de cromossomas semelhantes a cadeias; as estratégias evolutivas trabalham sobretudo com a mutação de números reais e muitas vezes adaptam por si próprias a amplitude das suas mutações pelo caminho. Os métodos modernos misturam ideias de ambos.

Porque é que os foguetões são tão desajeitados ao início?

Os seus primeiros genes são impulsos totalmente aleatórios, que em média se anulam, por isso os foguetões andam à deriva. Só depois de a seleção ter guardado os raros foguetões que por acaso empurravam mais ou menos na direção certa, e de o cruzamento ter combinado os seus bons troços, surgem voos coordenados.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir o laboratório de algoritmos genéticos