• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2010.tde-14042010-212445
Document
Auteur
Nom complet
Rafael Inhasz
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2010
Directeur
Jury
Stern, Julio Michael (Président)
Lauretto, Marcelo de Souza
Mascarenhas, Walter Figueiredo
Titre en portugais
Programação genética: operadores de crossover, blocos construtivos e emergência semântica 
Mots-clés en portugais
algoritmo genético
blocos construtivos
meta-controle
operador de recombinação
programação genética
semântica
Resumé en portugais
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.
Titre en anglais
Genetic programming: crossover operators, building blocks and semantic emergence
Mots-clés en anglais
building block
crossover
genetic algorithm
genetic programming
meta-control
semantics
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
dados.zip (76.60 Kbytes)
libraries.zip (13.94 Mbytes)
parameter_files.zip (14.53 Kbytes)
Source_Code.zip (5.71 Mbytes)
Date de Publication
2010-05-19
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.