Indexação Multidimensional para Problemas da Mochila Multiobjetivo com Paretos de Alta Cardinalidade
Autor: | BARONI, M. D. V. |
---|---|
Přispěvatelé: | RODRIGUES, A. L., MARTINS, S. L., Rauber, T. W., BOERES, M. C. S., Varejão, F. M. |
Rok vydání: | 2018 |
Zdroj: | Repositório Institucional da Universidade Federal do Espírito Santo (riUfes) Universidade Federal do Espírito Santo (UFES) instacron:UFES |
Popis: | Made available in DSpace on 2019-03-28T02:14:52Z (GMT). No. of bitstreams: 1 tese_12952_tese-mbaroni-final.pdf: 1653494 bytes, checksum: ff17d8c5279059531c2c03a07d311b25 (MD5) Previous issue date: 2018-07-31 "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." |
Databáze: | OpenAIRE |
Externí odkaz: |