双向半序网在两点间最优路径算法中的应用

最优路径搜索是地理信息系统重要的网络分析功能,也是其他网络分析功能的基础。该文在分析最优路径算法的基础上,针对特定两点间的最优路径问题,提出一种双向最优半序网结构,通过双向搜索构建该种双向最优半序网,可快速解得指定两点间所有满足最优条件的路径,并给出相应算法。结合计算实例分析并评价了该算法的运行效率。     

基于改进A*算法的移动机器人路径规划研究

A*算法广泛应用于移动机器人路径规划中，而传统A*算法在寻路时，普遍存在搜索时间较长、效率低下等问题，因此，采用双向搜索的方式，对传统A*算法加以改进，该算法在路径规划过程中，可同时进行正反向路径搜索，同时采用正反向搜索交替机制，保证了最终目标节点搜索在连线中点区域内相遇，从而缩短了寻路计算时间。在MATLAB平台上，针对改进后的A*算法进行仿真实验，结果证明，双向A*算法减少了规划时间，且可生成最优路径。最后，将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上，进行现场实验，实验结果表明，双向A*算法减少了寻路计算时间，从而使得路径搜索效率得到显著提升，且规划路径合理，满足路径规划要求。     

一种基于道路网络层次拓扑结构的分层路径规划算法

鉴于平面最短路径算法应用于大规模网络规划中的效率不高,而分层算法引入"分而治之"策略,则能有效解决此难题。为了利用分层算法进行路径规划,首先研究了分层算法的数据基础——道路网络层次拓扑结构,其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型;接着提出了一种适用于LBS(基于位置的服务)的分层路径规划算法。该算法先通过距离值判断是否切换到上一层;然后利用启发式A*算法搜索入口和出口;最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明,该算法能从本质上提高大规模网络中路径规划的效率。     

基于改进遗传模拟退火算法的WSN路径优化

针对无线传感器网络路径优化问题,提出了一种改进的最优保存的遗传模拟退火算法。利用LEACH算法构建初始路由表,使用GASA的高效率搜索,将路由计算和遗传演化计算同时进行,并直至寻找到近似最优路径为止。将最优保存遗传算法和模拟退火算法相结合,引入自适应的概率变化,有效地解决了这两种算法的早熟现象和时间问题。仿真实验表明,该算法有效地解决了无线传感器路径优化问题,具有定位准确、节能和搜索能力较强等优点。     

考虑同时取送和时间窗的车辆路径及求解算法

针对带时间窗的同时取送货车辆路径问题（vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW），构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型，提出自适应头脑风暴算法（adaptive brain storm optimization,ABSO）进行求解。全局搜索阶段，采用多项惩罚方式扩大搜索区域，并使用聚类及三种路径搜索策略进行全局搜索；局部搜索阶段，将六种破坏-修复算子作为备选集合，进而设计自适应动态选择邻域搜索机制，增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试，实验结果表明针对小规模标准算例，所提算法全部取得了当前已知最优解；对于大规模标准算例，通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比，所提算法实验计算结果有7.52%～12.03%的提升；对于实际案例，所提算法在收敛速度和寻优能力方面均展示出优越性，充分验证了所提算法对解决VRPSPDTW问题的有效性。     

QoS多约束优化路径选择算法

针对HMCOP算法在QoS多约束最优路径选择中存在产生累积误差,搜索范围不全面 的缺点,提出了一种改进的算法LMS,使用BFS算法双向搜索网络拓扑,在每个节点实时监测最优路 径。最优路径成功率的仿真实验表明,该算法有更低的时间复杂度和更高的性能表现。     

网络的粒度存储及在路径搜索中的应用

网络路径搜索是图论中的经典问题,对于大规模网络的最短路径搜索问题是人工智能领域研究热点问题。应用粒计算方法求解问题的思路实现网络的粒度存储,讨论不同基本类型的网络粒化,提出分层递阶商空间链实现网络的粒度存储。就大规模网络,提出社团作为基本粒的网络快速分割方法,实现网络的粒度存储。并将网络的粒度存储的分层递阶商空间链信息作为路径搜索前的预处理工作,提出一种启发式路径搜索方法。通过实验与启发式算法进行对比,验证了该算法的有效性。     

面向UAV的三维空间快速路径规划算法

无人机、无人水下机器人等工作在三维空间中的无人飞行器在进行路径规划时采用的路径规划算法多数为RRT*算法，但RRT*算法存在收敛速度较慢、迭代次数多、采样点利用率低、需要频繁进行碰撞检测等问题，针对现有算法采样的不足，提出双向自由化生长树算法（B-SOGT*）。该算法采用双向搜索、双引力场、试探性弹性扩张的方法来实现无人机在三维空间中的路径规划。双向搜索分别以起始点和目标点为根节点，构造出2棵随机树同时进行空间搜索，这样的方式提高了搜索效率；双引力场是分别以2颗随机树的根节点为中心生成的引力场，在引力场的作用下采样效率得到提升；试探性弹性扩张方法在生成路径时，引入父节点重选机制，并且去掉碰撞检测过程，提高了算法计算速度。仿真验证表明，B-SOGT*算法在取消碰撞检测过程后，拥有收敛速度更快、路径质量更优、迭代次数更少的优势。     

