提高链式Lin-Kernighan算法性能的策略

Strategy for improving the performance of chained Lin-Kernighan algorithm

Lin-Kernighan算法作为一种高效的组合优化问题优化算法,普遍应用于各种求解组合优化难题的算法中,尤其是旅行商问题的求解。通过对该类问题的可化简性论述,分析并建立了该类问题初始边集的概率化简模型,经实验分析方式确定了模型中的先验性概率值,并建立旅行商化简初始边集的随机算法。将该算法建立的边集作为链式Lin-Kernighan算法的参照优化边集,大幅度提高了链式Lin-Kernighan算法的求解性能,在与多种智能算法结合中取得了较好的收敛效果。

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-Kemighan algorithm was improved obviously by utilizing the edge set produced by the stochastic algorithm as reference optimizing edge set of chained Lin-Kemighan algorithm. Better convergence effect was achieved while combining the stochastic algorithm with different intelligence algorithms.