[1]周蓝海,蔡东风.TSP冰晶算法[J].智能系统学报,2008,3(2):167-172.
ZHOU Lan-hai,CAI Dong-feng.Solving the TSP problem with a crystal algorithm[J].CAAI Transactions on Intelligent Systems,2008,3(2):167-172.
点击复制
ZHOU Lan-hai,CAI Dong-feng.Solving the TSP problem with a crystal algorithm[J].CAAI Transactions on Intelligent Systems,2008,3(2):167-172.
TSP冰晶算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
3
期数:
2008年第2期
页码:
167-172
栏目:
学术论文—人工智能基础
出版日期:
2008-04-25
- Title:
- Solving the TSP problem with a crystal algorithm
- 文章编号:
- 1673-4785(2008)02-0167-06
- Keywords:
- traveling salesman problem; ice crystal; dendrite; convex hull; nondeterministic polynomialm
- 分类号:
- TP301.5
- 文献标志码:
- A
- 摘要:
- TSP即旅行商问题，是一个典型的NP困难问题，随问题规模的增加，获得最优解的代价呈指数级增长.受自然智能的启发，冰晶算法首次模拟湖水降温时，湖面冰晶的生长过程，在亚稳态区内维持适宜的饱和度来尝试解决TSP问题.冰晶生长的过程就是TSP路径形成的过程，试验表明，这是一种快速有效的TSP问题近似算法，可在O(knlogn)时间复杂度下获得可行解，同时该算法适用于并行计算，可对开环、动态、大规模的TSP问题实时求解.
- 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 region 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 solving TSP problems quickly and effectively, obtaining feasible solutions under O(knlogn) complexity. It can also be used in parallel computation, generating realtime solutions for openlooped, dynamic, and largescale TSP problems.
- 参考文献/References:
-
［1］GAREY M R, JOHNSON D S. Computers and intractability :a guide to th e theor y of NPcompleteness ［M］. San Francisco: Freeman W H, 1979.
［2］ DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems , Man and Cybernetics, 1996(1):2941.
［3］ KENNEDY J, EBERHART R C. Particle swarm optimization ［C］// Proceedings of IE EE International Conference on Neutral Net works,Perth,Australia , 1995: 1942 1948.
［4］ KIRKPATRICK D G, SEIDEL R. The ultimate planar convex hull algorithm［J］. SIAMJ Comput,1986,15:287299.
［5］ 周培德.计算几何：算法分析与设计［M］.北京:清华大学出版社, 2000. ［6］ 徐庭栋.非平衡晶界偏聚动力学和晶间脆性断裂［M］.北京:科学出版社, 2006.
［7］ GERHARD R.TSPLIB ［EB/OL］.［19970219］.http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html.
［8］ WU Ruiqian, LIN Huijuan,JIANG Fengyi.Final project for neural Network［EB/OL］.［19971228］. http://wayne.cs.nthu.edu.tw/~roland/nn/report_fc.html.
［9］ PEITGEN H O, RICHLET P H. The beauty of fractals: images of complex dyn amical systems［M］. New York:SpringerVerlag,1986.［10］ KENNETH J.分形几何——数学基础及其应用［M］.曾文曲,译.沈阳:东北大学出版社,1991.
［11］陈志平，徐宗本.计算机数学——计算复杂性理论与NP、CNP难问题的求解［M］.北京 :科学出版社, 2001.
- 相似文献/References:
-
[1]印 峰,王耀南,刘 炜,等.个体速度差异的蚁群算法设计及仿真[J].智能系统学报,2009,4(6):528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
YIN Feng,WANG Yao-nan,LIU Wei,et al.Design and simulation of an ant colony algorithm based on individual velocity differences[J].CAAI Transactions on Intelligent Systems,2009,4():528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
[2]沈继红,王侃.求解旅行商问题的混合粒子群优化算法[J].智能系统学报,2012,7(2):174.
SHEN Jihong,WANG Kan.The light ray particle swarm optimization for solving the traveling salesman problem[J].CAAI Transactions on Intelligent Systems,2012,7():174.
[3]王华鲜,华容,刘华平,等.无人机群多目标协同主动感知的自组织映射方法[J].智能系统学报,2020,15(3):609.[doi:10.11992/tis.201908022]
WANG Huaxian,HUA Rong,LIU Huaping,et al.Self-organizing feature map method for multi-target active perception of unmanned aerial vehicle systems[J].CAAI Transactions on Intelligent Systems,2020,15():609.[doi:10.11992/tis.201908022]
[4]齐小刚,张仲华,宋卫星,等.多中心维修任务分配研究现状[J].智能系统学报,2022,17(3):448.[doi:10.11992/tis.202109008]
QI Xiaogang,ZHANG Zhonghua,SONG Weixing,et al.Research status of multicenter maintenance task assignment[J].CAAI Transactions on Intelligent Systems,2022,17():448.[doi:10.11992/tis.202109008]
备注/Memo
收稿日期：2007-06-25.
基金项目：教育部科学技术研究重点资助项目（207148）
作者简介：
周蓝海，男，1980年生，硕士研究生，主要研究方向为人工智能、知识工程、机器翻译，发表论文4篇.
蔡东风，男，1958年生，教授，获东京大学工学博士学位，主要研究方向为人工智能、自然语言处理、信息检索.近年来完成科研项目20余项，发表学术论文60余
篇通讯作者：周蓝海.E-mail:zhlanhai@163.com
更新日期/Last Update:
2009-05-11