Lotka-Volterra recurrent neural network model for solving shortest path

doi:10.3724/SP.J.1087.2012.01965

Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (07): 1965-1968.DOI: 10.3724/SP.J.1087.2012.01965

• Artificial intelligence • Previous Articles Next Articles

Lotka-Volterra recurrent neural network model for solving shortest path

ZHENG Bo-chuan¹,²,SANG Yong-sheng³

1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 610054, China
2. College of Mathematics and Information, China West Normal University, Nanchong Sichuan 637002, China
3. College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China

Received:2011-12-31 Revised:2012-02-12 Online:2012-07-05 Published:2012-07-01
Contact: ZHENG Bo-chuan

求解最短路径问题的Lotka-Volterra回复式神经网络模型

郑伯川¹,²,桑永胜³

1. 电子科技大学计算机科学与工程学院，成都610054
2. 西华师范大学数学与信息学院，四川南充637002
3. 四川大学计算机学院，成都610065

通讯作者: 郑伯川
作者简介:郑伯川(1974-)，男，四川自贡人，副教授，博士研究生，主要研究方向：神经网络、计算机图形图像；桑永胜(1974-)，男，四川江油人，讲师，博士，主要研究方向：神经网络、物联网。
基金资助:
四川省教育厅资助科研项目（12ZA172）;西华师范大学校重点基金资助项目（10A003）

Abstract

Abstract: The Shortest Path (SP) problem of the directed graph is an optimization problem. By constructing the energy function for the shortest path problem of the directed graph, a Lotka-Volterra (LV) Recurrent Neural Network (RNN) model was proposed to solve the shortest path problem of the directed graph. When the LV RNN converged to its stable attractor, the corresponding energy function also reached its energy minimum point. Therefore, the shortest path of the directed graph could be obtained through the stable attractor of the LV RNN. The experimental results verify that the shortest path between any two vertices in the directed graph can be obtained efficiently by using the LV RNN model.

Key words: Lotka-Volterra (LV) Recurrent Neural Network (RNN), energy function, Shortest Path (SP), stable attractor, energy minimum point

摘要： 有向图的最短路径(SP)问题是一个优化问题。通过构造有向图的最短路径问题的能量函数，提出了一种Lotka-Volterra (LV)回复式神经网络(RNN)模型，用于求解有向图的最短路径。当LV神经网络迭代收敛到稳定吸引子时，对应的能量函数也达到其能量最小点。因此，通过稳定吸引子可以获取最短路径。实验结果表明，利用LV神经网络模型可以有效地求解有向图中任意两个顶点之间的最短路径。

关键词: Lotka-Volterra回复式神经网络, 能量函数, 最短路径, 稳定吸引子, 能量最小点

CLC Number:

TP183

ZHENG Bo-chuan SANG Yong-sheng. Lotka-Volterra recurrent neural network model for solving shortest path[J]. Journal of Computer Applications, 2012, 32(07): 1965-1968.

郑伯川桑永胜. 求解最短路径问题的Lotka-Volterra回复式神经网络模型[J]. 计算机应用, 2012, 32(07): 1965-1968.

References

［1］ HOPFIELD J J, TANK W. Neural computation of decisions in optimization problems ［J］. Biological Cybernetics, 1985, 52(3): 141-152.

［2］ THOMOPOULOS S C A, ZHANG L, WANN C D. Neural network implementation of the shortest path algorithm for traffic routing in commu-nication network ［C］// IJCNN'91: IEEE International Joint Conference on Neural Networks. Piscataway: IEEE, 1991: 2693-2702.

［3］ ALI M, KAMOUN F. Neural networks for shortest path computation and routing in computer networks ［J］. IEEE Transactions on Neural Networks, 1993, 4(6): 941-954.

［4］ WANG J. A recurrent neural network for solving the shortest path problem ［J］. IEEE Transactions on Circuits Systems I: Fundamental Theory and Applications, 1996, 43(6): 482-486.

［5］朱大铭，马绍汉.神经网络求解图最短路径问题的一种新方法［J］.软件学报，1996，7(zk): 191-198.

［6］ QU H, ZHANG Y. A new algorithm for finding the shortest paths using PCNNs ［J］. Chaos, Solitons and Fractals, 2007, 33(4): 1220-1229.

［7］ SANG Y, ZHANG Y. A modified pulse coupled neural network for shortest path computation ［J］. Journal of Computational Information Systems, 2010, 6(9): 3095-3102.

［8］纪其进.一种基于脉冲耦合神经网络的最短路径算法［J］.小型微型计算机系统，2005，26(5)：826-829.

