基于简化DPCNN的最短路径算法＊
张煜东1 吴乐南1 王水花1 段 力2 Neggaz Nabil3
【摘 要】摘 要 传统求解最短路径(SP)问题的方法一般有组合技术与代数方法2大类,但算法复杂度的指数上界为2.376,不能实时对大规模SP问题进行求解。文中提出1种简化的时延脉冲耦合神经网络(SDPCNN)模型,可1次求解源点到其他所有点的最短路径,算法时间复杂度仅有O(n).实验证实了这一模型的有效性,且计算时间仅为未简化模型的5%～10%。 【期刊名称】交通信息与安全 【年(卷),期】2010(028)001 【总页数】4
【关键词】关键词: 时延脉冲耦合神经网络;最短路径;并行算法
引 言
最短路径问题(SP)是指在1个给定的网络中寻找1条从特定源点到特定目的点的最短路线。它是1个组合优化的原型问题,在很多领域有广泛应用,如运输系统中的道路选择问题[1],机器人系统中的路径规划问题[2],以及通信网络中的路由选择问题[3]等。如果改变路径的权值,则SP问题可以有很多变化形式,如最快路径问题,最廉价路径问题等[4]。
解决SP问题的经典方法可分为组合技术和代数方法2种。组合技术主要是指标号算法(labeling algorithm s)。按照不同的标识节点处理策略,可分为标号设定(LS)和标号改正(LC)2大体系。其中著名的Dijkstra算法就是研究最深入、应用最广泛的LS算法。代数方法通过运筹学中的线性规划、联立方程、矩阵相乘等形式来求解[5]。一般地,算法 复杂度为 O(nω),ω=2.376[6]。但随着计算机
处理数据量的逐渐增多,传统的串行计算机的负荷也逐渐加重。SP算法必须向并行算法发展,以满足大量的实时SP查询的需要[7]。
考虑到脉冲耦合神经网络(PCNN)具有大规模并行处理、容错性,自组织、自适应、无需预先训练等优点,Caulfied[8]提出用其求解最短路径,优势在于:①神经网络的天然并行性,非常适合用集成电路实现;②PCNN无须训练,可以直接使用。缺点在于神经元数量巨大,不易实现。其后,为解决神经元数量问题,顾晓东[9]提出延时脉冲耦合神经网络(DPCNN),纪其进[10]提出mPCNNSP,两者均采用了延时概念,并且由于PCNN的并行处理,可以在O(2n)的时间内寻找到最短路径[10],其时间优势是传统串行方法所无法比拟。
本文在DPCNN的基础上提出1种简化模型,称为SDPCNN,可大幅减少每个神经元的计算量,更快地解决SP问题。
原 理
首先对神经网络与真实网络相同意义的术语进行比较,见表1。
可见,用脉冲耦合神经网络来求解SP问题的原理如下:用脉冲(即自动波)表示旅行者,神经元代表真实节点,整个神经网络就构成了真实的交通网络。 让我们来假想旅行者寻找最优路径的情况:
1)当旅行者来到1个交叉路口,他不知道该如何选择下1条路径,1个较好的办法是原地做下记号,然后力图走遍每条路径。然而,脉冲可以轻易解决这个问题。它能够“复制”自身,然后命令每个复制品选择1条路径前进。
2)当旅行者走到1个死胡同,他希望能够返回到上1个交叉路口,重新选择路径。然而,在计算机世界,脉冲可以迅速“自杀”,因为必定在上1个交叉路口有其他复制品搜索其他路径。
可见,采用脉冲来代替旅行者,是PCNN求解SP问题的关键。我们利用PCNN在计算机上实现类人化。
简介
由于直接采用PCNN求解SP问题会遭遇神经元数目爆炸等问题,因此一般采用延时PCNN,本质是利用时间换取空间。
图1显示了 1个DPCNN神经元的基本结构,分为4个部分:延时器D、树状结构(dendritic tree)、连接调制器和脉冲发生器。树状结构可分为馈送输入F与连接输出L,L经过偏置β后与F相乘,得到内部活动项U。最后脉冲发生器比较和动态阈值θ的大小,选择触发1个脉冲或者不触发。最后重新调整阈值θ,等待下1次被触发。如此循环往复,直到与该神经元相连的神经元均被触发。 描述整个PCNN运行过程的离散方程为:
DPCNN能够寻找最优解的原理在于脉冲能够在神经元之间传播。在求解过程中,源点首先被触发,所产生的脉冲通过L通道增加了与其相连的其它神经元的内部活动项U,因此在经过延时器D后,这些神经元相继被触发。从而形成了神经元间的脉冲传递通道,脉冲在通道间并行地搜索所有路径。具体请参见文献[9-10]。
求解 问题
仔细分析DPCNN,我们认为可作进一步简化,取消F通道和β偏置,并令其内部活动项U=L,同时令动态阈值θ始终为0,这样既保证了脉冲的产生和传递,又避免了DPCNN中的指数衰减过程。这些指数衰减恰恰是最耗费时间的。 图2显示了SDPCNN神经元结构,其中延时D uv=λωuv,与路径长度成正比。SDPCNN运行过程如下:当某个神经元被激活后,脉冲通过延时器向周围神经元
基于简化DPCNN的最短路径算法
