基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法

被引:9
作者
张军英
周斌
机构
[1] 西安电子科技大学计算机学院
关键词
TSP问题; 组合优化; 自组织映射; 全局优化; 总体优化; 局部优化;
D O I
暂无
中图分类号
TN402 [设计];
学科分类号
摘要
旅行商问题(TSP)是组合优化中最典型的NP完全问题之一,具有很强的工程背景和应用价值.文章在分析了标准SOM(Self-Organizing Map)算法在求解TSP问题的不足和在寻求总体最优解的潜力的基础上,引入泛化竞争和局部渗透这两个新的学习机制,提出了一种新的SOM算法---渗透的SOM(Infiltrative SOM,ISOM)算法.通过泛化竞争和局部渗透策略的协同作用:总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透,实现了在总体路径寻优指导下的局部路径优化,从而使所得路径尽可能接近最优解.通过对TSPLIB中14组TSP实例的测试结果及与KNIES、SETSP、Budinich和ESOM等类SOM算法的比较,表明该算法既简单又能使解的质量得到很大提高,同时还保持了解的良好的稳健特性.
引用
收藏
页码:220 / 227
页数:8
相关论文
共 6 条
[1]   A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints [J].
Ascheuer, N ;
Jünger, M ;
Reinelt, G .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2000, 17 (01) :61-84
[2]   The Kohonen network incorporating explicit statistics and its application to the travelling salesman problem [J].
Aras, N ;
Oommen, BJ ;
Altinel, IK .
NEURAL NETWORKS, 1999, 12 (09) :1273-1284
[3]   A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing [J].
Budinich, M .
NEURAL COMPUTATION, 1996, 8 (02) :416-424
[4]  
TSPLIB—A Traveling Salesman Problem Library[J] . Gerhard Reinelt.ORSA Journal on Computing . 1991 (4)
[5]   NEURAL COMPUTATION OF DECISIONS IN OPTIMIZATION PROBLEMS [J].
HOPFIELD, JJ ;
TANK, DW .
BIOLOGICAL CYBERNETICS, 1985, 52 (03) :141-152
[6]  
Computers and Intractability: A guide to the Theory of NP-Completeness .2 GAREY M R,JOHNSON D S. Freeman W H . 1979