Outlier-DivideConquer:近似聚集查询中离群分治取样算法

取样是一种通用有效的近似技术,利用取样技术进行近似聚集查询处理是决策支持系统和数据挖掘实现技术中的常用方法.如何正确有效地给出近似查询结果并最小化近似查询误差是近似查询处理的关键和目标.在深入研究近似聚集查询取样方法的基础上,本文提出了一个有误差确界且只需单遍扫描数据集的离群分治取样Outlier-DivideConquer算法,该算法在聚集属性内部存在高方差分布时能克服随机均匀取样局限,可显著降低近似查询误差,且执行效率优于同类算法.最后通过与传统均匀取样算法的实验比较验证了Outlier-DivideConquer算法的有效性和正确性.

灌溉机器人全覆盖路径规划方法

灌溉机器人全覆盖行动的各个任务具有较为明显的空间并行性,随着全覆盖范围扩大,在对覆盖区域进行分解阶段,需要充分考虑将整个区域空间分解为哪些区域。但是,灌溉机器人受到视觉感知区域限制,准确匹配和衔接路块间最近端点的难度较大,导致局部路点的连通和线路衔接出现差错,难以有效全覆盖。为了有效解决这一问题,提出一种灌溉机器人全覆盖路径规划方法。通过快速搜索随机算法展开需要覆盖区域的边界检测,考虑视觉传感器的感知范围受限因素,采用灰度质心法展开区域视图边界提取,根据提取结果建立地图。在地图上建立线段序列,通过曼哈顿最小距离原则连接地图上的部分路径线段,形成多个弓形线路块。使用分治算法匹配和衔接各个弓形线路块间最近端点对,引入改进A*算法对全局以及局部路点的连通和线路衔接,实现灌溉机器人的全覆盖路径规划。实验结果表明:针对简单灌溉区域,该方法的路径重复率为0.041%,灌溉覆盖率为98.90%;针对复杂灌溉区域,该方法的路径重复率为0.017%,灌溉覆盖率为99.87%。这说明针对不同的灌溉环境,该方法均可以实现理想的路径规划,不仅可以最大限度地实现全覆盖,并有效地减少路径冗余程度,可以获取理想的灌溉机器人全覆盖路径规划方案。

基于改进算法YOLOv5+的混凝土轨枕裂纹检测

基于既有研究成果在对混凝土轨枕裂纹检测效率不足的基础上,提出一种改进算法YOLOv5+,主要以YOLOv5网络模型为基础,对混凝土轨枕裂纹进行高效检测。首先,采用分治标签的策略来增大裂纹在标签中的实际占比,从而解决混凝土轨枕裂纹尺度变化大的问题,使网络更利于提取有效特征;其次,将YOLOv5网络结构中SPP模块的最大池化层改为平均池化层,减少裂纹漏检的现象;同时,在YOLOv5骨干网络中嵌入SE注意力模块(Squeeze and Excitation,SE)提高对细小裂纹的检测能力;最后,结合新的检测尺度与特征融合网络,降低微小裂纹的漏检现象。实验结果表明,以YOLOv5网络模型为基础的改进算法YOLOv5+,除了召回率Recall变化不大外,精确率Precision提高6.5%,平均精度均值mAP提升8%,帧率FPS也有所提升,能够满足实时性的检测需求。

基于误差分治的神经网络验证

随着神经网络技术的快速发展,其在自动驾驶、智能制造、医疗诊断等安全攸关领域得到了广泛应用,神经网络的可信保障变得至关重要.然而,由于神经网络具有脆弱性,轻微的扰动经常会导致错误的结果,因此采用形式化验证的手段来保障神经网络安全可信是非常重要的.目前神经网络的验证方法主要关注分析的精度,而易忽略运行效率.在验证一些复杂网络的安全性质时,较大规模的状态空间可能会导致验证方法不可行或者无法求解等问题.为了减少神经网络的状态空间,提高验证效率,提出一种基于过近似误差分治的神经网络形式化验证方法.该方法利用可达性分析技术计算非线性节点的上下界,并采用一种改进的符号线性松弛方法减少了非线性节点边界计算过程中的过近似误差.通过计算节点过近似误差的直接和间接影响,将节点的约束进行细化,从而将原始验证问题划分为一组子问题,其混合整数规划(MILP)公式具有较少的约束数量.所提方法已实现为工具NNVerifier,并通过实验在经典的3个数据集上训练的4个基于ReLU的全连接基准网络进行性质验证和评估.实验结果表明,NNVerifier的验证效率比现有的完备验证技术提高了37.18%.

基于优先级辅助分治策略的多星多站测控资源分配方法

