Strategy for improving the performance of chained Lin-Kernighan algorithm
Xiangbin Wu · Journal of Computer Applications · 2007
Lin-Kernighan algorithm is a kind of high effective optimization algorithm for combinatorial optimization problems.Traveling Salesmen Problem(TSP)is one of the typical NP-hard problems in the field of combinatorial optimization.Through the discussion on the simplification of the problems,probability simplifying model was established,the prior probability was produced via experimental analysis,and stochastic algorithm for simplifying initial edge set of traveling salesman problem was constituted.The solving performance of chained Lin-Kernighan algorithm was improved obviously by utilizing the edge set produced by the stochastic algorithm as reference optimizing edge set of chained Lin-Kernighan algorithm.Better convergence effect was achieved while combining the stochastic algorithm with different intelligence algorithms.