论文部分内容阅读
动态网络最短路径问题是网络优化的重要内容,传统的求解算法如Dijkstra算法、A*算法无法求解动态网络最短路径问题,而智能算法如遗传算法等迭代次数高、效率低下,为了更好的解决动态网络最短路径问题,我们尝试改进自动波神经网络算法来解决这一问题,论文的主要内容分为以下三个部分。(1)模糊网络最短路径问题的神经网络框架研究。为了解决模糊网络最短路径问题,给出了模糊期望最短路径问题的定义,提出了基于自动波神经网络的并行模糊神经网络最短路径(PFNNSP:Parallel Fuzzy Neural Network Shortest Path)算法,通过实例说明了PFNNSP算法的运行过程,在随机生成模糊网络上的仿真实验表明,PFNNSP算法的运行时间优于传统的Dijkstra算法,在国际数据集上的仿真实验表明,PFNNSP算法在迭代次数和收敛速度上优于Dijkstra算法和A*算法。(2)边权动态的时变最短路径问题的神经网络框架研究。为了解决边权动态的时变网络最短路径问题,给出了边权动态的时变期望最短路径问题的定义,通过公交车模型推导出了问题的形式化表示(这里假设边上的权值服从指数分布),提出了基于自动波神经网络的边权动态的时变神经网络(STDNN:Stochastic Time-dependent Neural Network)算法,考虑到算法设计的复杂性,在进行随机模拟时将网络中边上的权值看作服从指数分布,将随机权值转化为静态权值进行计算,实验结果表明,STDNN算法在求解边稠密边权动态的时变网络最短路径问题时效果明显优于DPA算法,在求解传统静态网络最短路径问题时,效率相差不大。(3)带时间窗的时变网络最短路径问题的神经网络框架研究。为了研究时变网络最短路径问题,给出了带时间窗的最短路径问题的定义,结合时变网络的特征设计了带时间窗的神经元,提出了基于自动波神经网络的时变神经网络(TDNN:Time-dependent Neural Network)算法,并且证明了最优解定理、自动波激活次数定理、TDNN算法优化定理,分析了TDNN算法的时间和空间复杂度,在小规模动态数据集上的仿真实验表明,TDNN算法的求解效率优于PCNN算法,在大规模静态数据集上的仿真实验表明,TDNN算法的运行时间优于传统的Dijkstra算法。