Towards a Population-Based Framework for Improving Stochastic Local Search Algorithms

摘要

Stochastic Local Search algorithms have already shown a good performance for solving large scale combinatorial optimization problems. 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.