Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/handle/123456789/14914
Title: Busca heurística através de algoritmo genético e memético com construção de vocábulos para o problema de atribuição de localidades a anéis Sonet
Authors: Silva, Ana Cristina Girao e
Keywords: Problema de atribuição de localidades a anéis SONET;Algoritmo genético, Algoritmo memético e vocabulary Building;SONET ring assignment problem;Genetic algorithm;Memetic algorithm;Vocabulary building
Issue Date: 23-Dec-2008
Publisher: Universidade Federal do Rio Grande do Norte
Citation: SILVA, Ana Cristina Girao e. Busca heurística através de algoritmo genético e memético com construção de vocábulos para o problema de atribuição de localidades a anéis Sonet. 2008. 75 f. Dissertação (Mestrado em Estratégia; Qualidade; Gestão Ambiental; Gestão da Produção e Operações) - Universidade Federal do Rio Grande do Norte, Natal, 2008.
Portuguese Abstract: As telecomunicações desempenham um papel fundamental na sociedade contemporânea. Mas à medida que novas tecnologias são introduzidas ao mercado, cresce também a demanda por novos produtos e serviços que dependem da infra-estrutura oferecida, tornando os problemas de planejamento de redes de telecomunicações, apesar da evolução tecnológica, cada vez maiores e complexos. No entanto, 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. Neste trabalho, foram desenvolvidas duas implementações metaheurísticas puras Algoritmo Genético (AG) e Algoritmo Memético (AM) além de uma terceira implementação híbrida Algoritmo Memético com Vocabulary Building (AM+VB) para um problema de telecomunicações que é conhecido na literatura por Problema de Atribuição de Localidades a Anéis SONET ou SRAP (do inglês, SONET Ring Assignment Problem). O SRAP surge durante a etapa do planejamento fésico da rede e consiste na determinação das conexões entre um conjunto de localidades (clientes), de modo a satisfazer uma série de restrições ao menor custo possível. Esse problema é NP-difícil e portanto algoritmos exatos eficientes (de complexidade polinomial) não são conhecidos, podendo, inclusive, nem existir
Abstract: Telecommunications play a key role in contemporary society. However, as new technologies are put into the market, it also grows the demanding for new products and services that depend on the offered infrastructure, making the problems of planning telecommunications networks, despite the advances in technology, increasingly larger and complex. However, many of these problems can be formulated as models of combinatorial optimization, and the use of heuristic algorithms can help solving these issues in the planning phase. In this project it was developed two pure metaheuristic implementations Genetic algorithm (GA) and Memetic Algorithm (MA) plus a third hybrid implementation Memetic Algorithm with Vocabulary Building (MA+VB) for a problem in telecommunications that is known in the literature as Problem SONET Ring Assignment Problem or SRAP. The SRAP arises during the planning stage of the physical network and it consists in the selection of connections between a number of locations (customers) in order to meet a series of restrictions on the lowest possible cost. This problem is NP-hard, so efficient exact algorithms (in polynomial complexity ) are not known and may, indeed, even exist
URI: https://repositorio.ufrn.br/jspui/handle/123456789/14914
Appears in Collections:PPGEP - Mestrado em Engenharia de Produção

Files in This Item:
File Description SizeFormat 
AnaCGS.pdf4.09 MBAdobe PDFThumbnail
View/Open


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