Otimização multiobjetivo e seus desafios no contexto de otimização combinatória: estudos de comportamento e abordagens de solução para problemas com muitos objetivos
Carregando...
Data
2023-08-30
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Diversos problemas presentes na ciência, engenharia, indústria, entre outros domínios do conhecimento, envolvem a otimização simultânea de dois ou mais objetivos frequentemente conflitantes. Problemas com tal característica são conhecidos na literatura como Problemas de Otimização Multiobjetivo (Multiobjective Optimization Problems, MOPs). Devido à existência de um certo nível de conflito entre os objetivos otimizados, para esta classe de problemas, não há uma única solução ótima (global), como ocorre em problemas mono-objetivo. Em vez disso, produzem um conjunto de soluções que representam os possíveis trade-offs entre os objetivos. Geralmente, na otimização multiobjetivo, a relação de dominância Pareto é adotada para comparar soluções. Desta forma, o conjunto de soluções ótimas de um MOPé denominado conjunto Pareto-ótimo, e a sua representação no espaço de objetivos é intitulada fronteira Pareto-ótimo. Ao longo dos últimos anos, estudos experimentais e teóricos têm demonstrado que, geralmente, o aumento no número de objetivos a serem otimizados simultaneamente introduz novos e complexos desafios. Entre eles, destacam-se o crescimento da proporção de soluções não-dominadas, o aumento exponencial do número de soluções necessárias para a obtenção de uma completa aproximação da fronteira Pareto-ótimo, a ineficácia das técnicas tradicionais de visualização das soluções, a dificuldade em garantir a manutenção da diversidade populacional, entre outros. No entanto, é sabido que um MOP não se torna necessariamente mais complexo com a adição de novos objetivos. Outras propriedades intrínsecas do problema também podem contribuir para o aumento de sua complexidade, como por exemplo, as especificidades dos problemas de teste utilizados. Além disso, a literatura científica, até o momento, tem se concentrado majoritariamente em MOPs contínuos, portanto, a otimização combinatória ainda é uma área de pesquisa com questões a serem exploradas. Como objetivo de aprofundar a compreensão dos desafios inerentes a MOPs combinatórios, a primeira parte desta tese apresenta um estudo de caso aplicado a uma formulação com muitos objetivos do problema logístico Dial-a-Ride Problem (DARP). Inicialmente, é realizada uma análise do fitness landscape com o propósito de investigar a geometria da fronteira Pareto obtida para cada conjunto de problemas de teste e identificar possíveis relações entre os objetivos otimizados. Em seguida, é apresentada uma análise comparativa de desempenho considerando diversos Algoritmos Evolutivos Multiobjetivo (Multiobjective Evolutionary Algorithms, MOEAs) provenientes de diferentes classes. Os resultados obtidos mostram que, mesmo utilizando a mesma formulação do problema, diferentes observações podem ser feitas tanto sobre as características do problema quanto sobre o comportamento dos algoritmos, quando diferentes conjuntos de problemas de teste são empregados. Em um segundo momento, desviando do foco principal da maioria das pesquisas atuais, iv que se concentram no desenvolvimento de novos métodos de otimização multiobjetivo e na criação de estratégias de seleção inovadoras, apresentamos uma abordagem que cria e otimiza, de forma independente e simultânea, diversas formulações alternativas do MOP abordado, nas quais são induzidas correlações lineares artificiais entre as funções objetivo. A abordagem proposta adota o paradigma de dividir para conquistar, distribuindo o processo de busca ao alocar um processo evolutivo independente (execução independente do MOEA) tanto para a formulação original do problema quanto para cada formulação com objetivos correlacionados criada. Ao final de cada execução, as soluções obtidas pela otimização de cada formulação são convertidas de volta para o espaço de objetivos original (com base na formulação original do MOP), sendo então combinadas. Todas as soluções não-dominadas resultantes compõem o conjunto de aproximação, que constitui a saída do algoritmo proposto. Ao realizar processos evolutivos independentes utilizando diferentes formulações do problema abordado, espera-se direcionar buscas para diferentes direções do espaço de objetivos, alcançando regiões que seriam difíceis de explorar apenas otimizando a formulação original do problema utilizando algum dos MOEAs do estado da arte. Quando integrada a MOEAs de diferentes classes, a abordagem proposta demonstrou eficácia no aprimoramento do desempenho desses algoritmos ao ser aplicada a um conhecido MOP combinatório. Baseando-se nessa melhoria de desempenho, foram introduzidos dois novos MOEAs, fundamentados na otimização de formulações com objetivos artificialmente correlacionados. Os resultados apresentados demonstraram a superioridade dos MOEAs propostos em comparação com renomados MOEAs da literatura, quando aplicados ao problema da mochila multiobjetivo com 4 a 10 objetivos.
Descrição
Palavras-chave
Otimização matemática, Algoritmos genéticos, Análise numérica, Problema de roteamento de veículos, Problema da mochila (Matemática)