第3卷第2期 智能系统学报 Vol.3№2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 TSP冰晶算法 周蓝海，蔡东风 (沈阳航空工业学院知识工程中心，辽宁沈阳110034) 摘要：TSP即旅行商问题，是一个典型的NP困难问题，随问题规模的增加，获得最优解的代价呈指数级增长.受自 然智能的启发，冰晶算法首次模拟湖水降温时湖面冰晶的生长过程，在亚稳态区内维持适宜的饱和度来尝试解决 TSP问题.冰晶生长的过程就是TSP路径形成的过程，试验表明，这是一种快速有效的TSP问题近似算法，可在O (kog)时间复杂度下获得可行解，同时该算法适用于并行计算，可对开环动态、大规模的TSP问题实时求解。 关键词：旅行商问题；冰晶；树枝晶；凸壳；非确定多项式 中图分类号：TP301.5文献标识码：A文章编号：16734785(2008)02-0167-06 Solving the TSP problem with a crystal algorithm ZHOU Lamhai,CAI Dong feng Knowledge Engineering Research Center,Shenyang Institute of Aeronautical Engineering,Shenyang 110034,China) Abstract:The traveling salesman problem (TSP)is a typical NP problem.The optimal solution can be costly to obtain as computational requirements of the problem increase exponentially with complexity.This paper proposes a new method for solving TSP problems.With this method,we simulated the growth process of crystals on the surface of a lake as the temperature of the water decreased.In the metastable re- gion we maintained an appropriate degree of saturation and found the growth process of the crystals was the same as the process of forming a TSP path.The proposed method is an appropriate algorithm for sol- ving TSP problems quickly and effectively,obtaining feasible solutions under O(knlogn)complexity.It can also be used in parallel computation,generating real-time solutions for opemlooped,dynamic,and large-scale TSP problems. Key words :traveling salesman problem;ice crystal;dendrite;convex hull;nondeterministic polynomialm 随着网络、通讯、宽带、物流等技术的发展，网络力学与动力学等多种因素影响，是复杂物理现象相 数据优先，电网电力调度，卫星信号中继，国际物流 互作用的结果.冰晶现象是描述自然界液态水降温 配送，多处理器协同等领域，要求能够快速对目标 凝固，结晶长大的过程，具有能量最小原则的特征， TSP现象进行正确和精确的定位，及时获得有效的 在过冷却水滴和冰晶共存的水面，如果存在E< 解决途径 e<Es(E表示饱和水汽压，e表示水汽压，i表示冰，s TsP问题被证明是一个NP-hard问题.目前 表示过冷却水)，冰晶就会凝结而不断长大，冰水共 解决TSP问题有蚂蚁算法！、遗传算法、粒子群算 存相互渗透.冰晶算法模拟自然湖面冰晶的生长过 法)及弹性网络等，在有限的时空复杂度下获得近 程来尝试解决TSP问题，并取得较好的试验结果， 似解或次（最）优解.迭代的求解方式，在大规模有实 1 时性要求的场合，就显得力不从心，有待寻求更高效 试验模型 的算法， TSP冰晶算法的提出是基于以下3个假设： 晶体生长是一种动态相变过程，受晶体生长热 假设1元素属性一致的前提下，系统边界层 的元素对系统的干扰很大，系统内元素只会产生局 收稿日期：2007-0625. 基金项目：教育部科学技术研究重点资助项目(207148) 部扰动，复杂存在于系统的边缘。 通讯作者：周蓝海，Email:zhlanhai@l63.com. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 TSP 冰晶算法 周蓝海 , 蔡东风 (沈阳航空工业学院 知识工程中心 ,辽宁 沈阳 110034) 摘 要 : TSP 即旅行商问题 ,是一个典型的 NP 困难问题 ,随问题规模的增加 ,获得最优解的代价呈指数级增长. 受自 然智能的启发 ,冰晶算法首次模拟湖水降温时 ,湖面冰晶的生长过程 ,在亚稳态区内维持适宜的饱和度来尝试解决 TSP 问题. 冰晶生长的过程就是 TSP 路径形成的过程 ,试验表明 ,这是一种快速有效的 TSP 问题近似算法 ,可在 O ( knlogn) 时间复杂度下获得可行解 ,同时该算法适用于并行计算 ,可对开环、动态、大规模的 TSP 问题实时求解. 关键词 :旅行商问题 ;冰晶 ;树枝晶 ;凸壳 ;非确定多项式 中图分类号 : TP301. 5 文献标识码 :A 文章编号 :167324785 (2008) 0220167206 Solving the TSP problem with a crystal algorithm ZHOU Lan2hai , CAI Dong2feng ( Knowledge Engineering Research Center , Shenyang Institute of Aeronautical Engineering ,Shenyang 110034 ,China) Abstract :The traveling salesman p roblem ( TSP) is a typical NP problem. The optimal solution can be costly to obtain as comp utational requirements of the problem increase exponentially wit h complexity. This paper proposes a new met hod for solving TSP problems. Wit h t his met hod , we simulated t he growt h process of crystals on t he surface of a lake as t he temperature of the water decreased. In t he metastable re2 gion we maintained an appropriate degree of sat uration and found t he growth process of t he crystals was t he same as the p rocess of forming a TSP pat h. The proposed met hod is an appropriate algorit hm for sol2 ving TSP problems quickly and effectively , obtaining feasible solutions under O ( knlog n) complexity. It can also be used in parallel comp utation , generating real2time solutions for open2looped , dynamic , and large2scale TSP p roblems. Keywords :traveling salesman problem ;ice crystal ;dendrite ;convex hull ;nondeterministic polynomialm 收稿日期 :2007206225. 基金项目 :教育部科学技术研究重点资助项目(207148) . 通讯作者 :周蓝海. E2mail :zhlanhai @163. com. 随着网络、通讯、宽带、物流等技术的发展 ,网络 数据优先 ,电网电力调度 ,卫星信号中继 ,国际物流 配送 ,多处理器协同等领域 ,要求能够快速对目标 TSP 现象进行正确和精确的定位 ,及时获得有效的 解决途径. TSP 问题被证明是一个 NP2hard [ 1 ] 问题. 目前 解决 TSP 问题有蚂蚁算法[ 2 ] 、遗传算法、粒子群算 法[3 ]及弹性网络等 ,在有限的时空复杂度下获得近 似解或次(最) 优解. 迭代的求解方式 ,在大规模有实 时性要求的场合 ,就显得力不从心 ,有待寻求更高效 的算法. 晶体生长是一种动态相变过程 ,受晶体生长热 力学与动力学等多种因素影响 ,是复杂物理现象相 互作用的结果. 冰晶现象是描述自然界液态水降温 凝固 ,结晶长大的过程 ,具有能量最小原则的特征 , 在过冷却水滴和冰晶共存的水面 ,如果存在 Ei < e < Es ( E 表示饱和水汽压 , e 表示水汽压 ,i 表示冰 ,s 表示过冷却水) ,冰晶就会凝结而不断长大 ,冰水共 存相互渗透. 冰晶算法模拟自然湖面冰晶的生长过 程来尝试解决 TSP 问题 ,并取得较好的试验结果. 1 试验模型 TSP 冰晶算法的提出是基于以下 3 个假设 : 假设 1 元素属性一致的前提下 ,系统边界层 的元素对系统的干扰很大 ,系统内元素只会产生局 部扰动 ,复杂存在于系统的边缘