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

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

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

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

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

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

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

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

多尺度自适应上采样的图像超分辨率重建算法

针对现有基于卷积神经网络的图像超分辨率重建网络中存在的训练难以收敛、无法适配多个放大系数和无法进行非整数放大系数上采样的问题,提出了一种基于多尺度和分而治之思想的自适应上采样图像超分辨率重建算法。该算法通过改进后的多尺度通道注意力特征提取模块对低分辨率图像进行多尺度特征提取以生成不同尺度下的特征图,再将其输入瓶颈层实现全局特征融合,使用基于分而治之的自适应上采样模块获得超分辨率图像,从而解决了不同放大系数的适配问题和非整数放大系数的上采样问题。在对比实验中,该算法在不使用任何初始化方法时仍然具有良好的收敛性。在整数放大系数下,该算法的图像重建性能超过当前主流的超分辨率网络,PSNR和SSIM性能相比MRFN分别提升了0.34 dB和0.039 1。在非整数放大系数下,其PSNR性能相比双三次插值方法平均提升1.24 dB,且不需要对每一个放大系数都进行训练。

基于模型驱动的分治并行函数式程序生成及自动验证

并行计算作为人工智能发展的动力,使得并行算法的可解释性和安全性成为人工智能领域重要研究方向。形式化方法以数理逻辑为基础,已经成为复杂安全苛求系统可信构建的重要方法,而函数式编程则在算法领域中具有更强的数学表达性。本文旨在提出一种基于模型驱动的分治并行函数式程序生成及自动验证方法,融合形式化方法,以解决目前分治并行程序生成和验证中缺乏可解释性、易错、低可信度等问题。首先,采用分划递推法和循环不变式等新策略推导出串行算法;然后,利用辅助函数和算法连接函数将其提升为并行算法,并使用我们提出的并行算法设计语言Radl+进行描述;进而,采用同态定理验证框架在Isabelle中验证算法连接函数满足同态定理,即提升后的算法可并行化;最后,提出了Radl+→Haskell转换规则,设计了“Radl+→Haskell并行程序生成系统”软件原型。实验结果表明,本文能够生成和验证一系列算法的并行函数式程序,并且能够产生良好的加速比。本文方法不仅具有一定的可解释性,而且自动验证减少了传统手工验证易错性和繁琐的工作量,保证算法正确性和提高安全性,对大幅度提升高可信并行函数式程序的开发效率具有重要意义。

输送带跑偏检测方法研究

基于机器视觉的输送带跑偏检测方法检测的输送带边缘特征中包含伪边缘,现有研究难以识别伪边缘,且多场景适应性差。针对该问题,对输送带监控图像提取感兴趣区域(ROI)并进行归一化,采用较大阈值区间的Canny算法提取边缘特征点,以提高算法的场景适应性,并采用形态学滤波方法处理部分杂质及伪边缘;对于Canny算法无法检测到有效边缘的图像,对提取的ROI进行伽马变换和45,135°方向的梯度滤波,以增强边缘特征,之后进行基于Canny算法的特征点提取和形态学滤波。以边缘点像素值关系、邻域特征、紧密性特征,以及边缘线长度、相对位置、斜率等作为约束条件,采用基于分治搜索思想的直线筛选排序算法对提取的边缘特征点进行筛选及拟合,得到输送带实时边缘。将实时边缘的像素值与未发生跑偏时边缘像素值做差,得到当前跑偏的像素值。试验结果表明,针对多种场景下的输送带监控图像,基于Canny算法和直线筛选排序的输送带跑偏检测方法检测误差小于3个像素值,百张图像检测时间为6.9451 s,边缘计算机处理4路视频图像的CPU占有率为132%,满足现场输送带边缘检测的准确性、实时性要求。

基于3DEXP的船舶管段装配信息计算方法

以实现任意形式船舶管段装配数据的自动化计算为目的,提出一种船舶管段装配信息计算方法。基于管段三维模型的重要特征,采用分治法构建管段通用数学模型,将复杂管段简化为相似子结构,计算相对角度和相对距离等管段装配信息。该方法在3DEXP上成功应用,研究成果对进一步探索船舶管系的数字化设计与制造具有重要意义。

带复杂计算的金融领域自然语言查询的SQL生成

研究金融领域基于自然语言查询的结构化查询语言(SQL)生成问题(Text-to-SQL),构建一个金融领域Textto-SQL数据集,称为SOFT数据集.该数据集覆盖了金融领域的常见查询,具有鲜明的特点,并对Text-to-SQL提出了挑战.提出金融领域Text-to-SQL模型FinSQL,该模型优化了对金融领域复杂查询的支持.通过分析一类复杂计算查询(行计算查询)的特点,提出一种基于分治的方法,即先将一个行计算查询分解为若干个子查询,分别针对每个子查询生成SQL语句,再将子查询的SQL语句组合在一起得到原始查询的SQL语句.在SOFT数据集上进行验证,结果显示,本研究所提的方法在复杂查询上效果优于已有方法.特别地,所提出的模型FinSQL能够较好地支持行计算查询.

