Indexação Multidimensional para Problemas da Mochila Multiobjetivo com Paretos de Alta Cardinalidade

"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.