一种任务分配问题的快速剪枝优化算法

任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高。文章提出了一种新的求解任务分配问题的方法——剪枝优化算法。算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题。对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解。论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较。仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度。

基于剪枝优化的多变邻域节能调度算法

为了提高异构计算机系统中任务调度的节能水平,提出了融合剪枝优化的多变邻域节能调度算法。算法构建处理机约束和时间约束两个邻域结构,借助处理机约束邻域减少冗余处理机量,从而降低整体能耗;利用时间约束邻域有效缩减关键路径长度,实现了任务调度对时间的要求。提出了基于时间和能耗的剪枝优化策略,以提高局部寻优效率。通过仿真实验和实际问题求解对比可知,所提算法在不同问题规模、处理机量和通信比下,都取得了较好的节能效果。

基于剪枝优化与索引求交的改进Eclat算法

针对现有Eclat算法中普遍存在的候选集规模大、求交效率低的问题,提出了基于剪枝优化和索引求交的改进Eclat算法。首先根据频繁集的性质采用预剪枝和后剪枝相结合的候选集优化策略,即利用预剪枝技术裁剪待连接的项集数量以减少项集连接操作,同时利用先验性质对连接后的项集进行后剪枝处理;接着提出了一种基于事务索引的布尔数组求交方法,即通过将事务标识作为索引来设置并检索布尔数组,以获得项集支持度计数;最后通过设计对比实验,在经典数据集上测试该方法的有效性。实验表明,通过该方法能够有效压缩候选集规模,改善求交计算效率,特别是在支持度阈值小、事务数规模大的情况下,算法的运行效率得到了明显的提升。

基于剪枝优化算法的反向条纹生成方法

反向条纹投影技术是一种应用于在线或批量、快速而稳定的光学三维面形检测技术,近年来得到广泛关注和应用。提出了一种反向条纹生成的新方法,利用了正向映射变换方法传递坐标以及摄像机坐标系中同名点所在的水平和垂直方向两条等相位线,求解它们的交点就可以得到投影器对应像素点在摄像机坐标系中的位置,再生成待投影的反向条纹。在分析了两条等相位线特点的基础上,提出了求解等相位线交点的优化算法剪枝优化算法。该算法逐步缩小两条等相位线上有效像素点的规模,直至找到交点周围邻近的4个整像素点,再拟合出两直线方程,联立方程精确解出亚像素精度的交点坐标。并将本剪枝优化算法与文献[10]的主要方法进行了对比分析,计算机模拟实验得到了相位标准差,分别为0.000798rad和0.0046rad;实物实验得到的相位标准差分别为0.0431rad和0.0292rad。对比结果表明:该优化算法有效提高了反向条纹生成的精度,并且能以较快的速度精确搜索到交点周围4个像素点,减小了反向条纹生成的时间。

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

快速扩展随机树算法(rapidly-exploring random trees,RRT)规划移动机器人路径时,存在搜索盲目性强、搜索时间长、收敛速度慢、路径冗余点多且不平滑等问题。鉴于此,提出一种改进的RRT路径规划算法。首先,针对传统RRT算法盲目搜索以及局部极值的问题,提出概率目标偏置与人工势场结合的采样策略,引导随机树的扩展;其次,针对随机树扩展的避障能力差的问题,提出基于安全距离的碰撞检测以及动态变步长扩展策略;最后,针对路径上冗余点多以及曲率不连续的问题,提出考虑安全距离的剪枝优化和三次B样条曲线对初始路径进行拟合优化。仿真结果表明,在不同地图的路径规划中,相比于传统RRT算法,增强了通过狭窄通道能力,优化了路径的平滑性,搜索时间、迭代次数、路径长度分别减少约70%、40%、15%;相比于RRT衍生算法RRT-Connect,搜索时间、路径长度分别减少约25%、10%。

基于结构优化递归神经网络的网络流量预测

