基于泛化竞争和局部渗透机制自组织网TSP问题的算法分析与研究
|
摘要
随着旅行商问题(Traveling Salesman Problem)的应用越来越广泛,任何能使其求解得以优化的方法,都将受到高度的评价和关注。本文对求解旅行商问题的基于泛化竞争和局部渗透机制的SOM改进算法进行了详细的分析与实验。认真分析了影响ORC-SOM算法性能的各个参数,从而得到适合该算法的参数取值。并对ORC-SOM算法的时间复杂度和空间复杂度进行了仔细的研究,发现该算法在此两点上都有一定的优势。最后通过对结构不同的旅行商问题和TSPLIB库中16组数据实例(从51到2392个城市)的实验,并与现有的Budinich、ESOM和CONN等SOM改进算法进行详细比较,表明了用ORC-SOM算法不但能更加接近理想最优解,而且算法的稳定性也非常好。
As the application of the traveling salesman problem become more and more popular, any the methods which can be used to optimize the TSP, will be received the strong attention. The paper carries out the detailed analysis and a lot of experiments to the improved algorithm of SOM based overall-regional competition for the TSP. We analyze the parameters which can affect the performance of the ORC-SOM algorithm and get the value which suit the algorithm. And we also study the computation complexity and the space complexity of the ORC-SOM algorithm, and find that the algorithm has the advantage of the computation complexity and the space complexity. By comparison with six typical SOM-based TSP algorithms, our experimental results on structure different TSP data and a set of 16 TSP instances indicate that the proposed algorithm is superior to those TSP algorithms, not only on the total tour length of the TSP, but also on the stability of the algorithm.
As the application of the traveling salesman problem become more and more popular, any the methods which can be used to optimize the TSP, will be received the strong attention. The paper carries out the detailed analysis and a lot of experiments to the improved algorithm of SOM based overall-regional competition for the TSP. We analyze the parameters which can affect the performance of the ORC-SOM algorithm and get the value which suit the algorithm. And we also study the computation complexity and the space complexity of the ORC-SOM algorithm, and find that the algorithm has the advantage of the computation complexity and the space complexity. By comparison with six typical SOM-based TSP algorithms, our experimental results on structure different TSP data and a set of 16 TSP instances indicate that the proposed algorithm is superior to those TSP algorithms, not only on the total tour length of the TSP, but also on the stability of the algorithm.
引文
[1]J. J. Hopfield, D. W. Tank. Neural computation of decisions in optimization problems. Biological Cybernetics.1985, vol.52. pp.141-152.
[2]T. Kohonen. Self-Organizing Maps.3rd edition. Springer-Verlag,1997.
[3]N. Aras, B. J. Oommen,I. K. Altinel. The Kohonen network incorporating explicit statistics and its application to the traveling salesman problem. Neural Networks. Nov.1999, vol.12. pp.1273-1284.
[4]S. Abe. Convergence acceleration of the Hopfield neural network by optimization integration step sizes. IEEE Trans Syst Man Cybern B Cybern.1996, vol.26. pp. 194-201.
[5]K. A. Smith. An argument for abandoning the traveling salesman problem as a neural network benchmark. IEEE Trans Neural Networks.1996, vol.7(6). pp. 1542-1544.
[6]K. S. Leung, H. D. Jin, Z. B. Xu. An expanding self-organizing neural network for the traveling salesman problem. Neurocomputing.2004, vol.62. pp.267-292.
[7]F. C. Vieira, A. D. D. Neto. An efficient approach to the Traveling Salesman Problem using self-organizing maps. International Journal of Neural Systems.2003, vol.13(2). pp.59-66.
[8]http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[9]E. L. Lawler, J. K. Lenstra, A. G Rinnoy Kan. The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization.4th edition. New York:John Wiley & Sons,1990. pp.474.
[10]M. Dorigo, L. M. Gambardella. Ant colony system:A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput. Apr.1997, vol.1. pp.53-66.
[11]N. Ascheuer, M. Junger, G Reinelt. A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and Applications.2000, vol.17(1). pp.61-84.
[12]G. Laporte. The vehicle routing problem:An overview of exact and approximate algorithms. European Journal of Operational Research.1992, vol.59. pp.345-358.
[13]Jiao LiCheng. Neural Computation. Xi'an:Xidian University Press,1996. pp. 195-196.
[14]Wang Wei. Artificial Neural Network:Theory and Application. Beijing:Beijing University of Aeronautic and Astronautic Science and Technology Press,1995.
[15]S. G. Kirkpatrick, Jr. C. D. Gelatt, M. P. Vecchi. Optimization by simulated annealing. Science.1983, vol.220. pp.671-680.
[16]J. Knox. Tabu search performance on the symmetric traveling salesman problem. Comput Oper Res.1994, vol.21. pp.867-876.
[17]T. Kohonen. Self-Organizing Maps. New York:Springer-Verlag,1997.
[18]B. Angeniol, G D. L. C. Vaubois, J. Y. L. Texier. Self-Organizing Feature Maps and the Traveling Salesman Problem. Neural Netw.1988, vol.4(1):pp.289-293.
[19]B. Fritzke, P. Wilke. FLEXMAP—neural network with linear time and space complexity for the traveling salesman problem. Joint Conf:Neural Networks,1991: pp.929-934.
[20]L. I. Burk, P. Damany. The guilty net for the traveling salesman problem. Computers and Operations Research.1992, vol.19(3-4). pp.255-265.
[21]F. Favata, R. Walker. A study of the application of Kohonen-type neural networks to the traveling salesman problem. Biological Cybernetics.1991, vol.64. pp.463-468.
[22]M. Budinich. A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing. Neural computation.1996, vol.8. pp. 416-424.
[23]Simon Haykin. Neural Networks:A Comprehensive Foundation.2nd Edition. New Jersey:Prentice Hall,1999, pp.444-460.
[24]C. M. Bishop, M. Svensen, C. K. I. Williams. GTM:the generative topographic mapping. Neural Computation.1998, vol.10(1). pp.215-235.
[25]Yan Xuesong, Liu Hanmin, Yan Jia. A Fast Evolutionary Algorithm for Traveling Salesman Problem. Third International Conference on Natural Computation. Aug. 2007, vol.4. pp.85-90.
[26]Yang Ning, Li Ping, Mei Baisha. An Angle-Based Crossover Tabu Search for the Traveling Salesman Problem. Third International Conference on Natural Computation. Aug.2007, vol.4. pp.512-516.
[27]R. M. Brady. Optimization Strategies Gleaned from Biological Evolution. Nature. 1994, vol.313. pp.804-806.
[28]N. Srinivas, Kalyanmoy Deb. Multiobjective Optimization Using Nondominated sorting in Genetic Algorithm. Evolutionary Computation.1994, vol.2(3). pp. 221-248.
[29]张军英,王德峰,石美红.输出-阈值耦合神经网络及基于此的最短路问题求解. 中国科学.2003,vol.33(2).
[30]马欣,朱双东,杨斐.旅行商问题(TSP)的一种改进遗传算法.计算机仿真.2003.pp.36-37.
[31]权光日.基于Hopfield-Tank模型的神经网络的变参数方法.电子学报.1995,vol.23(1).
[32]郑军里,孙守宇.Hopfield网络求解TSP的一种改进算法和理论证明.电子学报.1995,vol.23(1).
[33]张军英,许进,保铮.神经网络求解TSP问题的理论分析及其改进.西安电子科技大学学报.1996,vol.12.pp.23.
[34]边肇祺.模式识别.第二版.北京：清华大学出版社,2000.
[35]焦李成.神经网络系统理论.西安：西安电子科技大学出版社,1996.
[36]杨行峻,郑君里.人工神经网络.北京：高等教育出版社,1992.
[37]张立明.人工神经网络的模型及其应用.上海：复旦大学出版社,1993.
[38]潘正君,康立山,陈毓屏.演化计算.北京：清华大学出版社,广西科学技术出版社,1998.
[2]T. Kohonen. Self-Organizing Maps.3rd edition. Springer-Verlag,1997.
[3]N. Aras, B. J. Oommen,I. K. Altinel. The Kohonen network incorporating explicit statistics and its application to the traveling salesman problem. Neural Networks. Nov.1999, vol.12. pp.1273-1284.
[4]S. Abe. Convergence acceleration of the Hopfield neural network by optimization integration step sizes. IEEE Trans Syst Man Cybern B Cybern.1996, vol.26. pp. 194-201.
[5]K. A. Smith. An argument for abandoning the traveling salesman problem as a neural network benchmark. IEEE Trans Neural Networks.1996, vol.7(6). pp. 1542-1544.
[6]K. S. Leung, H. D. Jin, Z. B. Xu. An expanding self-organizing neural network for the traveling salesman problem. Neurocomputing.2004, vol.62. pp.267-292.
[7]F. C. Vieira, A. D. D. Neto. An efficient approach to the Traveling Salesman Problem using self-organizing maps. International Journal of Neural Systems.2003, vol.13(2). pp.59-66.
[8]http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[9]E. L. Lawler, J. K. Lenstra, A. G Rinnoy Kan. The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization.4th edition. New York:John Wiley & Sons,1990. pp.474.
[10]M. Dorigo, L. M. Gambardella. Ant colony system:A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput. Apr.1997, vol.1. pp.53-66.
[11]N. Ascheuer, M. Junger, G Reinelt. A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and Applications.2000, vol.17(1). pp.61-84.
[12]G. Laporte. The vehicle routing problem:An overview of exact and approximate algorithms. European Journal of Operational Research.1992, vol.59. pp.345-358.
[13]Jiao LiCheng. Neural Computation. Xi'an:Xidian University Press,1996. pp. 195-196.
[14]Wang Wei. Artificial Neural Network:Theory and Application. Beijing:Beijing University of Aeronautic and Astronautic Science and Technology Press,1995.
[15]S. G. Kirkpatrick, Jr. C. D. Gelatt, M. P. Vecchi. Optimization by simulated annealing. Science.1983, vol.220. pp.671-680.
[16]J. Knox. Tabu search performance on the symmetric traveling salesman problem. Comput Oper Res.1994, vol.21. pp.867-876.
[17]T. Kohonen. Self-Organizing Maps. New York:Springer-Verlag,1997.
[18]B. Angeniol, G D. L. C. Vaubois, J. Y. L. Texier. Self-Organizing Feature Maps and the Traveling Salesman Problem. Neural Netw.1988, vol.4(1):pp.289-293.
[19]B. Fritzke, P. Wilke. FLEXMAP—neural network with linear time and space complexity for the traveling salesman problem. Joint Conf:Neural Networks,1991: pp.929-934.
[20]L. I. Burk, P. Damany. The guilty net for the traveling salesman problem. Computers and Operations Research.1992, vol.19(3-4). pp.255-265.
[21]F. Favata, R. Walker. A study of the application of Kohonen-type neural networks to the traveling salesman problem. Biological Cybernetics.1991, vol.64. pp.463-468.
[22]M. Budinich. A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing. Neural computation.1996, vol.8. pp. 416-424.
[23]Simon Haykin. Neural Networks:A Comprehensive Foundation.2nd Edition. New Jersey:Prentice Hall,1999, pp.444-460.
[24]C. M. Bishop, M. Svensen, C. K. I. Williams. GTM:the generative topographic mapping. Neural Computation.1998, vol.10(1). pp.215-235.
[25]Yan Xuesong, Liu Hanmin, Yan Jia. A Fast Evolutionary Algorithm for Traveling Salesman Problem. Third International Conference on Natural Computation. Aug. 2007, vol.4. pp.85-90.
[26]Yang Ning, Li Ping, Mei Baisha. An Angle-Based Crossover Tabu Search for the Traveling Salesman Problem. Third International Conference on Natural Computation. Aug.2007, vol.4. pp.512-516.
[27]R. M. Brady. Optimization Strategies Gleaned from Biological Evolution. Nature. 1994, vol.313. pp.804-806.
[28]N. Srinivas, Kalyanmoy Deb. Multiobjective Optimization Using Nondominated sorting in Genetic Algorithm. Evolutionary Computation.1994, vol.2(3). pp. 221-248.
[29]张军英,王德峰,石美红.输出-阈值耦合神经网络及基于此的最短路问题求解. 中国科学.2003,vol.33(2).
[30]马欣,朱双东,杨斐.旅行商问题(TSP)的一种改进遗传算法.计算机仿真.2003.pp.36-37.
[31]权光日.基于Hopfield-Tank模型的神经网络的变参数方法.电子学报.1995,vol.23(1).
[32]郑军里,孙守宇.Hopfield网络求解TSP的一种改进算法和理论证明.电子学报.1995,vol.23(1).
[33]张军英,许进,保铮.神经网络求解TSP问题的理论分析及其改进.西安电子科技大学学报.1996,vol.12.pp.23.
[34]边肇祺.模式识别.第二版.北京：清华大学出版社,2000.
[35]焦李成.神经网络系统理论.西安：西安电子科技大学出版社,1996.
[36]杨行峻,郑君里.人工神经网络.北京：高等教育出版社,1992.
[37]张立明.人工神经网络的模型及其应用.上海：复旦大学出版社,1993.
[38]潘正君,康立山,陈毓屏.演化计算.北京：清华大学出版社,广西科学技术出版社,1998.