Uma abordagem evolucionária para o projeto de redes eixo-raio com alocação simples
AUTOR(ES)
Bruno Nonato Gomes
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
16/09/2011
RESUMO
O projeto de redes eixo-raio com alocação simples é foco desta dissertação. Esse é um problema muito importante na área de otimização discreta, possuindo diversas aplicações em diferentes contextos, tais como sistemas de telecomunicação e informação, redes de transporte de carga e passageiros, entre outras. Para resolução desse problema, propõe-se três abordagens evolucionárias diferentes: algoritmo genético (AG), nomeado GGA; GGA com busca local; e GGA com descida em vizinhança variável (VND). O GGA possui uma fase de construção muito eficiente, a qual provê indivíduos de alta qualidade para a população inicial, e os operadores desenvolvidos, especificamente para o problema, são capazes de melhorar as soluções durante o processo evolucionário. Tendo em vista que os indivíduos promissores da população não passavam por um procedimento de refinamento de soluções, é proposta a implementação de 4 buscas locais para o problema. Porém, cada uma das buscas locais propostas explora uma determinada solução somente em uma vizinhança específica, assim, propõe-se também uma técnica, conhecida como VND, que explora o espaço de soluções através de trocas sistemáticas de estruturas de vizinhança. Dessa forma, as diferentes buscas locais propostas podem ser exploradas em uma solução. Para avaliação de desempenho dos métodos propostos são realizados experimentos computacionais utilizando a base de dados do serviço postal australiano (AP). Inicialmente, o GGA proposto é comparado com três outros AGs considerados estado da arte na literatura. Os resultados mostram que o GGA claramente supera os outros AGs estudados, tanto em qualidade das soluções, quanto em tempo para obtenção de uma solução alvo. Posteriormente, o GGA é comparado com o GGA combinado com as buscas locais. Percebe-se que, a combinação do AG com as buscas locais propostas proporcionam melhores soluções que o GGA sozinho, e requisita menor tempo de processamento para obtenção de uma solução alvo. Os melhores resultados apresentados são proporcionados pelo GGA com o VND, o qual superou o GGA com a busca local de re-alocação em todas as métricas avaliadas, e é mais rápido para obtenção de uma solução alvo. Além disso, o GGA-VND também é mais eficiente para encontrar a solução ótima das instâncias teste.
ASSUNTO(S)
ACESSO AO ARTIGO
http://hdl.handle.net/1843/BUOS-8SRHX9Documentos Relacionados
- Sistemas eixo-raio de alocação simples: modelos e algoritmos
- Sistemas eixo-raio de múltipla atribuição:: modelos e algoritmos
- Uma abordagem híbrida para alocação de profissionais em projeto de tecnologia da informação
- Uma Abordagem Hìbrida GRASP-ILS para o Problema de Projeto de Redes com Topologia Anel-Estrela
- Uma abordagem distribuída para o problema de roteamento e alocação de comprimentos de ondas em redes WDM