一种基于最小生成树的网络路径优化算法研究

本研究提出了一种基于最小生成树的网络路径优化算法,旨在解决网络路径规划中的效率和成本问题。通过分析最小生成树算法的原理及其变种,如Prim和Kruskal算法,本研究设计了一种新的算法流程,该流程包括输入数据处理、网络构建、最小生成树生成以及优化路径的选择与调整。该算法利用最小生成树进行初步网络连通性分析,并对边权重进行定义与计算,以实现路径优化。算法特点在于其高效性和对复杂网络结构的适应性,优势在于能够提供成本效益最优的网络路径。

基于危险天气不确定性的最小风险路径规划方法

为降低飞行过程中遭遇危险天气的概率,同时避免大范围绕飞导致的路径与耗油增加,针对航路中的雷暴、积冰和颠簸天气,使用数值预报和概率预报,面向航前飞行计划,提出一种基于危险天气不确定性的最小风险路径规划方法.首先,基于概率预报数据使用配料法和C-F模型计算雷暴发生概率,基于数值预报数据计算积冰预测指数和颠簸预测指数;然后,融合多类型危险天气,提出一种具备风险标识的栅格化地图;在此基础上,改进传统路径最短的规划算法,构建以风险最小化为目标的Dijkstra和A^(*)算法;最后,使用2023年4月3日华中地区强对流天气预测数据建立风险地图,使用上述改进算法与传统Dijkstra、A^(*)和RRT算法进行路径规划并对比分析.结果表明,传统Dijkstra和A^(*)算法可计算得到最短飞行路径,而改进的A^(*)算法可计算得到总风险最小路径;若综合考虑飞行风险与路径长度,改进的Dijkstra算法最为适合.

一种基于Beta分布的风电功率预测误差最小概率区间的模型和算法

针对用正态分布计算风电功率预测误差区间时出现的问题,提出一种基于Beta分布的风电功率预测误差区间的估计方法。该方法根据发电调度对系统备用容量安全性和经济性的要求,建立一个能够计算任意概率水平、Beta分布最小概率区间的优化模型,通过引入Beta分布函数的反函数形式,把等式约束的优化问题简化成一个无约束的优化问题,并根据Beta分布特点给出了一个快速的算法。仿真结果证明了所提模型、算法的正确性,和Beta分布的合理性。

给定限制期条件下最小风险路径的选取算法

讨论在给定限制期情况下，边的长度（权值）为区间数的赋权图最小风险路径的选取算法，该算法将非线形比例路径问题的求解转化为最短路问题的变权迭代，算例及实际应用取得了令人满意的效果．

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义 ,具有广泛的应用领域 .交通网络和通信网络可以抽象为时间依赖的网络模型 .当模型中弧的长度是时间依赖的变量 ,最短路径问题的求解变得非常困难 ,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的 ,因此给出限制性条件使得传统最短路径算法是有效的 .该文从最短路径算法的理论基础入手 ,从理论上证明了传统最短路径算法 ,如 Dijkstra算法和标号设置算法 ,在时间依赖的网络上不能有效地求解最短路径问题 ;并且 ,在没有任何限制性条件下 ,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和 SPTDN算法 ,从理论上证明了 SPTDN算法的正确性 .算法的实验结果是正确的 .

基于改进的最大最小蚁群算法求解电力线路最佳抢修路径

电力线路最佳抢修路径就是一条物资点到故障点耗费时间最少的交通路径。最大最小蚁群算法改善了基本蚁群算法的过早停滞现象,适合于求解大规模问题,但仍存在收敛速度慢、求解质量差等缺点。针对最大最小蚁群算法的不足,提出了一种改进的最大最小蚁群算法来求解电力线路最佳抢修路径。该算法采用分段函数设置状态转移规则,结合噪声扰动方法进行局部搜索,并利用变异思想和A*算法产生邻域解。仿真实验表明,在求解电力线路最佳抢修路径时,该算法比其他改进蚁群算法具有更多的优越性,并分析了噪声扰动方法的参数对求解质量的影响。

自适应和最大最小蚁群算法的物流车辆路径优化比较

针对物流车辆路径优化问题,考虑到基本蚁群算法有收敛速度慢、易陷入局部最优的缺点,采用了自适应蚁群算法和最大最小蚁群算法进行车辆路径优化,分析、比较了这两种算法的不同并在Matlab上做了仿真。仿真实验结果显示自适应蚁群算法在收敛速度和寻找最短路径上都略逊于最大最小蚁群算法,最大最小蚁群算法在物流车辆路径优化上优于适应蚁群算法。