针对传统方法预测网络流量精度较低的问题,提出了一种基于改进双线性递归神经网络模型(BLRNN)的非线性网络流量预测方法.首先,给出了双线性递归神经网络的定义及网络结构描述;然后从网络结构和修剪过程两方面对双线性递归神经网络进行优化改进,采用遗传算法全局搜索进行修剪;最后,通过真实工况下的网络流量数据用仿真试验对模型性能进行分析.试验结果表明,优化后双线性递归神经网络模型大幅降低了算法复杂度,提高了计算效率,与传统的多层神经网络预测方法相比,该方法预测精度更高.同时,该方法也为其他具有相似特征的非线性预测问题提供了一种新的研究思路.

基于改进RRT算法的智慧小区物料小车路径规划

针对快速搜索随机树(RRT)算法在物料小车路径规划算法中路径转折点多、路径较长、算法运行速度慢等问题,开展了一种基于改进RRT算法的物料小车路径规划算法研究。首先分析了RRT算法与RRT-C算法的原理与优缺点;然后,提出针对优化目标点寻找的采样优化策略、步长优化策略以及保证物料小车运行安全的转角约束条件;最后,采用剪枝优化以及圆切角路径平滑策略来优化所得路径以符合物料小车实际运行线路,并将障碍物进行膨胀化处理,进而规避安全性不足的问题。优化后的RRT算法比初始方法在规划时长和路径长度上分别有着40%~60%和15%~30%的提升,证明了所提方法的有效性。基于改进RRT算法的智慧小区物料小车路径规划研究具有重要的理论和应用意义,并对未来智慧小区动态物流管理系统的优化提供了基础。

面向智能工厂应用的启发式板材排样优化算法

为给出企业合理的订购原材料方案,需要使得板材的利用率达到最大化.针对智能工厂应用场景,构建了二维规则板材的排料优化问题,并在此基础上提出了一种启发式的板材排样优化算法.该算法利用板材原料的基础信息,进行剪枝搜索排样.通过仿真实验结果表明:该算法具有较高的利用率以及时效性,较好地满足实际生产中的需求.

基于motif连通性的社区搜索方法

社区搜索的目标是从数据图中得到包含查询顶点的紧密子图,在社会学、生物学等领域有着广泛应用。针对现有基于子图连通性的社区模型的基础连通结构都是完全连通图,无法满足实际应用中用户对社区结构多样性的需求的问题,提出一种基于motif连通性的社区搜索方法,其中包括基于motif连通性的社区(MCC)模型以及两个相应的社区搜索算法——MPCS(Motif-Processed Community Search)算法和基于MP-index的社区搜索算法。MCC模型可以协助用户自由指定社区的基础连通结构,MPCS算法可以用来解决MCC的搜索问题。此外,提出两个分别针对motif实例搜索过程及所属社区判断过程的剪枝优化技术。最后,设计了MP-index以避免社区搜索过程中的冗余遍历操作。在多个真实数据集上进行实验的结果表明:剪枝优化可以使MPCS算法的耗时减少60%~85%,而基于MP-index的社区搜索算法相较于加入剪枝优化的MPCS算法,效率提升普遍达到了2~3个数量级。可见,所提方法在商品推荐和社交网络等问题上有着实际应用价值。

同根双向扩展的贪心RRT路径规划算法

针对传统RRT-Connect算法路径规划过程中随机性大、算法效率低、搜索时间长、搜索路径冗长等问题,提出一种同根双向扩展的贪心RRT路径规划算法。将由起点开始向终点进行扩展的方式改为由起点与终点连线的中间点同时向起点和终点进行双向扩展,同时在扩展节点时叠加引力场和极度贪心算法,使树快速向起点和终点的方向扩散,加速路径的生成。对生成的路径进行剪枝优化处理,删除路径中冗余的节点,缩短路径长度。在三种不同环境中对改进算法进行仿真对比实验,结果表明所提算法相关性能优于传统RRT-Connect算法及其相关衍生算法。将改进RRT-Connect算法应用在实际移动机器人中,进一步证明改进算法的实用性和有效性。

基于多源数据汇集和决策树的满意度提升技术

