Genetic programming: crossover operators, building blocks and semantic emergence / Programação genética: operadores de crossover, blocos construtivos e emergência semântica
AUTOR(ES)
Rafael Inhasz
DATA DE PUBLICAÇÃO
2010
RESUMO
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.
ASSUNTO(S)
meta-controle genetic programming algoritmo genético programação genética crossover operador de recombinação building block genetic algorithm meta-control semântica blocos construtivos semantics
Documentos Relacionados
- QUANTUM-INSPIRED LINEAR GENETIC PROGRAMMING
- Genetic Programming Applied to Scheduling Programmable Logic Controllers
- Programação Genética Aplicada à Programação de Controladores Lógico Programáveis
- Programação Genética Aplicada à Programação de Controladores Lógico Programáveis
- Genetic Programming, Neural Network and the Minority Game