基于改进概率路线图算法的煤矿机器人路径规划方法

路径规划是煤矿机器人在煤矿井下非结构化狭长受限空间中应用亟待解决的关键技术之一。针对传统概率路线图(PRM)算法在空间狭长封闭巷道环境中难以保障采样的节点均匀分布于自由空间中导致路径规划失效,以及节点可能距离障碍物较近导致规划的路径可通行性差等问题,提出了一种基于改进PRM算法的煤矿机器人路径规划方法。在构造阶段引入人工势场法,将落在障碍物中的节点沿与其距离最近自由空间中的节点连线方向推至自由空间,并在障碍物边缘建立斥力场,实现节点的均匀分布且使其距离障碍物有一定距离;在查询阶段融合D^(*)Lite算法,当遇到动态障碍物或前方无法通行时可实现路径的重规划。仿真结果表明:改进PRM算法的节点均匀分布在自由空间中,且均距离障碍物一定距离,提高了路径规划的安全性;当节点数为100个时,改进PRM算法成功率较传统PRM算法提高了25%;随着节点数增加,传统PRM算法和改进PRM算法路径规划成功次数均呈增长趋势,但改进PRM算法在效率方面优势更明显;当节点数为400个时,改进PRM算法运行效率较传统PRM算法提高了35.13%,且规划的路径更平滑,路径长度更短;当障碍物突然出现时,改进PRM算法能够实现路径的重规划。

最小-最大车辆路径问题的蚁群算法

为了最小化车辆路径问题中行程最长子线路的长度,提出了一种可应用于不同数据集特点的参数自适应最大最小蚂蚁系统。针对聚类分布和随机分布的客户,分别采用顺序法和并行法构建路线,同时在算法执行过程中对期望启发式因子、选择概率、信息素持续参数和蚂蚁数量等参数进行自适应调整,既强化最优解附近的搜索,加快算法的收敛速度,也从一定程度上保证解的多样性,避免陷入局部优化。将该算法应用于7个经典算例的最小-最大车辆路径问题,计算结果表明,不仅可以取得较好的计算结果,而且算法的计算效率较高,收敛速度较快。

局部搜索最小路径费用算法

本文在MPH(MinimumPathCostHeuristic)的基础上 ,改进了端节点的加入过程 ,得到了两种改进的MPH算法 :局部搜索最小路径费用算法LSMPH(LocallySearchingMPH)和简化的LSMPH :最短端节点最小路径费用算法STMPH(ShortestTerminalMPH) .在随机网络模型的基础上 ,我们进一步进行了仿真 .仿真结果表明 ,LSMPH以相对较小的费用增加换取更快的计算速度 .如果要求更快的速度 ,可以采用STMPH .

最小费用最大流算法在路径规划中的应用

针对一类动态路径规划问题 ,先利用最短路算法将其简化 ,把动态的路径规划问题转化为静态的路径规划问题 ,然后建立非线性规划模型 ,再利用最小费用最大流算法进行求解 ,得到了比较精确的结果 。

无线传感器网络中新的最小暴露路径问题及其求解算法

无线传感器网络中原始的最小暴露路径问题没有考虑对路径的实际限制条件,提出一种要求经过某一特别保护区域部分边界的最小暴露路径问题。由于无法建立相应的图模型,原有求解最小暴露路径问题的经典方法(网格法和维诺图法)对提出的新问题不再起效。先将该问题转化成带约束条件的优化问题,然后针对转化后的数学模型高度非线性、高维度而不好用确定性优化方法的特点,结合问题实际背景设计出混合人工蜂群求解算法。通过在多种情况下的仿真实验发现,设计的带约束条件优化模型和混合人工蜂群求解算法能有效解决提出的最小暴露路径问题。

基于GIS和最小交通阻抗的公交出行最佳路径算法

分析了现有公交出行最佳路径算法,并针对现有算法不完善的地方,根据乘客的出行心理,利用G IS的空间分析功能,提出了一种基于最小交通阻抗的公交出行最佳路径算法。首先根据城市公共交通网络的特点抽象出合理的公交网络模型,建立了此网络的拓扑关系,并用有效的数据结构存储此公交网络图;然后根据乘客的出行特点确定了合理的交通阻抗函数;为了进一步提高搜索效率设定了节点限制搜索区域;最后对算法的仿真实现证明了此算法的可行性和有效性。

一种基于概率的多最小支持度挖掘算法

传统的Apriori算法由于始终保持单一的最小支持度,所以在实际应用中不能挖掘小比例事件中的关联规则。针对这一缺陷,该文提出并实现了一种基于概率的多最小支持度关联规则算法。该算法针对每个项目设定了最小项支持度,最小项支持度与该项目的出现概率相关。实验证明该算法不仅能有效地挖掘出发生概率较低的事件中的关联规则,同时又不丢失原有的大概率事件中的关联规则。另外,实验结果也说明该算法存在候选项集增多的缺点。

基于声纳搜索累积探测概率的平台路径优化方法

针对面向移动目标的移动搜索平台最优路径研究不足问题,提出一种基于累积搜索概率理论的移动搜索平台路径优化方法。基于传感器性能评价的重要标准之一的累积探测概率(cumulative detection probability,CDP),利用时序相关性模型,即(λ,σ)过程模型,构造单峰CDP计算公式。构建一组目标运动想定,利用贝叶斯后验概率修正目标想定轨迹概率和不同时刻下的CDP。以搜索完成时CDP最大以及CDP达到目标水平时间最短为多目标,在连续时间与连续空间中实现高效搜索,构建面向声纳搜索移动目标的路径优化模型,通过多目标遗传算法给出优化解。与随机搜索模式下的CDP结果比对可以发现,本文方法可以获得更高的CDP,比单目标优化结果所得到的搜索方案具有更高的效率。

一种基于路况预测信息的最小时间路径算法

动态路径规划是实现车辆动态导航的核心技术之一,首先构建了时间依赖动态路网模型,介绍了动态路径导航的实现策略,提出了一种基于道路短时预测信息的最小时间路径规划算法,实验仿真结果表明,该算法能够提供实时、高效、预测性强的规划路径,满足城市交通中用户的需求。

基于改进蚁群优化算法的AUV三维路径规划

针对蚁群算法在三维路径规划时收敛速度慢且难以收敛至最优的缺点,提出一种新的改进蚁群算法,并将其应用于自主式水下机器人(autonomous underwater vehicle,AUV)三维路径规划。与现有算法相比,改进算法优点主要体现在3个方面:首先,引进伪随机状态转移概率提升算法全局搜索能力;其次,将距离和轨迹限定因子引入启发式函数,距离因子保证搜索不断趋近目标点,在轨迹限定因子约束下,轨迹累计转角更小,以此提升收敛速度和精度;最后,通过扩大信息素增量差距并逐步提高信息素衰减系数,进一步提高路径规划效率。实验结果表明,改进蚁群算法能够获得累计转角更小路径,且路径长度更小,收敛速度更快。

随机网络最大概率路径问题的模型与算法

为了求解满足一定时间限制的最大概率路径问题,在建立该问题数学模型的基础上,提出了一种改进蚁群算法。首先根据随机网络的定义建立了随机网络最大概率路径问题的数学模型,然后结合随机网络最大概率路径问题的特点,设计了一种新的启发式信息和信息素更新规则的改进蚁群算法,最后选择了4组数据,将改进蚁群算法与一种混合遗传算法进行对比试验,分别求取对应的全局最大概率路径和反映算法总体性能的多项数据。实验表明,改进蚁群算法的收敛速度和总体性能均优于混合遗传算法,为求解随机网络最大概率路径问题提供了一种快速、可行的方法。

最小时间路径算法模糊结构元改进

针对运输的最小时间路径问题,采用模糊数表示车辆在各路段的运行时间,建立模糊最小时间路径模型.该模型不仅得到两节点间的最小模糊时间值,而且得到最小时间路径;利用模糊结构元处理模糊数的运算,简化了模型的运算.实例表明:该模型有效地解决了交通网络中任意两节点间的最小时间路径问题.

基于RRT*算法和DWA算法的分层结构路径规划策略

为优化复杂动态环境下路径规划问题,提高路径搜索效率,缩短路径规划时间,提出一种基于改进RRT*算法和DWA算法的分层结构路径规划策略;该路径规划分层结构由全局路径规划层和局部路径规划层组成,全局路径规划层根据已知静态障碍物信息利用改进RRT*算法进行全局路径规划;当路径中出现未知动态障碍物时,根据规划策略将启用局部路径规划层,基于获取的动态障碍物信息,利用DWA算法进行局部路径规划;最终通过全局与局部路径规划策略相结合得到最终的可行路径;仿真实验结果表明:文章提出的分层结构路径规划策略在复杂动态环境中可以高效地完成路径规划任务。