求解恰当可满足性问题的随机局部搜索算法

可满足性问题(SAT)是一种NP完全问题,被广泛运用于人工智能和机器学习等研究。恰当可满足性问题(XSAT)是SAT中一类重要的子问题。目前的大部分关于XSAT的研究主要为理论层面,对高效的求解算法特别是具有高效验证性的随机局部搜索算法研究很少。针对以上问题,分析了基础编码和等价编码两种转化方式的公式的部分性质,提出一种直接求解XSAT的随机局部搜索算法WalkXSAT。首先使用随机局部搜索框架进行基础搜索与条件判定;其次加入变元所属文字的恰当不可满足计分值,优先处理不易恰当满足的变元;然后使用防重复选择翻转变元的启发式策略减小搜索空间;最后,采用多种来源以及多种格式的实例进行对比实验。在直接求解XSAT时,相较于ProbSAT,WalkXSAT的变元翻转次数与求解时间显著减少;在求解基础编码转化后的实例中,当实例变元规模大于100时,ProbSAT已失效,而WalkXSAT依然能够在短时间内求解。实验结果表明,所提WalkXSAT精确性高、稳定性强、收敛快。

随机正则3-可满足性问题的解簇结构分析

正则3-可满足性(3-SAT)问题是一个NP难问题,研究正则3-SAT问题解簇结构变化,旨在深入理解该问题的判定难度和可满足性解的分布情况。然而,现有分析模型只研究了接近簇集相变点的几个离散值,在不同约束密度下,缺乏统一的分析模型来描述解簇的结构演变。为了解决这一问题,提出解簇结构相变分析模型(PMSS)。该模型主要思想是采用WalkSAT算法和信息传播算法求得正则3-SAT问题可满足的初始解,再利用随机游走构造该初始解的解簇,并对解簇进行分析。用模块度和社区度量解簇社区结构,用结构熵度量解簇结构复杂性。实验结果表明,PMSS能够准确分析解簇结构演变过程,并且正则3-SAT问题实例的可满足相变点位于13~14,与使用Zchaff求解器得到的相变点一致,进一步验证了PMSS的有效性。

知识图谱的双注意力机制推荐方法

为解决知识图谱推荐方法中存在的忽略用户个人信息,或将用户和项目采用相同注意力机制,致使用户和项目的潜在语义表达不充分的问题,提出了一种知识增强的双注意力机制推荐方法。采用交叉压缩融合单元获取用户个人信息和交互历史的潜在特征,以增强用户特征表示;使用不同注意力机制关注用户和项目的重要邻居,以增强知识图谱中的结构信息和语义信息表示。为了验证方法的有效性,在MovieLens-1M、MovieLens-20M、Book-Crossing和Last. FM这4个数据集上进行实验,并与RippletNet、KGAT、CKAN等6种方法进行对比分析。结果表明,本文方法与RippletNet、KGCN、LKGR等方法相比,受试者工作特征曲线下面积(area under the receiver operator characteristic curve,AUC)性能平均提升了5.34%。

单阶段实例分割——从局部到整体的网络结构研究综述

单阶段实例分割是近年来深度学习领域的研究热点,其通过将目标检测和目标分割并行的方式实现图像的实例级分割,该方法目前已被广泛应用于图像目标分割领域。首先,阐述了单阶段实例分割基本原理。然后,从局部和整体2个方面对单阶段实例分割的网络结构进行梳理,在局部网络结构方面,从特征提取、特征融合、特征预测3个方面进行归纳,其中,在特征预测部分,按照有锚框到无锚框的思路对目标边界框的生成方式进行分类,按照全局掩膜到局部掩膜的思路对目标掩膜的表示方式进行分类,全局掩膜包括原型系数方法、目标位置方法和目标边界方法,局部掩膜包括目标轮廓方法、目标位置方法和目标特征方法;在整体网络结构方面,对22个主流的网络结构进行总结。接着,归纳了单阶段实例分割在医学图像分割、视频图像分割、遥感图像分割等应用领域的发展现状。最后,对单阶段实例分割的发展方向进行展望。

求解Max-Re-SAT的离散混沌量子蝙蝠算法

针对最大正则可满足性问题求解算法的研究空缺,以及提升求解最大可满足性问题的智能优化算法的精度,基于蝙蝠算法(bat algorithm,BA),提出了一种基于离散混沌量子的蝙蝠算法。在该算法中,将连续数值转化为离散的二进制编码,对算法进行了离散化处理。该研究运用量子理论、引入量子比特编码和启发式量子变异,通过量子旋转门改变非最优个体的概率振幅来实现变异,解决了早熟和收敛速度慢的问题。在位置更新中,使用混沌映射替代固定参数,增强了灵活性和多样性,提高了全局寻优能力和求解效率。实验结果表明:在随机正则可满足性问题实例产生模型产生的不同规模算例上,所提算法的求解精度远远高于传统启发式算法;同时,与获奖的求解器相比,也具有一定的竞争力,验证了该算法的有效性。

seqAFF-ResNet:面向新冠肺炎的诊断模型

