Introdução à programação genética

Nós, como programadores, estamos acostumados a ditar regras ao computador. Ainda que os defensores da programação funcional digam que eles não tenham de ensinar ao computador como fazer (como é o caso das linguagens procedurais), eles ainda tem de dizer qual a relação entre o valor que aquela função retorna e seus argumentos. Por exemplo, podemos definir a função soma como sendo soma(x, y) = x + y, mas e se pudéssemos fazer o contrário, criar um banco de dados e mandar o computador analisar esses dados e achar a relação entre eles?

A Programação Genética (PG) surge justamente dessa idéia, misturando também conceitos da biologia, ou mais precisamente, da genética e da evolução. Por mais estranho que possa parecer, criaremos programas que irão se reproduzir e sofrer mutações. Através disso e de um processo de seleção natural, seremos capazes de determinar a relação entre valores que a princípio pareciam não ter nada em comum.

Além disso, podemos usá-la também para desenvolvermos algoritmos que sejam mais rápidos, basta ajustarmos a nossa seleção “natural” para que ela leve em consideração o tempo também.

Programas, cromossomos, cruzamentos e mutações

O problema agora passa a ser como representar a nossa população de programas para que seja possível fazê-los reproduzir e trocar informações genéticas. A forma mais comum de se fazer isso é representar o programa como uma árvore: cada branch é uma operação e cada folha é um valor – seja uma constante: 2, 0.56, π, ou seja uma variável do problema: x, θ, etc.

A reprodução (também chamada de crossover) acontece com a troca de material genético entre dois programas. Na prática, isso significa a troca de um branch de uma árvore-programa pelo branch de uma outra. Em Lisp, linguagem frequentemente utilizada para esse tipo de programa por ser fácil representar essas árvores, a reprodução de A e B poderia gerar dois descendentes, C e D, da seguinte forma:

(+ (* 7 2) x) ; A
(* (/ x 2) 5) ; B
(+ (* 7 2) (/ x 2)) ; C
(* x 5) ; D

A e B trocaram entre si x e (/ x 2) dando origem ao que chamamos de C e D. Para que haja a troca genética, não é necessário que os branches trocados estejam na mesma posição, o que nos permite um maior número de combinações possíveis.

Há também as mutações, que permitem o surgimento de novos cromossomos que não seriam possíveis apenas com a reprodução. Por exemplo, nosso programa A poderia se tornar um programa E da seguinte forma:

(+ (* 7 2) x) ; A
(+ (* 7 2) (- x 1)) ; E

O cromossomo x sofreu mutação e se transformou em (- x 1), o que não existia em nenhuma de nossas árvores anteriores A–D.

Seleção natural

A reprodução e o surgimento de novos programas não nos serve de nada se não pudermos selecionar quais são os programas que melhor solucionam nosso problema. Aqui entra a função fitness, que mede o quanto aquele programa está adaptado. Como ela irá funcionar exatamente depende do problema em questão.

A partir de seus resultados podemos decidir quem irá se reproduzir ou que programas serão eliminados. A função fitness também é uma das formas que podemos usar para decidir quando encerrar os ciclos de reprodução. Quando acharmos um problema com fitness perfeito, então provavelmente encontramos a solução para nosso problema.

Outra forma de terminar o programa é determinar um número máximo de ciclos de reprodução. Isso não nos garante, no entanto, que chegamos à solução do problema.

Um exemplo de função fitness é caso estejamos programando um robô para acertar um alvo (que não é um humano, lei número de Asimov), ela poderia retornar a distância entre a posição do tiro e o centro do alvo, quanto menor o valor retornado, mais adequado é aquele algoritmo.

Publicidade

2 Respostas para “Introdução à programação genética

  1. Cesar abril 9, 2009 às 12:15 pm

    Só para complementar seu post, recentemente utilizaram uma técnica similar para obter equações que descrevessem o comportamento de alguns sistemas dinâmicos não-lineares:

    http://blog.wired.com/wiredscience/2009/04/newtonai.html

    O mais interessante:

    “Initially, the equations generated by the program failed to explain the data, but some failures were slightly less wrong than others. Using a genetic algorithm, the program modified the most promising failures, tested them again, chose the best, and repeated the process until a set of equations evolved to describe the systems. Turns out, some of these equations were very familiar: the law of conservation of momentum, and Newton’s second law of motion. ”

    Agora, se você assistiu Exterminador do Futuro (imagino que sim), verá que a ideia de que máquinas que são capazes de construir máquinas melhores ainda, não é de tudo absurda. É apenas uma questão de tempo.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: