A Evolucionistas para a Evolução de Sistemas

Dos Estudos Evolucionistas para a Evolução de Sistemas. O Papel dos Operadores Genéticos

A programação genética é uma área relacionada à Inteligência Artificial e à Machine Learning, mas que possui um objetivo geral de fácil entendimento. Este é promover os meios para que os computadores achem sozinhos a solução para problemas propostos, dada uma maneira de se medir a aptdão das soluções. Segundo Banzhaf (1998, p. 4), “Genetic programming, GP for short, aspires to do precisely that – to induce a population of computer programs that improve automatically as they experience the data on which they are trained.”.

É através de um algoritmo genético que essas populações de programas evoluem iterativamente, dando origem à uma nova geração de programas a cada iteração. Langdon (2007, p. 928, grifo do autor) menciona aqueles que são os responsáveis pelas mudanças entre gerações:

“During the process, GP constructs new programs by applying genetic operations which are specialized to act on computer programs.

Algorithmically, GP comprises the steps shown in Algorithm 1. The main genetic operations involved in GP (line 5 of Algorithm 1) are the following:

• Crossover: the creation of one or two offspring programs by recombining randomly chosen parts from two selected programs.

• Mutation: the creation of one new offspring program by randomly altering a randomly chosen part of one selected program.”

É importante lembrar que a forma de representação adotada na maioria dos sistemas de programação genética é a de árvore sintática. Os operadores genéticos, cruzamento e mutação, agirão portanto sobre programas expressados no formato de árvore sintática. Banzhaf (1998, p. 5) diz que: “The focus on tree structures is really a tribute to the immense influence of Koza. In 1992, he wrote a treatise entitled ‘Genetic Programming. On the Programming of Computers by Means of Natural Selection.’ ". Os nós internos da árvore serão os elementos do conjunto de funções dos programas e as folhas serão os elementos do conjunto dos terminais.

Sobre os operadores genéticos, Banzhaf (1998, p. 5) faz a seguinte descrição:

“In GP, the primary transformation operators are ‘crossover’ and ‘mutation’ (see Chapter 5). Mutation works by changing one program; crossover by changing two (or more) programs by combining them in some manner. Both are, to a large extent, controlled by pseudo-random number generators.”

Entre as formas de cruzamento, o mais comum é o cruzamento de sub-árvores, que acontece entre duas sub-árvores, denominados pais. Para realizar a operação escolhe-se aleatoriamente um ponto de cruzamento em cada um dos pais. Esse ponto é uma aresta e a partir dele será feita uma quebra e troca de sub-árvores entre cada pai. O cruzamento não tem uma receita absoluta, e poderá afetar uma ou mais sub-árvores originais. Langdon (2007, p. 934) ilustra um exemplo de cruzamento:

Fonte: LANGDON, W.B et al, 2007, p. 934

Em cada pai um ponto de cruzamento foi escolhido aleatóriamente e o algoritmo deste exemplo simplesmente descartou uma das sub-árvores delimitadas por tal ponto. Alternativamente a este exemplo, a sub-árvore da região acinzentada, ao invés

...