EB-GLS: An Improved Guided Local Search Based on the Big Valley
  Structure
  Local search is a basic building block in memetic algorithms. Guided Local
Search (GLS) can improve the efficiency of local search. By changing the guide
function, GLS guides a local search to escape from locally optimal solutions
and find better solutions. The key component of GLS is its penalizing mechanism
which determines which feature is selected to penalize when the search is
trapped in a locally optimal solution. The original GLS penalizing mechanism
only makes use of the cost and the current penalty value of each feature. It is
well known that many combinatorial optimization problems have a big valley
structure, i.e., the better a solution is, the more the chance it is closer to
a globally optimal solution. This paper proposes to use big valley structure
assumption to improve the GLS penalizing mechanism. An improved GLS algorithm
called Elite Biased GLS (EB-GLS) is proposed. EB-GLS records and maintains an
elite solution as an estimate of the globally optimal solutions, and reduces
the chance of penalizing the features in this solution. We have systematically
tested the proposed algorithm on the symmetric traveling salesman problem.
Experimental results show that EB-GLS is significantly better than GLS.