［9］ FUKAI T, TANAKA S. A simple neural network exhibiting selective activation of neuronal ensembles: from winner-take-all to winner-share-all ［J］. Neural Computation, 1997, 9(1): 77-97.

［10］ ZHANG Y, TAN K K. Dynamical stability conditions for Lotka-Volterra recurrent neural networks with delays ［J］. Physical Review E, 2002, 66(1): 011910.

［11］ ASAI T, FUKAI T, TANAKA S. A subthreshold MOS circuit for the Lotka-Volterra neural network producing the winner-take-all solutions ［J］. Neural Networks, 1999, 12(2): 211-216.

［12］ ASAI T, OHTANI M, YONEZU H. Analog integrated circuits for the Lotka-Volterra competitive neural networks ［J］. IEEE Transactions on Neural Networks, 1999, 10(5): 1222-1231.

［13］ ZHANG Y. Foundations of implementing the competitive layer model by Lotka-Volterra recurrent neural networks ［J］. IEEE Transactions on Neural Networks, 2010, 21(3): 494-507.

［14］ ZHENG B, ZHANG Y. A method for MRI segmentation of brain tissue ［C］// Proceedings of the 7th International Conference on Advances in Neural Networks, LNCS 6064. Berlin: Springer-Verlag, 2010: 378-384.

［15］ ZHENG B, ZHANG Y. Extracting long contour by using the competitive layer model of the Lotka-Volterra recurrent neural networks ［C］// 2010 International Conference on Advanced Computer Theory and Engineering. Piscataway: IEEE, 2010: V3627-V3631.

［16］ ZHENG B, ZHANG Y. Some properties of the competitive layer model with application to object regions extraction ［C］// 2010 International Conference on Communications, Circuits and Systems. Piscataway: IEEE, 2010: 491-495.

[1]	JIAO Hailin, GUO Yuying, ZHU Zhengwei. Acceleration compensation based anti-swaying flight control for unmanned aerial vehicle with slung-load [J]. Journal of Computer Applications, 2021, 41(2): 604-610.
[2]	YU Yongbin, QI Minhui, Nyima Tashi, WANG Lin. Association rule mining algorithm for Hopfield neural network based on threshold adaptive memristor [J]. Journal of Computer Applications, 2019, 39(3): 728-733.
[3]	CAI Xingquan, SUN Chen, GE Yakun. Mesh parameterization method based on limiting distortion [J]. Journal of Computer Applications, 2019, 39(10): 3034-3039.
[4]	DING Feifei, YANG Wenyuan. Video object segmentation via information entropy constraint [J]. Journal of Computer Applications, 2018, 38(10): 2782-2787.
[5]	WANG Xingxing, LI Guocheng. Sparse signal reconstruction optimization algorithm based on recurrent neural network [J]. Journal of Computer Applications, 2017, 37(9): 2590-2594.
[6]	WANG Lei, HUANG Chenxue. Improved hierarchical Markov random field algorithm color image segmentation algorithm [J]. Journal of Computer Applications, 2016, 36(9): 2576-2579.
[7]	FAN Haiju, LIU Guoqi. Supervised active contour image segmentation by kernel self-organizing map [J]. Journal of Computer Applications, 2016, 36(10): 2832-2836.
[8]	ZHANG Lihong HE Shucheng. Fast convergent stereo matching algorithm based on sum of absolute difference and belief propagation [J]. Journal of Computer Applications, 2014, 34(3): 824-827.
[9]	Bin YANG Yuan-yuan FAN Ji-dong WANG. Computation of approximate geodesics on point cloud [J]. Journal of Computer Applications, 2011, 31(04): 1050-1052.
[10]	. Sudden violence identification algorithm based on motion feature [J]. Journal of Computer Applications, 2011, 31(02): 410-412.
[11]	. Human abnormal behavior identification algorithm based on time-spatial Markov random field [J]. Journal of Computer Applications, 2010, 30(8): 2238-2240.
[12]	. No-reference quality index for image blur [J]. Journal of Computer Applications, 2010, 30(4): 921-924.
[13]	. Polarized characteristics image segmentation based on minimum cut [J]. Journal of Computer Applications, 2010, 30(06): 1587-1589.
[14]	. Gait contour extraction based on improved snake model [J]. Journal of Computer Applications, 2007, 27(6): 1468-1471.

Lotka-Volterra recurrent neural network model for solving shortest path

求解最短路径问题的Lotka-Volterra回复式神经网络模型

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics