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

Página do item simplificado
dc.contributor.advisorMartins, Flávio Vinícius Cruzeiro
dc.contributor.advisor-coWanner, Elizabeth Fialho
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/2243256075052322
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3199420233273400
dc.contributor.authorViana, Renan José dos Santos
dc.contributor.authorLatteshttp://lattes.cnpq.br/2637804041805899
dc.contributor.refereeMartins, Flávio Vinícius Cruzeiro
dc.contributor.refereeWanner, Elizabeth Fialho
dc.contributor.refereeTakahashi, Ricardo Hiroshi Caldeira
dc.contributor.refereeLopes, Cláudio Lúcio do Val
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.date.accessioned2026-11-10T20:19:46Z
dc.date.available2026-11-10T20:19:46Z
dc.date.issued2023-08-30
dc.description.abstractDiversos 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.
dc.description.abstractotherMany problems present in science, engineering, industry, among other fields of knowledge, involve the simultaneous optimization of two or more often conflicting objectives. Problems with such characteristic are known in the literature as Multiobjective Optimization Problems (MOPs). Due to the existence of a certain level of conflict between the optimized objectives, for this class of problems, there is no single optimal solution (global), as occurs in single objective problems. Instead, they produce a set of solutions that represent the possible trade-offs between objectives. Generally, in multiobjective optimization, the Pareto dominance relation is adopted to compare solutions. Therefore, the set of optimal solutions of an MOP is called the Pareto-optimal set, and its representation in the objective space is referred to as the Pareto-optimal front. Over the past few years, experimental and theoretical studies have shown that increasing the number of objectives to be simultaneously optimized generally introduces new and complex challenges. Among these challenges are the growth in the proportion of non dominated solutions, the exponential increase in the number of solutions required to achieve a complete approximation of the Pareto-optimal front, the ineffectiveness of traditional solutions visualization techniques, the difficulty of ensuring population diversity maintenance, among others. However, it is known that a MOP does not necessarily become more complex with the addition of new objectives. Other intrinsic properties of the problem may also contribute to its complexity, such as the specific characteristics of the test problems used. Moreover, scientific literature has so far primarily focused on continuous MOPs, leaving combinatorial optimization as a research area with open questions to be explored. To deepen the understanding of the challenges inherent in combinatorial MOPs, the first part of this thesis presents a case study applied to a many-objective formulation of the logistic problem Dial-a-Ride Problem (DARP). Initially, a fitness landscape analysis is performed to investigate the geometry of the Pareto front obtained for each set of test problems and to identify possible relationships between the optimized objectives. Then, a comparative performance analysis is presented, considering various Multiobjective Evolutionary Algorithms (MOEAs) from different classes. The results obtained show that, even using the same problem formulation, different observations can be made regarding both the problem’s characteristics and the algorithms’ behavior when different sets of test problems are employed. In a second stage, deviating from the main focus of most current research, which concentrates on the development of new multiobjective optimization methods and the creation of innovative selection strategies, we present an approach that independently and simultaneously creates and optimizes multiple alternative formulations of the addressed MOP, in which artificial linear correlations are induced between the objective functions. The proposed approach adopts the divide-and-conquer paradigm, distributing the search process by allocating an independent evolutionary process (independent execution of the MOEA) to both the original problem formulation and each formulation with correlated objectives created. At the end of each execution, the solutions obtained from optimizing each formulation are converted back to the original objective space (based on the original MOP formulation) and then combined. All resulting non-dominated solutions constitute the approximation set, which is the output of the proposed algorithm. By performing independent evolutionary processes using different problem formulations, the goal is to direct searches to different regions of the objective space, reaching areas that would be difficult to explore by only optimizing the original problem formulation using a state-of-the-art MOEA. When integrated with MOEAs from different classes, the proposed approach demonstrated effectiveness in improving the performance of these algorithms when applied to a well-known combinatorial MOP. Based on this performance improvement, two new MOEAs were introduced, based on optimizing formulations with artificially correlated objectives. The presented results demonstrated the superiority of the proposed MOEAs compared to well-established MOEAs in the literature when applied to the multiobjective knapsack problem with 4 to 10 objectives.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/3236
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectOtimização matemática
dc.subjectAlgoritmos genéticos
dc.subjectAnálise numérica
dc.subjectProblema de roteamento de veículos
dc.subjectProblema da mochila (Matemática)
dc.titleOtimizaçã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
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Otimização multiobjetivo e seus desafios no contexto de otimização combinatória.pdf
Tamanho:
123.03 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional