Programação genética: operadores de crossover, blocos construtivos e emergência semântica (2010)
- Autores:
- Autor USP: INHASZ, RAFAEL - IME
- Unidade: IME
- Sigla do Departamento: MAE
- Assuntos: COMBINATÓRIA; ALGORITMOS GENÉTICOS
- Idioma: Português
- Resumo: 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.
- Imprenta:
- Data da defesa: 19.03.2010
-
ABNT
INHASZ, Rafael. Programação genética: operadores de crossover, blocos construtivos e emergência semântica. 2010. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2010. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/. Acesso em: 19 abr. 2024. -
APA
Inhasz, R. (2010). Programação genética: operadores de crossover, blocos construtivos e emergência semântica (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/ -
NLM
Inhasz R. Programação genética: operadores de crossover, blocos construtivos e emergência semântica [Internet]. 2010 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/ -
Vancouver
Inhasz R. Programação genética: operadores de crossover, blocos construtivos e emergência semântica [Internet]. 2010 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
