Consultant-Guided Search Combined with Local Search for the Traveling Salesman Problem

Consultant-Guided Search (CGS) is a recent swarm intelligence metaheuristic for combinatorial optimization problems, inspired by the way real people make decisions based on advice received from consultants. CGS has been applied to the Traveling Salesman Problem (TSP) and, in experiments without local search (LS), it has been able to outperform some of the best Ant Colony Optimization (ACO) algorithms. However, LS is an important part of any ACO algorithm and a comparison without LS can be misleading. In this paper, we investigate if CGS is still able to compete with ACO when all algorithms are combined with LS. In addition, we propose a new variant of CGS for the TSP, which introduces the concept of confidence in relation to the recommendations made by consultants. Our experimental results show that the solution quality obtained by this new CGS algorithm is comparable with or better than that obtained by Ant Colony System and MAX-MIN Ant System with LS.