Genetic iterated local search algorithm and its optimization performance

Standard iterated local search (ILS) algorithms for the traveling salesman problem (TSP) include a local search procedure and a double-bridge move that is a useful technique using only four edges to escape from the best local optimum found by ILS. The paper presents a new ILS approach to the TSP and its optimization performance. We incorporate an idea based on empirical conjectures, e.g., different approximate solutions may share common parts, into the ILS. To escape from the local optimum, an intelligent technique that efficiently reconnects many edges derived from information of two good solutions is adopted. From our experimental results, new ILSs could find better solutions with fewer iterations than standard ILSs. In particular, we demonstrated that one algorithm combined with the Lin–Kernighan heuristic was one of high-performance approaches.