Problema da árvore de suporte de custo mínimo com restrições de salto

Abstract

Nesta dissertação é apresentada uma implementação de um algoritmo genético para o problema da Árvore de Suporte de Custo Mínimo com Restrições de Salto. Este é um problema de optimização combinatória NP-Difícil, associado a problemas de desenho de redes de telecomunicações centralizadas. Nestas redes um dispositivo central deve ser ligado a outros dispositivos periféricos, sem exceder um número máximo de ligações intermédias, designado por salto H, de forma a garantir a integridade e qualidade do sinal da ligação. O algoritmo genético implementado considera duas codificações para os cromossomas, a codificação por sequências de Prüfer e a codificação por sequências de arestas. A geração da população consiste em dois métodos, um aleatório e um heurístico que considera a restrição de salto do problema. Os resultados computacionais mostram a performance destes dois métodos de geração da população, assim como a influência de vários parâmetros do algoritmo genético na solução obtida, para as duas codificações em estudo. Os parâmetros considerados são: o número máximo de iterações do algoritmo genético, a dimensão da população, a dimensão de um torneio, o número de torneios, a percentagem de mutação e o número de iterações para renovação da população.

In this thesis we present a genetic algorithm implementation for the Hop-Constrained Minimum Spanning Tree problem (HMST). This is an NP-Hard combinatorial optimization problem, associated with centralized telecommunications network design problems. In these networks a central device must be connected to other devices, without exceeding the maximum number of in-between connections, known as hop H, in order to ensure the signals integrity and quality. The implemented genetic algorithm considers two chromosome codings, the Pr ufer coding and the edge-set coding. Two methods are considered for generating the population, a random and an heuristic method which considers the hop constraints of the problem. The computational results show the performance of the algorithms for these two methods, as well as the in uence of the genetic algorithm parameters in the solutions, considering the two chromosome codings. The studied genetic algorithm parameters are: maximum number of iterations for the genetic algorithm, population dimension, tournament dimension, number of tournaments, mutation percentage and the number of iterations for population renewal.