Evolução de funções em programação genética orientada a gramáticas

Abstract

Resumo: Um dos grandes desafios da Inteligência Artificial tem sido permitir que os computadores possam resolver problemas sem serem explicitamente programados para tal. Tal desafio implica em um sistema que recebe uma descrição em alto nível de um determinado problema e produz como resposta um programa capaz de resolvê-lo de forma satisfatória. Neste sentido, a Programação Genética é um método de indução de programas usando, por analogia, os princípios da evolução natural. Durante o processo de evolução, mantém-se uma população de programas que são continuamente alterados. A qualidade de cada programa é avaliada através de uma função de aptidão (fitness) que representa o quanto o programa aprendeu a resolver determinado problema. Através da recombinação ou alteração de determinados programas, evolui-se até que a solução seja encontrada ou algum critério de término seja satisfeito. Tradicionalmente, a formação dos programas é feita através de árvores de sintaxe abstrata, notadamente expressões em LISP. Porém, dependendo do domínio do problema ou da linguagem alvo desejada, algumas restrições devem ser satisfeitas, como por exemplo: formato da solução, tipificação correta dos dados, dentre outras. Neste trabalho explora-se o uso de gramáticas em Programação Genética como forma de impor restrições sintáticas na formação de programas, orientando a geração de programas e aplicação correta dos operadores genéticos, a fim de produzir programas válidos no domínio desejado. O uso de evolução de funções também é abordado através da apresentação de diversos métodos atualmente usados (MA, ARL, ADM e ADF). Dentre eles, ADF tem apresentado resultados promissores em problemas cuja complexidade varia em função da escalabilidade, tais como paridade par. Desta forma, ADF foi o método escolhido neste trabalho para verificar se, com o uso de gramáticas, os resultados são semelhantes. Diferentes aspectos do uso de gramáticas em Programação Genética são discutidos ao longo deste trabalho. Entre eles destacam-se mudança na representação dos programas, alterações na forma de criação da população inicial e restrições na atuação dos operadores genéticos. A comprovação da eficiência desta abordagem é feita através do uso de uma ferramenta, Chameleon, desenvolvida em C++ e apresentada em detalhes neste trabalho. Chameleon representa uma ferramenta útil de Programação Genética, fácil de usar e adaptável praticamente a qualquer problema que possa ser descrito por uma gramática. Isto é feito sem necessidade de mudanças em seu código fonte, portanto não exigindo do usuário conhecimentos sobre a linguagem em que a ferramenta foi desenvolvida. Os parâmetros são definidos em um único arquivo texto de fácil compreensão, apesar de Chameleon permitir que sejam modificados durante a execução sem o comprometimento de sua funcionalidade. Além disso, permite a gravação e recuperação de populações durante o processo evolutivo, permitindo o uso de checkpoints. A eficiência da abordagem é comparada com os resultados apresentados por John Koza no problema de paridade par (even parity). Pelos resultados obtidos até agora, o uso de gramáticas apresenta performance equivalente e diversas vantagens como: independência de domínio, uso de qualquer linguagem alvo para solução e facilidade em se impor o formato da solução.

Abstract: One of the great challenges of Artificial Intelligence is to get a computer to solve a problem without explicitly programming it. This challenge envisions an automatic system whose input is a high level statement of a problem's requirements and whose output is a satisfactory solution to the given problem. The Genetic Programming method is an approach to inductively forming programs. The use of natural selection based on a fitness function for reproduction of the program population has allowed many problems to be solved. Traditionally, the programs are represented by an abstract syntax tree, usually LISP S-expressions. However, depending on the problem or the desired language, some restrictions must be satisfied, to ensure legal programs are always created. In this work, we explore the use of grammars in Genetic Programming to define the structure of the initial population and to direct crossover and mutation operators to produce only valid programs in the desired domain. The evolution of functions is also presented. Different methods proposed by various researches (MA, ARL, ADM and ADF) are described. Among them, ADF is advantageous for the scaled-up versions of the even-parity problem. In this way, we study how well the combination of grammars and ADF solves a even-parity problem. We detail how to modify the Genetic Programming components to accommodate a grammar, focusing the program representation, the initialization procedure and genetic operators constraints. A Grammar-Guided Genetic Programming system called Chameleon are presented. The system was written in C++ and its implementation details are discussed. Chameleon is a valuable tool to work with the Genetic Programming and grammars. The parameters are defined in a simple text file, although Chameleon allows parameter changes during the run, without lost of functionality. Furthermore, a population can be saved or loaded during the evolution process, allowing the use of checkpoints. The efficiency of the grammar approach is compared with the results obtained by John Koza in the even parity problem. We observed that the use of grammars does not improve the convergence, but it has many advantages such as: domain independence, easiness to impose the format of the solution, among others.