Authors:

Autores

Person role Person
7081
162,539,3127
7080
162,539,3127
7079
162,539,3127

Informations:

Pesc publication

Title
Machine Learning-Based Probabilistic Stopping Rule for The GRASP Metaheuristic
Research area
Mathematical Optimization
Publication type
Master's thesis
Identification Number
Date
12/6/2021
Resumo

Metaheurísticas, como Simulated Annealing, Ant Colony, Algoritmos Genéticos e GRASP, são métodos genéricos que são normalmente aplicados a problemas computacionalmente difíceis. Porém, elas normalmente carecem de um critério de parada efetivo, recorrendo a opções genéricas que resultam em desperdício de recursos computacionais e de tempo. A fim de mitigar esse problema, existe para a metaheurística GRASP um critério de parada probabilístico que utiliza a função de distribuição acumulada (FDA) para calcular, a partir de uma dada iteração, a probabilidade de melhorar a solução em iterações futuras. No entanto, apesar de efetivo, ele possui suas próprias deficiências. Especificamente, o cálculo da FDA é relativamente lento e as probabilidades estimadas, em muitos casos, podem divergir significativamente da probabilidade observada em execuções suficientemente longas. Neste trabalho, propõe-se uma alternativa ao critério de parada probabilística baseada em aprendizado de máquina. Esta dissertação mostra que, ao substituir a FDA por modelos baseados em árvore, é possível reduzir o tempo necessário para estimar probabilidades e diminuir a divergência com a probabilidade observada em execuções do GRASP. Também é mostrado que é possível, para um modelo treinado sobre execuções de uma instância de um problema, generalizar para instâncias do mesmo ou de outros problemas, mas com limitações.

Abstract

Metaheuristics, like Simulated Annealing, Ant Colony, Genetic Algorithms and GRASP, are generic methods that are applied to solve problems that are computationally hard. However, they usually lack an effective stopping criterion, relying on generic options that usually result in a waste of computational resources and time. Seeking to mitigate that problem, there is a probabilistic stopping criterion for GRASP that uses the cumulative distribution function (CDF) to calculate, for a given iteration, the probability of improving the current solution in future iterations. Yet, that criterion also has its own drawbacks. Specifically, the CDF can be relatively slow to calculate and the probabilities it estimates, in many cases, can significantly diverge from the probabilities observed in sufficiently large executions. In this work, a machine learning-based alternative to the probabilistic stopping rule is proposed. This dissertation shows that, by replacing the CDF with a tree-based machine learning model, it is possible to reduce the time taken to estimate a probability and reduce the divergence between that probability and the probability observed in sufficiently large executions. It is also shown that it is possible for a model trained on a given instance, of a given problem, to generalize to other instances, even from other problems, but with limitations.

JSN_TPLFW_GOTO_TOP