Indexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidade

Página do item simplificado
dc.contributor.advisor1Varejão, Flávio Miguel
dc.contributor.authorBaroni, Marcos Daniel Valadão
dc.contributor.referee1Rodrigues, Alexandre Loureiros
dc.contributor.referee2Martins, Simone de Lima
dc.contributor.referee3Rauber, Thomas Rauber
dc.contributor.referee4Boeres, Maria Claudia Silva
dc.date.accessioned2019-03-28T02:14:52Z
dc.date.available2019-03-27
dc.date.available2019-03-28T02:14:52Z
dc.date.issued2018-07-31
dc.description.abstractSeveral 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.eng
dc.description.resumoDiversos problemas reais envolvem a otimização simultânea de múltiplos critérios, os quais são, geralmente, conflitantes entre si. Estes problemas são denominados multiobjetivo e não possuem uma única solução, mas um conjunto de soluções de interesse, denominadas soluções eficientes ou não dominadas. Um dos grande desafios a serem enfrentados na resolução deste tipo de problema é o tamanho do conjunto solução, que tende a crescer rapidamente dado o tamanho da instância, degradando o desempenho dos algoritmos. Dentre os problemas multiobjetivos mais estudados está o problema da mochila multiobjetivo, pelo qual diversos problemas reais podem ser modelados. Este trabalho propõe a aceleração do processo de solução do problema da mochila multiobjetivo, através da utilizando da árvore 𝑘-d como estrutura de indexação multidimensional para auxiliar a manipulação das soluções. O desempenho da abordagem é analisada através de experimentos computacionais, realizados no contexto exato utilizando um algoritmo estado da arte. Testes também são realizados no contexto heurístico, utilizando a adaptação de uma meta-heurística para o problema em questão, sendo esta também uma contribuição do presente trabalho. Segundo os resultados, para o contexto exato a proposta foi eficaz, apresentam speedup de até 2.3 para casos bi-objetivo e 15.5 em casos 3-objetivo, não sendo porém eficaz no contexto heurístico, apresentando pouco impacto no tempo computacional. Em todos os casos, porém, houve considerável redução no número de avaliações de soluções.
dc.formatText
dc.identifier.citationBARONI, 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.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/10986
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseDoutorado em Ciência da Computação
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectMultiobjective knapsack problemeng
dc.subjectMultidimensional indexingeng
dc.subjectMetaheuristiceng
dc.subjectExact algorithmeng
dc.subjectProblema da mochilapor
dc.subjectMeta-heurísticaspor
dc.subjectMultiobjetivopor
dc.subjectIndexação multidimensionalpor
dc.subjectAlgoritmo exatopor
dc.subject.br-rjbnAlgoritmos
dc.subject.br-rjbnIndexação
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleIndexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidade
dc.typedoctoralThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Tese-mbaroni-final.pdf
Tamanho:
1.58 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Doutorado em Ciência da Computação