基于改进A^(*)算法的无人机避障航线规划

采用常规A^(*)算法进行无人机避障航线规划存在搜索节点多、区域大、时间长、效率低,生成的航线拐角多且含有大量非必要航线冗余点,以及未考虑无人机自身体积与尺寸导致在飞行中与障碍物边界碰撞等问题。为此,文中设计一种改进的A^(*)算法。首先考虑无人机自身体积与尺寸,提出一种消除边界碰撞事故的子节点扩展方法;其次,改进评价函数以减少往复搜索次数,减少搜索节点数量,提高搜索效率;然后,根据Floyd思想对生成的航线进行简化处理,消除航线中的冗余航路点,减少航线转角数量,达到简化航线并改善航线平滑度的效果;最后,基于改进的A^(*)算法对无人机避障航线进行非线性仿真。结果表明,改进的A^(*)算法生成的航线合理、安全,使无人机的飞行更加连续和顺畅。

轻量化FPGA布线路径搜索算法

针对FPGA布线耗时较长的问题,提出一种基于最优节点预测的轻量化FPGA布线路径搜索算法.该算法通过预测最优布线资源节点,在搜索最优布线路径时只对最优节点进行详细计算、分析,无须搜索其他节点,从而提高搜索速度;当轻量化搜索失败时,以全局最优节点为源点重新进行轻量化搜索,提高全局搜索能力;在寻找全局最优节点时,只对可能出现在最优路径上的次优节点进行详细计算分析,减少无效计算.使用VTR标准电路对所提算法和VPR 8.0进行测试,并从布线所需时间和结果质量2个方面进行比较.实验结果表明,与VPR 8.0中布线路径搜索算法相比,所提算法在保证布线结果质量基本不变的情况下,将搜索的布线资源节点数量减少41.8%,可节省31.3%的运行时间.

基于Dubins-双蚁群算法的搜潜航路规划

针对航空搜潜浮标距离近、偏航角较大的特点,提出Dubins路径和双蚁群算法相结合的航路规划算法。对比传统航路规划先确定直线航路再进行平滑处理的方式,所提算法在迭代寻路阶段将直线路径转化为Dubins路径,减少了转弯半径约束下无法抵达目标的风险;同时以Dubins距离作为判优基准,相比直线距离,更加接近全局最优;并且增加偏航距离扰动参数,引导蚂蚁选择直线距离和偏航角均较小的目标;发挥不同蚁群的信息素负反馈作用,促使寻找新路径,提升寻路能力。仿真结果表明,该算法加快了规划收敛速度,有效缩短了航路距离,缩短幅度平均达14.6%以上。

基于MMAS的机器人路径规划

文章针对移动机器人系统在复杂环境中搜索目标和寻求最短路径问题,介绍了一种基于MMAS的机器人路径规划新方法;在MMAS算法的信息素更新中,采用了最大-最小蚂蚁系统的思想动态调整信息素,加强了正反馈的效果,同时周游最优蚂蚁和全局最优蚂蚁路径信息的动态更新,在一定程度上增加了解的多样性,也提高了蚂蚁的搜索效率;在搜索过程中,采取随机搜索与重点搜索相结合的方式对路径进行搜索,有利于加快搜索较好的解,而动态调整各项参数后,陷入局部解的可能性大大减少,并且可以找到最优解;最后通过仿真证明了该算法的有效性。

两级定位—路径问题的路径重连变邻域搜索人工蜂群算法

为适应物流需求从少品种大批量到多品种少批量的转变,建立了两级定位—路径问题的数学模型,提出求解该问题的路径重连变邻域搜索人工蜂群算法,即在基本人工蜂群算法中嵌入近年来广泛应用于组合优化问题求解的两种启发式搜索策略——变邻域搜索和路径重连。采用Lingo求解小规模两级定位—路径问题;选取三组较大规模的两级定位—路径问题,分别采用基本人工蜂群算法、路径重连人工蜂群算法、变邻域搜索人工蜂群算法和路径重连变邻域搜索人工蜂群算法进行求解。结果表明,所建数学模型是正确的,所提算法不但能够取得更好的优化结果,而且具有更好的收敛性。

