Algoritmo evolutivo paralelo para o problema de atribuição de localidades a anéis em redes sonet/sdh

The telecommunications play a fundamental role in the contemporary society, having as one of its main roles to give people the possibility to connect them and integrate them into society in which they operate and, therewith, accelerate development through knowledge. But as new technologies are introduced on the market, increases the demand for new products and services that depend on the infrastructure offered, making the problems of planning of telecommunication networks become increasingly large and complex. Many of these problems, however, 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 the development of a Parallel Evolutionary Algorithm to be applied to telecommunications problem known in the literature as SONET Ring Assignment Problem SRAP. This problem is the class NP-hard and arises during the physical planning of a telecommunication network and consists of determining the connections between locations (customers), satisfying a series of constrains of the lowest possible cost. Experimental results illustrate the effectiveness of the Evolutionary Algorithm parallel, over other methods, to obtain solutions that are either optimal or very close to it

As telecomunicações desempenham um papel fundamental na sociedade contemporânea, tendo como um de seus principais papéis o de conceder às pessoas a possibilidade de conectá-las e integrá-las à sociedade em que vivem e com isso acelerar o desenvolvimento por meio do conhecimento. Mas, à medida que novas tecnologias são introduzidas no mercado, cresce também a demanda por novos produtos e serviços que dependem da infraestrutura oferecida, tornando os problemas de planejamento de redes de telecomunicações cada vez maiores e mais complexos. Muitos desses problemas, no entanto, 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 o desenvolvimento de um Algoritmo Evolutivo paralelo a ser aplicado ao problema de telecomunicações conhecido na literatura por Problema de Atribuição de Localidades a Anéis em Redes SONET/SDH ou PALAS. Esse problema é da classe NP-difícil e surge durante a etapa do planejamento físico da rede e consiste na determinação das conexões entre localidades (clientes), de modo a satisfazer uma série de restrições ao menor custo possível. Os resultados dos experimentos ilustram a eficiência do Algoritmo Evolutivo paralelo, sobre outros métodos, em obter soluções ótimas ou muito próximas do valor ótimo