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:
- Publisher place: São Carlos
- Date published: 2009
- Data da defesa: 22.05.2009
-
ABNT
SOARES, Telma Woerle de Lima. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes. 2009. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/. Acesso em: 21 maio 2024. -
APA
Soares, T. W. de L. (2009). Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes (Tese (Doutorado). 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. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes [Internet]. 2009 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/ -
Vancouver
Soares TW de L. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes [Internet]. 2009 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28052009-163303/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
