基于流水算法的旅行商问题求解
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于流水算法的旅行商问题求解范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：为了求解旅行商问题，本文借用“水无常形，水往低处流，水流千里归大海”的自然规律，提出新型元启发式求解算法：流水算法。新算法主要包括流水局部搜索、水漫溢出、流水凿洞、蒸发下雨4个算子，同时具有禁忌搜索和正反馈机制特点，兼顾全局搜索和局部搜索能力。最后，本文应用MATLAB平台对算例进行仿真，并与其他经典的元启发式算法进行比较，结果表明流水算法是求解旅行商问题的有效方法，具有较好的收敛性。
关键词：旅行商问题；流水算法；元启发式算法；优化
中图分类号：C934文献标识码：A文章编号：10035192（2014）01006505doi：10.11847/fj.33.1.65
1引言
旅行商问题（Traveling Salesman Problem，简称TSP）又称为旅行推销员问题、货郎担问题，最早于1859年由威廉·汉密尔顿首次提出，属于运筹学中经典的组合优化难题。该问题是单一旅行者由起点出发，不重复地走完其余地点并回到原出发点，在所有可能的路径中求出路径长度最短的一条。旅行商问题属于组合优化范畴，是NPhard问题，具有组合优化问题的典型特征，并且问题描述简单，因此很多学者将旅行商问题算例作为算法研究的公共实例。同时，旅行商问题有着广泛的实际应用背景，如物流配送、调度排班、道路交通、计算机网络节点配置、生产调度、组合优化求极值等问题。所以，旅行商问题成为优化领域里的研究热点，吸引了管理优化、运筹学、数学、物理、生物和人工智能等领域的研究者的关注。
TSP问题的解空间是多维、多局部极值、复杂的解空间。这个解空间类似一个无穷大的丘陵地带，山峰、山谷连绵起伏，其中的山谷就代表局部极低值，最低的山谷代表最短路径，对应的方案就是最佳旅行方案。旅行商问题的求解方法大体可以分为两类：精确求解法和近似求解法。精确求解法主要是通过解析方法求得最优解，包括枚举法、分枝定界法、动态规划等。旅行商问题描述虽然非常简单，但随着需要访问城市数目的增加，会出现所谓的“组合爆炸”现象，在多项式时间内无法精确求解。所以，人们提出了以获得次优解为目标的近似启发式求解算法。受到自然界的启发，人们提出各种各样的元启发式算法（MetaHeuristics）用于优化求解，如遗传算法[1]、模拟退火[2]、禁忌搜索算法[3]、蚁群算法[4～6]、粒子群优化算法[7]等。这些智能算法被广泛地应用于TSP问题求解，虽然不能保证获取最优解，但当问题规模较大时，保证在可行时间内找到满意的解。求解TSP问题的近似求解算法又可分为环路构造算法和环路改进算法两类[8]。前者从某个非法解开始，通过某种增广策略逐步改变该解，直到得到一个合法解为止，这类算法包括最近邻算法、贪心算法、ClarkeWright算法和Christofides算法等。环路改进算法则在给定初始的合法解后使用某种策略来改进初始解。这些策略更多的是元启发式算法，包括遗传算法[9～12]、模拟退火[13]、禁忌搜索算法[14]、蚁群算法[15，16]、粒子群优化算法[17，18]等。旅行商问题的本质是根据旅行商问题的解空间特征，研究局部最优解、全局最优解和邻域结构之间的关系，具体包括：一种邻域结构的局部最优解和另一种邻域结构的局部最优解之间的关系；全局最优解和所有邻域结构的局部最优解之间的关系。所以，提出一种更能协调上述关系的启发式算法是组合优化领域学者长期追求的目标。
3流水算法原理
现代元启发式算法成为近似求解大规模复杂的旅行商问题的研究热点。研究者从生物系统的进化和大自然中自适应性现象得到灵感，提出了一些以搜索近优解为目标的仿生元启发式算法，如遗传算法、蚁群优化算法、粒子群优化算法等。仿生优化算法是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称。借鉴自然和社会的各种现象，提出并设计优化算法成为一个重要的求解途径。本文正是在这样的背景下，基于旅行商问题的解空间类似一个无穷大的丘陵地带特点，受到自然现象“水无常形，水往低处流，水流千里归大海”的启发，设计新型的求解旅行商问题的元启发式算法—流水算法。
3.1流水的启示
总启示：“水无常形，水往低处流，水流千里归大海”是众多流水全局寻优，求极值（地势最小）的过程。如图1所示，一个流水从初始位置A，流经B、C、D等锚点位置（局部极小）最终到达最低点E（全局最小）。流水的位置与旅行商问题可行域具体解的编码相互映射。
（1）流水局部搜索启示：“水无常形，水往低处流” 是一个流水根据地势状况局部搜索更低点，并向着下一个局部更低位置流动的过程，在这个过程中流水总是尽可能选择并流经最短路径到达最低点。并且，流水不可能倒着流动，具有禁忌搜索的特点。
（2）水漫溢出的启示：当流水流到一个局部最低的位置，会出现停滞（如图1中位置B）；但随着水量增加，水位上升到一定高度，流水从一个局部次优的位置溢出，并由此继续向下流动，跳出局部收敛。从优化算法的角度，流水的这种特点具有突破局部收敛的能力，即当流水若干代不变后，强行更换位置到局部次优的位置，从而继续进行局部搜索。
（3）流水凿洞的启示：流水向着下一个更低、更好位置流动时，落差越大，流水冲击惯性越大，就会对周围的泥土或岩石进行磨损，甚至可以凿洞突破当前位置的限制，向着比当前位置好的附近点流动（向着局部较优解方向搜索），向着最低点流动（向着全局最优解方向搜索）。并且，在现实中往往可以通过人工凿洞方式，让水流到更低位置，并且路径较短。从优化算法的角度，流水的这种特点具有突破局部收敛、向着全局最优解收敛的优点。
（4）蒸发下雨的启示：在自然界中，位置高、水量少的流水容易被蒸发掉形成水蒸气；相应水蒸气会在一定的气候影响下随机下雨，形成相对应数量的流水。从优化算法的角度，“蒸发”具有“优胜劣汰”优点；“下雨”具有多样化群体，具备随机全局寻优的优点。
[4]Colorni A， Dorigo M， Maniezzo V. Distributed optimization by ant colonies[A]. Processings of the First European Conference on Artificial Life[C]. Amsterdam： Elsevier， 1992. 134142.
[5]Colorni A， Dorigo M， Maniezzo V. An investigation of some properties of an ant algorithm[A]. Processings of the Parallel Problem Solving from Nature Conference[C]. Amsterdam： Elsevier， 1992. 509520.
[6]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on System， Man， and Cybernetics PartB： Cybernetics， 1996， 26（1）： 2941.
[7]Kennedy J， Eberhart R C. Particle swarm optimization[A]. Proceedings of the 1995 IEEE International Conference on Neural Networks[C]. Piscataway， New Jersey， 1995. 19421948.
[8]戚玉涛，焦李成，刘芳.基于并行人工免疫算法的大规模TSP问题求解[J].电子学报，2008，36（8）：15521558.
[9]唐立新.旅行商问题的改进遗传算法[J].东北大学学报，1999，20（1）：4042.
[10]Chang P C， Huang W S， Ting C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications， 2010， 37（3）： 18631878.
[11]Albayrak M， Allahverdi N. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J]. Expert Systems with Applications， 2011， 38： 13131320.
[12]Nagata Y， Soler D. A new genetic algorithm for the asymmetric traveling salesman problem[J]. Expert Systems with Applications， 2012， 39： 89478953.
[13]Geng X， Chen Z， Yang W. et al.. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search[J]. Applied Soft Computing， 2011， 11： 36803689.
[14]刘于江，喻泽峰.一种求解旅行商问题的禁忌搜索算法[J].江西理工大学学报，2006，27（4）：3840.
[15]Manfrin M， Birattari M， Stützle T， et al.. Parallel ant colony optimization for the traveling salesman problem[J]. Lecture Notes in Computer Science， 2006， 4150： 224234.
[16]蔡荣英，王李进，吴超，等.一种求解旅行商问题的迭代改进蚁群优化算法[J].山东大学学报（工学版），2012，42（1）：611.
[17]郭崇慧，谷超，江贺.求解旅行商问题的一种改进粒子群算法[J].运筹与管理，2010，19（5）：2026.
[18]沈继红，王侃.求解旅行商问题的混合粒子群优化算法[J].智能系统学报，2012，7（2）：174182.