“分而治之”方法构建复杂分子体系高精度势能面及应用

“分而治之”是处理复杂分子势能面的一种快速简洁方案。本文介绍了近年来本课题组在这一领域的方法研究进展及相关应用研究。在新的组装势能面算法和数据库支持下,我们将复杂大分子势能面计算量降低到O(N1~2)次方的标度,并且计算精度接近DFT甚至CCSD(T)的水平。采用该方法,我们对两个不同的应用场景进行了测试。结果表明,高性能的组装势能面可以完成以往难以实现的大规模的分子结构搜索、稳定性分析以及新型分子结构设计等关键性任务。

基于设备协同的大规模卸载:融合分治和贪心的双层优化算法

随着通信技术的飞速发展,移动设备的数量不断激增,而这也将导致大规模卸载场景频频发生。但是如何在多项式时间内解决大规模卸载问题仍然是个挑战。本文基于协作计算网络架构提出一个融合分而治之和贪心的双层优化算法,称为DCGreedy。该算法可在多项式时间内高效求解所有任务的卸载策略和资源分配方案。在满足所有约束的同时可以有效降低系统的总能耗。在至少400个移动设备的模拟场景下根据任务满足截止日期的总数、系统总能耗和算法运行时间来评估DCGreedy的性能。将DCGreedy与其他4种基准算法进行大量的实验对比,并发现在不同规模的卸载场景中DCGreedy的平均总能耗比排名第二的算法高出2.11%,而算法运行时间却仅为0.0049%,充分证实了DCGreedy在优化系统能耗的同时有效地减少了算法的运行时间。

基于分治法的神经网络修复方法

神经网络作为一种求解复杂问题的有效方法已经广泛应用于医学影像,自动驾驶等领域。然而,神经网络十分脆弱,对一个样本添加一点肉眼难以察觉的微小扰动就可能导致神经网络做出错误的判断。当神经网络出现了错误的行为,常用的修复方法是对神经网络进行重训练或者微调,然而这些方式需要较高的代价而且无法保证完全修复错误行为。在本文中,我们关注神经网络的完备修复问题,给定一个待修复的神经网络和一个目标样本集合,该问题要求修复后的神经网络在目标样本集合上表现出100%的正确率。在本文中,我们基于分治法的思想提出了一种神经网络修复方法。在该方法中,我们将目标样本集合不断划分为更小的集合,直到样本集合达到可接受的规模,之后对于划分得到的每一个集合逐个进行修复得到一个局部补丁,最后所有的局部补丁进行整合得到对于整个特征空间的补丁。在两个公开数据集上的实验表明我们的方法优于当前最先进的神经网络修复算法。针对对抗攻击和后门攻击生成的目标样本集合,我们的方法不仅完全修复了神经网络在目标样本集合上的行为,而且将网络在相同攻击方式生成的测试集上的准确率分别提高了55.79%和60.59%。同时,我们的方法可以避免修复后网络在标准测试集上的准确率大幅度降低。

基于分治策略的SAT差分自动化搜索算法及其应用

为了提高自动化搜索效率,结合分治策略提出了一种基于SAT模型的最优差分特征搜索算法。利用任意部分连续轮的Matsui边界条件提供的信息,将搜索空间划分为互不相交的子集。通过分析SAT差分模型间的可满足性关系,提出一种降序分支搜索链模型。进一步地,在模型优化层面,减少了需搜索划分子集数量的方法;在算法实现层面,结合并行技术实现对模型搜索空间的约减。将加速算法应用于ARX类密码算法族SPECK,获得了20轮、14轮、11轮SPECK-48、SPECK-96、SPECK-128的最优差分特征,较现有最好结果分别提高了1轮、4轮、2轮。

极值指数的分布式矩率估计量

基于分治算法和矩率估计量构造了分布式矩率估计量并证明其相合性和渐近正态性.

基于改进双向峰-谷搜索算法的煤矸模型电磁波正演模拟

