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.
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.
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