Exportar registro bibliográfico

Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes (2009)

  • Authors:
  • Autor USP: SOARES, TELMA WOERLE DE LIMA - ICMC
  • Unidade: ICMC
  • Sigla do Departamento: SSC
  • Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; COMPUTAÇÃO BIOINSPIRADA; ALGORITMOS GENÉTICOS
  • Language: Português
  • Abstract: Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidadecomputacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE ) para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA
  • Imprenta:
  • Data da defesa: 22.05.2009
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SOARES, Telma Woerle de Lima; DELBEM, Alexandre Cláudio Botazzo. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes. 2009.Universidade de São Paulo, São Carlos, 2009. Disponível em: < http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/ >.
    • APA

      Soares, T. W. de L., & Delbem, A. C. B. (2009). Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes. Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/
    • NLM

      Soares TW de L, Delbem ACB. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/
    • Vancouver

      Soares TW de L, Delbem ACB. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/

    Ú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