Estratégias de solução baseadas em paralelismo CUDA para o problema de instalação de fibras em redes óticas
Carregando...
Data
2023-08-18
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Este trabalho otimiza métodos sequenciais e propõe métodos heurísticos paralelizados em GPUs Nvidia CUDA para a solucionar o Problema de Instalação de Fibras em Redes Óticas - PIFRO. O PIFRO consiste em alocar, em uma rede ótica que utiliza tecnologia Wavelength Division Multiplexing (WDM), um conjunto de requisições previamente conhecidas com múltiplas origens e destinos. O objetivo é minimizar o custo total dos dispositivos necessários para a operação da rede. Após provar que a versão de decisão do PIFRO é NP-Difícil, é realizada uma formulação matemática e implementadas duas metaheurísticas paralelizadas em formatos inéditos, buscando a melhoria dos resultados da literatura. Uma das heurísticas é baseada em Biased Random Key Genetic Algorithm (BRKGA) e a outra é baseada em Iterated Local Search (ILS) as quais foram selecionadas pelos bons resultados existentes para o problema. Os conceitos básicos de processamento paralelo são analisados e selecionados para execução de novas metaheurísticas em ambientes heterogêneos com GPUs
Descrição
Palavras-chave
Programação heurística, Algoritmos genéticos, Otimização, Fibra ótica