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. DOI 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 | Size | Format | |
---|---|---|---|---|
EstrategiasBioinspiradasAplicadas.pdf | 3.75 MB | Adobe PDF | ![]() View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.