A hill-jump algorithm of Hopfield neural network for shortest path problem in communication network

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.     

基于混沌神经网络的最短路径路由算法

将最短路径问题映射到混沌神经网络，提出了一种带有混沌噪音的神经网络最短路径路由算法。首先设计了与最短路径有关的网络费用和路径表达方法；其次结合混沌神经网络的数学模型建立神经元的运动方程；最后依据网络费用和约束条件构造神经网络的能量函数。分别在具有9个结点和15个结点的网络拓扑结构上进行了实验，单个和多个分组请求均能快速地找到最短路径。结果表明，该文提出的最短路径路由算法用于高速交换网络是有效可行的。     

Neural networks for shortest path computation and routing incomputer networks

The application of neural networks to the optimum routing problem in packet-switched computer networks, where the goal is to minimize the network-wide average time delay, is addressed. Under appropriate assumptions, the optimum routing algorithm relies heavily on shortest path computations that have to be carried out in real time. For this purpose an efficient neural network shortest path algorithm that is an improved version of previously suggested Hopfield models is proposed. The general principles involved in the design of the proposed neural network are discussed in detail. Its computational power is demonstrated through computer simulations. One of the main features of the proposed model is that it will enable the routing algorithm to be implemented in real time and also to be adaptive to changes in link costs and network topology.     

基于累积竞争神经网络的多约束路由算法

针对无约束最优路径问题，提出累积竞争神经网络模型及其搜索算法，该算法具有高度并行性、能获得最优解、结构简单等特点．以QoS路由选择为例，将算法推广到多约束路由问题．实验结果表明，对于大多数多约束QoS问题，在与相应最短路径上节点数目相当的迭代次数内，该算法能找到问题的满意解甚至最优解．     

最短路径的独立变量神经网络算法

将有向图中的每条边对应一个决策变量,在求解两点间的路径时,这些决策变量满足基尔霍夫约束关系。决策变量可以分为独立的和不独立的两部分,分别对应独立变量神经网络和不独立变量神经网络的状态,这些神经网络的状态代表了最短路径的解。不独立变量神经网络的状态由独立变量神经网络的状态线性组合而成,给出了独立变量神经网络方程。     

基于OpenStreetMap最短路径算法的分析与实现

随着计算机网络技术和地理信息科学的发展,最短路径问题无论是在交通运输,还是在城市规划、物流管理、网络通讯等方面,都发挥了重要的作用。文中旨在阐述如何基于OSM运用Dijkstra算法计算两联通节点之间的最短路径。首先介绍了开放式OSM的特点以及地图数据文件中道路图像元素的数据结构;然后运用正则表达式算法从OSM数据中提取出交通道路信息,并选择合适的结构进行存储;最后通过将道路信息抽象成路径拓扑图,并以道路的地理距离作为路径权值,运用Dijkstra最短路径算法求解出两连通节点之间的最短路径。     

Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks

Due to mobility of wireless hosts, routing in mobile ad-hoc networks (MANETs) is a challenging task. Multipath routing is employed to provide reliable communication, load balancing, and improving quality of service of MANETs. Multiple paths are selected to be node-disjoint or link-disjoint to improve transmission reliability. However, selecting an optimal disjoint multipath set is an NP-complete problem. Neural networks are powerful tools for a wide variety of combinatorial optimization problems. In this study, a transient chaotic neural network (TCNN) is presented as multipath routing algorithm in MANETs. Each node in the network can be equipped with a neural network, and all the network nodes can be trained and used to obtain optimal or sub-optimal high reliable disjoint paths. This algorithm can find both node-disjoint and link-disjoint paths with no extra overhead. The simulation results show that the proposed method can find the high reliable disjoint path set in MANETs. In this paper, the performance of the proposed algorithm is compared to the shortest path algorithm, disjoint path set selection protocol algorithm, and Hopfield neural network (HNN)-based model. Experimental results show that the disjoint path set reliability of the proposed algorithm is up to 4.5 times more than the shortest path reliability. Also, the proposed algorithm has better performance in both reliability and the number of paths and shows up to 56% improvement in path set reliability and up to 20% improvement in the number of paths in the path set. The proposed TCNN-based algorithm also selects more reliable paths as compared to HNN-based algorithm in less number of iterations.     

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

Network design techniques using adapted genetic algorithms

In recent years we have evidenced an extensive effort in the development of computer communication networks, which have deeply integrated in human being's everyday life. One of important aspects of the network design process is the topological design problem involved in establishing a communication network. However, with the increase of the problem scale, the conventional techniques are facing the challenge to effectively and efficiently solve those complicated network design problems. In this article, we summarized recent research works on network design problems by using genetic algorithms (GAs), including multistage process planning (MPP) problem, fixed charge transportation problem (fc-TP), minimum spanning tree problem, centralized network design, local area network (LAN) design and shortest path problem. All these problems are illustrated from the point of genetic representation encoding skill and the genetic operators with hybrid strategies. Large quantities of numerical experiments show the effectiveness and efficiency of such kind of GA-based approach.     

Neural network for optimal steiner tree computation

Hopfield neural network model for finding the shortest path between two nodes in a graph was proposed recently in some literatures. In this paper, we present a modified version of Hopfield model to a more general problem of searching an optimal tree (least total cost tree) from a source node to a number of destination nodes in a graph. This problem is called Steiner tree in graph theory, where it is proved to be a NP-complete. Through computer simulations, it is shown that the proposed model could always find an optimal or near-optimal valid solution in various graphs.     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks     

A discrete-time recurrent neural network for shortest-path routing

