Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/9661
Title: Problema da árvore de suporte de custo mínimo com restrições de salto
Author: Correia, Pedro Miguel Henriques
Advisor: Agra, Maria Cristina Saraiva Requejo
Keywords: Matemática
Algoritmos genéticos
Optimização combinatória
Árvores (Teoria de grafos)
Defense Date: 2010
Publisher: Universidade de Aveiro
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.
Description: Mestrado em Matemática e Aplicações
URI: http://hdl.handle.net/10773/9661
Appears in Collections:DMat - Dissertações de mestrado
UA - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
dissertacao.pdf1.63 MBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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