0-1背包问题算法分析与研究

0／1背包问题是计算机算法中一个经典问题。提出背包问题在现实生活中具有广泛的应用,从理论入手,给出背包问题的数学描述,并对0-1背包问题的四种经典算法：分支界限法、动态规划法、近似算法、遗传算法的算法思想进行详细描述。并对四种算法在实现的时间,空间和准确性等性能方面进行分析和对比,总结四种方法实现的优缺点,并得出结论：在不同的约束条件下,四种算法各有优劣,但遗传算法应该是未来发展的方向。     

基于克隆选择算法的面向程序路径测试数据生成方法

面向程序路径的测试数据自动生成技术是软件测试自动化的关键技术之一.文中结合程序分支函数叠加法和克隆选择算法的全局搜索性,提出一种基于克隆选择算法的面向程序路径测试数据生成方法.希望能够借助克隆选择算法具有多样性、记忆性、可实现快速全局优化搜索的优点,设计一种新的面向程序路径的测试数据自动生成方法.对算法的原理和实现做了详细描述,并将其与传统的基于遗传算法、模拟退火算法来实现软件测试数据自动生成方法进行实验对比,证实了该方法能较快地生成指定路径的测试数据.     

基于分支函数线性逼近的测试数据自动生成算法

软件测试是保证软件可靠性的一个重要手段.面向路径测试是软件测试中一种重要方法.提出了一种分支函数线性逼近的测试数据自动生成算法.结合赵瑞莲给出的谓词切片算法和程序DUC表达方式以及本文提出的算法,给出了一个基于程序执行的路径测试及测试数据自动生成新算法.由于算法采用DUC表达式,不仅可以从源端判断子路径是否可行,而且有效地降低了不可行路径对算法性能的影响.另外,与现有文献中单纯利用分支函数极小化方法的算法相比,新算法由于有机结合了分支函数线性逼近和极小化方法的长处,因此减少了测试用例的数量,提高了测试效率.     

一种支持大规模数据逻辑函数优化的改进选拔算法

选拔算法是两级逻辑综合中求解最小化覆盖的经典方法之一,但在输出变量集合和质立方体集合规模较大的情况下,采用选拔法求最小化覆盖存在空间复杂度高、求解时间长等问题。为此,提出了求解多输出函数最小化覆盖的改进选拔算法。利用相交迭代和局部搜索的思想,分别对选拔法的极值运算和分支处理进行了改进。实验结果表明,在现有计算机资源条件下,该算法为大规模数据条件下逻辑函数的优化提供了一种有效的方法。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

融合注意力分支特征的甲烷泄漏红外图像分割

甲烷是现代化工业生产和社会生活的重要能源之一,实现其有效探测与分割对于及时发现甲烷泄漏事故并识别其扩散范围具有重要意义。针对红外成像条件下甲烷气体图像的轮廓模糊、泄漏的甲烷气体与背景对比度较低、形状易受大气流动因素影响等问题,本文提出一种融合注意力分支特征的红外图像分割网络（Attention Branch Feature Network,ABFNet）实现甲烷气体泄漏探测。首先,为增强模型对红外甲烷气体图像的特征提取能力,设计分支特征融合模块将残差模块1和残差模块2的输出特征与残差模块3以逐像素相加的方法融合,获取红外甲烷气体图像丰富细致的特征表达以提高模型识别精度。其次,为进一步加快模型的推理速度,将标准瓶颈单元中的3×3卷积替换为深度可分离卷积,大幅度减少参数量达到实时检测甲烷气体泄漏。最后,将scSE注意力机制嵌入到分支特征融合模块,更多地关注扩散区域边缘和中心语义信息以克服红外甲烷气体轮廓模糊对比度低等问题提高模型的泛化能力。实验结果表明,本文提出的ABFNet模型AP50@95、AP50、AP60定量分割精度分别达到38.23%、89.63%和75.33%,相比于原始YOL...     

基于分布式分支界限算法的产消者联盟电能交易策略

随着分布式能源在配电网中的高比例渗透,产消者作为新型主体参与市场竞争日益受到关注。基于合作博弈的产消者联盟电能交易可增加产消者的整体收益,产消者采用动态联盟结构可提升对环境变化的适应协调能力。为此,提出基于多代理系统（MAS）的产消者联盟运行框架,以及在此框架下产消者联盟电能交易的双层优化模型。上层模型使用分布式分支界限算法求解最优联盟结构下的产消者电能交易策略;下层模型根据更新的交易电价调整产消者购售电计划。最后通过仿真算例验证了所提方法的合理性、有效性及模型的可扩展性。     

一种改进残差深度网络的多目标分类技术

由于受场景、视角、光照、尺度变化以及局部变形等因素的影响,对重叠目标、拥挤目标、小目标的识别精度较低,提出了一种改进多支路的残差深度卷积神经网络来提高多目标识别的准确度。首先,在第一个卷积残差块layer1后保留恒等映射的同时,增加一个1×1的短接分支尽可能多的保留原始特征;再平行嵌入一个修改激活函数RELU6的空间_通道注意力机制模块（CBAM）;最后这三个特征图进行融合。融合后的特征层着重关注空间和通道中比较显著的信息,从而增强特征图的特征表达能力,以至于卷积神经网络(CNN)获得更多的判别特征,从而大大提高物体识别精度。在FashionMNIST和Cifar10两个数据集的对比性实验显示改进的resnet50算法是准确性-速度较为折中的目标识别模型。     

基于双分支融合注意力机制的图像分割算法

针对DeepLabV3+在特征提取阶段忽略了不同尺度特征重要程度出现的部分细节信息损失导致图像分割不细致,提出一种融合双分支特征提取和注意力机制的改进算法. ResNet101骨干网络初步提取出的特征图作为注意力机制的输入特征,解决了网络退化及梯度消失的问题,也能够捕获到被DeepLabV3+忽略的图像细节信息;设计双分支特征提取机制扩大特征提取能力,细化图像边缘信息以优化网络对不同尺度特征关注不均的问题;同时,联合采用交叉熵损失和类别不平衡函数两种损失函数作为损失函数,通过聚焦于前景样本降低背景的影响,提高算法分割精度.实验结果表明,改进算法在PASCAL VOC 2012和CityScapes数据集上的平均交并比(MIoU)值分别达到了79.92%和68.59%,与经典算法和基于DeepLabV3+改进的算法相比,特征提取的准确性有所提高,分割效果更优.     

分支定价方法求解带二维装箱约束的车辆路径问题EI北大核心CSCD

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.