基于电子海图的最佳航线优化算法

自动化的航线设计有助于更好发挥电子海图的智能性,进一步提高航线的安全性、经济性和可靠性。首先,对电子海图进行栅格化处理并以不同的颜色值填充不同的碍航物,提取碍航物包围盒,在此基础上,求取一条基本绕障航线。运用elasticity算法进行优化,充分利用栅格间的邻接关系,自动搜索一条最短的安全航线。该算法具有稳定性好、算法简单、搜索效率高的优点。实验结果表明,该算法可应用于大面积复杂海域的航线规划和实时避障。

两约束路由问题的近似解法

首先回顾了一些重要的QoS路由算法,然后对关于两约束路由问题(BCP,bi-constraintpath problem)的线性搜索算法进行了数学分析,确定了搜索因子的范围和最佳搜索因子的值。基于以上分析,我们给出了BCP和单约束最短路径问题(RSP,restricted shortest path problem)的近似算法,并对算法性能进行了分析;最后,本文研究了采用非线性链路代价函数求解BCP。测试结果表明本文提出的算法是求解BCP和RSP的有效算法。

基于Dijkstra算法的矿井最佳避灾路线分类求取

为使矿井避灾路线有更好的适用性,探讨了矿井面临不同类型灾害危险时最佳避灾路线分类求取方法。根据不同灾变的特点,将矿井灾害分为突水灾害,煤与瓦斯突出、瓦斯或煤尘爆炸、矿井火灾,冒顶事故三大类;绘制三类灾害的可行避灾路线拓扑图,并计算各条巷道的当量长度;将巷道当量长度作为可行路线各边的权值代入拓扑图中,用最短路径算法Dijkstra算法求解各拓扑图对应的最佳避灾路线。分析结果表明,基于Dijkstra算法的矿井最佳避灾路线分类求取方法扩大了避灾路线的选取范围,在避灾人员较多时,可使巷道系统的通行能力得以充分发挥。

基于蚁群算法WDM网络故障恢复路由研究

蚁群故障恢复算法是一种新颖的模拟进化算法。该算法基于群以正反馈作为首要的搜索机制,为复杂的组合优化问题提供了一种新方法。本文在传统蚁群算法的选择策略,本地搜索,以及信息更新三方面做出改进。改进后的算法用于解决波分复用光网络中不同故障条件下的优化恢复路由问题。通过对一个典型网络CHINANET的数值仿真,证明了蚁群故障恢复算法在WDM网络中故障恢复路由的可行性。

一种新的城市交通路径搜索算法

针对我国城市交通道路实际情况,提出一种新的基于邻接矩阵的交通路径搜索算法,算法利用邻接矩阵的特点及其相乘原理,在n阶An-矩阵中找出交通中的"途径线路",结合道路上网络节点的相关权值,计算得出一条最佳交通路径。通过算法分析和仿真实验,结果表明,算法运行效率高,设计简单,实用性强。

广度优先寻路算法在手机游戏寻路中的应用

本文探讨了手机游戏开发中的一些寻路算法,提出了如何在手机中使用广度优先寻路算法在手机游戏寻路中的基本思路,使查找容易,实现最佳路径。

基于信息差异度蚁群算法的QoS路由算法

针对基本蚁群算法在求解QoS路由问题中存在的容易陷入局部最优和收敛速度慢的缺陷,提出一种基于信息差异度的蚁群算法对该问题进行求解。该算法在节点选择中嵌入路径信息素的差异度调节函数和迭代算子,动态调整节点选择策略;根据各路径上信息素的"集中"程度判断解的早熟、停滞情况,并引入路径变异和二次蚁群操作;根据最大-最小蚁群算法原理对信息素进行限制。仿真实验表明,算法全局搜索能力较强,能够跳出局部极值区间,快速收敛到全局最优解,算法是可行、有效的。

智能全电船的低能耗路径规划算法研究

