求解动态路径诱导K路最短问题的人工免疫优化方法

针对智能交通诱导系统中传统最短K路算法的运行效果不佳,提出一种新型人工免疫优化搜索算法,并将其应用于扩展节点法建立的城市交通路网模型,实现了城市交通诱导系统的最优K路搜索. 该算法基于生物免疫系统的免疫记忆功能,具有全局性并行搜索的特点. 在K路最短问题求解时能同时给出K条最短路径,不存在遗传算法的早熟现象并具有更好的并行处理能力. 示例仿真验证了算法的有效性与实用性.     

基于空间方向关系的城市交通事故救援最佳路径算法

城市交通事故救援的最基本问题就是对出行路径的选择,其本质也就是最短路径的选择。本文通过对经典最短路径的算法进行分析与对比,总结了其各自的优缺点;介绍了空间方向关系的特性,利用方向关系在查询上具有的约束性,研究了基于空间方向关系的最短路径算法,这种算法克服了传统算法Dijkst-ra的盲目搜索,提高了最短路径算法的效率,并验证了此算法的有效性。     

动态限制搜索区域的带约束K则最优路径算法

为了有效解决分布式动态诱导系统中存在的拥挤漂移问题,有针对性地根据城市交通网络的空间分布特性提出了适合于导航用户使用的动态限制搜索区域的带约束K则最优路径算法。该算法基于MAPX控件编程实现,并采用VISSIM仿真软件进行了模拟和测试。实验结果表明:该算法一方面合理限制了路网的搜索规模、显著提高了路径优化算法的执行效率;另一方面又有效均衡了路网上的交通流,预防了拥挤漂移现象的发生,为个体出行者和整个交通系统带来效益。     

一种基于A*算法改进的最短路径搜索方法

无论是城市交通导航还是游戏人物导航,最短路径的有效搜索都是人们最为关注的部分。A~*算法是目前在导航方面较为有效的最短路径算法。对传统的A~*算法,A_ε算法,Alpha A~*算法以及添加启发式算法进行了对比分析,提出了一种改进方法 A~(*+)算法,即在原有算式上添加父节点启发式,并计算临界值筛选候选节点。实验结果表明,该方法节点排查能力明显优化,搜索效率得到提高。     

基于改进蚁群算法的动态多路径诱导系统研究

传统的动态路径诱导系统只能向出行者提供唯一一条最优路径,可能引起出行者的集聚反应,进而导致拥挤漂移问题的出现.本文提出了一种基于改进蚁群算法求解最短路径的方法,实现了动态路径诱导系统中最短路径的搜索.改进蚁群算法对信息素和启发信息进行标准化,消除量纲和取值范围的影响,引入方向函数作为新的启发式因子,使算法的收敛速度得到提高.仿真实验表明该方法收敛速度比较快,搜索结果比较合理、有效,能够满足动态路径诱导的实时性和快速性要求.     

一种基于K最短路径的QoS路由选择算法

针对多约束服务质量路由问题,提出了一种基于K最短路径路由选择算法QRBKP。该算法首先计算针对各约束度量参数的K最短路径,然后在所有的最短路径中选择满足多约束的QoS路由,其中最短路径数k根据各QoS约束自适应变化。基于此,本文提出了节点对之间的路由空间再分配技术和节点对内部的路由空间再分配技术,确保总的路由表空间不会超过设计路由空间。理论分析表明,QRBKP不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题。仿真结果表明:在求解QoS路由问题时,在相同的计算次数下,QRBKP算法比同类算法具有更高的路由计算成功率。     

基于多支路切除和背离路径的潮流转移识别算法

给出了一种基于多支路切除和路径搜索的潮流转移快速识别算法。该方法根据故障支路切除后的潮流转移特征,首先深入分析了转移到非故障线路上的潮流组成,其次在一定的节点深度内搜索切除支路两端节点间的前K条最短路径集,最终识别出受潮流转移影响较大的线路构成输电断面。文中在切除支路的潮流转移估算、K值选取和断面判据方面作了重要改进,以适应于发生多支路切除情况下潮流转移的识别;重新建立了一种K的取值方案,并采用背离路径算法确定最短路径集,在减少分析计算量的同时有效避免了输电断面漏选问题。IEEE30节点系统的仿真验证了本文算法的有效性。     

具有稀疏矩形障碍的近似迷宫算法

给出了一个在具有稀疏矩形障碍的迷宫中寻找给定的两个单元之间的最短路径的算法。本算法以“不改变方向”为预测条件，根据迷宫中各障碍与起讫单元之间的相对位置沿水平或竖直的方向进行直线扩展以缩小搜索范围并减少搜索时间。经大量的实例验证和实验对比，结果证明所给出的算法在障碍较少的情况下能够大幅度地缩小搜索范围并具有较高的精确度和较快的速度。     

在ITS中Dijkstra算法优化分析

