Genetic programming: crossover operators, building blocks and semantic emergence

Os algoritmos evolutivos são métodos heurísticos utilizados para a solução de problemas de otimização e que possuem mecanismos de busca inspirados nos conceitos da Teoria de Evolução das Espécies. Entre os algoritmos evolutivos mais populares, estão os Algoritmos Genéticos (GA) e a Programação Genética (GP). Essas duas técnicas possuem como ponto em comum o uso pesado do operador de recombinação, ou \"crossover\" - mecanismo pelo qual novas soluções são geradas a partir da combinação entre soluções existentes. O que as diferencia é a flexibilidade - enquanto que nos algoritmos genéticos as soluções são representadas por códigos binários, na programação genética essa representação é feita por algoritmos que podem assumir qualquer forma ou extensão. A preferência pelo operador de crossover não é simplesmente uma característica em comum das duas técnicas supracitadas, mas um poderoso diferencial. Na medida em que os indivíduos (as soluções) são selecionados de acordo com a respectiva qualidade, o uso do operador crossover tende a aumentar mais rapidamente a qualidade média da população se as partes boas de cada solução combinada (os \"building blocks\") forem preservadas. Holland [1975] prova matematicamente que sob determinadas condições esse efeito ocorrerá em algoritmos genéticos, em um resultado que ficou conhecido como \"Schema Theorem of GAs\". Entretanto, a implementação prática de GA (e, em especial, de GP) geralmente não ocorre segundo as condições supostas neste teorema. Diversos estudos têm mostrado que a extensão variável das estruturas utilizadas em GP dão um caráter de mutação ao operador de crossover, na medida em que a seleção aleatória dos pontos de combinação pode levar à destruição dos building blocks. Este trabalho propõe um novo operador de crossover, baseado em uma técnica de meta-controle que orienta a seleção dos pontos para a recombinação das soluções, respeitando o histórico de recombinação de cada ponto e a compatibilidade semântica entre as \"partes\" de cada solução que são \"trocadas\" neste processo. O método proposto é comparado ao crossover tradicional em um estudo empírico ligado à área Financeira, no qual o problema apresentado consiste em replicar a carteira de um fundo de investimentos setorial. Os resultados mostram que o método proposto possui performance claramente superior ao crossover tradicional, além de proporcionar a emergência de semântica entre as soluções ótimas.Evolutionary algorithms are heuristic methods used to find solutions to optimization problems. These methods use stochastic search mechanisms inspired by Natural Selection Theory. Genetic Algorithms and Genetic Programming are two of the most popular evolutionary algorithms. These techniques make intensive use of crossover operators, a mechanism responsible for generating new individuals recombining parts of existing solutions. The choice of crossover operator to be used is very important for the algorithms´ performance. If individuals are selected according to the fitness, the use of crossover operator helps to quickly increase the average quality of the population. In GA we also observe the emergence of \"building blocks\", that is, encapsulated parts of good solutions that are often preserved during the recombination process. Holland [1975] proves that, under some conditions, this phenomenon will occur in GAs. This result is known as Schema Theorem of GAs. However, practical implementations of these algorithms may be far away from the conditions stated in Holland´s theorem. In these non-ideal conditions, several factor may contribute to higher rates of destructive crossover (building blocks destruction). This work proposes a new crossover operator, based on a meta-control technique that drives selection of crossover points according to recombination history and semantic compatibility between the code blocks to be switched. The proposed method is compared to common crossover in a case study concerning the replication of an investment fund. Our results show that the proposed method has better performance than the common crossover. Meta-control techniques also facilitate the emergence of building blocks that, in turn, give raise to emergent semantics that can be used to give meaning or interpretations to an optimal solution and its components