针对以锂电池组作为电源的智能全电船路径规划,考虑包括海流、风和浪的复杂海洋环境对船舶能耗产生的很大影响以及锂电池组有限的能量,提出了一种以能耗最少为主要优化目标的路径规划算法。基于概率路图法构建全电船航行路线图;通过分析船舶在海流环境中的阻力模型,建立了全电船的能耗函数;提出了能耗最优的改进A*搜索算法,并且将该算法在不同的海流状态下进行了仿真试验。仿真结果表明,该算法相比于传统的以距离最优算法能够节省更多的能量,得出一条更加经济环保和实际可行的路径,有效地提高了智能全电船的续航能力。

一种时延约束最小代价路由选择算法

使用禁忌搜索方法寻找最优路径,将最小时延路径作为初始解,在满足时延约束的情况下根据禁忌搜索规则求解代价最小的路径。仿真实验证明DCLC_TSR算法具有代价性能良好、可靠性高、耗时少、收敛速度快的优越特点。

基于改进Dijkstra算法的进路搜索研究

进路搜索是计算机联锁的核心部分,其准确性及高效性对保证行车安全至关重要。建立铁路站场结构的有向图模型,将站场进路搜索问题转化为有向图的遍历问题;根据铁路站场简化图的特点,从数据存储结方式和队列结构2个方面改进传统Dijkstra算法,采用广度优先搜索方式,提出以最短路径为目标函数的进路搜索策略;编制仿真程序对该算法进行验证,结果表明:基于改进Dijkstra算法能够正确、高效地完成多种类别进路搜索。

面向LEO卫星网络的高效路由算法

由于卫星星上处理以及存储能力有限,随着卫星网络的规模越来越庞大,迫切需要一种简单高效的路由算法。为此,提出了一种基于网络拥塞程度感知的路由策略(Network Congestion-Aware Routing Algorithm,NCARA)。NCARA路由策略在网络处于非拥塞状态时采用Dijkstra算法寻路,网络拥塞时换用改进广度优先搜索算法(Enhance Breadth First Search,en-BFS)寻找最短路径。en-BFS算法利用卫星网络拓扑呈二维网格拓扑的特征,将最小跳数作为主要衡量指标,选出最小跳数路径集合;然后将传输时延和传播时延作为衡量标准,以O(V+E)(V为图的节点个数,E为图的边的数目)的时间复杂度在最小跳数集合中选择出最小权值路径。最后通过数学方法证明了算法的正确性以及有效性。仿真结果表明,所提路由算法的平均时延、丢包率等都与传统算法相当,但是算法复杂度却得到极大的降低。

基于A*算法的游戏地图最短路径搜索

介绍了常用的搜索算法思想,重点剖析了采用启发式A*算法实现大地图与复杂地形的最短路径搜索,在对估价函数特性进行分析的基础上,讨论了它的几个一般构造原则,并简要介绍一些常用的启发函数。

不确定条件下交通网络的动态最优路径求解算法

针对不确定性条件下的最优路径问题,引入行驶时间波动性及路段间相关性,定义最优路径为一定概率保证程度下行驶时间期望值最小的路径.以Dijkstra算法为基础,从不同路段行驶时间相互独立及相互关联两个角度,分别建立动态路径寻优模型和时间期望函数模型;设计适用于不确定条件下搜寻最优路径的BEST算法,并通过仿真实验验证模型的可行性.结果表明:时耗方差选择的差异化会导致最优路径解的多样化;考虑路段间相关性后绕城公路对市区公路的选择替代性增强.

基于象群-蚁群算法改进的小车路径规划

社会发展对智能机器人运行要求不断提高,单一蚁群算法已经无法满足路径规划的要求。针对蚁群算法存在探索和开发不平衡的问题,本文提出一种改进蚁群算法。首先采用栅格法建立环境模型;其次使用最佳优先搜索算法预搜索次优路径,来初始化蚁群算法的信息素浓度,以提高算法前期收敛速度;利用象群算法优化蚁群算法参数,以减小参数设置对算法影响,从而提高蚁群算法搜索性能。将改进蚁群算法进行仿真实验,并与传统蚁群算法进行对比。实验结果证明,改进蚁群算法搜索效率更高,迭代次数减少近65%。