实现放顶煤过程煤矸含量自动识别是综采自动化的重要目标,现有煤矸含量自动识别方法存在准确性、实时性较低等问题。放顶煤过程产生的煤矸混合物是由煤、矸石和空气形成的三相介质,各相介质的电性参数不同,在不同组分的混合三相介质中,电磁波的传播特性也不同。煤和矸石相对介电常数差异明显,通过研究不同含矸率煤矸混合物的电性参数,可为放顶煤工作面含矸率自动识别提供新的思路和方法。为了探究不同含矸率煤矸混合物的电性差异,提出了一种基于分治策略的双向峰-谷搜索算法,基于该算法建立了煤矸多相离散随机介质模型,基于麦克斯韦方程组及其本构关系方程,利用时域有限差分法对所建立的模型进行电磁波正演模拟。分析表明,基于分治策略改进双向峰-谷搜索算法后,煤矸多相离散随机介质模型中的煤、矸石、空气三相之间不仅存在明显的相界面,且各相离散程度更大,不存在聚集现象,因此局部介质也能体现整体的电性参数,能够满足电磁波正演的介质模型需求。正演模拟结果表明:(1)激励信号的频率会影响透射波的幅值,在12 GHz范围内,激励信号频率越高,透射波幅值越大;频率过低会降低信号的鲁棒性,激励频率应高于2 GHz。(2)煤矸混合物的含矸率与介质整体的等效介电常数呈正相关。含矸率越高,电磁波信号的传播损耗越多,接收平面接收到的信号幅值越小,电磁波信号穿透介质所用的时间越长。不同含矸率之间呈现明显的差异性,可以用作综采放顶煤含矸率识别的依据。

基于改进TCNN算法的电子组装路径优化研究

电子组装不断朝着规模化、密集化的趋势发展,对电子组装路径进行优化,是提升电子组装生产过程的生产效率重要途径。传统的电子组装路径优化算法是ACO算法,但ACO算法的效率低,逐渐无法满足规模越来越大的电子组装路径优化问题求解需求。因此提出一种高效的TCNN算法进行电子组装路径优化,并采取并行化策略和分治策略对其进行优化,以进一步提升TCNN算法的效率和精度。实验结果显示,改进TCNN算法的效率远超过ACO算法,优化比比ACO算法仅低2.4%。综上所述,改进TCNN算法比ACO算法更能满足大规模电子组装路径优化的需求。

海量数据下光滑分位数回归聚合估计

计算机内存限制和分位数回归损失函数的不光滑性,对海量数据下分位数回归的研究提出了挑战。文章将聚合估计方程与核卷积光滑方法相结合,提出了一种在分布式环境下基于估计方程的光滑分位数的回归聚合估计算法(DSCQR)。理论研究表明,在分块数K满足一定条件时,聚合估计量与全样本估计量具有相同的渐近性质。模拟和实证研究结果表明,所提方法和已有研究提出的DCQR方法相比,在计算速度上具有显著优越性,且在K满足一定条件时具有相当的稳健性。

基于动态规划和分治算法减小相控阵辐射“凹坑”

为使以特定功率覆盖给定水平角和俯仰角情况下各波束在该区域内的功率极差最小,计算出各组合成波束的天线阵移相器配置。用动态规划方法找出使天线对站点影响最小的一组移相器配置;用分治算法改进并构建接近给定功率信号幅度的模型;根据半功率角来确定辐射范围,根据站点的天线覆盖数确定一个波束参与计算的天线单元,通过改进的分治算法求出每个波束的凹坑,并找出满足要求的一组相控阵天线的移相器配置。实例分析表明,该算法能有效解决在给定功率覆盖给定水平角和俯仰角情况下有效减小相控阵辐射“凹坑”。

基于像素级分治策略的超分网络加速方法

在图像超分辨率任务中通过加大网络参数量和计算复杂度可以提升性能,但该方法不适用于很多计算能力受限的应用场景。因此当超分图像较大时,轻量化超分网络的设计是个至关重要的方向。针对该问题的一个经典加速策略是分治法(将大问题拆解成小问题逐一击破),现有方法通常将大图像的超分问题分解成不同子图像块的超分问题,并根据每个子图像块的超分难易程度,使用不同计算量规模的网络分别进行超分处理,从而减少了冗余的计算。然而,该分治策略仅将子问题分解到了子图像块级别,并未达到满意的加速效果。据此,将分治策略中的子问题分解进一步深入到了像素级,根据不同像素的超分难易程度采用不同计算量的网络来分而治之。具体来说,引入一个不确定度估计的思想在训练中自适应预测每个像素所在位置的超分难易程度;提出了一个自适应像素特征精炼模块,根据不同像素的超分难易程度,对超分困难的像素点进行采样和特征修复,从而为困难点的超分问题分配了更多的计算量进行处理。大量实验表明,相比现有的子图像块级的超分网络加速方法,提出的像素级超分网络加速方法更为高效,在相同精度的情况下,有效减少了计算复杂度。

基于分治策略的海上风电场集电系统拓扑优化设计

为了解决海上风电场集电系统拓扑设计中,传统采用聚类算法面临的回路负载差异大、算法不稳定以及各类改进最小生成树算法面临的搜索效率较低的问题,提出一种基于分治策略的拓扑优化方法。首先,根据风力机位置分布将整场划分为多个子区域,各子区域的容量满足负载平衡条件;然后,通过最小生成树算法,对子区域进行拓扑优化;最后,采用遍历手段对上述过程进行搜索,生成拓扑方案库,根据总成本最低获取最佳方案。对某海上风电场项目进行拓扑优化设计,验证了方法的有效性、普适性和实用性。