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

被引：9

作者：

张军英

周斌

机构：

[1] 西安电子科技大学计算机学院

来源：

计算机学报 | 2008年 / 02期

关键词：

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

← 1 →