随着商业测控的不断发展和在轨运行的商业卫星数量增多,针对商业地面测控资源有限,以及各种临时的任务需求导致的中低轨卫星测控资源紧张的问题,文章提出了一种基于优先级辅助分治策略的多星多站测控资源分配方法。经仿真分析,结果表明:该方法能够简单灵活的以较少的计算量和内存开销实现分配方案求解,该求解方案能够保证在优先级较高的卫星和任务优先获得调度资源的前提下,最大限度的为卫星和任务提供测控资源,可为测控资源调度系统建设提供参考。

基于三阶段优化的大无人机辅助小无人机物流配送方法

无人机包裹配送是近年来获得广泛关注的新配送方式,相比于基于地面车辆的配送方式,多无人机配送具有高效率、强时效性和灵活机动等优势.因此,本文提出了一种全新的异构多无人机物流配送模式,即单架大无人机辅助多架小无人机进行的包裹配送.该配送模式的新特点是:大无人机携带多架小无人机到配送区域放飞,多架小无人机分别配送所指派区域的包裹,每架无人机在一次航行中可配送多个包裹,多架小无人机同时进行配送.为了高效的求解这个新配送问题,文章设计了一种基于分而治之三阶段的迭代优化算法,第1阶段采用聚类方法对客户点聚类并生成初始解;第2阶段提出一种改进的变邻域搜索算法优化大无人机路径;第3阶段使用动态规划方法优化小无人机路径.这3个阶段不断迭代优化直至满足停止准则.为了验证所提出算法的有效性,在大量算例上进行了实验测试,实验结果展示了所提出算法的求解效率和目标函数值显著优于其他对比算法.文章所提出的新的异构多无人机配送模式及其求解方法,为解决现代物流配送的痛点问题提供了一种全新方式与决策依据.

大数据序贯检验方法及其应用

分布的一致性检验在很多领域中得到了广泛的应用,它是统计学在众多应用中的一个基本主题。然而,随着大数据时代的到来,各个科学领域收集存储了丰富的数据。这些数据规模庞大、类型多样、结构复杂、更新速度快,传统的分布一致性检验方法受数据规模和存储方式的影响在处理和分析这类数据时面临着巨大的挑战。目前,分治策略是解决这类问题的主要方法,其核心思想是采用分布式框架对每个节点数据的计算结果进行集成以获取最终的结果。在处理大规模分布一致性检验问题时,这种对所有节点的检验结果进行集成的方式并不高效,特别是在数据分布存在明显差异时这种方式往往会增加检验的成本。因此,基于序贯检验的思想通过合理设置检验问题的“误差区域”对已有的分治策略进行优化,提出了一种分布式序贯检验方法。该方法在检验过程中不集成所有的节点数据,而是根据当前收集到的节点数据实时调整后续的决策,通过这种方式能够实现在不使用全部节点数据的前提下,做出正确的检验结果。模拟实验和实例分析结果表明:相比于已有的分治策略检验方法,所提出的分布式序贯检验方法能够在保证检验水平与功效的同时,提高分布式检验的计算效率,为解决临床试验、工业检验等领域中大规模数据检验成本高的问题提供了方法支撑。

四针汉诺塔问题的算法设计

对传统三针汉诺塔问题的递归求解算法进行简要分析和研究,在此基础上对四针汉诺塔问题进行深入研究,给出四针汉诺塔最优移动次数的算法,并通过穷举法分析提炼出最优参数的取值。

一种生成Delaunay三角网的合成算法

经过２０ 多年的研究，自动生成Ｄｅｌａｕｎａｙ 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３ 类。其中前两类较第３ 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。

基于并行禁忌搜索算法的配电网重构

为更好地实现配电网重构,引入了分治法,进而提出了采用并行禁忌搜索算法实现重构的方法。将配电网简化为只含支路组的环网,并给出了配电网重构的必要条件。重构时,首先选择断开的支路组,采用深度优先搜索算法形成父子链表;然后引入可降低复杂度的分治思想,以可断开支路组为解空间进行分组,应用多处理器进行并行禁忌搜索。算例结果验证了该方法的有效性。

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-e个并行处理机单元,0e1,O(2n/2)个存储单元,在O(2n/4(2n/4)e)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.

平面连通域VORONOI图的算法

本文探讨了平面多边形的ＶＯＲＯＮＯＩ图的性质，研究了通过合并多边形边界的两个子集生成平面单连通域ＶＯＲＯＮＯＩ图的分治算法，以及合并外轮廓和“岛”轮廓的ＶＯＲＯＮＯＩ图来生成平面多连通域ＶＯＲＯＮＯＩ图的算法。

对两个基于混沌的序列密码算法的分析

本文指出“混沌非线性反馈密码序列的理论设计和有限精度实现”和“一类新型混沌反馈密码序列的理论设计”两文基于混沌设计的两个序列密码算法产生的乱数序列的前若干值对密钥的变化并不敏感 ,据此在已知混沌变换的条件下 ,可以利用已知明文采取先攻击高位密钥再攻击低位密钥的方法对这两个密码算法进行分割攻击 .本文还提出了在正确密钥的分布已知条件下使平均计算复杂性达到最小的穷举攻击算法 ,并将它与分割攻击方法结合 ,提出了对上述两个密码算法的优化分割攻击方案 。

网络流量特征选择方法中的分治投票策略研究

特征选择作为机器学习过程中的预处理步骤,是影响分类性能的关键因素.网络流量具有数据量大,特征维度高的特点,如何快速提取特征子集,并提高分类效率对于基于机器学习的流量分类方法具有重要意义.本文提出基于分治与投票策略的特征提取方法,将数据集分裂为多个子集,分别执行特征提取算法,利用投票方法获得最后的特征子集.实验表明可有效提高特征提取的时间效率,同时使分类器取得良好的分类准确率.

基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2q/2),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.

基于分治思想的尺寸自动标注方法的研究与实现

提出了一种新的尺寸自动标注策略 ,即直接从三维模型出发完成二维标注 ,并引入分治思想将尺寸自动标注划分为基于特征模型、基于几何模型、基于二维图形等三个阶段 .从特征模型出发 ,基于分治思想提出尺寸自动标注的二维与三维空间分治策略 .在三维空间分治中 ,主要解决尺寸标注的完整性与合理性问题 ,提出形体分治、组合方式分治和工艺分治等三种分治策略 ;在三维到二维投影的二维空间分治中 ,主要解决尺寸标注的正确性与清晰性问题 ,提出投影分治、正确性分治和清晰性分治等三种分治策略 .研制并实现了一个尺寸自动标注原型系统 .研究成果可以与现有特征模型连接起来 ,具有一定的实用意义 .同时 ,可以接受特征识别和三维重建的数据 。

大规模时间序列分析框架的研究与实现

工业互联时代,每天数以亿计的传感器源源不断生成时间序列,用以记录工业设备的温度、振动、压力、曲度和张力等参数.如何从这些非结构化的时间序列中挖掘出有价值信息,并运用于状态监测、故障诊断和控制决策,引起了广泛的关注和研究.随着数据规模日益增长,能够提供较为完备数据分析算法库的主流单机环境如Matlab、R等已无法较好地应对大规模时间序列分析场景下的数据处理需求.而现有的并行分析算法数量有限,常与平台相互绑定,更换平台需对算法进行二次开发,可扩展性较差.本文旨在设计一种通用的近似解分析框架,支持第三方算法快速实现并行化,解决因数据规模过大而导致的算法适用性问题.分析框架主要包含任务划分、治理和合并三个步骤.任务划分通过冗余保留了数据的局部相关性,生成相互独立的子任务,减少分布式节点之间的数据通信和同步开销.对于任务划分问题,本文提出了近似解代价模型,得到了最优的任务划分方案.基于Spark平台设计并实现了原型系统,实验结果表明,该系统在确保分析结果准确性的前提下,其加速能力随着并行程度保持近似线性的增长,解决了单机算法的数据规模受限问题.同时,该系统易于集成与扩展,使数据分析人员免于算法重复开发.

考虑成本的多出救点多物资应急调度研究

为减少应急资源调度过程中发生的经济损失,在某些最短完成时间值要求不十分敏感的应急资源调度基础上,提出引入资源需求紧迫程度的多出救点多物资调度模型,同时定义调度成本目标函数,并结合分治算法基本思想,求解综合调度效益最高的出救点方案,最后进行实例分析和对比分析。结果表明:在对应急资源储备仓库进行选择时,需求紧迫度的引入能极大地改善调度的盲目性,结合基于道路因素建立的成本函数能有效地减少不必要的调度成本,从而提高资源调度的综合效益。

基于动态描述逻辑的服务组合及质量模型

本文提出一个基于动态描述逻辑的Web服务自动组合框架.在该框架中,Web服务自动组合被划分为逻辑层和实现层两部分,于是服务的自动组合问题在逻辑上归结为一个动作规划问题,在实现上归结为一个根据动作选择具体服务的服务选择问题.基于该框架,本文给出了一个支持非线性QoS聚合和显式数据流声明的QoS模型.得益于合理的服务组合框架和QoS模型,本文提出的服务选择方法可以将复杂服务分解为较小的服务,然后分别用递归的剪枝算法求解.实验显示该方法是有效的,不但可适应候选Web服务数量较大的情况,且相对于现有方法能更好地处理服务组合中的复杂结构.

生物网络比对的模型与算法

生物网络比对是生物体结构、功能和进化分析的重要研究手段.首先给出了生物网络比对问题的形式化定义;其次重点分析了现有的比对模型和算法,按照比对方法的数学特性对其进行了分类,并对典型算法结合应用进行了深入探讨,对3类比对方法的特点进行了总结与比较;再次,分析归纳了生物网络比对软件,阐述了生物网络比对研究的意义和应用;最后指出了生物网络比对研究中的关键问题及生物网络比对未来的研究方向.