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

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

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

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