Please use this identifier to cite or link to this item: http://repositorio.ufersa.edu.br/handle/prefix/859
metadata.dc.type: Dissertação
Title: Uma abordagem via metaheurística híbrida para o problema de atribuição de localidade a anéis sonet/sdh
metadata.dc.creator: Pereira, Jeferson Queiroga
metadata.dc.contributor.advisor1: Aloise, Dario José
metadata.dc.contributor.referee1: Pinheiro, Plácido Rogério
metadata.dc.contributor.referee2: Fontes, Francisco Fábio da Costa
metadata.dc.contributor.referee3: Liberalino, Carlos Heitor Pereira
metadata.dc.description.resumo: Os sistemas de telecomunicações estão na fase de grandes transformações e expansões, que tornam os problemas de planejamento de redes de telecomunicações cada vez maiores e mais complexos. Com isso, muitos desses problemas podem ser formulados como modelos de otimização combinatória, e o uso de algoritmos heurísticos podem ajudar a solucionar essas questões da fase de planejamento. Este trabalho propõe uma implementação da metaheurística BRKGA ( Biased Random-Key Genetic Algorithm) – além de duas implementações híbridas – BRKGA com Vocabulary Building (BRKGA+VB) e BRKGA com Q-learning (BRKGA+QL) – para o Problema de Atribuição de Localidades a Anéis SONET/SDH (ou abreviadamente, PALAS). Neste problema, cada localidade cliente deve ser atribuída a exatamente um anel SONET, também denominado de anel local e um anel especial, chamado de Anel Federal, que interligam os anéis locais entre si. É imposta sobre cada anel uma restrição de capacidade. O objetivo do problema é encontrar uma atribuição de localidades clientes que minimize o número total de anéis utilizados, pois quanto menos anéis, menor o custo total da rede. Esse problema é NP-difícil e, portanto, não se pode garantir a obtenção dos melhores resultados para todas instâncias utilizando os métodos exatos, em um tempo computacional viável, dessa forma, é proposto para solução desse problema, a utilização dos métodos heurísticos. Os algoritmos foram implementados na linguagem de programação JAVA e utilizaram as instâncias das classes C1, C2, C3 e C4 para realizações dos experimentos computacionais. A análise dos experimentos mostrou a competitividade dos algoritmos propostos frente aos melhores resultados encontrados na literatura
Abstract: The Telecommunication systems are in the phase of major transformations and expansions, which make telecommunication network planning problems increasingly larger and complex. In this context, many of these problems can be formulated as combinatorial optimization models, and the use of heuristic algorithms can help solve these issues in the planning phase. This paper proposes an implementation of the BRKGA (Biased Random-Key Genetic Algorithm) metaheuristic - in addition to two hybrid implementations - BRKGA with Vocabulary Building (BRKGA + VB) and BRKGA with Q-learning (BRKGA + QL) - to be applied to problem SONET Ring Assignment Problem – SRAP. In this problem, each customer location must be assigned to exactly one SONET ring, also called the local ring and a special ring, called the Federal Ring, which interconnect the local rings with each other. A capacity constraint is imposed on each ring. The solution looking for the problem is to find an allocation of customer locations that minimize the total number of rings used, since the fewer rings the lower the cost of the telecommunication network planning. This problem is the class NP-hard, so it can not be guaranteed to obtain the best results for all instances using the exact algorithms, with a viable computational time. It is proposed to solve this problem with the heuristic methods mentioned above. The algorithms were implemented in the JAVA programming language and used the instances of classes C1, C2, C3 and C4 to perform computational experiments. The analysis of the experiments showed the competitiveness of the proposed algorithms against the best results found in the literature
Keywords: Projeto de Redes
BRKGA
PALAS
Vocabulary building
Q-learning
Network design
BRKGA
PALAS
Vocabulary building
Q-learning
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
metadata.dc.publisher.initials: UFERSA
metadata.dc.publisher.department: Departamento de Ciências Exatas, Tecnológicas e Humanas
metadata.dc.publisher.program: Programa de Pós-Graduação em Ciência da Computação
Citation: Citação com autor incluído no texto: Pereira (2018) Citação com autor não incluído no texto: (PEREIRA, 2018)
metadata.dc.rights: Acesso Aberto
URI: http://repositorio.ufersa.edu.br/handle/prefix/859
Issue Date: 19-Apr-2018
Appears in Collections:MESTRADO EM CIÊNCIA DA COMPUTAÇÃO

Files in This Item:
File Description SizeFormat 
JefersonQP_DISSERT.pdf17 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.