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

论文题目：基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法 论文作者：张军英，周斌 详细工作单位：西安电子科技大学　计算机学院 城市及邮政编码：陕西 西安 710071 摘 要 旅行商问题(TSP)是组合优化中最典型的NP完全问题之一，具有很强的工程背景和应用价值。本文在分析了标准SOM(self-organizing map)算法在求解TSP问题的不足和在寻求总体最优解上的潜力的基础上，引入泛化竞争和局部渗透这两个新的学习机制，提出了一种新的SOM算法，叫渗透的SOM(Infiltrative SOM, ISOM)。通过泛化竞争和局部渗透策略的协同作用：总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透，实现了在总体路径寻优指导下的局部路径优化，从而使所得路径尽可能接近最优解。通过对TSPLIB中14组TSP实例的测试结果及与如KNIES、SETSP、Budinich和ESOM等类SOM算法的比较，表明该算法既简单解的质量又得到了很大提高，同时还保持了解的良好的稳健特性。 关键词： TSP问题；组合优化；自组织映射；全局优化；总体优化；局部优化 论文题目：基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法 论文作者：张军英，周斌 论文相关的背景： 旅行商问题(TSP)是组合优化中最典型的NP难问题，特别对于大规模TSP问题的求解，无论是理论上还是应用上，都有极其重要的意义。 本项研究，既看到了该问题研究的难度，同时也注意到了由于其困难使对这一问题的解决在理论上和方法上的巨大潜力。我们注意到：(1)要获得TSP问题全局最优解是及其困难的；(2)用标准自组织网络(SOM)求解TSP问题可以获得对问题的总体最优解，因此，我们在标准SOM的基础上创造性地引入了泛化竞争机制和局部渗透机制，通过这两个机制的协调和竞争，即总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透，实现了在基于标准SOM学习的总体路径寻优指导下的局部路径优化，从而使得所得的路径尽可能接近最优解。通过对TSPLIB中14组TSP实例（其中有的实例城市数达1600多个）的测试实验结果表明，本文所提出的算法简单，在解的质量上已超越了如KNIES、SETSP、Budinich和ESOM等类SOM算法，同时算法还保持了较低的计算复杂度和解的良好的稳健特性。 该项研究受到我们负责的国家自然科学基金项目的支持。 本论文的内容全部是作者原创的科研成果；署名无争议；引用他人成果已注明出处；未公开发表过 基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法? 张军英，周斌 (西安电子科技大学　计算机学院，西安， 710071) 摘 要 旅行商问题(TSP)是组合优化中最典型的NP完全问题之一，具有很强的工程背景和应用价值。本文在分析了标准SOM(self-organizing map)算法在求解TSP问题的不足和在寻求总体最优解上的潜力的基础上，引入泛化竞争和局部渗透这两个新的学习机制，提出了一种新的SOM算法，叫渗透的SOM(Infiltrative SOM, ISOM)。通过泛化竞争和局部渗透策略的协同作用：总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透，实现了在总体路径寻优指导下的局部路径优化，从而使所得路径尽可能接近最优解。通过对TSPLIB中14组TSP实例的测试结果及与如KNIES、SETSP、Budinich和ESOM等类SOM算法的比较，表明该算法既简单解的质量又得到了很大提高，同时还保持了解的良好的稳健特性。 关键词： TSP问题；组合优化；自组织映射; 全局优化；总体优化；局部优化 中图法分类号：TP18 文献表示码：A 文章编号： 引 言 作为在VLSI芯片设计[1]、网络路由[2,3]、车辆选路[4]等领域有着广泛应用的旅行商问题(Traveling Salesman Problem, TSP)[5]，是NP完全问题中的最为典型的问题[6]。解决它对于解决所有NP完全问题具有重要的理论意义[7]，所以长期以来一直吸引着众多领域的研究人员对其进行研究和算法改进。TSP问题要求找到经过每个城市、每个城市只经过一次、且路径最短的Hamilton回路。对于一个城市的TSP问题，由于该问题一共存在条可能的路径，用穷举的办法显然是不现实的。譬如，用穷举有哪些信誉好的足球投注网站法对的TSP问题进行求解，即使采用每秒计算1亿次的超级计算机也需要运行年[8]。可喜的是，一些智能优化算法可用于获取TSP问题的次优解，如模拟退火[9]、遗传算法[10]、禁忌有哪些信誉好的足球投注网站算法[11]、蚁群算法[12]和神经网路方法[13,14]等。本文则研究基于SOM神经网