Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/10986
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorVarejão, Flávio Miguel-
dc.date.accessioned2019-03-28T02:14:52Z-
dc.date.available2019-03-27-
dc.date.available2019-03-28T02:14:52Z-
dc.identifier.urihttp://repositorio.ufes.br/handle/10/10986-
dc.publisherUniversidade Federal do Espírito Santopor
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
dc.subjectProblema da mochila-
dc.subjectMeta-heurísticas-
dc.subjectMultiobjetivopor
dc.subjectIndexação multidimensionalpor
dc.subjectAlgoritmo exatopor
dc.subjectMultiobjective knapsack problemeng
dc.subjectMultidimensional indexingeng
dc.subjectMetaheuristiceng
dc.subjectExact algorithmeng
dc.titleIndexação multidimensional para problemas da mochila multiobjetivo com paretos de alta cardinalidadepor
dc.typedoctorThesiseng
dc.subject.udc004-
dc.subject.br-rjbnAlgoritmospor
dc.subject.br-rjbnIndexaçãopor
dcterms.abstractDiversos 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.por
dcterms.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
dcterms.creatorBaroni, Marcos Daniel Valadão-
dcterms.formatTextpor
dcterms.issued2018-07-31-
dcterms.languageporpor
dc.publisher.countryBRpor
dc.publisher.programPrograma de Pós-Graduação em Informáticapor
dc.publisher.initialsUFESpor
dc.subject.cnpqCiência da Computaçãopor
dc.publisher.courseDoutorado em Ciência da Computaçãopor
dc.contributor.refereeRodrigues, Alexandre Loureiros-
dc.contributor.refereeMartins, Simone de Lima-
dc.contributor.refereeRauber, Thomas Rauber-
dc.contributor.refereeBoeres, Maria Claudia Silva-
Aparece nas coleções:PPGI - Teses de doutorado

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
tese_12952_tese-mbaroni-final.pdf1.61 MBAdobe PDFVisualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons