Geração
Alvo atingido
Chegada mais rápida
Distância mínima
  • Em voo
  • Alvo atingido
  • Despenhados
  • Melhor voo da última geração
  • Alvo atingido
  • Despenhados

Mais sobre algoritmos genéticos

Laboratório de algoritmos genéticos

Um algoritmo genético resolve um problema da mesma forma que a evolução molda os seres vivos: experimentar muitas respostas ao acaso, guardar as melhores, misturá-las, alterar alguns pedaços ao acaso e repetir. Aqui as respostas são foguetões. Cada um segue uma lista de impulsos aleatórios e nada mais, e ao início andam aos tombos sem rumo. Carregue em «Lançar» e veja a população melhorar geração após geração, até que a maioria dos foguetões contorna as paredes e chega ao alvo, sem que ninguém lhes diga para onde ir. Carregue em «Lançar» e veja uma população de foguetões a tentar alcançar o alvo verde. Cada foguetão segue apenas os seus genes, uma lista de pequenos impulsos, um para cada momento do seu voo. Depois de cada voo, os foguetões que mais se aproximaram, e sobretudo os que chegaram, têm mais probabilidade de se tornarem pais da geração seguinte; os seus genes são misturados e alguns são alterados ao acaso. «Geração seguinte» salta o resto de um voo. Arraste sobre o campo para desenhar uma parede e clique numa parede para a remover.

Como funciona

  1. Escolha obstáculos, ou arraste sobre o campo para desenhar as suas próprias paredes, e defina a população, a taxa de mutação e o tempo de vida.
  2. Carregue em «Lançar» e veja cada geração voar; «Geração seguinte» salta o resto de um voo.
  3. Acompanhe nos mosaicos e no gráfico a proporção que atinge o alvo, e experimente outras taxas de mutação e métodos de seleção.

Como os foguetões evoluem

Cada foguetão tem genes: um pequeno impulso para cada momento do seu voo. Os genes da primeira geração são aleatórios. Depois do voo, cada foguetão recebe uma pontuação de aptidão, máxima para uma chegada rápida, depois tanto mais alta quanto mais perto do alvo terminou, e dividida por dez após uma queda. Os pais da geração seguinte são escolhidos ao acaso, mas os foguetões mais aptos têm mais probabilidade de ser escolhidos. Cada filho recebe a primeira parte dos seus genes de um progenitor e o resto do outro, e alguns genes são substituídos por impulsos aleatórios: as mutações. Ao longo das gerações, os bons planos de voo espalham-se e melhoram.

O que mudam as definições

Uma população maior explora mais planos de voo ao mesmo tempo e tem menos probabilidade de ficar presa, mas cada geração demora mais. A taxa de mutação equilibra explorar e manter o que funciona: sem mutação, a população fica depressa sem ideias novas; com demasiada, esquece os bons voos mais depressa do que os consegue encontrar. A seleção por roleta escolhe os pais em proporção à aptidão, enquanto um torneio escolhe o melhor de três foguetões ao acaso, o que é menos sensível à escala da aptidão. O elitismo copia o melhor foguetão sem alterações para a geração seguinte, pelo que o melhor resultado nunca piora.

Perguntas frequentes

Porque é que os foguetões ficam presos atrás das paredes desfasadas?

A sua aptidão mede a distância em linha reta até ao alvo, por isso um foguetão que voa contra a parede por baixo do alvo obtém melhor pontuação do que um que se afasta para encontrar a abertura. A população amontoa-se nesse beco sem saída, um ótimo local. Populações maiores, mais mutação ou a seleção por torneio ajudam-na a escapar, e uma aptidão que medisse o percurso real à volta das paredes evitaria a armadilha. Escolher uma boa função de aptidão é a parte mais difícil de usar um algoritmo genético.

É assim que a evolução funciona na natureza?

Em traços gerais: a variação por mutação e recombinação, a hereditariedade dos genes e a seleção dos mais aptos são os ingredientes de Darwin. As diferenças, no entanto, são grandes. A natureza não tem alvo nem fórmula de aptidão, apenas sobrevivência e reprodução, e os genomas reais constroem corpos através do desenvolvimento em vez de enumerarem ações.

Para que servem os algoritmos genéticos?

Para problemas com um espaço enorme de respostas possíveis e uma forma simples de pontuar um candidato: dar forma a antenas, asas e peças de automóveis, elaborar horários, afinar as definições de outros algoritmos, conceber redes neuronais e criar arte e estratégias de jogo. A antena evoluída da NASA nos satélites ST5 de 2006 é um exemplo famoso.

Porque é que o melhor foguetão às vezes voa pior na geração seguinte?

Sem elitismo, o melhor foguetão não é copiado: os seus genes só sobrevivem misturados com outros e possivelmente mutados, por isso a geração seguinte pode perder o seu voo exato. Com o elitismo ativado, o melhor foguetão é mantido sem alterações e o melhor resultado nunca piora.

É enviado algo para um servidor?

Não. Os foguetões voam e evoluem no seu navegador, e as paredes que desenha ficam no armazenamento local deste navegador.

Pronto para experimentar?

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

Ir para o editor