Auto-parametrização de meta-heurísticas para problemas de escalonamento em ambiente industrial

Abstract

Há uma série de Problemas de Otimização que pela sua complexidade, não podem ser resolvidos, pelo menos de forma eficiente. Entre os problemas que são demasiados complexos para serem resolvidos à otimalidade há inúmeros Problemas de Escalonamento. É normal recorrer a Meta-Heurísticas para abordar os Problemas de Escalonamento. As Meta-Heurísticas não encontram sempre as soluções ótimas, mas são capazes de encontrar soluções satisfatórias em pouco tempo computacional. Embora a comunidade científica tenha demonstrado muito interesse na análise do comportamento das Meta-Heurísticas, a análise da sua parametrização tem merecido pouca atenção. É a parametrização que vai adequar a Meta-Heurística ao problema, no entanto ainda é feita, maioritariamente, de uma forma empírica. Há múltiplos métodos de parametrização, no entanto, ou são morosos, requerendo um esforço considerável, ou não aproveitam os benefícios das Meta-Heurísticas que vão parametrizar. De maneira a abordar e simplificar a parametrização de Meta-Heurísticas, neste trabalho, é proposto um sistema de auto-parametrização. Isto vai permitir automatizar a parametrização, tratando-a como um Problema de Otimização, evitando que o utilizador despenda demaisado tempo em ensaios de parametrização. O modelo vai automatizar o processo de parametrização através de duas Meta Heurísticas: uma Meta-Heurística do Espaço de Soluções e uma Meta-Heurística do Espaço de Parâmetros. A Meta-Heurística do Espaço de Parâmetros vai fazer uma pesquisa por soluções de parametrização e a Meta-Heurística do Espaço de Soluções é executada para avaliar o desempenho das soluções de parametrização. Para analisar o desempenho o modelo, foi implementado um protótipo de auto-parametrização. O protótipo foi comparado e analisado num Problema de Escalonamento e no TSP (Traveling Salesman Problem). O protótipo encontrou, no Problema de Escalonamento, soluções de melhor qualidade que as do protótipo de parametrização manual embora as diferenças não tenham sido expressivas. Já no TSP, foi mais eficaz, desta vez, com diferenças estatisticamente significativas.

In Optimization Problems, there are problems which, either because of their complexity or dimension, cannot be solved, at least, efficiently. Between the Optimization Problems that are too complex to be solved, optimally, by non-enumerative techniques, there are several Scheduling Problems. It is common to use Meta-Heuristics to address these problems. Meta-Heuristics are Optimization Techniques that do not always find the optimal solutions, but require little computational time. Even with all the interest the scientific community has shown in Meta-Heuristics, the parameterization procedure has received little attention. It is the parameterization that will adapt the Meta-Heuristic to an Optimization Problem, the parameterization is still, more often than not, done empirically. While there are numerous parameterization techniques, they either require considerable time and effort, or, they do not benefit from the characteristics Meta-Heuristics that will be parameterized. In order to streamline the parameterization procedure, this thesis proposes an self-parameterization framework that will use Meta-Heuristics in the parameterization. It will automate the parameterization by approaching the parameterization procedure as an Optimization Problem, which will spare the user from the cumbersome manual parameterization. In the framework the parameterization procedure will be automatized by two Meta-Heuristics: a Solution Space Meta-Heuristic and a Parameter Space Meta Heuristic. It is the Parameter Space Meta-Heuristic that searches for parameterization solutions, while Solution Space Meta-Heuristic is used to evaluate the performance of the solutions. In order to examine the performance of the proposed framework, an self-parameterization prototype was developed. Its performance was evaluated in a Scheduling Problem and in the Traveling Salesman Problem (TSP). It was able to find found better solutions than those found by manual parameterization for the Scheduling Problem, but these variances in performance were not statistically significant. In the TSP, it also found better solutions, but, this time, differences were statistically significant.