推销员问题的重要抽样模拟退火方法

计算物理 ›› 1994, Vol. 11 ›› Issue (3): 278-282.

推销员问题的重要抽样模拟退火方法

陈军, 陈天崙, 黄五群

南开大学物理系, 天津 300071

收稿日期:1992-10-30 修回日期:1993-10-16 出版日期:1994-09-25 发布日期:1994-09-25
基金资助:
国家基础性研究重大项目《非线性科学》及国家自然科学基金

THE TRAVELING SALESMAN PROBLEM: OPTIMIZATION BY IMPORTANCE SAMPLING SIMULATED ANNEALING METHOD

Chen Jun, Chen Tianlun, Huang Wuqun

Dapartment of Physics, Nankai University Tianjin 300071

Received:1992-10-30 Revised:1993-10-16 Online:1994-09-25 Published:1994-09-25

摘要/Abstract

摘要： 采用随机三角点阵上城市间的最近邻关系,构造路径子空间来求解旅行推销员问题。用重要抽样的模拟退火算法及分段优化法大大提高了计算的效率,节省了计算时间,得到较优的结果。

关键词: 随机三角点阵, 重要抽样, 模拟退火, 旅行推销员问题

Abstract: The nearest neighbour relation between cities on random triangle lattice has been used to construct a tour subspace and to solve the traveling salesman problem. With importance sampling simulated annealing method and subtour optimization method, the efficiency has been raised obviously. Near optimal solutions are obtained in shorter computation time.

Key words: random triangle lattice, importance sampling, simulated annealing, traveling salesman problem

中图分类号:

O224

陈军, 陈天崙, 黄五群. 推销员问题的重要抽样模拟退火方法[J]. 计算物理, 1994, 11(3): 278-282.

Chen Jun, Chen Tianlun, Huang Wuqun. THE TRAVELING SALESMAN PROBLEM: OPTIMIZATION BY IMPORTANCE SAMPLING SIMULATED ANNEALING METHOD[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 1994, 11(3): 278-282.

[1]	李琼, 刘海风, 张弓木, 张其黎. 模拟退火算法在化学自由能模型中的应用[J]. 计算物理, 2019, 36(3): 259-264.
[2]	王瑞宏, 姫志成, 江松, 黄正丰, 裴鹿成. 计算动态系统网格通量场的驿站重要抽样方法[J]. 计算物理, 2010, 27(5): 733-739.
[3]	井西利, 徐天赋, 陈秀娟, 李栋宇. 薄膜椭偏测量的自适应混合反演算法[J]. 计算物理, 2007, 24(5): 619-624.
[4]	常建华, 王婷婷, 陶在红, 张明德. 多波长宽带拉曼放大器的优化设计[J]. 计算物理, 2007, 24(2): 227-233.
[5]	尹玉华, 孙平川, 李宝会, 金庆华, 丁大同. 非对称半结晶两嵌段共聚物的微相分离与结晶行为的模拟退火研究[J]. 计算物理, 2007, 24(1): 95-98.
[6]	刘洪亮, 赵逸琼, 李永平, 付绍军, 张巍, 张晓波, 舒方杰. 一种用于均匀照明的衍射光学元件设计的快速模拟退火法[J]. 计算物理, 2005, 22(3): 240-244.
[7]	杨树军. 理想正电子湮灭寿命谱解析程序DPSⅠ[J]. 计算物理, 2003, 20(6): 561-564.
[8]	李涛, 付绍军, 王炜, 徐俊中, 李永平. 一种用于均匀照明的衍射光学元件设计的混合算法[J]. 计算物理, 2002, 19(1): 77-80.
[9]	张子平, 叶竞波. 高能物理过程事例产生器的建立[J]. 计算物理, 1995, 12(2): 275-278.
[10]	龚新高, 郑庆祺, 何怡贞. 硅原子集团结构的分子动力学研究[J]. 计算物理, 1992, 9(S2): 721-722.