Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/24921
Document type: Dissertação
Access type: Acesso Aberto
Title: Estratégias bio-inspiradas aplicadas em problemas discretos com muitos objetivos
Alternate title (s): Bio-inspired strategies applied to many-objective discrete problems
Author: França, Tiago Peres
First Advisor: Oliveira, Gina Maira Barbosa de
First coorientator: Martins, Luiz Gustavo Almeida
First member of the Committee: Delgado, Myriam Regattieri De Biase da Silva
Second member of the Committee: Gabriel, Paulo Henrique Ribeiro
Summary: Problemas de otimização multiobjetivo são muito comuns no nosso dia-a-dia e surgem em diversas áreas do conhecimento. Neste trabalho, exploram-se e comparam-se várias estratégias de otimização multiobjetivo em dois problemas discretos bem conhecidos na computação: o problema da mochila e o problema do roteamento multicast. Dentre as estratégias para solucionar problemas multiobjetivos discretos, destacam-se os algoritmos genéticos (AGs) e os algoritmos baseados em colônias de formigas (ACOs). Ambas as abordagens são investigadas neste trabalho por meio de experimentos que avaliaram o desempenho de 10 algoritmos diferentes. Todos os algoritmos avaliados foram adaptados para os problemas propostos e, além disso, desenvolveu-se um novo algoritmo denominado Many-objective Ant Colony Optimization based on Non-Dominated Sets (MACO/NDS), o qual foi avaliado e comparado com todos os outros métodos aqui investigados, considerando-se diferentes métricas de desempenho. A partir dos resultados experimentais, foi possível comprovar a eficiência e eficácia do método proposto. Em diversos cenários, ele foi capaz de encontrar conjuntos de soluções superiores aos produzidos pelos demais algoritmos e levou menos tempo para executar.
Abstract: Multi-objective optimization problems are very common in the day-to-day life and come up in many fields of knowledge. In this work, several strategies for multi-objective optimization have been explored and compared on two well known discrete problems in computer science: the knapsack problem and the multicast routing problem. Among all strategies to solve multi-objective discrete problems, genetic algorithms (GAs) and ant colony optimization (ACO) are the ones which generally provide the best results. In this work both approaches are explored through several experiments involving 10 different algorithms. All of the algorithms evaluated were adapted to the proposed problems. Furthermore, a new algorithm has been proposed, the Many-objective Ant Colony Optimization based on Non-Dominated Sets (MACO/NDS), which has been evaluated and compared against all other methods investigated here, considering different performance metrics. In many scenarios, it has been capable of finding superior sets of solutions and took less time to execute.
Keywords: Algoritmos many-objectives
Algoritmos genéticos
Otimização por colônia de formigas
Problema do roteamento multicast
Problema da mochila multiobjetivo
Computação
Roteamento (Administração de redes de computadores)
Problema da mochila (Matemática)
Many-objective algorithms
Genetic algorithms
Ant colony optimization
Multicast routing problem
Multi-objective knapsack problem
Computação
Roteamento (Administração de redes de computadores)
Problema da mochila (Matemática)
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: FRANÇA, Tiago Peres. Estratégias bio-inspiradas aplicadas em problemas discretos com muitos objetivos. 2018. 165 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2019. Disponível em: http://dx.doi.org/10.14393/ufu.di.2019.368
Document identifier: http://dx.doi.org/10.14393/ufu.di.2019.368
URI: https://repositorio.ufu.br/handle/123456789/24921
Date of defense: 15-Jun-2018
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
EstrategiasBioinspiradasAplicadas.pdf3.75 MBAdobe PDFThumbnail
View/Open


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