Towards a population-based framework for improving stochastic local search algorithms
Ignacio A. Araya, L A Lopez Perez, Maria Cristina Riff · 2012
In this paper, we introduce a method which goal is to help the search done by a Stochastic Local Search algorithm. Given a set of initial configurations, our algorithm dynamically discriminates the ones that seems to give more promising solutions, discarding at the same time those which did not help. The concept of diversity is managed in our framework in order to both avoid stagnation and to explore the search space. To evaluate our method, we use a well-known local search algorithm. This algorithm has been specially designed for solving instances of the challenging Traveling Tournament Problem. We compare the performance obtained running different configurations of the local search algorithm to the ones using our framework. Our results are very encouraging in terms of both the quality of the solutions and the execution time required.