网络搜索是一个经典的问题，在ITS（Intelligent Transportation System）中具有重要的意义。在ITS中，常常希望能在巨大的电子地图中搜寻一条最短路径。Dijkstra算法是一种经典的路径算法，但是这种算法的效率不高，不足以满足在真实交通网络图中搜索的实时响应的要求。于是，针对这种情况提出各种优化算法，提高经典Dijkstra算法的效率。介绍了几种通过缩小搜索范围来提高搜索效率的算法，并通过在虚拟交通网络中做了大量的实验来分析这几种算法。     

SDH虚级联中的最优化路径选择

虚级联技术的同步数字体系（SDH）网络中，虚级联组成员的选路将是一个完全非确定多项式（NP-complete）问题．为优化网络资源以及保证新加虚级联组的成员的相对延迟在系统允许的范围内，提出了双向约束路径优化算法（TSOP）．仿真结果表明, 该算法优于已有的k个最短路径算法和可改链路权重的k个最短路径算法．     

电力通信业务路由分配算法

针对电力通信网中重要通信业务集中于少数几条路径,提出了业务风险均衡K-shortest path算法.建立了电力通信节点、通道段风险度模型,并在此基础上提出了业务通道风险均衡度评价模型;采用改进的Dijkstra算法搜索K-shortest path作为候选路径,并基于最大最小模型进行风险均衡路由决策;通过仿真实验评价了业务风险均衡K-shortest path算法与已有算法的性能差异,验证了新算法的有效性.     

预防拥挤漂移的带约束K则最优路径算法

为解决城市交通流诱导系统中存在的拥挤漂移问题,对拥挤漂移现象的形成机理和预防机制进行了深入的分析,并有针对性地提出了适用于导航用户的带约束K则最优路径算法.算法基于MapX控件编程实现,并采用VISSIM仿真软件进行了分析模拟验证.模拟效果表明:该算法有效地预防了拥挤漂移现象的发生,给出行者和整个交通系统带来效益.     

NoC映射问题中的列举路径分配算法

映射和路径分配是片上网络在编译过程中两个相辅相成的重要步骤,对系统的通信功耗影响很大。该文针对片上网络映射过程中现有路径分配法寻径不充分的问题,提出了一种基于列举的路径分配算法。该算法通过列举各通信流的所有合法路径,对路径的各种组合方式进行充分搜索。同时将路径分配算法应用到禁忌搜索映射算法中,并对映射算法做了改进,以适应路径分配算法。仿真结果表明,基于列举的路径分配算法提高了满足约束的路径被搜索到的概率,优化了映射算法的结果。     

城市交通信号免疫自适应控制

针对城市交通流具有较强的时变特性,传统控制方法控制效果不佳的问题,借鉴免疫系统自学习、自适应原理,提出一种城市交通信号免疫自适应控制方法,该方法采用免疫网络记忆控制过程中获得的控制经验,采用克隆选择算法进行绿信时间的全局优化,通过采用知识引导下的在线学习模式,实现了快速在线自适应控制.仿真结果表明该方法可以获得较好交通信号实时控制效果.     

动态并行路径流量工程的可实现性研究

利用遗传算法研究动态并行路径流量工程的实现方法和可实现性。首先给出了并行路径流量工程理论最优解的求解方法,并对其运算成本和运算结果在工程上的不可实现性进行了分析和验证;进而采用简洁、典型的分流方案,对已有的理论最优解进行局部近似,并基于这些分流方案从全局的角度设计遗传算法,达到了与理论最优解近似的优化效果,且运算量大为减小。通过仿真分析得出了在优化过程中需要对并行路径间的分流误差进行有效控制的结论。     

前N条最短路径问题的算法及应用

现有最短路径问题指的是狭义最短路径问题，针对该问题而设计的算法只能求得最短的一条路径。前N条最短路径拓宽了最短路径问题的内涵（即不仅要求得最短路径，还要求得次短、再次短…第N短路径），是广义最短路径问题，在图论理论基础上分析问题之后，设计了一个递归调用Dijkstra算法的新算法，该算法可以求取前N条最短路径，而且时间、空间复杂度都为多项式阶。该算法已经成功应用于一个交通咨询系统中，自然满足实时应用需要。     

应用改进的V-detector算法检测蠕虫

通过分析主机感染蠕虫后网络流量特性的变化，基于免疫系统的阴性选择机制，提出了一种蠕虫检测方法。首先改进了可变半径实值阴性选择算法V-detector，改进策略是在检测器生成过程中根据非自体空间的分布产生具有尽可能大覆盖范围的检测器。改进算法与原算法相比，所生成的检测器集合中检测器的数量大幅度下降，检测效率提高。应用改进的V-detector算法生成检测器集合监控主机的网络流量特性，以检测蠕虫攻击。实验结果表明，该方法能有效检测传统蠕虫及多维传播的多态蠕虫。     

基于时延和跳数的Ad hoc网络流量分配算法

提出一种基于时延和跳数的Ad hoc网络流量分配算法。该算法根据每个链路的时延和跳数进行流量分配,采用动态分配流量的方法来实现流量的均衡,优化网络资源的利用。仿真结果表明,该算法可动态调整每个链路之间的流量分配,使网络资源占用达到最小。