Programação Genética Explicada: Como Máquinas Aprendem a Escrever Seu Próprio Código

Talvez o "Santo Graal" da ciência da computação terá sido descoberto no dia em que nossas máquinas puderem escrever seus próprios programas. Programação genética (PG) é um paradigma de machine learning relativamente novo representando um passo nessa direção.

PG tem grande promessa no reino da engenharia de controle. Neste artigo, discutiremos o que é programação genética, como pode ser representada, e veremos um exemplo de programa.

Este artigo é o primeiro de uma série. Para pular para as próximas entradas, selecione uma abaixo:

• Operadores Genéticos em Algoritmos Evolutivos
• Exemplos de Algoritmo Genético: Evoluindo Programa de Ordenação e Regressão Simbólica
• Aplicações e Limitações da Programação Genética

Programação Genética e Algoritmos Genéticos

PG é essencialmente uma variação do algoritmo genético (AG) originalmente concebido por John Holland. Como um AG, PG é um algoritmo evolutivo dependendo de operadores genéticos como reprodução proporcional à aptidão, crossover e mutação para impulsionar uma população de programas codificados, ou "indivíduos", através de gerações sucessivas em direção a uma solução.

No entanto, ao contrário de um AG, que tipicamente usa codificação de string de bits de tamanho fixo, PG emprega representação baseada em árvore de tamanho variável de um programa real. Portanto, o resultado de uma execução PG bem-sucedida produz um programa de computador que, quando dada entrada apropriada e executado, produz o resultado desejado.

Nichael Cramer e John Koza são creditados por lançar as fundações da PG. John Koza (que também detém patente sobre PG) fez quantidade significativa de pesquisa em PG e seu livro marco "Genetic Programming" é considerado obra seminal no assunto. Pesquisa atual demonstrou alguns sucessos encorajadores de PG em ampla gama de aplicações, incluindo navegação de robô, aquisição de estratégia de jogo, análise de regressão simbólica e sistemas de controle.

Representação da Programação Genética

A representação baseada em árvore mencionada anteriormente é central ao tema PG pois virtualmente qualquer programa de computador pode ser representado desta forma. Na prática, uma linguagem funcional como LISP é bem adequada a esta forma e é fácil ver como uma S-expression LISP pode ser diagramada como árvore (Figura 1).

Abaixo, você encontrará três representações separadas da mesma informação:

Um fragmento de programa simples:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


Equivalente LISP:
(progn (if (a < b)
 (setq a (+ a 1))
 (setq b (* b b))
 )
 (setq c (* (* a b) 2))
)

Figura 1. Representação em árvore de um programa. Note que (progn arg1 arg2 arg3 ... argn) avalia sequencialmente cada argumento.

Os nós interiores da árvore consistem de funções enquanto os nós folha consistem de terminais. Funções devem ter contagem de argumentos (comumente referida como aridade) de pelo menos um, permitindo que sejam conectadas a outras funções ou terminais, fornecendo a "cola" para ramos dentro da árvore.

Terminais tipicamente incluem coisas como constantes e variáveis. Como terminais formam as folhas da árvore, eles sempre têm aridade zero. Você é requerido a escolher o conjunto de funções e terminais para o problema que está tentando resolver. Por exemplo, funções lógicas AND, OR e NOT e terminais X1 e X2, representando duas variáveis de entrada booleanas, são apropriados se você está tentando descobrir programa capaz de sintetizar a função booleana XOR. Uma função de aptidão também é requerida já que você deve fornecer meios para um programa ser medido contra outro no sentido de que um é melhor em resolver dado problema.

Por exemplo, no caso XOR, podemos testar a aptidão de um programa executando o programa uma vez para cada caso de aptidão correspondente às quatro entradas booleanas possíveis para X1 e X2 (0 0, 0 1, 1 0, 1 1) e somando o número de respostas corretas (0, 1, 1, 0) respectivamente, para cada caso de teste.

Obviamente, um programa produzindo pontuação perfeita de quatro é considerado solução para o problema XOR, como mostrado no Listing 1.

Listing 1. Resultado XOR

Uma solução perfeita para o problema XOR descoberta por PG:
(defun program ()
 (AND (OR X1 X2)
 (NOT (AND X1 X2) )
 )
)

Próximo: Operadores Genéticos

No próximo artigo, daremos uma olhada nos operadores genéticos que tornam algoritmos evolutivos possíveis. Também os usaremos em um exemplo de algoritmo mais complexo.

Leitura Sugerida

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. "Strongly Typed Genetic Programming." BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.