基于动态粒子群优化的X结构Steiner最小树算法

Steiner最小树(SMT)是总体布线的最佳连接模型,其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现,而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此,利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略,以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT)算法以解决总体布线问题。首先,设计动态子群与信息交换策略,对种群进行子群划分,引入信息交换的概念,让子群在保持独立性的同时与其他子群进行信息交换,增加子群多样性;其次,设计粒子学习与变异策略,通过设置子群中粒子的学习对象使子群趋向于全局最优,并选择每个子群中适应度值最好的粒子进行变异,使粒子更易于跳出局部最优;最后,设计从多群局部学习过渡到单群全局学习策略,使算法在迭代次数到达阈值之后从局部学习过渡到全局学习,使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明,与现有的2种R结构SMT(RSMT)算法相比,所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比,该算法在优化线长方面分别优化了2.44%、1.46%、0.48%,验证了算法的有效性。

储粮仓仓壁动态侧压力的树模型预测方法

针对储粮仓卸料时仓壁动态侧压力难以准确预测的问题,利用机器学习方法中的树模型建立了仓壁动态侧压力预测模型。首先,分析了仓壁动态侧压力的主要影响因素为筒仓的结构尺寸、贮料的物理参数及测点位置。利用收集的496组仓壁动态侧压力数据,构建机器学习预测模型的数据集。然后,基于树模型,建立了仓壁动态侧压力的决策树(decision tree,DT)预测模型,在此基础上,利用Bagging算法和Boosting算法,建立了仓壁动态侧压力的随机森林(random forest,RF)预测模型和梯度提升树(gradient boosting decision tree,GBDT)预测模型。通过对比3种预测模型在测试集的均方误差(mean-square error,MSE)、决定系数和相对误差,表明GBDT预测模型的泛化性能最优。最后,通过开展模型试验和数值模拟,对GBDT预测模型进行验证,结果表明拟合良好。同时,根据树模型的分枝原理,判断出仓壁动态侧压力影响因素的重要性,得到对于贮料的物理参数,密度的重要性排第一;对于筒仓的结构尺寸,卸料口尺寸排第一。因此,在进行储粮仓设计时,建议优先考虑仓内散体物料的密度和仓的卸料口尺寸。

基于回溯树的动态容重比平衡货物配载研究

针对零担物流货物装载率低下的现状,研究货物有限条件下多车多品种货物的货物配载问题,构建以最小化车辆数量、最大化车辆总容积和总载重量利用率为目标的多目标数学模型,考虑到单件货物的装载会对车辆以及车辆集合的剩余容积和剩余载重量产生影响,设计基于动态容重比平衡法和装载回溯树的启发式算法,对算法结果进行非支配排序,得到帕累托解集,计算帕累托解集内每个解的拥挤距离,并选择拥挤距离最大的解为最优装载方案。以算法计算精度和时间复杂度为标准,将所设计算法与NSGA-2、CPLEX算法进行对比分析,算例结果验证了算法的有效性。

奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

基于动态故障树的交通信号灯监测系统故障分析

针对交通灯故障无法及时处理影响交通效率与安全的问题,设计了基于ZigBee技术的监测终端,根据监测系统中部件发生故障的时序关系建立动态故障树模型,分别采用二元决策图法BDD(binary decision diagrams)和马尔科夫模型对静态子树和动态子树进行定量分析,确定监测系统底事件对系统整体的概率重要度,计算得到导致交通灯故障的主要原因为光纤传感器位置移动和灯珠寿命到期。使用动态故障树法设计交通灯监测系统为工作人员快速分析故障原因提供了理论依据。

基于动态融合索引树的ARXML查询处理算法

随着汽车行业的不断发展和智能化进程的加速,AUTOSAR已成为一种广泛采用的汽车软件架构标准,ARXML(AUTOSAR结构化文档)是该架构标准中描述车辆电子控制单元(electronic control unit,ECU)的重要资源。针对大量数据密度高且内容复杂的ARXML文档查询处理效率的问题,提出了一种基于动态融合索引树的结构化文档查询处理算法。算法从节点关系规则出发,对单个文档中的内部节点和不同文档中节点之间的关系规则进行分析,在保留节点原始关系的同时构建了带有外部关系的节点关系结构,并基于结构化文档查询表达式对该结构进行改进,最后将其扩展成动态融合索引树结构,降低文档解析处理时间消耗,提高查询性能。复杂性分析和实验结果表明,使用动态融合索引树结构的文档查询效率高于现有的查询方法,具备一定的实用性。

基于T-S动态故障树的桁架机器人系统可靠性分析