新冠肺炎的计算机辅助诊断是一种实现智能化影像诊断、临床诊断及临床分型的方法,在新冠肺炎的辅助诊断过程中,图像的病灶区域与组织边界对比不明显,导致模型不能较好地关注病灶区域,对有效特征的提取不够充分。针对上述问题,提出一个新冠肺炎辅助诊断模型seqAFF-ResNet(sequential attentional feature fusion-residual neural network)。设计串行注意力特征融合(sequential attentional feature fusion,seqAFF)模块,该模块串联条带注意力特征融合(strip attentional feature fusion,SAFF)模块和全局局部注意力特征融合(global local attentional feature fusion,GLAFF)模块,获取图像的纹理信息以及全局和局部信息,弥补卷积神经网络对于细节特征提取能力的不足,使得模型可以更好地关注于病灶区域;构造深浅层特征融合(deep and shallow feature fusion,DSFF)模块,使用深层特征的语义信息来影响浅层信息,同时将浅层的空间信息传入深层特征中,使深浅层特征进行有效融合,捕获丰富的上下文信息,实现跨层注意力特征增强,使网络能够更好地定位病变区域。与残差神经网络(residual neural network,ResNet)相比,seqAFF-ResNet准确率提升了3.42%,精确率提升了3.53%,F1分数提升了2.77%,AUC值提升了0.9%,实验结果表明,所提模型可以提高新冠肺炎的识别准确率,且与同类模型相比具有更好的性能。所提方法为新冠肺炎的辅助诊断提供了有效的识别方法,对新冠肺炎的计算机辅助诊断具有重要意义。

地震场景下无人机群路径规划与任务分配均衡联合优化

无人机(UAV)群路径规划和任务分配是UAV群救援应用的核心,然而传统方法分开求解路径规划与任务分配,导致资源分配不均。为了解决上述问题,结合UAV群的物理属性与应用环境因素,改进蚁群算法(ACO),提出联合并行蚁群(JPACO)模型。首先,借助分级信息素增强系数机制更新信息素,以提高JPACO任务分配均衡性和能耗均衡性;其次,设计路径平衡因子和动态概率转移因子优化蚁群模型易陷入局部收敛的情况,从而提高JPACO的全局搜索能力;最后,引入集群并行处理机制,以降低JPACO运算耗时。将JPACO与自适应动态蚁群算法(ADACO)、扫描动态蚁群算法(SMACO)、贪婪策略蚁群算法(GSACO)和交叉蚁群算法(IACO)在公开数据集CVRPLIB上对比最优路径、任务分配均衡、能耗均衡和运算耗时。实验结果表明:与IACO和ADACO相比,JPACO处理小规模运算的最优路径平均值分别降低7.4%和16.3%;处理大规模运算的求解耗时与GSACO、ADACO相比降低8.2%和22.1%。以上结果验证了JPACO在处理小规模运算时能够改善最优路径,处理大规模运算时任务分配均衡、能耗均衡和运算耗时明显优于对比算法。

图谱嵌入传播的推荐方法

根据知识图谱(KG)丰富用户和项目信息的侧重不同,现有的图谱嵌入传播的推荐方法可归纳为用户嵌入传播、项目嵌入传播和混合嵌入传播这3类。用户嵌入传播方法侧重使用用户交互的项目和KG学习用户表示;项目嵌入传播方法使用KG中的实体表征项目;而混合嵌入传播方法融合了用户-项目交互信息和KG,以弥补前两类方法存在的信息利用不充分的不足。为深入对比3类方法的技术特点,重点剖析图谱嵌入传播的推荐方法中的图谱构建、嵌入传播和预测这3个核心任务的关键技术;同时,在MovieLens、Booking-Crossing和Last.FM通用数据集上复现每类方法中的主流模型,通过使用点击率(CTR)指标对比分析上述方法的效果。分析实验结果可知,混合嵌入传播方法的推荐性能最优,它综合了用户和项目嵌入传播方法的优势,利用交互信息和KG增强用户和项目表示;此外,对比分析每类方法,阐述各自的优缺点并展望未来的研究工作。

面向下颌骨骨折检测的主辅网络YOLOv5模型

为了检测出下颌骨的骨折部位,帮助医生采取准确的治疗方案,同时解决骨折部位的CT影像受到出血和其余未骨折部位等的干扰所导致的骨折部位信息提取不充分、骨折部位检测精度不高等问题,提出了一种面向下颌骨骨折检测的主辅架构YOLOv5(primary and auxiliary YOLOv5,PA-YOLOv5)网络。首先,主干网络实现局部注意力和特征图多尺度通道混洗的耦合,获得影像的局部多尺度信息;其次,辅助网络实现结构重参数化和Transformer的耦合,获得影像的全局多尺度信息;最后,在所提出的数据集上进行消融实验和对比实验。结果表明,所提出的PA-YOLOv5网络的mAP(0.50)为98.18%,较原始YOLOv5网络提升了2.57%。所提出的网络能够较好地进行下颌骨骨折部位的检测,为医生提供相应的参考,从而辅助医生针对不同的骨折部位采取不同的治疗手段,为下颌骨骨折治疗提供一种新的诊断方法。