在IT服务过程中,普遍存在满意度数据采集单一、满意度分析不全面、满意度预测机制简单,以及缺少满意度智能纠错机制等问题,为此设计一种基于多源数据汇集和决策树的满意度提升技术,利用满意度决策树模型,对多IT系统和多渠道来源的满意度数据进行了归一化处理和融合。提出满意度智能计算模型,为满意度管理、预警、智能微调及自动纠错提供计算基础。引入剪枝优化的记忆化搜索算法,对满意度数据进行智能纠错。通过建立分层次、多角度、全方位的满意度管理模式,有效提升IT系统服务满意度,具有广泛的应用前景。

基于VMD-TPE-LSTM模型的月径流预测方法研究

科学、准确、可靠的径流预测对防汛抗旱、水资源高效利用、水利设施综合效益的发挥至关重要。受到气候变化和人类活动的影响,径流过程易呈现出高度的非线性、非平稳性特征,给径流预测带来了更大的挑战。本文提出了一种基于变分模态分解(VMD)、剪枝优化算法(TPE)、长短期记忆网络(LSTM)等方法结合的月径流预测模型(VMD-TPE-LSTM),采用受钱塘江上游新安江水库调控影响的富春江水库1969~2022年月径流序列对VMD-TPE-LSTM模型进行了训练、验证与测试,月径流预测结果表明:VMD-TPE-LSTM模型的纳什效率系数达到了0.91,能够对峰值流量实现较好的预测,模型具有良好的泛化性能;进一步开展了对照实验,揭示了各因素在组合径流预测模型中对模型预测性能影响程度排序为:预处理技术 > 基准模型 > 模型参数。因此,耦合预处理技术和参数优化算法的径流预测方法能有效解决气候和人类活动影响的径流非平稳性问题,从而提高月径流预测精度和能力。

FP-Growth-DW算法在离散车间的数据挖掘分析

针对离散车间生产能耗数据多源异构,干扰因素间关联关系不易分析的问题,根据离散制造能耗机理分析结果构建多源能耗数据挖掘模型(Multi-source Energy-consumption Data-mining Model,MEDM),提出一种面向离散车间的频繁模式增长(Frequent Pattern Growth for Discrete Workshop,FP-Growth-DW)算法。首先,应用关联视图、分箱处理和多源异构统一编码方法,对离散车间多源异构海量数据进行预处理;然后,采用分区并行策略和3种剪枝技术优化候选项集以构建频繁模式树(FP-Tree),并提取强关联规则合并存储到规则库中。最后实例验证表明,该算法在离散车间多源异构数据挖掘分析上具有可行性和有效性,算法效率提升了68.8%。

基于改进YOLO v3的机械装置目标检测算法

基于计算机视觉的机械装置检测技术虽然已有研究,但大多检测效率低。为此提出基于改进的YOLO v3算法的机械装置识别方法,对YOLO v3算法进行剪枝优化研究,即通过对图像数据标注,构建机械装置红外图像数据集;运用L1正则化将神经网络稀疏化进而剔除冗余通道,以达到网络精简。实验结果表明,进行剪枝后的目标检测算法综合性能有较大提升,其模型体积缩小82.14%,运行速度加快74.38%,准确率为92.47%,检测速率为27.9 fps.通过性能对比分析,证实此方法在满足检测准确率条件下显著提高了检测速率,降低检测所使用设备的硬件要求及功耗,易于满足实际中对机械装置快速识别检测的要求。

非均匀步长的同步Bi-RRT-DWA算法

为解决传统快速搜索随机树(RRT)算法在航迹规划中搜索效率较低、转折点过多且规划的路径未考虑无人机的动力学约束等问题,提出一种非均匀步长的同步Bi-RRT-DWA算法。该算法在传统RRT算法基础上设计了一种非均匀步长的同步双向扩展策略,减少算法无效扩展;设计剪枝优化方法,减少无效转折点;优化动态窗口法中的评价函数,提高安全性和平滑度。最后,通过仿真实验将非均匀步长的同步Bi-RRT-DWA算法与RRT算法进行对比,在同一工作环境不同起终点条件下,搜索路径长度减少了23.3%,搜索路径转折点个数减少了77.4%,验证了算法在规划效率、安全性和路径平滑性等方面有很大提升。

