• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2010.tde-14042010-212445
Documento
Autor
Nombre completo
Rafael Inhasz
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2010
Director
Tribunal
Stern, Julio Michael (Presidente)
Lauretto, Marcelo de Souza
Mascarenhas, Walter Figueiredo
Título en portugués
Programação genética: operadores de crossover, blocos construtivos e emergência semântica 
Palabras clave en portugués
algoritmo genético
blocos construtivos
meta-controle
operador de recombinação
programação genética
semântica
Resumen en portugués
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.
Título en inglés
Genetic programming: crossover operators, building blocks and semantic emergence
Palabras clave en inglés
building block
crossover
genetic algorithm
genetic programming
meta-control
semantics
Resumen en inglés
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
dados.zip (76.60 Kbytes)
libraries.zip (13.94 Mbytes)
parameter_files.zip (14.53 Kbytes)
Source_Code.zip (5.71 Mbytes)
Fecha de Publicación
2010-05-19
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.