为了提高桁架机器人系统的动态可靠性,并且在发生故障时提升排查故障的效率,提出一种对桁架机器人系统动态可靠性分析的方法。首先,对桁架机器人系统建立T-S动态故障树;然后,把T-S动态故障树和T-S动态门规则分别转化为离散时间贝叶斯网络(DTBN)与相应网络节点的条件概率表,根据DTBN正反向推理分别计算得到各时间段以及任务时间内系统失效概率和根节点后验概率,并获得各根节点的T-S概率重要度、T-S关键重要度和灵敏度;最后,应用Monte Carlo仿真法进行验证,结果显示相对误差为0.29%,证明所提方法可行。给出当系统发生故障时应优先排查的零部件,并确定了系统薄弱环节,得出应优先提高可靠度的零部件,为桁架机器人系统的动态可靠性分析提供了理论依据。

电力物联网用户侧负荷数据动态R-树匹配方法

电力物联网用户侧负荷数据维度较大,导致数据匹配延时时间过长,为了解决上述问题,基于动态R-树实现电力物联网用户侧负荷数据动态匹配。建立负荷计算模型,分析负荷历史运行信息,实现数据检测。通过归一化函数完成归一化处理,提取动态特征,构建动态R-树,确定匹配机制,根据矩阵计算函数完成压缩处理,利用动态匹配算法更新集对R-树内部结构进一步加以修改,在清除矩形之前,利用叶结点的Hash索引得到R-树匹配矩阵,使用Hash搜索准确地找到目标矩形,增强分布与交互仿真中的实时性,实现用户侧负荷数据动态匹配。实验结果表明,研究的动态R-树匹配方法在数据插入、数据匹配、数据维护过程中的延时时间低于48ms,实时性较好。

支持动态配置和模糊搜索的调控对象树

调控云模型数据平台逐渐成为电力调度管理系统电网模型数据的唯一来源,因此急需一个公共、实用、灵活的组件为各应用提供基础模型数据支撑。设计一个支持动态配置和模糊搜索的调控对象树提出基于调控云的对象树模型。基于对象树模型提出一种支持动态配置和模糊搜索的方法,实现调控对象选择树组件,并基于真实的调控云电网模型数据进行实验验证。实验分析表明,设计的支持动态配置和模糊搜索的调控对象树,能有效支撑新一代电力调度管理系统的实际应用。

基于表达式的逐层聚合和动态选择的图到方程树模型

现有树解码器仅适合求解单变量问题而求解多元问题的效果欠佳,而大多数数学求解器对真值表达式的错误选择导致训练出现学习偏差。针对上述问题,提出基于表达式的逐层聚合和动态选择的图到方程树(GET)模型。首先,通过图编码器学习文本语义;其次,从方程树的底层开始逐层迭代地聚合数量和未知变量以得到子表达式;最后,结合输出表达式的最长前缀动态地选择真值表达式以实现偏差最小化。实验结果表明,所提模型在Math23K数据集上的精度达到83.10%,相较于图到树(Graph2Tree)模型提升了5.70个百分点。可见,所提模型适用于复杂多元数学问题的求解,并能降低学习偏差对实验结果的影响。

动态分类树构造下的自适应差分隐私数据发布算法

针对当前隐私数据发布过程中存在的耗时较长、损失量较大等问题,提出一种动态分类树构造下的自适应差分隐私数据发布算法。首先,构建基础树索引模型,优化隐私预算环节,以实现分类树动态化;然后,对原始数据集进行小波变换处理,为分类树提供数据基础;最后,设定数据发布粒度,结合动态分类树层级分布进行数据发布。经实验验证,该算法可有效减少数据查询误差,缩短数据发布时间,降低数据发布损失量。

近海复杂环境下UUV动态路径规划方法研究

为解决近海环境下水下无人航行器(unmanned underwater vehicle,UUV)的动态路径规划问题,本文提出一种结合全局和局部动态路径规划的算法。首先,本文提出一种基于自适应目标引导的快速拓展随机树算法,以增加随机树生长的方向性,并通过转向和重选策略减少无效拓展加快算法的收敛速度。接着,获得全局路径之后使用自适应子节点选取策略获取动态窗口法的子目标点,将复杂的全局动态任务规划分解为多个简单的动态路劲规划,从而防止动态窗口法陷入局部极小值。最后,通过UUV出港任务仿真实验验证了算法的有效性和实用性。

基于动态监测与事故树分析的超大深基坑风险分析方法研究

为对城市特大交通枢纽超大深基坑工程进行动态风险等级定量分析,提出风险事故树与基坑动态监测数据相结合的超大深基坑工程风险分析方法。列举基坑工程典型的各类风险源,绘制风险事故树并分析其基本事件结构重要度,将风险影响程度高的监测项目作为风险动态评价指标,同时考虑监测项目的动态评价因素和静态评价因素,将主因素突出法和综合评价分析法相结合。方法应用于北京城市副中心站特大交通枢纽超大深基坑工程项目中。研究结果表明:可有效避免获取事故树底事件发生概率的困难和单一使用综合评价分析法对基坑风险评价的失真影响,在实际工程中能够得到合理的基坑风险等级,具有较好的实用性和可操作性。研究结果可为超大深基坑工程风险分析提供参考。

