Exploring and Exploiting Effectively Based Hyper-Heuristic Approach for Solving Travelling Salesman Problem

Heuristic algorithms are one of the major volunteer for solving NP problems. These algorithms by trading off between exploration and exploitation attempt to find an optimum solution in a reasonable time. Therefore, heuristic studies which are combination of global heuristic algorithm for exploring solution space and local heuristic algorithm for exploiting solution space have been attended. In these combinational heuristic algorithms, local heuristic algorithm is problem oriented. This issue can decrease a capability of exploiting of combinational heuristic algorithms and cause to decrease a probable of finding an optimal solution. In this paper, we propose a new optimization algorithm based on Hyper-Heuristic for solving TSP which uses local searches with domain-independent. A hyper-heuristic approach has two levels. In low level, it has some local searches which search neighborhood of solution and in high level it has choice function which select a proper local search depended on characteristics of the region of the solution space that is currently under exploration and also the performance history of local searches. In the proposed method, we use 6 local searches and our choice function based on reinforcement learning. In our choice function, the local search that has better performance history has high chance to be chosen. In aim of improving efficiency of our method we use a global search algorithm, Genetic Algorithm. Empirical results on standard databases of TSP confirm the efficiency of the proposed method in comparison with combinational heuristic algorithms.