5.3 Programação Genética e Arte Genética
Agora vamos estudar uma abordagem diferente de algoritmos genéticos
chamada programação genética, desenvolvida por John Koza em 1990
Programação genética, ao invés de utilizar listas de números, como fizemos para o robô Robby, usa em seus programas
árvores sintáticas, que serão abordadas daqui a pouco.
Aqui temos uma foto de John Koza, em um curso sobre programação genética.
Ele escreveu 1, 2, 3 livros neste assunto, que se tornou uma grande sub-área de algoritmos genéticos.
Aqui está a idéia: vamos considerar o problema do robô Robby novamente e evoluir uma estratégia de controle para ele.
Ao invés de representar a sua estratégia de controle como uma lista de números que representam ações em todas as situações possíveis
Aqui vamos representar a sua estratégia de controle como um tipo de árvore, isto é o que na ciência da computação é chamada de árvore.
Onde os elementos do programa são representados em termos de nós e ramos.
Este programa em particular é uma sequência "if-then-else" na raiz, e ele diz: se esta é uma cláusula a ser considerada, se existe uma lata
no leste, e o norte está vazio então o robô deve mover-se para o leste, caso contrário, o robô deve mover-se para o sul.
Isto é o que a árvore representa e você pode interpretar isto como um tipo comum de programa: se leste for igual a lata
e norte for igual a vazio então mova-se para o leste caso contrário mova-se para o sul.
Agora suponha que Robby encontra-se nesta situação e esta é a sua estratégia. Ele faria o seguinte: ele olharia para esta cláusula
aqui que diz: existe uma lata ao leste e vazio ao norte, ele seguiria este primeiro ramo, movendo para o leste, lá vai ele.
Agora, ele está em uma situação nova, e segue a estratégia novamente: existe uma lata ao leste o norte está vazio?
- Não, então devo seguir o segundo ramo e mover para o sul, e ele faz isto novamente: não existe lata ao leste e o norte não está vazio,
então movo para o sul. Esta não é uma estratégia muito boa, mas é o que está disponível para ele seguir. É uma representação diferente
da apresentada previamente. Obviamente esta árvore é simples demais para ser uma boa estratégia pois não há regras
para pegar latas. Considere agora esta estratégia mais complicada representada por uma árvore mais longa.
Bem, isto está ficando difícil de interpretar, mas aqui temos Robby seguindo a estratégia.
Aqui está ele, e a instrução diz: se existe uma lata ao leste, e isto é verdade, então siga o primeiro ramo.
Agora este primeiro ramo possui outra condição: se é verdade tanto que não existe uma lata ao oeste e existe uma lata ao leste, e essas
afirmações são verdadeiras, então o robô deve mover-se para o leste. Agora ele está em uma situação nova, e olhamos a regra:
o norte está vazio e existe uma lata ao leste? - Não. Então olhamos o último ramo: se existe uma lata na posição atual, existe
então pegamos a lata. Agora, ele está em uma situação onde esta primeira cláusula if é falsa, então ele vai para a próxima,
e não existe uma lata na posição atual. Então ele move-se para o sul. Espero que vocês tenham entendido a idéia de que esta
é uma forma diferente de se expressar uma estratégia. É difícil encontrar uma árvore que seja uma boa estratégia,
mas esta será a tarefa do algoritmo genético. A única diferença em relação ao que fizemos antes é que o algoritmo genético
irá evoluir estas árvores ao invés das listas de números. Aqui está como o algoritmo funciona: temos uma população inicial
que ao invés de listas aleatórias, é um conjunto de árvores aleatórias com vínculos sintáticos, por exemplo:
precisamos de um condicional if-else na raiz da árvore, e outros vínculos. Não irei abordar os detalhes aqui,
só espero passar a idéia geral. Para calcular a aptidão, é o mesmo procedimento: Robby executará cada estratégia
em diferentes ambientes e cada estratégia terá a sua pontuação média. Então teremos os melhores indivíduos com
mais descendentes do que os piores indivíduos, implementando a seleção.
Para realizar o crossover e gerar os descendentes, ao invés de trocar partes da lista, trocaremos sub-árvores.
Aqui temos um exemplo, existem dois possíveis pais, duas árvores, e o filho resultante terá esta sub-árvore do segundo pai
no lugar desta posição aqui, mova para leste. Colocamos esta sub-árvore e temos agora o filho que tem esta forma.
Este é exatamente o primeiro pai exceto por esta substituição do bloco mova para leste pelo bloco if-else.
Ainda é uma árvore com sintática correta, ainda é uma estratégia, e é desta maneira que o algoritmo genético é capaz
de selecionar partes dos pais e recombiná-las.
Na mutação, ao invés de substituirmos um valor escolhido aleatoriamente por outro valor aleatório,
vamos substituir uma sub-árvore por uma sub-árvore gerada aleatoriamente.
Dessa forma, essa sub-árvore aqui será eliminada e substituída por uma outra sub-árvore gerada aleatoriamente.
Eu não implementei uma versão utilizando programação genética de Robby, esta é uma tarefa para programadores mais avançados.
Mas eu quero apresentar a vocês um projeto real de programação genética, na verdade dois projetos, que são interessantes.
O primeiro deles envolve a aplicação da programação genética a gráficos computacionais. Isto vem sendo feito por muitas pessoas,
mas o exemplo mais famoso foi feito por Karl Sims nos anos 90. Ele é um artista gráfico computacional e decidiu desenvolver programas
que utilizam gráficos computacionais que são esteticamente agradáveis.
Aqui temos um perfil do programa. Os indivíduos na população são árvores, como foi mostrado anteriormente, só que ao invés de
representarem estratégias para um robô virtual, eles representam equações que geram uma cor diferente para cada pixel da imagem.
Estes são alguns exemplos. Aqui temos alguns programas. Não vou explicar para vocês o funcionamento deles, você pode ler os artigos.
Mas apenas entenda a idéia de que você pode representar estes programas como árvores e cada programa gera uma cor para
cada pixel na imagem. Então você pode imaginar que são gerados muitos programas aleatórios que colorem os pixels da imagem
de forma aleatória. A questão é: como definir uma função de aptidão, como definir a aptidão de uma imagem particular?
Bem, isto é algo que - agora - está além do que os computadores podem realizar, então Karl Sims tinha pessoas para esta etapa.
O que ele fez foi utilizar pessoas - incluindo ele - analisando imagens criadas pelo computador, imagens aleatórias, e escolhendo
a imagem favorita. A imagem escolhida seria utilizada como pai e seria feito um crossover com outro programa aleatório, e mutações,
produzindo novos programas, que produzem novas imagens que possuem relação com a imagem escolhida.
Este processo é repetido continuamente, e o algoritmo genético produz resultados muito bonitos.
Aqui temos um exemplo: aqui está a imagem e o programa que a criou. Esta foi uma colaboração, entre o algoritmo genético e
uma pessoa. Esta pessoa não está escrevendo o programa, apenas dizendo o que ela gosta, e então o algoritmo genético evolui mais
o programa. Aqui temos outro exemplo.
E outro.
E aqui um particularmente bonito, que lembra pinturas japonesas, eu acho.
Mais um, e existem muitos outros.
Aqui temos dois sites, o primeiro é o website de Karl Sims, onde temos todas essas imagens e ele fala sobre diferentes projetos.
O segundo é um applet que permite que você desenvolva estas figuras você mesmo.
Algo muito interessante feito por Karl Sims, além do que já foi apresentado, foi organizar uma exposição em um museu.
Esta exposição foi feita no Centro Georges Pompidou em Paris, onde ele tinha uma série de monitores, cada um mostrando
uma imagem diferente do tipo das que foram mostradas aqui. E aqui no chão existem sensores. Então as pessoas que gostaram de
uma imagem em particular poderiam ficar sobre o sensor em frente à imagem escolhida e esta imagem seria evoluída mais uma vez,
utilizando outra imagem da exposição para reprodução. Desta forma, não foi apenas uma pessoa, mas um grupo atuando na seleção
do algoritmo genético na galeria.
Aqui está o que Sims disse sobre a exposição:
"As pessoas na exposição podem observar uma evolução simulada computacionalmente em progresso:
uma evolução de imagens. Porém nesta evolução, as pessoas não são apenas observadoras: elas causam a evolução e
podem alterar o seu caminho."
Ele continua:
"Uma população de imagens é mostrada pelo computador em um arco de 16 telas de vídeo. As pessoas determinam quais
imagens irão sobreviver ao ficar sobre sensores em frente às imagens que acharam mais interessantes esteticamente.
As imagens que não são selecionadas são removidas e substituídas pelos descendentes das imagens sobreviventes.
As novas imagens são cópias e combinações dos seus pais, porém com várias alterações.
Esta é uma evolução artifical onde as próprias pessoas determinam interativamente a "aptidão" das imagens ao escolher onde ficar.
Na continuação do ciclo, a população de imagens pode evoluir para efeitos visuais cada vez mais interessantes.
Esta instalação interativa é uma forma não usual de colaboração entre humanos e máquinas:
os humanos fornecem as decisões sobre estética visual, e o computador fornece a habilidade matemática para gerar, combinar e
realizar a mutação de texturas e padrões complexos.
As pessoas não precisam entender as equações técnicas envolvidas.
O computador pode apenas experimentar aleatoriamente sem ter noções de estética - mas a combinação de habilidades
de humanos e máquina permite a criação de resultados que nenhum dos dois poderia produzir sozinho.