Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas


Autoria(s): Pinheiro, Lucas Daniel Monteiro dos Santos
Contribuinte(s)

Gouvea, Elizabeth Ferreira

06538970494

http://lattes.cnpq.br/2366752353326968

81652011749

http://lattes.cnpq.br/2888641121265608

Maia, Silvia Maria Diniz Monteiro

01397968435

http://lattes.cnpq.br/1498104590221901

Goldbarg, Marco Cesar

25841025953

http://lattes.cnpq.br/1371199678541174

Gonçalves, Richard Aderbal

28850139829

http://lattes.cnpq.br/4210531173050798

Data(s)

26/07/2016

26/07/2016

03/02/2016

Resumo

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

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

O problema da Árvore Geradora Mínima Quadrática (AGMQ) é uma generalização doproblema da Árvore Geradora Mínima onde, além dos custos lineares das arestas, custosquadráticos associados a cada par de arestas são considerados. Os custos quadráticos sãodevidos à custos de interação entre as arestas. No caso das interações ocorrerem somenteentre arestas adjacentes, o problema é denominado Árvore Geradora Mínima Quadráticaem Adjacência de Arestas (AGMQA). Tanto a AGMQ quanto a AGMQA são NP-difíceise modelam diversos problemas reais envolvendo projeto de redes de infraestrutura. Oscustos lineares e quadráticos são somados nas versões mono-objetivo destes problemas.Frequentemente, aplicações reais lidam com objetivos conflitantes. Nestes casos a consideração dos custos lineares e quadráticos separadamente é mais adequada e a otimizaçãomultiobjetivo provê modelos mais realistas. Algoritmos exatos e heurísticos são investigados neste trabalho para a versão biobjetivo da AGMQA. As seguintes técnicas sãopropostas: backtracking, branch-and-bound, busca local, Greedy RandomizedAdaptive Search Procedure, Simulated Annealing, NSGAII, Algoritmo Transgenético, Otimização por Nuvem de Partículas e uma hibridização entre a técnica do MOEA-D eo Algoritmo Transgenético. São utilizados indicadores de qualidade Pareto concordantespara comparar os algoritmos em um conjunto de instâncias de bases de dado da literatura.

Identificador

PINHEIRO, Lucas Daniel Monteiro dos Santos. Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas. 2016. 90f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2016.

http://repositorio.ufrn.br/handle/123456789/21031

Idioma(s)

por

Publicador

Universidade Federal do Rio Grande do Norte

Brasil

UFRN

PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO

Direitos

Acesso Aberto

Palavras-Chave #Algoritmos experimentais #Algoritmos exatos #Metaheurísticas #Otimização multiobjetivo #Árvore geradora quadrática em adjacência de arestas biobjetivo #CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Tipo

masterThesis