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

Nome: Marcos Daniel Valadão Baroni
Tipo: Tese de doutorado
Data de publicação: 31/07/2018
Orientador:

Nomeordem decrescente Papel
Flávio Miguel Varejão Orientador

Banca:

Nomeordem decrescente Papel
ALEXANDRE LOUREIROS RODRIGUES Examinador Externo
Flávio Miguel Varejão Orientador
Maria Claudia Silva Boeres Examinador Interno
Simone de Lima Martins Examinador Externo
Thomas Walter Rauber Examinador Interno

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

Acesso ao documento

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910