基于深度优先搜索的铁路中转路线规划研究

目前,许多长距离铁路出行没有直达列车,或直达列车绕路,导致额外的时间和金钱花费。本文针对这一现象,将复杂的铁路路线数据抽象成计算机方便处理的图,使用带有剪枝优化的深度优先搜索算法,对可能的乘车中转方案进行遍历,根据不同目标(如花费最少、耗时最短、到达时间最早等)挑选出不同中转方案,供用户出行参考。根据软件设计的原则和方法,给出了使用实现该算法的系统的设计。

海量数据下的并行频繁项集挖掘算法

文章针对频繁项集挖掘中传统串行Eclat算法面对海量数据时挖掘效率不高的问题,提出一种海量数据下的并行频繁项集挖掘算法,即I-SPEclat算法。首先,对Eclat算法存在的缺陷进行改进,引入图的邻接矩阵作为数据的存储结构,避免了大量的交集运算;其次,利用先验性质对候选项集进行预剪枝和后剪枝,减少无用候选项集的数量,节约存储空间;再次,根据项集的前缀对数据进行划分,平衡每个计算节点的工作负载;最后,将改进的Eclat算法在Spark分布式计算框架上实现并行化。实验结果表明,I-SPEclat算法较已有的改进Eclat算法在时间消耗和内存消耗方面均有减少,且面对不同规模的数据集也有着良好的扩展性。

基于积温理论的温室温度混杂系统预测控制

温室温度系统作为典型的混杂系统,其输入包括离散的设备控制量以及可测不可控的多个室外环境扰动量。本文针对温室温度混杂系统,建立切换系统模型,基于此模型设计多输入预测控制。首先分别在4种离散状态(保温模式、自然通风模式、强制通风模式、湿帘-风机模式)下确定模型的主相关输入,采用带遗忘因子的递推最小二乘法建立子模型。然后设计预测控制器,利用双周期积温法规划预测控制设定值。求解多输入预测控制量问题为NP-hard问题,采用最优化剪枝法优化搜索。最后在实验温室应用控制算法进行实验,实验结果表明,多输入预测控制算法可以有效调控温室内温度,并且由于积温理论动态规划预测控制设定值,可减少设备的切换次数,降低能耗。

一维下料问题的多叉树遍历算法研究

切割条形材料,获得不同长度工件问题普遍存在。为满足原材料利用率最大的实际加工要求,将数据建立为多叉树模型,添加剪枝优化条件,使用深度优先遍历,递归调用深度优先遍历函数,搜索全局最优解,即最优化的下料方案。使用其他论文中的实例,对比启发式多级序列线性优化方法的运算结果。对比结果表明:多叉树遍历算法的材料利用率最高、结果更优。

基于DiffNodeset结构的最大频繁项集挖掘算法

在数据挖掘中,通过挖掘最大频繁项集来代替挖掘频繁项集可以大大地提升系统的运行效率。针对现有的最大频繁项集挖掘算法的运行时间消耗仍然很大的问题,提出了一种基于DiffNodeset结构的最大频繁项集挖掘(DNMFIM)算法。首先,采用了一种新的数据结构DiffNodeset来实现求交集以及支持度的快速计算;其次,引入一种新的线性复杂度的连接方法来降低两个DiffNodeset在连接过程中的复杂度,避免了多次的无效计算;然后,将集合枚举树作为搜索空间,同时采用多种优化剪枝策略来缩小搜索空间;最后,再结合最大频繁项集挖掘算法(MAFIA)中所使用的超集检测技术来有效地提高算法的准确性。实验结果表明,DNMFIM算法在时间效率方面性能优于MAFIA与基于N-list的MAFIA(NB-MAFIA),该算法在不同类型数据集中进行最大频繁项集挖掘时均有良好的效果。