| dc.description.abstract | "Diversos 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 a performance 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 k-d como estrutura de indexação multidimensional para auxiliar a
manipulação das soluções. A performance 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." | |