基于动态故障树联合动态Bayes网络的汽轮机跳机电磁阀配电系统可靠性研究

跳机电磁阀配电系统可靠性关系到机组安全运行。针对跳机电磁阀配电系统中因电源切换易造成跳机电磁阀误动问题,分析了误动及遮断系统失效原理,从取消电源切换装置和改变供电拓扑结构两方面考虑,提出两种配电系统改进方案,并采用动态故障树蒙特卡洛联合动态Bayes网络对跳机电磁阀配电系统进行可靠性研究。仿真结果表明,所提的改进方案不仅解决了电源切换引起电磁阀误动问题,提高了供电稳定性,而且系统具有较高的可用率。

南京紫金山糙叶树种群结构与动态

为明晰地带性植被糙叶树种群结构与动态特征,根据1 hm^(2)固定样地中优势种糙叶树的每木调查结果,通过种群静态生命表、存活曲线、生存分析函数及时间序列模型,对糙叶树种群的结构动态进行分析。结果表明:1)糙叶树种群属于增长型,在自然干扰下,种群数量变化动态指数为3.04%,表明该种群能够在当前演替阶段保持稳定。2)种群存活曲线趋于Deevey-Ⅱ直线型B 3亚型,死亡率和消失率均表现出波动性特征。3)时间序列预测表明,在经过2~5个龄级后,除Ⅸ和Ⅺ龄级外,种群各龄级的个体数量均有不同程度增长。综上所述,虽然紫金山糙叶树种群个体数量在当前演替阶段能够维持稳定,但种群在幼中龄过渡阶段死亡率(43.2%)和死亡密度(9.7%)偏高,需通过适度开展科学的经营性择伐等森林抚育措施,及时伐除病残木,营造小林窗,改善林内生存环境,从而促进糙叶树种群的天然更新与苗木生长。

基于动态故障树的汽车系统故障诊断方法

为了提高汽车故障诊断效率,降低诊断代价并解决静态故障树(SFT)无法描述汽车系统中动态失效序列的问题,提出一种基于动态故障树(DFT)的汽车系统故障诊断方法。首先,利用DFT建立系统的失效模式模型,并采用顺序二元决策图(SBDD)计算DFT的最小割集(MCS);然后计算MCS以及MCS中组件的诊断重要度(DIF);并在此基础上给出基于统一诊断服务(UDS)协议的汽车故障诊断方法,将诊断故障码对应的MCS过滤并排序,优先诊断DIF大的MCS和系统组件;最后通过一个汽车主动转向系统的应用实例对本文方法的有效性进行验证。案例分析结果表明,所提方法能够计算汽车故障诊断MCS序列,可以有效指导汽车故障诊断工作。

基于动态故障树的铸造起重机起升机构可靠性分析

针对铸造起重机起升机构可靠性问题,提出一种基于动态故障树的起升机构可靠性分析方法。首先介绍动态故障树理论与动态故障门,对铸造起重机进行动态故障树建模,通过线性搜寻法对动态故障树进行分层,得到其动态子树和静态子树,采用马尔可夫链和二元决策图相结合的方法对子树模块进行求解,最后综合各个子树故障率得到起升机构故障率。

基于带权单链表多元哈希树的云数据审计方案

针对传统Merkle哈希树节点利用率低以及动态更新效率低的问题,提出一种支持批量更新的基于带权单链表的多元哈希树(WSLL-MHT)数据结构,在该结构中,将多元哈希树的叶子节点替换成单链表结构以存储更多数据块,增加其节点利用率。在动态更新过程中,引入树的平衡机制确保链表长度的平衡,提高动态更新的效率。采用BLS-HVA签名技术实现批量审计和隐私保护,结合随机掩蔽技术确保第三方审计员不能从返回的证据中获取用户隐私信息。实验结果表明,所提方案能安全高效实现云端数据的批量审计和全动态更新。

考虑动态倾覆稳定性的液压重载机械臂路径规划方法

针对液压重载机械臂的动态倾覆稳定性问题,提出了一种基于改进快速扩展随机树(Rapidly-exploring Random Tree,RRT)算法的路径规划方法。与只对危险工况的静态稳定性校核不同,该算法以机械臂运动过程中的动态倾覆稳定性最优为目标,在机械臂的关节空间内进行路径规划。以7个关节变量组成的七维数组作为采样点,结合正运动学与力矩法建立机械臂的动态倾覆稳定性计算模型,利用双采样点择优原则,选择其在对应位姿下抗倾覆稳定力矩最优的随机点作为采样点,以增强算法的启发性。在Matlab平台进行的仿真实验表明,改进RRT算法规划路径的倾覆裕度在3种典型工况下分别提升了37%、28%和38%,有效地改善了液压重载机械臂作业平台的抗倾覆稳定性。