Presents a discrete-time recurrent neural network, with a fixed step parameter, for solving the shortest path problem. The proposed discrete-time recurrent neural network with a simple architecture is proven to be globally convergent to exact optimal solutions and is suitable for hardware implementation. Furthermore, an improved network with a larger step size independent of the problem size is proposed to increase its convergence rate. The performance and operating characteristics of the proposed neural network are demonstrated by means of simulation results.     

基于城市道路网的最短路径分析解决方案

近年来GIS对网络分析功能的需求迅速增长．网络分析中的一个关键问题是最短路径问题，它作为许多领域中速择最优问题的基础，在交通网络分析系统中占有重要地位．由于最短路径分析常用于汽车导航系统以及各种城市应急系统(如l10报警、l19火警以及120急救系统)，本文针对城市道路网的特点，提出了一种实用、高效的最短路径分析解决方案．     

Primal and dual neural networks for shortest-path routing

Presents two recurrent neural networks for solving the shortest path problem. Simplifying the architecture of a recurrent neural network based on the primal problem formulation, the first recurrent neural network called the primal routing network has less complex connectivity than its predecessor. Based on the dual problem formulation, the second recurrent neural network called the dual routing network has even simpler architecture. While being simple in architecture, the primal and dual routing networks are capable of shortest-path routing like their predecessor     

基于数据库中间件与GIS实现的最短路径算法

地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等,而最短路径分析是其中关键的环节,因而对其算法进行优化很有必要,为此在传统的最短路径算法,即Dikstra算法的基础上,采用关系数据库的存储机制,实现对最短路径查询,不但降低了系统的开销,而且较好地解决空间数据访问的并发控制问题和数据安全性问题。通过具体案例分析表明,该方法是有效可行的。     

A new algorithm for packet routing problems using chaotic neurodynamics and its surrogate analysis

We propose a new algorithm for routing packets which effectively avoids packet congestion in computer networks. The algorithm involves chaotic neurodynamics. To realize effective packet routing, we first composed a basic method by a neural network, which routes packets with shortest path information between two nodes in the computer network. When the computer network has an irregular topology, the basic routing method does not work well, because most of packets cannot be transmitted to their destinations due to packet congestion in the computer network. To avoid such an undesirable problem, we employed chaotic neurodynamics to extend the basic method. Numerical experiments show that our proposed method exhibits good performance for scale-free networks. We also analyze why the proposed routing method is effective, comparing the proposed method with several stochastic methods. We introduced the method of surrogate data, a statistical hypothesis testing which is often used in the field of nonlinear time-series analysis. Analysis of the proposed method by the method of surrogate data reveals that the chaotic neurodynamics is most effective to decentralize the packet congestion in the computer network.     

基于重填化学反应优化解决无线网络动态最短选路优化问题

采用人工智能优化技巧轻易解决静态最短选路(SP)优化问题,但是随着无线通讯的发展,诸如移动Ad Hoc网络与无线传感网络等新式无线网络被大量广泛使用.在这些新式无线网络中,网络拓扑随着时间而不断变化从而导致最短选路优化问题被转变成动态优化问题.提出了一种新式的基于化学反应优化(CRO)的算法来解决这个问题.化学反应优化...     

A neural network for shortest path computation

This paper presents a new neural network to solve the shortest path problem for inter-network routing. The proposed solution extends the traditional single-layer recurrent Hopfield architecture introducing a two-layer architecture that automatically guarantees an entire set of constraints held by any valid solution to the shortest path problem. This new method addresses some of the limitations of previous solutions, in particular the lack of reliability in what concerns successful and valid convergence. Experimental results show that an improvement in successful convergence can be achieved in certain classes of graphs. Additionally, computation performance is also improved at the expense of slightly worse results.     

一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法

类脑处理器能够支持多种脉冲神经网络SNN的部署来完成多种任务。片上网络NoC能够用较少的资源和功耗解决片上复杂的互连通信问题。现有的类脑处理器多采用片上网络来连接多个神经元核,以支持神经元之间的通信。SNN在时间步内瞬时突发的通信会在短时间内产生大量的脉冲报文。在这种通信行为下,片上网络会在短时间内达到饱和,造成网络拥塞。片上网络中非拥塞感知路由算法会进一步加剧网络拥塞状态,如何在每一个时间步内有效处理这些数据包,从而降低网络延迟,提高吞吐率,成为了目前需要解决的问题。首先对SNN的瞬时猝发通信特性进行了分析;然后提出一种拥塞感知的哈密尔顿路径路由算法,以降低NoC平均延迟和提高吞吐率;最后,使用Verilog HDL实现该路由算法,并通过模拟仿真进行性能评估。在网络规模为16×16的2D Mesh结构的片上网络中,相对于没有拥塞感知的路由算法,在数量猝发模式和概率猝发模式下,所提出的拥塞感知路由算法的NoC平均延迟分别降低了13.9%和15.9%;吞吐率分别提高了21.6%和16.8%。     

A novel solution for maze traversal problems using artificial neural networks

In this paper we have addressed the problem of finding a path through a maze of a given size. The traditional ways of finding a path through a maze employ recursive algorithms in which unwanted or non-paths are eliminated in a recursive manner. Neural networks with their parallel and distributed nature of processing seem to provide a natural solution to this problem. We present a biologically inspired solution using a two level hierarchical neural network for the mapping of the maze as also the generation of the path if it exists. For a maze of size S the amount of time it takes would be a function of S (O(S)) and a shortest path (if more than one path exists) could be found in around S cycles where each cycle involves all the neurons doing their processing in a parallel manner. The solution presented in this paper finds all valid paths and a simple technique for finding the shortest path amongst them is also given. The results are very encouraging and more applications of the network setup used in this report are currently being investigated. These include synthetic modeling of biological neural mechanisms, traversal of decision trees, modeling of associative neural networks (as in relating visual and auditory stimuli of a given phenomenon) and surgical micro-robot trajectory planning and execution.