Machine Learning-Based Probabilistic Stopping Rule for The GRASP Metaheuristic

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.