Indexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidade
Nenhuma Miniatura disponível
Arquivos
Data
2018-07-31
Autores
Baroni, Marcos Daniel Valadão
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal do Espírito Santo
Resumo
Several real problems involve the simultaneous optimization of multiple criteria, which are generally conflicting with each other. These problems are called multiobjective and do not have a single solution, but a set of solutions of interest, called efficient solutions or non-dominated solutions. One of the great challenges to be faced in solving this type of problem is the size of the solution set, which tends to grow rapidly given the size of the instance, degrading algorithms performance. Among the most studied multiobjective problems is the multiobjective knapsack problem, by which several real problems can be modeled. This work proposes the acceleration of the resolution process of the multiobjective knapsack problem, through the use of a k-d tree as a multidimensional index structure to assist the manipulation of solutions. The performance of the approach is analyzed through computational experiments, performed in the exact context using a state-of-the-art algorithm. Tests are also performed in the heuristic context, using the adaptation of a metaheuristic for the problem in question, being also a contribution of the present work. According to the results, the proposal was effective for the exact context, presenting a speedup up to 2.3 for bi-objective cases and 15.5 for 3-objective cases, but not effective in the heuristic context, presenting little impact on computational time. In all cases, however, there was a considerable reduction in the number of solutions evaluations.
Descrição
Palavras-chave
Multiobjective knapsack problem , Multidimensional indexing , Metaheuristic , Exact algorithm , Problema da mochila , Meta-heurísticas , Multiobjetivo , Indexação multidimensional , Algoritmo exato
Citação
BARONI, Marcos Daniel Valadão. Indexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidade. 2018. 81 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2018.