Doutorado em Ciência da Computação
URI Permanente para esta coleção
Nível: Doutorado
Ano de início:
Conceito atual na CAPES:
Ato normativo:
Periodicidade de seleção:
Área(s) de concentração:
Url do curso:
Navegar
Navegando Doutorado em Ciência da Computação por Assunto "Algoritmo exato"
Agora exibindo 1 - 1 de 1
Resultados por página
Opções de Ordenação
- ItemIndexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidade(Universidade Federal do Espírito Santo, 2018-07-31) Baroni, Marcos Daniel Valadão; Varejão, Flávio Miguel; Rodrigues, Alexandre Loureiros; Martins, Simone de Lima; Rauber, Thomas Rauber; Boeres, Maria Claudia SilvaSeveral 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.