旅行商问题的闭环DNA算法

J4 ›› 2014, Vol. 36 ›› Issue (01): 111-114.

旅行商问题的闭环DNA算法

徐京雷，赵洪超，刘希玉

（山东师范大学管理科学与工程学院，山东济南 250014）

收稿日期:2012-04-27 修回日期:2012-11-30 出版日期:2014-01-25 发布日期:2014-01-25
基金资助:
国家自然科学基金资助项目（61170038）

Closed circle DNA algorithm of traveling salesman problem

XU Jinglei,ZHAO Hongchao,LIU Xiyu

（College of Management Science and Engineering,Shandong Normal University,Jinan 250014,China）

Received:2012-04-27 Revised:2012-11-30 Online:2014-01-25 Published:2014-01-25

摘要/Abstract

摘要：

旅行商问题TSP是NP完全问题，在工程实践中有着广泛的应用，利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式，与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进；随后提出了一种基于改进的闭环模型求解TSP问题的算法，并对算法的实验过程进行了详细的描述；最后运用该算法解决了一个小规模的TSP问题算例，结果表明，该算法能在较低的时间复杂度内有效地解决TSP问题。

关键词: TSP问题, DNA计算, 闭环模型, DNA算法

Abstract:

Traveling Salesman Problem (TSP) is a hard NPcomplete problem, which has wide applications in the engineering. It is very difficult to solve TSP problem in polynomial time by using regular algorithms. DNA computing is a new computing pattern; its inherent huge parallel computing power makes it show a huge advantage in solving many NP problems. We try to solve the TSP problem by the improved closed circle model. Firstly, the closed circle model and its improved version are introduced. Secondly, a closed circle DNA algorithm based on the improved model is proposed, which can solve the TSP problem. And the procedure is described in detail. Finally, a small case is solved by the algorithm. Experimental results show that the proposed algorithm can solve the TSP problem effectively in a lower time complexity.

Key words: TSP problem;DNA computing;closed circle model;DNA algorithm

徐京雷，赵洪超，刘希玉. 旅行商问题的闭环DNA算法[J]. J4, 2014, 36(01): 111-114.

XU Jinglei,ZHAO Hongchao,LIU Xiyu. Closed circle DNA algorithm of traveling salesman problem [J]. J4, 2014, 36(01): 111-114.

参考文献［6］

［1］	Adleman L M. Molecular computation of solutions to combinatorial problems［J］.Science,1994,266(11):10211024.
［2］	Maley C C.DNA computation：Theory，practice and prospects［J］.Evolutionary Computation,1999,6(3):201230.
［3］	Zhou Kang, Tong Xiaojun, Liu Wenbin, et al. Closed circle DNA algorithm of shortest path problem［J］. System Engineering and Electronic Technology, 2008,30(3):556560.(in Chinese)
［4］	Zhou Kang, Xu Jin. Closed circle DNA algorithm of the minimal covering problem［J］. Computing Engineering and Applications, 2006,42(20):79.(in Chinese)
［5］	Zhou Kang, Tong Xiaojun, Xu Jin. Closed circle DNA algorithm of knapsack problem［J］. Journal of System Simulation, 2008,20(17):46054608.(in Chinese)
［6］	Zhou Kang, Tong Xiaojun, Xu Jin. Closed circle DNA algorithm of eight queens problem［J］. Computer Engineering and Applications, 2007,43(6):46.(in Chinese)
	附中文参考文献：
［3］	周康,同小军,刘文斌,等.最短路问题的闭环DNA 算法［J］.系统工程与电子技术,2008,30(3):556560.
［4］	周康,许进.最小顶点覆盖问题的闭环DNA算法［J］.计算机工程与应用,2006,42(20):79.
［5］	周康,同小军,许进.背包问题的闭环DNA算法［J］.系统仿真学报,2008, 20(17):46054608.
［6］	周康,同小军,许进.基于闭环DNA模型的八皇后问题算法［J］.计算机工程与应用,2007,43(6):46.

[1]	吴俊斌, 吴晟, 吴兴蛟. 一种用于求解TSP问题的随机最佳插入烟花算法[J]. 计算机工程与科学, 2020, 42(11): 2080-2087.
[2]	张瑾1，毕国通2，李丽丽1. 一种求解TSP问题的离散蝙蝠算法[J]. 计算机工程与科学, 2018, 40(11): 2085-2091.
[3]	张于贤，丁修坤，薛殿春，王晓婷. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学, 2017, 39(08): 1576-1580.
[4]	张晓强1，王蒙蒙2，朱贵良2. 图像加密算法研究新进展[J]. J4, 2012, 34(5): 1-6.
[5]	任晓娜1，张大方1,2，向旭宇2. 基于离散粒子群的DNA编码序列组合优化方法[J]. J4, 2011, 33(3): 179-184.
[6]	朱雅莉李肯立. DNA计算机中堆栈数据结构的设计[J]. J4, 2008, 30(4): 121-123.
[7]	许智宏宋勃董建波. 用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J]. J4, 2008, 30(10): 43-44.
[8]	刘毅[1,2] 宋玉阶[1]. 收缩背包问题的DNA算法[J]. J4, 2007, 29(8): 55-57.
[9]	潘果[1] 李肯立[1] 刘完芳[2]. 基于分治的子集积问题DNA计算机算法[J]. J4, 2007, 29(8): 74-78.
[10]	宋玉阶吴怀宇. 求解线性约束二次优化问题的神经计算模型[J]. J4, 2000, 22(2): 73-76.
[11]	陈沐天. 货郎担问题的几何分块算法及ChinaTSP问题的最终解决[J]. J4, 1998, 20(1): 22-27.