基于k-shell的复杂网络最短路径近似算法

复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于[k]-shell的复杂网络最短路径近似算法。算法利用节点的[k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。     

基于信息素负反馈的超启发式蚁群优化算法

针对蚁群算法应用于自动导引小车路径规划收敛速度慢、极易陷入局部最优的缺点，提出一种基于信息素负反馈的超启发式蚁群优化（ACONhh）算法。该算法充分利用历史搜索信息和持续获得错误经验，较快引导蚁群探索最优路径；分层化选择可行节点，加快算法初期收敛速度；设置挥发因子呈类抛物线变化以及调整信息素更新机制，改善路径全局的随机搜索特性。通过严格的数学方式证明了ACONhh算法具有收敛性。仿真和实验结果表明，该算法的收敛速度以及全局搜索性能显著优于目前流行的ACO、ACOhh和ACOihh算法。     

基于方向优先和对向搜索的改进Dijkstra算法

传统Dijkstra算法在搜索最短路径时需要逐一遍历网络图中所有顶点,计算量大,占用存储空间大,搜索效率很低。因此,针对交通网络的空间特性和传统算法的不足,改进存储结构,采用“方向优先+对向搜索”相结合的搜索方法,以减少存储空间,缩小搜索范围,从而加快搜索速度,提高算法的搜索效率。实验数据表明：与传统算法相比,改进的算法能够更有效地搜索交通网络中的最短路径,具有更好的实用价值。     

基于关键路径链和PACGA的网络总线资源调度方法研究

针对传统工业控制网络总线资源调度算法在节点数量逐渐增加时收敛速度慢和搜索精度不高,且准确度及效率低等问题,提出了一种基于关键路径链和多态蚁群遗传算法(PACGA)的资源调度方法,采用关键路径链的调度算法获取需求调度的节点,不同节点间采用多态蚁群遗传算法进行资源的调度,依据照工业控制网络资源调度的特征,用自适应调整挥发系数增强节点的全局搜索性能,通过候选节点集方法缩小搜索区域提高算法的搜索效率,完成工业控制网络总线资源的高效调度;仿真实验说明,该种方法在工业控制过程中任务数量较多的情况下仍然具备较高的运行效率和精度,并且具有较低的运行时间,具有较强的应用价值。     

基于分层法的通风网络图绘制算法研究

最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径,采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中;且采用几何相交方法判断分支交叉,效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层,求解整数规划问题优化节点分层减少长边;采用模拟退火遗传算法优化节点排序,从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程,采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。     

APF-guided adaptive immune network algorithm for robot path planning

Inspired by the mechanism of Jerne’s idiotypic network hypothesis, a new adaptive immune network algorithm (AINA) is presented through the stimulation and suppression between the antigen and antibody by taking the environment and robot behavior as antigen and antibody respectively. A guiding weight is defined based on the artificial potential field (APF) method, and the guiding weight is combined with antibody vitality to construct a new antibody selection operator, which improves the searching efficiency. In addition, an updating operator of antibody vi-tality is provided based on the Baldwin effect, which results in a positive feedback mechanism of search and accelerates the convergence of the immune network. The simulation and experimental results show that the proposed algorithm is characterized by high searching speed, good convergence performance and strong planning ability, which solves the path planning well in complicated environments.     

一类标准矩形网络节点间最短路径的求解方法

针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络. 与常见的求取最短路径的Dijkstra、Floyd、ACO、A* 等算法进行仿真实验比较, 实验结果表明, 对于大规模标准矩形道路网络, 所提出算法具有更好的寻优精度、稳定性和寻优速度.

     

基于语义路径的XML签名

针对现有的XML签名对特定细粒度信息查找困难和签名速度慢的问题,提出一种基于语义路径提取信息的变换算法,此语义路径通过构建XML索引结构得到。运用该算法查找细粒度信息方便快捷。对语义路径和信息的签名提高了XML签名的效率和灵活性,保证了数据的安全和良好的文档结构。     

基于分块路径缓存的在线路径搜索算法

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法。对路网重采样得到路网密集度图像,提出路网分块算法ISODATA。根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法。实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s以内,降低网络地图服务路径计算服务器负荷。     

遗传算法在网络优化问题中的研究

针对城市交通网络优化问题的实际意义,本论文以TSP为背景构建了网络路径搜索优化的模型,并采用遗传算法改进了算子设计,给出了完整的算法执行步骤,其仿真测试结果也表明了该算法在网络优化中具有良好的搜索性能,对于进一步研究遗传算法在网络优化问题中的实际应用具有一定借鉴意义。     

并行最短路径搜索算法的设计与实现

针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O（N²）减少到O（N²/p+N*（p-1））,提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。