Uma introdução à programação genética:um sistema que se programa?

Talvez o "Santo Graal" da ciência da computação tenha sido descoberto no dia em que nossas máquinas puderem escrever seus próprios programas. A programação genética (GP) é um paradigma de aprendizado de máquina relativamente novo que representa um passo nessa direção.

A GP é muito promissora no domínio da engenharia de controle. Neste artigo, discutiremos o que é programação genética, como pode ser representada e daremos uma olhada em um programa de exemplo.

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 algoritmos genéticos:evolução de um programa de classificação e regressão simbólica
• Aplicações e limitações da programação genética

Programação genética e algoritmos genéticos

GP é essencialmente uma variação do algoritmo genético (GA) originalmente concebido por John Holland. Como um GA, o GP é um algoritmo evolutivo que depende de operadores genéticos, como reprodução proporcional de aptidão, cruzamento e mutação para conduzir 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 GA, que normalmente usa uma codificação de sequência de bits de comprimento fixo, o GP emprega uma representação de tamanho variável e baseada em árvore de um programa real. Portanto, o resultado de uma execução de GP bem-sucedida produz um programa de computador que, quando dado entrada apropriada e executado, produz o resultado desejado.

Nichael Cramer e John Koza são creditados por lançar as bases do GP. John Koza (que também detém uma patente de GP) fez uma quantidade significativa de pesquisas sobre GP e seu livro marcante, "Programação Genética", é considerado o trabalho seminal sobre o assunto. A pesquisa atual demonstrou alguns sucessos encorajadores da GP em uma ampla gama de aplicações, incluindo navegação de robôs, 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 para o tema GP, pois virtualmente qualquer programa de computador pode ser representado dessa forma. Na prática, uma linguagem funcional como LISP é adequada para esta forma e é fácil ver como uma expressão LISP S pode ser diagramada como uma árvore (Figura 1).

Abaixo, você encontrará três representações separadas das mesmas informações:

  Um fragmento de programa simples: COMEÇAR SE a  Equivalente de LISP: (progn (se (a  
 
 
  
 
   Figura 1.  Representação em árvore de um programa. Observe que (progn arg1 arg2 arg3 ... argn) avalia sequencialmente cada argumento.  
 
 
 
 Os nós internos da árvore consistem em funções, enquanto os nós folha consistem em terminais. As funções devem ter uma contagem de argumentos (comumente referida como aridade) de pelo menos um, permitindo que eles sejam conectados a outras funções ou terminais, fornecendo assim a "cola" para os galhos dentro da árvore. 
 
 Os terminais normalmente incluem coisas como constantes e variáveis. Como os terminais formam as folhas da árvore, eles sempre têm aridade zero. Você deve escolher o conjunto de funções e terminais para o problema que está tentando resolver. Por exemplo, as funções lógicas AND, OR e NOT e os terminais X1 e X2, representando duas variáveis ​​de entrada booleanas, são apropriados se você está tentando descobrir um programa capaz de sintetizar a função booleana XOR. Uma função de aptidão também é necessária, uma vez que você deve fornecer os meios para um programa ser medido em relação a outro, no sentido de que seja melhor para resolver um determinado problema. 
 
 Por exemplo, no caso XOR, podemos testar a adequação de um programa executando o programa uma vez para cada caso de adequaçã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 que produz uma pontuação perfeita de quatro é considerado uma solução para o problema XOR, conforme mostrado na Listagem 1. 
 
 
 
  Uma solução perfeita para o problema XOR descoberto pelo GP: (programa defun () (E (OU X1 X2) (NÃO (E X1 X2)) ) ) 
 
   Listagem 1.  Resultado XOR  
 
 
 
 Próximo:Operadores genéticos 
 
 No próximo artigo, daremos uma olhada nos operadores genéticos que tornam possíveis os algoritmos evolutivos. Também os usaremos em um algoritmo de exemplo mais complexo. 
 
 
 
 Leitura sugerida 
 
 
 Kinnear, Jr., K. E. (ed.).  Avanços na programação genética  . 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.  Programação genética  . 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, maio de 1993. 
 
 Mitchell, Melanie,  Uma introdução aos algoritmos genéticos  , The MIT Press, 1998. 
 
 

            

            

               Avaliando Buzzwords:Transformação Digital        
                Como projetar um controlador lógico difuso