Empirical Analysis of Operators for Permutation Based Problems
Pierre Desport, Matthieu Basseur, Lardeux, Frédéric, Adrien Goëffon, Frédéric Saubion · 2015
Abstract. This paper presents an analysis of different possible oper-ators for local search algorithms in order to solve permutation-based problems. These operators can be defined by a distance metric that de-fine the neighborhood of the current configuration, and a selector that chooses the next configuration to be explored within this neighborhood. The performance of local search algorithms strongly depends on their ability to efficiently explore and exploit the search space. We propose here a methodological approach in order to study the properties of dis-tances and selectors in order to buildtheir performances operators that can be used either for intensification of the search or for diversification stages. Based on different observations, this approach allows us to define a simple generic hyperheuristic that adapt the choice of its operators to the problem at hand and that manages their use in order to ensure a good trade-off between intensification and diversification. Moreover this hyperheuristic can be used on different permutation-based problems. 1