Dissertação
Stochastic Multi-Objective Combinatorial Optimization Algorithms EVALUATED
Otimização Combinatória Multi-Objetivo (MOCO) tem diversas aplicações no mundo real como Consolidação de Máquinas Virtuais, Alocação do Nível de Garantia de Desenvolvimento, Problema de Cobertura do Conjunto, entre outros. Novas abordagens para MOCO foram propostas baseadas em iterativamente resolver formulações de Lógica Proposicional. Além disso, esta abordagem demonstrou que consegue resolver efetivamente instâncias mais restritas. Por outro lado, abordagens estocásticas são normalmente melhores em instâncias menos restritas. Recentemente, abordagens híbridas que combinam técnicas estocásticas com técnicas de Lógica Proposicional, na forma de operadores inteligentes, têm sido propostas. Estes algoritmos demonstraram resolver muitos problemas de forma eficaz, como a Consolidação de Máquinas Virtuais, que utiliza variáveis inteiras na formulação do problema. Neste trabalho, apresentamos Neon, uma abordagem híbrida genérica para resolver instâncias MOCO compostas por fórmulas Booleanas Multi-Objetivo, que utilizam variáveis Booleanas. Além disso, Neon incorpora dois operadores inteligentes. O primeiro é o de mutação inteligente, que transforma uma atribuição inviável numa viável utilizando um solucionador Pseudo-Booleano. O outro chama-se melhoria inteligente, e melhora uma atribuição já viável ao extrair Subconjuntos de Correção Mínimos do problema. Utilizar variáveis Booleanas na formulação do problema é normalmente mais difícil para o algoritmo estocástico do que usar variáveis inteiras, portanto, o Neon implementa uma técnica chamada melhoria da estrutura que explora a estrutura de algumas restrições, ao criar variáveis inteiras que representam as referidas restrições e obrigam-nas a que sejam sempre satisfeitas.
janeiro 28, 2021, 18:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Vasco Miguel Gomes Nunes Manquinho
Departamento de Engenharia Informática (DEI)
Professor Associado
