Exportar registro bibliográfico

Programação genética: operadores de crossover, blocos construtivos e emergência semântica (2010)

  • Authors:
  • Autor USP: INHASZ, RAFAEL - IME
  • Unidade: IME
  • Sigla do Departamento: MAE
  • Subjects: COMBINATÓRIA; ALGORITMOS GENÉTICOS
  • Language: Português
  • Abstract: 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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      INHASZ, Rafael; STERN, Julio Michael. Programação genética: operadores de crossover, blocos construtivos e emergência semântica. 2010.Universidade de São Paulo, São Paulo, 2010. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/ >.
    • APA

      Inhasz, R., & Stern, J. M. (2010). Programação genética: operadores de crossover, blocos construtivos e emergência semântica. 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, Stern JM. Programação genética: operadores de crossover, blocos construtivos e emergência semântica [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/
    • Vancouver

      Inhasz R, Stern JM. Programação genética: operadores de crossover, blocos construtivos e emergência semântica [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45133/tde-14042010-212445/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021