栏目文章信息

    先进计算 栏目所有文章列表
    (按年度、期号倒序)
        一年内发表的文章 |  两年内 |  三年内 |  全部
    Please wait a minute...
    选择: 显示/隐藏图片
    1. 智能算法的亚群优化策略综述
    杜晓昕, 周薇, 王浩, 郝田茹, 王振飞, 金梅, 张剑飞
    《计算机应用》唯一官方网站    2024, 44 (3): 819-830.   DOI: 10.11772/j.issn.1001-9081.2023030380
    摘要157)   HTML2)    PDF (2404KB)(129)    收藏

    群智能算法的优化是提升群智能算法性能的一个主要途径,随着群智能算法越来越广泛地运用到各类模型优化、生产调度、路径规划等问题中,对智能算法性能的要求也越来越高。亚群策略作为一种优化群智能算法的重要手段,能够灵活地平衡算法的全局勘探能力和局部开发能力,已经成为群智能算法的研究热点之一。为了促进亚群优化策略的发展和应用,对动态亚群策略、基于主从范式的亚群策略和基于网络结构的亚群策略进行了详细调查,阐述了各类亚群策略的结构特点、改进方式和应用场景。最后,总结了亚群策略目前存在的问题以及未来的研究趋势和发展方向。

    图表 | 参考文献 | 相关文章 | 多维度评价
    2. 基于自适应布谷鸟优化特征选择的 K-means聚类
    孙林, 刘梦含
    《计算机应用》唯一官方网站    2024, 44 (3): 831-841.   DOI: 10.11772/j.issn.1001-9081.2023030351
    摘要91)   HTML1)    PDF (2193KB)(81)    收藏

    K-means聚类算法随机确定初始聚类数目,而且原始数据集中含有大量的冗余特征会导致聚类时精度降低,而布谷鸟搜索(CS)算法存在收敛速度慢和局部搜索能力弱等问题,为此提出一种基于自适应布谷鸟优化特征选择的K-means聚类算法(DCFSK)。首先,为提升CS算法的搜索速度和精度,在莱维飞行阶段,设计了自适应步长因子;为调节CS算法全局搜索和局部搜索之间的平衡、加快CS算法的收敛,动态调整发现概率,进而提出改进的动态CS算法(IDCS),在IDCS的基础上构建了结合动态CS的特征选择算法(DCFS)。其次,为提升传统欧氏距离的计算精确度,设计同时考虑样本和特征对距离计算贡献程度的加权欧氏距离;为了确定最佳聚类数目的选取方法,依据改进的加权欧氏距离构造了加权簇内距离和簇间距离。最后,为克服传统K-means聚类目标函数仅考虑簇内的距离而未考虑簇间距离的缺陷,提出基于中位数的轮廓系数的目标函数,进而设计了DCFSK。实验结果表明,在10个基准测试函数上,IDCS的各项指标取得了较优的结果;相较于K-means、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)等算法,在6个合成数据集与6个UCI数据集上,DCFSK的聚类效果最佳。

    图表 | 参考文献 | 相关文章 | 多维度评价
    3. 求解恰当可满足性问题的随机局部搜索算法
    赵星宇, 王晓峰, 杨易, 庞立超, 杨澜
    《计算机应用》唯一官方网站    2024, 44 (3): 842-848.   DOI: 10.11772/j.issn.1001-9081.2023030364
    摘要115)   HTML0)    PDF (906KB)(28)    收藏

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

    图表 | 参考文献 | 相关文章 | 多维度评价
    4. 量子近似优化算法在精确覆盖问题中的应用
    郭玲玲, 李志强, 段孟环
    《计算机应用》唯一官方网站    2024, 44 (3): 849-854.   DOI: 10.11772/j.issn.1001-9081.2023030332
    摘要122)   HTML2)    PDF (1100KB)(70)    收藏

    精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法对量子逻辑门中的参数进行优化。首先,通过精确覆盖问题的数学模型建立经典伊辛模型;其次,利用量子理论中的旋转变量对经典伊辛模型进行量子化,再用泡利旋转算子代替旋转变量,得到量子伊辛模型和问题哈密顿量,提高QAOA寻找最优的速度;最后,以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积,得到问题哈密顿量期望的表达式,并由此设计生成量子线路。另外,通过经典处理器对两个酉变换中的参数进行优化,调整问题哈密顿量的期望值,从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验,实验结果表明,所提方案能够在多项式时间内以95.6%的概率获得问题的解,验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。

    图表 | 参考文献 | 相关文章 | 多维度评价
    5. 防恶意竞价的众包多任务分配激励机制
    张佩瑶, 付晓东
    《计算机应用》唯一官方网站    2024, 44 (1): 261-268.   DOI: 10.11772/j.issn.1001-9081.2023010024
    摘要119)   HTML3)    PDF (1958KB)(43)    收藏

    众包的飞速发展丰富了任务执行者的阅历和技能,使他们更加了解任务且倾向于同时完成多种任务,因此根据执行者对任务的主观偏好进行分配成为一种常见的任务分配方式;但是出于个人利益,执行者可能采取恶意竞价行为换取更高的收益,这对众包平台的发展是不利的。为此,提出一种防恶意竞价的众包多任务分配激励机制GIMSM(Greedy Incentive Mechanism for Single-Minded)。该机制定义了一个线性比值作为分配依据,再根据贪心策略从执行者比值递增的序列中依次选取并分配任务,最后按照支付函数对分配算法选中的任务执行者进行支付,得到最终的任务分配结果。在Taxi and Limousine Commission Trip Record Data数据集上进行实验。相较于TODA(Truthful Online Double Auction mechanism)、TCAM(Truthful Combinatorial Auction Mechanism)和FU方法,GIMSM在不同工人数下的任务结果平均质量水平分别提高了25.20、13.20和4.40个百分点,GIMSM在不同任务数下的任务结果平均质量水平分别提高了26.17、16.17和9.67个百分点。此外,GIMSM满足个体理性和激励相容,可在线性时间内得到任务分配结果。实验结果表明GIMSM具有良好的防恶意竞价性能,在具有大量数据的众包平台上有更好的表现。

    图表 | 参考文献 | 相关文章 | 多维度评价
    6. 基于两阶段搜索与动态资源分配的约束多目标进化算法
    马勇健, 史旭华, 王佩瑶
    《计算机应用》唯一官方网站    2024, 44 (1): 269-277.   DOI: 10.11772/j.issn.1001-9081.2023010012
    摘要184)   HTML2)    PDF (2145KB)(86)    收藏

    解决约束多目标优化问题(CMOP)的难点在于平衡目标优化和约束满足的同时兼顾解集的收敛性和多样性。为解决具有大型不可行区域和较小可行区域的复杂约束多目标优化问题,提出一种基于两阶段搜索与动态资源分配的约束多目标进化算法(TSDRA)。该算法在第一阶段通过忽略约束跨越不可行区域;然后在第二阶段通过动态分配两种计算资源协调局部开发和全局探索,兼顾算法的收敛性和多样性。在LIRCMOP和MW系列测试问题上进行的仿真实验结果表明,与四个代表性的算法CMOEA-MS(Constrained Multi-Objective Evolutionary Algorithm with Multiple Stages)、ToP(Two-phase)、PPS(Push and Pull Search)和MSCMO(Multi Stage Constrained Multi-Objective evolutionary algorithm)相比,所提算法在反转世代距离(IGD)和超体积(HV)上得到了更优异的结果。在LIRCMOP系列测试问题上,TSDRA获得了10个最佳的IGD值和9个最佳的HV值;在MW系列测试问题上,TSDRA获得了9个最佳的IGD值和10个最佳的HV值,表明所提算法可以更有效地解决具有大型不可行区域和较小可行区域的问题。

    图表 | 参考文献 | 相关文章 | 多维度评价
    7. 基于分解法与轨迹搜索的无人机群轨迹多目标优化模型
    柳隽琰, 江沸菠, 彭于波, 董莉
    《计算机应用》唯一官方网站    2023, 43 (12): 3806-3815.   DOI: 10.11772/j.issn.1001-9081.2022121882
    摘要129)   HTML3)    PDF (1873KB)(112)    收藏

    基于深度学习(DL)的传统多目标求解器存在模型利用率低以及容易陷入局部最优的问题。针对这些问题,提出了基于分解法与轨迹搜索的无人机群轨迹多目标优化模型(DTMO-UT)。所提模型包含编码与解码部分。首先,编码部分由设备编码器(Dencoder)和权重编码器(Wencoder)组成,用于提取物联网(IoT)设备的状态信息与权重向量的特征,其中权重向量代表分解多目标优化问题(MOP)的标量优化子问题,因此解决所有子问题即可解决该MOP。权重编码器可以实现对所有子问题的编码,从而提高了模型的利用率。然后,使用包含轨迹解码器(Tdecoder)的解码部分对编码特征进行解码,以生成帕累托最优解。最后,为了减少贪婪策略陷入局部最优的现象,为轨迹解码器设计轨迹搜索技术,即通过生成多个候选轨迹选标量值最优的轨迹作为帕累托最优解,从而增强了轨迹解码器在轨迹规划时的探索能力,并获得质量更好的帕累托集。仿真实验结果表明,所提模型相较于主流的基于DL的MOP求解器,在模型参数量降低98.93%的情况下,MOP解的分布性提高了0.076%,延展性提高了0.014%,平均综合性提高了1.23%,表现出较强的实用性路径规划能力。

    图表 | 参考文献 | 相关文章 | 多维度评价
    8. 基于动态簇粒子群优化的无人机集群路径规划方法
    王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳
    《计算机应用》唯一官方网站    2023, 43 (12): 3816-3823.   DOI: 10.11772/j.issn.1001-9081.2022111763
    摘要153)   HTML7)    PDF (2693KB)(176)    收藏

    路径规划对于无人机(UAV)集群的任务执行十分重要,而且高维场景中的计算通常很复杂。群体智能为解决该问题提供了较好的解决思路。粒子群优化(PSO)算法具有参数少、收敛速度快、操作简单等优点,尤其适用于路径规划问题,但它在应用时存在全局搜索能力差、容易陷入局部最优的问题。为了解决上述问题以提升无人机集群路径规划的效果,提出了动态簇粒子群优化(DCPSO)算法。首先,利用人工势场法和滚动时域控制原理建模UAV集群路径规划问题的任务场景;其次,引入Tent混沌映射和动态簇机制进一步提升全局搜索能力和搜索精度;最后,使用DCPSO算法优化模型的目标函数,以获得UAV集群的每个轨迹点的选择。在单峰/多峰、低维/高维不同组合的10种基准测试函数下的仿真实验结果表明,与PSO、鸽子启发优化(PIO)、麻雀搜索算法(SSA)和混沌扰动鸽群优化(CDPIO)算法相比,DCPSO算法具有更好的计算最优值、均值和方差,搜索精度更佳,稳定性更强。此外,UAV集群路径规划应用实例仿真结果也验证了DCPSO算法的性能与效果。

    图表 | 参考文献 | 相关文章 | 多维度评价
    9. 分布式工厂中微型制造单元多目标优化
    柳春锋, 李峥, 王居凤
    《计算机应用》唯一官方网站    2023, 43 (12): 3824-3832.   DOI: 10.11772/j.issn.1001-9081.2022111772
    摘要107)   HTML0)    PDF (1527KB)(65)    收藏

    由于各地区存在资源禀赋和产业政策差异,分布式生产对提升制造企业竞争力的作用非常重要,如何利用分布式生产增强大规模定制的柔性是提振消费信心需要解决的重要问题。结合微型制造单元的思想,在多市场多类型产品的分布式混流生产情景下,以最小化人工和转运等运营成本以及最大完工时间为目标,提出分布式工厂构建和生产调度集成模型,以求解微型单元构建、工人和机器配置和各批次产品的生产策略。所提模型能帮助企业实现产能快速释放和合理混流生产,从而实现满足多区域、多产品和差异化需求的分布式制造与销售,并在确保产量的同时降低制造过程中的运营成本。此外,设计多目标粒子群优化(MOPSO)算法求解模型,并将它与非支配排序遗传算法Ⅱ(NSGA?Ⅱ)和多目标模拟退火(MOSA)算法进行比较。大规模数值实验的结果表明,在相同的运行时间内,MOPSO算法在解集支配覆盖率(CM)、平均理想距离(MID)和最大分散度(MS)这3个指标上均优于NSGA?Ⅱ和MOSA算法。所提算法可以为微型化分布式生产系统提供高质量的生产运作决策方案。

    图表 | 参考文献 | 相关文章 | 多维度评价
    10. 结合遗传算法和滚动调度的多机器人任务分配算法
    邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟
    《计算机应用》唯一官方网站    2023, 43 (12): 3833-3839.   DOI: 10.11772/j.issn.1001-9081.2022121916
    摘要343)   HTML6)    PDF (2617KB)(191)    收藏

    研究多机器人任务分配(MRTA)的目的是提高智能工厂中机器人完成任务的效率。针对现有算法在处理大规模、多约束的MRTA时存在不足的问题,提出一种结合遗传算法和滚动调度的MRTA算法(ACGARS)。首先,在遗传算法中采用基于有向无环图(DAG)的编码方式高效地处理任务之间的优先级约束;其次,在遗传算法的初始种群中加入先验知识以提高算法的搜索效率;最后,设计基于任务组的滚动调度策略用于减小求解问题的规模,从而实现对大规模问题的高效求解。在大规模问题实例上的实验结果表明,相较于构造性启发式算法(CHA)、最小化干扰算法(MIA)和基于惩罚策略的遗传算法(GAPS)生成的方案,当任务组数为20时,所提算法生成的方案的平均订单完成时间分别缩短了30.02%、16.86%和75.65%,验证了所提算法能有效地缩短订单的平均等待时间,提升多机器人任务分配效率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    11. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题
    黄霖, 符强, 童楠
    《计算机应用》唯一官方网站    2023, 43 (12): 3840-3847.   DOI: 10.11772/j.issn.1001-9081.2022121847
    摘要190)   HTML5)    PDF (1437KB)(126)    收藏

    针对启发式算法在机器人路径规划过程中存在路径长度不稳定和易陷入局部极小点的问题,提出一种基于自适应调整哈里斯鹰优化(AAHHO)算法。首先,利用收敛因子调整策略,调节全局搜索阶段和局部搜索阶段的平衡,同时利用自然常数为底数,提高搜索效率和收敛精度;其次,在全局搜索阶段,采用精英合作引导搜索策略,通过3个精英哈里斯鹰合作引导其他个体更新位置以提高搜索性能,通过3个最优位置加强种群间的信息交流;最后,通过模拟种内竞争策略增强哈里斯鹰跳出局部最优的能力。函数测试和机器人路径规划对比实验结果表明,所提算法无论是函数测试还是机器人路径规划都优于IHHO(Improve Harris Hawk Optimization)和CHHO(Chaotic Harris Hawk Optimization)等对比算法,对于求解机器人的路径规划具有较好的有效性、可行性和稳定性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    12. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度
    薛海蓉, 韩晓龙
    《计算机应用》唯一官方网站    2023, 43 (12): 3848-3855.   DOI: 10.11772/j.issn.1001-9081.2022121923
    摘要171)   HTML10)    PDF (3405KB)(53)    收藏

    针对自动引导车(AGV)在自动化集装箱码头(ACT)执行任务过程中的电量问题,提出基于改进的非支配排序遗传算法-Ⅱ(NSGA-Ⅱ)的考虑AGV充电策略的集成调度。首先,在岸桥、场桥和AGV集成调度模式下,考虑AGV在不同作业状态下的耗电量,并建立以最小化作业完工时间和总耗电量为目标的多目标混合规划模型;其次,为提高传统NSGA-Ⅱ的性能,设计自适应NSGA-Ⅱ,并将所提算法与CPLEX求解器、NSGA-Ⅱ和多目标粒子群优化(MOPSO)算法进行性能对比;最后,设计AGV不同充电策略并对设备数量配比进行实验研究。算法对比实验结果表明:相较于传统NSGA-Ⅱ算法,自适应NSGA-Ⅱ对双目标的优化分别提升了2.8%和2.63%。利用自适应NSGA-Ⅱ进行的充电策略和设备数量配比实验的结果表明:增加AGV充电次数能够减少AGV的充电时间,且调整设备数量配比至3∶3∶9和3∶7∶3时,场桥和AGV的时间利用率分别达到最高。可见,AGV充电策略及设备数量配比对码头多设备集成调度有一定影响。

    图表 | 参考文献 | 相关文章 | 多维度评价
    13. 带状稀疏矩阵乘法及高效GPU实现
    刘丽, 陈长波
    《计算机应用》唯一官方网站    2023, 43 (12): 3856-3867.   DOI: 10.11772/j.issn.1001-9081.2022111720
    摘要190)   HTML3)    PDF (3222KB)(120)    收藏

    稀疏-稠密矩阵乘法(SpMM)广泛应用于科学计算和深度学习等领域,提高它的效率具有重要意义。针对具有带状特征的一类稀疏矩阵,提出一种新的存储格式BRCV(Banded Row Column Value)以及基于此格式的SpMM算法和高效图形处理单元(GPU)实现。由于每个稀疏带可以包含多个稀疏块,所提格式可看成块稀疏矩阵格式的推广。相较于常用的CSR(Compressed Sparse Row)格式,BRCV格式通过避免稀疏带中列下标的冗余存储显著降低存储复杂度;同时,基于BRCV格式的SpMM的GPU实现通过同时复用稀疏和稠密矩阵的行更高效地利用GPU的共享内存,提升SpMM算法的计算效率。在两种不同GPU平台上针对随机生成的带状稀疏矩阵的实验结果显示,BRCV的性能不仅优于cuBLAS(CUDA Basic Linear Algebra Subroutines),也优于基于CSR和块稀疏两种不同格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比分别为6.20和4.77。此外,将新的实现应用于图神经网络(GNN)中的SpMM算子的加速。在实际应用数据集上的测试结果表明,BRCV的性能优于cuBLAS和基于CSR格式的cuSPARSE,且在大多数情况下优于基于块稀疏格式的cuSPARSE。其中,相较于基于CSR格式的cuSPARSE,BRCV的最高加速比为4.47。以上结果表明BRCV可以有效提升SpMM的效率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    14. 基于自适应竞争学习的教与学优化算法
    王培崇, 冯浩婧, 李丽荣
    《计算机应用》唯一官方网站    2023, 43 (12): 3868-3874.   DOI: 10.11772/j.issn.1001-9081.2023010025
    摘要107)   HTML3)    PDF (1194KB)(83)    收藏

    针对求解较高维度优化问题时教与学优化(TLBO)算法容易出现早熟、解精度降低等问题,提出一种自适应竞争学习教与学优化算法(ITLBOAC)。首先,在“教”算子中引入非线性变化的权重参数,以决定当前个体自身状态的保持能力以及调整当前个体向教师学习的态度,从而使当前个体在早期更多地向教师学习,以迅速提升自身状态,而后期更多地保持自身状态,以减缓教师对它的影响;其次,以生态学协同竞争机制为基础,引入基于近邻个体间的自适应竞争的“学”算子,从而使当前个体选择它的近邻个体,并且让个体们从协作演化逐渐过渡到竞争学习。在12个Benchmark测试函数上的测试结果表明,相较于其他4种改进TLBO算法,所提算法具有更好的解精度、稳定性和收敛速度,同时相较于TLBO算法有大幅提升,验证了所提算法适合于求解较高维度的连续型优化问题。选择压缩弹簧和三杆桁架设计问题进行测试的结果表明,ITLBOAC获得的最优值分别比TLBO算法下降了3.03%和0.34%。可见,在求解约束工程优化问题时,ITLBOAC同样值得信任。

    图表 | 参考文献 | 相关文章 | 多维度评价
    15. k元( n-1)方体子网络可靠性的近似评估方法
    冯凯, 李建德, 姬张建
    《计算机应用》唯一官方网站    2023, 43 (12): 3875-3881.   DOI: 10.11772/j.issn.1001-9081.2022111719
    摘要87)   HTML0)    PDF (2399KB)(45)    收藏

    多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。kn方体网络的子网络可靠性是以kn方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下kn方体中k元(n-1)方体子网络的可靠性,提出基于反向传播(BP)神经网络的k元(n-1)方体子网络可靠性的近似评估方法。首先,利用蒙特卡洛仿真方法和k元(n-1)方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法;其次,基于生成的训练数据集构造用于评估k元(n-1)方体子网络可靠性的BP神经网络模型;最后,对BP神经网络模型得出的k元(n-1)方体子网络可靠性的近似评估结果进行了分析,并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比,所提方法得出的结果更为精确;与基于蒙特卡洛的评估方法相比,所提方法的评估耗时平均减少了约59%。实验结果表明,所提方法在兼顾精度和效率方面具有一定优势。

    图表 | 参考文献 | 相关文章 | 多维度评价
    16. 面向国产高性能众核处理器的编程模型
    陈虎, 周鹏灵
    《计算机应用》唯一官方网站    2023, 43 (11): 3517-3526.   DOI: 10.11772/j.issn.1001-9081.2022101548
    摘要204)   HTML3)    PDF (3529KB)(102)    收藏

    在国产高性能众核处理器上编程时,需要直接使用最底层的接口开发软件,这使编程和调试非常困难;并且各自平台的高性能软件编程模型较为基础,计算软件不能通用,造成了重复性开发。针对以上问题,实现了通用编程模型以及所对应的支撑库:一方面基于消息队列机制开发国产高性能众核处理器的线程级并行机制;另一方面基于单指令多数据流(SIMD)编程模型开发从核上的数据级并行性。首先,对国产高性能众核处理器体系结构进行抽象;其次,设计模型的消息队列机制,并为程序员提供一套异构并行编程接口,如系统参数接口、从核线程控制接口、消息队列接口、SIMD抽象接口;最后,在上述基础上形成全新的高性能计算软件开发模型和方法,方便用户开发基于国产高性能众核处理器的并行计算软件。性能传输测试结果表明,在国产众核处理器上,当启动核数较少时,所提模型的传输带宽普遍达到了峰值直接内存访问(DMA)带宽的90%;当启动的核数较多时,消息队列模型的传输带宽普遍达到了峰值DMA带宽的70%。在矩阵乘法实验中,与系统原语传输矩阵并计算的性能相比,所提模型的性能达到前者的90%;在口令猜测系统中,所提模型的代码性能与直接使用最底层的接口开发的代码性能基本持平。所提通用编程模型和支撑框架使高性能计算(HPC)软件开发更简易,并且具有更好的可移植性,可为促进国产自主HPC软件研发提供帮助。

    图表 | 参考文献 | 相关文章 | 多维度评价
    17. 流密码非线性布尔函数可重构运算单元设计方法RA-NLBF
    张宗仁, 戴紫彬, 刘燕江, 张晓磊
    《计算机应用》唯一官方网站    2023, 43 (11): 3527-3533.   DOI: 10.11772/j.issn.1001-9081.2022111690
    摘要108)   HTML0)    PDF (1594KB)(53)    收藏

    分组密码中的S盒(多输出)以及流密码中的反馈函数都需要特殊的布尔函数来保证密码算法的安全性。为解决现有流密码算法中非线性布尔函数(NLBF)可重构硬件运算单元资源占用过大、时钟频率低等问题,提出一种高效的基于与非锥(AIC)的NLBF可重构运算单元设计方法(RA-NLBF)。以密码学理论为基础,在着重分析多种流密码算法的NLBF特性,提取了涵盖与项次数、与项个数、输入端口数等NLBF函数特征的基础上,提出基于“混合极性Reed-Muller(MPRM)”和“传统布尔逻辑(TB)”双逻辑混合形式的NLBF化简方法,NLBF的与项数量减少29%,形成了适用于AIC的NLBF表达式;根据化简后的表达中与项个数、与项次数分布等特征,设计了可重构AIC单元和互联网络,形成可满足现有公开流密码算法中的NLBF运算的可重构单元。基于CMOS 180 nm工艺对提出的RA-NLBF进行逻辑综合验证,结果显示该方法的面积为12 949.67 μm2,时钟频率达到505 MHz,与现有相同功能的单元可重构序列密码逻辑单元(RSCLU)相比,面积减少了59.7%,时钟频率提高了37.3%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    18. 融合卷积与自注意力机制的基因型填补算法
    陈炯环, 鲍胜利, 王啸飞, 李若凡
    《计算机应用》唯一官方网站    2023, 43 (11): 3534-3539.   DOI: 10.11772/j.issn.1001-9081.2022111756
    摘要189)   HTML4)    PDF (1678KB)(61)    收藏

    基因型填补可以通过填补估算出在基因测序数据中未覆盖的样本区域弥补因技术限制导致的缺失,但现有的基于深度学习的填补方法不能有效捕捉到全序列位点间的连锁关系,造成整体填补准确率低、批量序列填补准确率分散等问题。针对这些问题提出一种融合卷积与自注意力机制的填补方法——FCSA,使用两种融合模块构成编解码器组建网络模型。编码器融合模块使用自注意力层得到全序列位点间的关联度,将该关联度融合到全局位点后再通过卷积层提取局部特征;解码器融合模块使用卷积对编码后的低维向量进行局部特征重建,应用自注意力层对全序列建模并融合。使用多物种的动物基因数据进行模型训练,并在Dog、Pig和Chicken数据集上进行比较验证,结果表明,与SCDA(Sparse Convolutional Denoising Autoencoders)、AGIC(Autoencoder Genome Imputation and Compression)和U-net相比,FCSA在10%、20%和30%缺失率下的平均填补准确率均取得了最高值,且批量序列填补准确率的分散程度较小;消融实验的结果也表明,这两种融合模块的设计能够有效提升基因型填补的准确率。

    图表 | 参考文献 | 相关文章 | 多维度评价
    19. 面向DCU非一致控制流的编译优化
    杨小艺, 赵荣彩, 王洪生, 韩林, 徐坤坤
    《计算机应用》唯一官方网站    2023, 43 (10): 3170-3177.   DOI: 10.11772/j.issn.1001-9081.2022091338
    摘要154)   HTML10)    PDF (4315KB)(66)    收藏

    国产DCU采用单指令多线程(SIMT)的并行执行模型,在程序执行时核函数内会产生非一致控制流,导致线程束中的线程部分只能串行执行,即线程束分化。针对核函数的性能因线程束分化受到严重制约的问题,提出一种减少线程束分化时间的编译优化方法——部分控制流合并(PCFM)。首先,通过散度分析找到同构且含有大量相同指令和相似指令的可融合发散区域;其次,统计合并后节省的指令周期百分比,从而评估可融合发散区域的融合盈利;最后,查找对齐序列,并合并有收益的可融合发散区域。在DCU上使用PCFM测试从图形处理器(GPU)基准测试套件Rodinia和经典的排序算法中选择的测试用例,实验结果表明,PCFM对测试用例能够取得1.146的平均加速比,与分支融合+尾合并方法相比,使用PCFM的加速比平均提高了5.72%。可见,所提方法减少线程束分化的效果更好。

    图表 | 参考文献 | 相关文章 | 多维度评价
    20. 基于数据驱动的云边智能协同综述
    田鹏新, 司冠南, 安兆亮, 李建辛, 周风余
    《计算机应用》唯一官方网站    2023, 43 (10): 3162-3169.   DOI: 10.11772/j.issn.1001-9081.2022091418
    摘要520)   HTML29)    PDF (1772KB)(373)    收藏

    随着物联网(IoT)的快速发展,大量在传感器等边缘场景产生的数据需要传输至云节点处理,这带来了极大的传输成本和处理时延,而云边协同为这些问题提供了有效的解决方案。首先,在全面调查和分析云边协同发展过程的基础上,结合当前云边智能协同中的研究思路与进展,重点分析和讨论了云边架构中的数据采集与分析、计算迁移技术以及基于模型的智能优化技术;其次,分别从边缘端和云端深入分析了各种技术在云边智能协同中的作用及应用,并探讨了云边智能协同技术在现实中的应用场景;最后,指出了云边智能协同目前存在的挑战及未来的发展方向。

    图表 | 参考文献 | 相关文章 | 多维度评价
    21. 基于新评价指标自适应预测的动态多目标优化算法
    李二超, 张生辉
    《计算机应用》唯一官方网站    2023, 43 (10): 3178-3187.   DOI: 10.11772/j.issn.1001-9081.2022091453
    摘要217)   HTML8)    PDF (3391KB)(72)    收藏

    现实生活中的多目标优化问题(MOP)大多为动态多目标优化问题(DMOP),此类问题的目标函数、约束条件和决策变量都可能随时间的变化而发生改变,这需要算法在环境变化后快速适应新的环境,且在保证Pareto解集多样性的同时快速收敛到新的Pareto前沿。针对此问题,提出一种基于新评价指标自适应预测的动态多目标优化算法(NEI-APDMOA)。首先,在种群非支配排序过程中提出一种优于拥挤度的新评价指标,并分阶段平衡收敛快速性和种群多样性,使种群的收敛过程更加合理;其次,提出一种可判断环境变化强弱的因子,为预测阶段提供有价值信息,并引导种群更好地适应环境变化;最后,根据环境变化因子匹配3种更加合理的预测策略,使种群快速响应环境变化。将NEI-APDMOA与DNSGA-Ⅱ-A(Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A)、DNSGA-Ⅱ-B(Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B)和PPS(Population Prediction Strategy)算法在9个标准动态测试函数上进行对比。实验结果表明,NEI-APDMOA分别在9、4和8个测试函数上取得了最优的平均反世代距离(IGD)值、平均间距(SP)值和平均世代距离(GD)值,可以更快地响应环境变化。

    图表 | 参考文献 | 相关文章 | 多维度评价
    22. CHAIN:基于重合支配的边缘计算节点放置算法
    赵徐炎, 崔允贺, 蒋朝惠, 钱清, 申国伟, 郭春, 李显超
    《计算机应用》唯一官方网站    2023, 43 (9): 2812-2818.   DOI: 10.11772/j.issn.1001-9081.2022081250
    摘要145)   HTML8)    PDF (1484KB)(75)    收藏

    边缘计算将计算资源部署在离终端用户更近的边缘计算节点,从待选的位置中选择合适的边缘计算节点部署位置能提升边缘计算服务的节点容量以及用户服务质量(QoS)。然而,目前对于如何放置边缘计算节点以降低边缘计算成本的研究较少。此外,在边缘服务的时延等QoS因素的约束下,目前尚没有一种边缘计算节点部署算法能最大限度地提高边缘服务的鲁棒性同时最小化边缘节点部署成本。针对上述问题,首先,通过建立计算节点、用户传输时延和鲁棒性的模型将边缘计算节点放置问题转化为带约束条件的最小支配集问题;随后,提出重合支配的概念,基于重合支配衡量网络鲁棒性,设计了基于重合支配的边缘计算节点放置算法——CHAIN(edge server plaCement algoritHm based on overlApping domINation)。仿真实验结果表明,与面向覆盖的近似算法和面向基站的随机算法相比,CHAIN的系统时延降低了50.54%与50.13%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    23. 基于空间语义和个体活动的电动汽车充电站选址方法
    郭茂祖, 张雅喆, 赵玲玲
    《计算机应用》唯一官方网站    2023, 43 (9): 2819-2827.   DOI: 10.11772/j.issn.1001-9081.2022091421
    摘要159)   HTML9)    PDF (6390KB)(58)    收藏

    针对电动汽车充电站(EVCS)的选址问题,提出一种基于空间语义和个体活动模式的城市充电站选址方法。首先,根据城市规划,采用无监督学习对非服务半径内兴趣点(POI)进行聚类,以确定新建充电站个数;然后,采用受约束的双存档进化算法(CTAEA)求解目标函数,在站间距最大化以及新充电站覆盖POI最多的约束条件下优化电动汽车选址方案。以成都市二环路内出租车的轨迹数据和POI为实验样本,并规划了15个充电站的选址方案。实验结果表明,相较于NSGA2(Non-dominated Sorting Genetic Algorithm 2)和SPEA2(Strength Pareto Evolutionary Algorithm 2),CTAEA的POI覆盖率指标提高了22.9和20.6个百分点,司机平均选择距离缩短了18.9%和25.5%,验证了所提方法在电动汽车选址方面的便利性与合理性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    24. 异构平台下卷积神经网络推理模型自适应划分和调度方法
    尚绍法, 蒋林, 李远成, 朱筠
    《计算机应用》唯一官方网站    2023, 43 (9): 2828-2835.   DOI: 10.11772/j.issn.1001-9081.2022081177
    摘要271)   HTML9)    PDF (3025KB)(113)    收藏

    针对卷积神经网络(CNN)在异构平台执行推理时存在硬件资源利用率低、延迟高等问题,提出一种CNN推理模型自适应划分和调度方法。首先,通过遍历计算图提取CNN的关键算子完成模型的自适应划分,增强调度策略灵活性;然后,基于性能实测与关键路径-贪婪搜索算法,在CPU-GPU异构平台上根据子模型运行特征选取最优运行负载,提高子模型推理速度;最后利用张量虚拟机(TVM)中跨设备调度机制,配置子模型的依赖关系与运行负载,实现模型推理的自适应调度,降低设备间通信延迟。实验结果表明,与TVM算子优化方法在GPU和CPU上的推理速度相比,所提方法在模型推理准确度无损前提下,推理速度提升了5.88%~19.05%和45.45%~311.46%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    25. 基于张量虚拟机的深度神经网络模型加速方法
    申云飞, 申飞, 李芳, 张俊
    《计算机应用》唯一官方网站    2023, 43 (9): 2836-2844.   DOI: 10.11772/j.issn.1001-9081.2022081259
    摘要237)   HTML10)    PDF (3331KB)(114)    收藏

    随着人工智能(AI)技术的蓬勃发展,深度神经网络(DNN)模型被大规模应用到各类移动端与边缘端。然而,边缘端算力低、内存容量小,且实现模型加速需要深入掌握边缘端硬件知识,这增加了模型的部署难度,也限制了模型的推广应用。因此,基于张量虚拟机(TVM)提出一种DNN加速与部署方法,从而实现卷积神经网络(CNN)模型在现场可编程门阵列(FPGA)上的加速,并在分心驾驶分类应用场景下验证了所提方法的可行性。通过计算图优化方法减小了模型的访存和计算开销,通过模型量化方法减小了模型尺寸,通过计算图打包方法将卷积计算卸载到FPGA上执行以提高模型推理速度。与微处理器(MPU)相比,所提方法可使ResNet50和ResNet18在MPU+FPGA上的推理时间分别减少88.63%和77.53%;而在AUC(American University in Cairo)数据集上,相较于MPU,两个模型在MPU+FPGA上的top1推理精度仅下降了0.26和0.16个百分点。可见,所提方法可以降低不同模型在FPGA上的部署难度。

    图表 | 参考文献 | 相关文章 | 多维度评价
    26. 基于多个改进策略的增强麻雀搜索算法
    李大海, 詹美欣, 王振东
    《计算机应用》唯一官方网站    2023, 43 (9): 2845-2854.   DOI: 10.11772/j.issn.1001-9081.2022081270
    摘要286)   HTML5)    PDF (4003KB)(125)    收藏

    针对麻雀搜索算法(SSA)存在寻优精度不高且易陷入局部最优的问题,提出一种基于多个改进策略的增强麻雀搜索算法(EMISSA)。首先,为平衡算法的全局和局部搜索能力,引入模糊逻辑来动态调整麻雀发现者的规模;其次,对麻雀跟随者进行混合差分变异操作以产生变异子群,从而增强EMISSA跳出局部最优的能力;最后,通过拓扑对立学习(TOBL)产生当前麻雀发现者个体的拓扑对立解,以充分挖掘搜索空间内的优质位置信息。通过2013年进化计算大会(CEC2013)中的12个测试函数评估EMISSA、标准SSA以及混沌麻雀搜索优化算法(CSSOA)等改进麻雀算法的性能。实验结果表明,EMISSA在30维情况下,在12个测试函数上获得了11个第一;在80维情况下,在所有的测试函数上都获得了第一。而在Friedman检验中,EMISSA的排名均获得了第一。将EMISSA应用于障碍物环境下的无线传感器网络(WSN)节点部署,实验结果表明,相较于其他算法,EMISSA获得了最高的无线节点覆盖率,节点分布更均匀,覆盖冗余更少。

    图表 | 参考文献 | 相关文章 | 多维度评价
    27. 面向异构多背包问题的多级二进制帝国竞争算法
    李斌, 唐志斌
    《计算机应用》唯一官方网站    2023, 43 (9): 2855-2867.   DOI: 10.11772/j.issn.1001-9081.2022081189
    摘要182)   HTML7)    PDF (2507KB)(45)    收藏

    在传统多背包问题的基础上,从典型物流服务场景中共性抽象出异构多背包问题(HMKP),并设计和定制了一种帝国竞争算法(ICA)对HMKP进行求解和评估。针对原始ICA易陷入局部最优以及0-1背包问题最优解往往在约束边界周围的特点,设计了双点自变异策略(TPAS)和跳出局部最优算法(JLOA)对ICA进行改进,提出面向0-1背包问题的二进制帝国竞争算法(BICA)。BICA在求解35个0-1背包问题算例时展现出了全面、高效的寻优能力,基于最佳匹配值法(BMV)的BICA在第一组测试集的20个算例上能对19个算例100%找到理想最优值,在第二组测试集的15个算例上能对12个算例100%找到理想最优值,在所有对比算法中表现最优。数值结果分析表明,BICA在寻优演化中维持多极发展策略,并依托独特的种群进化方式在解空间中高效搜索理想解。在此基础上,针对HMKP强约束性和高复杂度的特性,基于BICA设计了求解HMKP的多级二进制帝国竞争算法(MLB-ICA)。分别在多个典型0-1背包问题算例组合构建的HMKP高维测试集上进行了MLB-ICA的数值实验和性能评估,结果表明虽然MLB-ICA的求解时间比Gurobi长,但求解精度提高了28%。可见,MLB-ICA能以较低的计算代价在可接受的时间范围内高效求解高维复杂的HMKP,为ICA在超大规模组合优化问题中的求解提出了可行的算法设计方案。

    图表 | 参考文献 | 相关文章 | 多维度评价
    28. 基于亚群和差分进化的混合蜻蜓算法
    王波, 王浩, 杜晓昕, 郑晓东, 周薇
    《计算机应用》唯一官方网站    2023, 43 (9): 2868-2876.   DOI: 10.11772/j.issn.1001-9081.2022060813
    摘要172)   HTML9)    PDF (2338KB)(115)    收藏

    针对蜻蜓算法(DA)存在开发能力弱、种群多样性低、易过早收敛至局部最优等问题,提出一种基于亚群和差分进化的混合蜻蜓算法(HDASDE)。首先,对基本蜻蜓算法进行改进:融入混沌因子和有目的的莱维飞行来提升蜻蜓算法的寻优能力,并提出混沌跃迁机制加强基本蜻蜓算法的勘探能力;其次,在差分进化(DE)算法的基础上引入反向学习加强DE算法的开发能力;再次,利用亚群策略提高算法跳出局部最优的能力,设计了一种动态双亚群策略将整个种群划分为动态变化的两个亚群;然后使用动态亚群结构将改进蜻蜓算法和改进DE算法进行融合,融合后的算法具有较好的全局勘探能力以及较强的局部开发能力。最后,将HDASDE应用于13个典型的复杂函数优化问题和三杆桁架的设计优化问题,并与原始的DA、DE算法以及其他元启发式优化算法进行对比。实验结果表明,HDASDE在所有13个测试函数中优于DA、DE、人工蜂群(ABC)算法;在12个测试函数中优于粒子群优化(PSO)算法;在10个测试函数中优于灰狼优化(GWO)算法。并且,在三杆桁架的设计优化问题中效果较好。

    图表 | 参考文献 | 相关文章 | 多维度评价
    29. 基于新一代神威超算的量子计算模拟器加速和优化
    史新民, 刘勇, 陈垚键, 宋佳伟, 刘鑫
    《计算机应用》唯一官方网站    2023, 43 (8): 2486-2492.   DOI: 10.11772/j.issn.1001-9081.2022091456
    摘要411)   HTML59)    PDF (2000KB)(385)    收藏

    针对量子硬件规模逐步扩大、当下量子计算经典模拟速度不高的问题,提出了基于神威超算量子模拟器的两种优化方法。首先,通过改进张量转置策略和计算策略重新构建了张量收缩算子库SWTT,从而提高了部分张量收缩的计算内核效率并减少了冗余访存;其次,通过提高数据局部性的收缩路径调整方法实现了路径计算复杂度和计算效率之间的均衡。测试结果表明,该算子库改进方法可将“悬铃木”量子霸权电路模拟效率提升5.4%,单步张量收缩效率最高提升49.7倍;该路径调整方法可在路径计算复杂度膨胀2倍条件下提升约4倍的浮点效率。两种优化方法使神威超算整机模拟谷歌53量子比特20层量子芯片随机电路百万振幅采样的单精度和混合精度浮点运算效率分别从3.98%和1.69%提升至18.48%和7.42%,理论估计模拟时间从单精度的470 s降至226 s,混合精度的304 s降至134 s,证明两种方法大幅提高了量子计算模拟速度。

    图表 | 参考文献 | 相关文章 | 多维度评价
    30. 基于汉明距离的量子 K-Means算法
    钟静, 林晨, 盛志伟, 张仕斌
    《计算机应用》唯一官方网站    2023, 43 (8): 2493-2498.   DOI: 10.11772/j.issn.1001-9081.2022091469
    摘要293)   HTML31)    PDF (1623KB)(376)    收藏

    K-Means算法在处理大规模异构数据时,通常使用欧氏距离来衡量数据点之间的相似度,然而这样存在效率低下以及计算复杂性过高的问题。受到汉明距离在处理数据相似性计算上存在显著优势的启发,提出一种基于汉明距离的量子K-Means(QKMH)算法来计算相似度。首先,将数据制备成量子态,并使用量子汉明距离计算待聚类点和K个聚类中心之间的相似度;然后,改进了Grover最小值搜索算法查找距离待聚类点最近的聚类中心;最后,循环以上步骤,直到达到规定迭代次数或者聚类中心不再改变。基于量子模拟计算框架QisKit,将提出的算法在MNIST手写数字数据集上进行了验证并与传统和改进的多种方法进行了对比,实验结果表明,QKMH算法的F1值相较于基于曼哈顿距离的量子K-Means算法提高了10个百分点,相较于最新优化的基于欧氏距离的量子K-Means算法提高了4.6个百分点;同时经计算,QKMH算法时间复杂度比上述对比算法更低。

    图表 | 参考文献 | 相关文章 | 多维度评价
    31. 零点分布更均匀的广义极谐复指数变换
    曾泽芝, 杨建伟
    《计算机应用》唯一官方网站    2023, 43 (8): 2499-2504.   DOI: 10.11772/j.issn.1001-9081.2022071020
    摘要137)   HTML3)    PDF (5046KB)(49)    收藏

    针对极谐复指数变换(PCET)因自身径向函数实部和虚部的零点分布不均匀而存在的信息抑制问题,提出了一种零点分布更均匀的广义PCET。首先,改造了PCET,将PCET径向函数的指数推广为更一般的构造函数,而近来出现的指数傅里叶矩(EFM)、分数阶极谐变换、广义极谐变换、修正的广义极谐变换等都是所提广义PCET的特例;其次,选取了构造函数,使得所构造的广义PCET的径向函数实部和虚部的零点分布更均匀,并给出了这一特性的证明。在所取的汉字图像库、Coil-20库和COREL库上进行了图像重构实验,同时测试了广义PCET的旋转不变性及抗噪性能。当噪声强度为0时,PCET和广义PCET的识别率均为100%,这验证了PCET和广义PCET的旋转不变性。相较于PCET,所提广义PCET具有更低的重构误差及更高的识别率。理论分析和实验结果表明,零点分布比PCET更均匀的广义PCET同样具有旋转不变性和正交性,且其重构性能和抗噪性能均优于PCET,一定程度上解决了PCET的信息抑制问题,并在原点处数值稳定。

    图表 | 参考文献 | 相关文章 | 多维度评价
    32. 基于零模型的含时网络模体识别方法
    胡博仁, 裴忠民, 罗章凯, 丁杰
    《计算机应用》唯一官方网站    2023, 43 (8): 2505-2510.   DOI: 10.11772/j.issn.1001-9081.2022071033
    摘要157)   HTML7)    PDF (2277KB)(65)    收藏

    在带有时间属性的含时网络中,常规的基于频繁子图统计的网络模体识别方法容易受网络规模与结构差异的影响。而与实证网络具有相同规模和某些相同性质的零模型网络能为实证网络的特性挖掘提供了准确的基准,于是提出一种基于零模型的含时网络模体识别方法,用两种网络子图特征比较后的相对值来识别含时网络中的具有显著结构意义的子图。同时,为确定零模型网络何时达到稳定,采用成功置乱次数方法来改进基于时间置乱或时间随机化的含时网络零模型构造方法。在实验阶段,对包含卫星和地面站的46节点全球定位系统(GPS)星座进行仿真实验,确定了零模型网络子图特征稳定时的成功置乱次数;构造10个零模型网络与卫星网络比较,发现反映节点连接具有连续性特点的子图的出现次数仅为最高频子图的1/34,却是卫星网络中最重要的模体。实验结果表明,以零模型为参照的含时网络模体识别方法能更准确地识别出反映网络结构特性和动态变化过程的模体。

    图表 | 参考文献 | 相关文章 | 多维度评价
    33. 基于权重向量聚类的动态多目标进化算法
    李二超, 程艳丽
    《计算机应用》唯一官方网站    2023, 43 (7): 2226-2236.   DOI: 10.11772/j.issn.1001-9081.2022060843
    摘要164)   HTML4)    PDF (3030KB)(51)    收藏

    实际生活中存在许多的动态多目标优化问题(DMOP)。对于此类问题,当环境发生改变时,就要求动态多目标进化算法(DMOEA)能快速和准确地跟踪新环境下的帕累托前沿(PF)或帕累托最优解集(PS)。针对现有算法的种群预测性能差的问题,提出一种基于权重向量聚类预测的动态多目标进化算法(WVCP)。该算法首先在目标空间中生成均匀的权重向量,并对种群中的个体进行聚类,再根据聚类情况分析种群的分布性。其次,对聚类个体的中心点建立时间序列。对同一权重向量,针对不同的聚类情况采取相应的应对策略对个体进行补充,若相邻时刻均存在聚类中心,则采用差分模型预测新环境下的个体;若某一时刻不存在聚类中心,则用相邻权重向量聚类中心的质心作为该时刻的聚类中心,再运用差分模型预测个体。这样不仅可以有效地解决种群分布性差的问题,还可以提高预测的准确性。最后,引入个体补充策略,以充分地利用历史信息。为验证WVCP算法的性能,把它与四种代表性算法进行了仿真对比。实验结果表明,所提算法能够很好地解决DMOP。

    图表 | 参考文献 | 相关文章 | 多维度评价
    34. 信息迁移多任务优化共生生物搜索算法
    程美英, 钱乾, 熊伟清
    《计算机应用》唯一官方网站    2023, 43 (7): 2237-2247.   DOI: 10.11772/j.issn.1001-9081.2022060896
    摘要150)   HTML2)    PDF (3862KB)(50)    收藏

    针对现有共生生物搜索(SOS)算法只能求解单个任务,以及信息负迁移影响多任务优化(MTO)性能这两个难题,提出一个信息迁移多任务优化共生生物搜索(ITMTSOS)算法。首先基于多种群演化MTO框架,根据任务个数设置相应数量种群;然后各种群独立运行基本SOS算法,当某一种群连续若干代停滞进化时,引入个体自身最优经验和邻域最优个体以形成知识模块并将该模块迁移至该种群个体进化过程中;最后对ITMTSOS算法时间和空间复杂度进行分析。仿真实验结果表明,ITMTSOS算法同时求解多个不同形态高维函数时均能快速收敛至全局极值解0,与单任务SOS算法相比,平均运行时间最多缩短约25.25%;而在同时求解多维0/1背包问题和师生匹配问题时,所提算法在测试集weing1和weing7上的最优适应值与目前测试集公布的最优结果相比分别提高了22 767和22 602,师生最优匹配差和平均匹配差的绝对值分别下降了26和33,平均运行时间约缩短了7.69%。

    图表 | 参考文献 | 相关文章 | 多维度评价
    35. 求解带容量约束车辆路径问题的多模态差分进化算法
    林剑, 叶璟轩, 刘雯雯, 邵晓雯
    《计算机应用》唯一官方网站    2023, 43 (7): 2248-2254.   DOI: 10.11772/j.issn.1001-9081.2022060812
    摘要165)   HTML7)    PDF (1138KB)(149)    收藏

    针对带容量约束车辆路径问题(CVRP)中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题,提出一种多模态差分进化(MDE)算法,以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特点,构建高效的解个体编解码策略,并基于修复机制提升解个体的质量;然后在差分进化(DE)算法框架下,基于多模态优化视角引入动态半径小生境生成方法,并采用杰卡德系数来度量解个体之间相似性,进而实现对于解个体之间距离的计算;最后,改进邻域搜索策略,采用精英存档和更新策略来得到多模态最优解集。基于典型数据集的仿真实验与分析结果表明,所提MDE算法寻优得到的平均最优解个数达到1.743 4个,平均最优解与已知最优解的平均偏差为0.03%,而差分进化(DE)算法二者分别为0.8486和0.63%。可见,所提算法在求解CVRP上表现出较高的有效性和稳定性,能同时得到CVRP的多个近似最优解。

    图表 | 参考文献 | 相关文章 | 多维度评价
    36. 基于深度强化学习的多数据中心一体化调度优化
    方和平, 刘曙光, 冉泳屹, 钟坤华
    《计算机应用》唯一官方网站    2023, 43 (6): 1884-1892.   DOI: 10.11772/j.issn.1001-9081.2022050722
    摘要221)   HTML11)    PDF (2415KB)(202)    收藏

    多数据中心任务调度策略的目的是把计算任务分配到各个数据中心的不同服务器上,以促进资源利用率和能效的提升,为此提出了基于深度强化学习的多数据中心一体化调度策略。所提策略分为数据中心选择和数据中心内部任务分配两个阶段。在多数据中心选择阶段,整合算力资源以提高总体资源利用率,首先采用具有优先经验回放的深度Q网络(PER-DQN)在以数据中心为节点的网络中获取到达各个数据中心的通信路径;然后计算资源使用成本和网络通信成本,并依据这两个成本之和最小的原则选择最优的数据中心。在数据中心内部任务分配阶段,首先在所选数据中心内部,划分计算任务并遵循先到先服务(FCFS)原则将任务添加到调度队列中;然后结合计算设备状态和环境温度,采用基于双深度Q网络(Double DQN)的任务分配算法获得最优分配策略,以选择服务器执行计算任务,避免热点的产生,并降低制冷设备的能耗。实验结果表明,基于PER-DQN的数据中心选择算法相较于计算资源优先(CRF)、最短路径优先(SPF)路径选择方法的平均总成本分别下降了3.6%、10.0%;基于Double DQN的任务部署算法相较于较轮询调度(RR)、贪心调度(Greedy)算法的平均电源使用效率(PUE)分别下降了2.5%、1.7%。可见,所提策略能够有效降低总成本和数据中心能耗,实现多数据中心的高效运行。

    图表 | 参考文献 | 相关文章 | 多维度评价
    37. 无人机辅助移动边缘计算中的任务卸载算法
    李校林, 江雨桑
    《计算机应用》唯一官方网站    2023, 43 (6): 1893-1899.   DOI: 10.11772/j.issn.1001-9081.2022040548
    摘要414)   HTML5)    PDF (2229KB)(215)    收藏

    无人机(UAV)灵活机动、易于部署,可以辅助移动边缘计算(MEC)帮助无线系统提高覆盖范围和通信质量,但UAV辅助MEC系统研究中存在计算延迟需求和资源管理等挑战。针对UAV为地面多个终端设备提供辅助计算服务的时延问题,提出一种基于双延迟深度确定性策略梯度(TD3)的时延最小化任务卸载算法(TD3-TOADM)。首先,将优化问题建模为在能量约束下的最小化最大计算时延的问题;其次,通过TD3-TOADM联合优化终端设备调度、UAV轨迹和任务卸载比来最小化最大计算时延。仿真实验分析结果表明,与分别基于演员-评论家(AC)、深度Q网络(DQN)以及深度确定性策略梯度(DDPG)的任务卸载算法相比,TD3-TOADM得到的计算时延减小了8.2%以上。可见TD3-TOADM能获得低时延的最优卸载策略,具有较好的收敛性和鲁棒性。

    图表 | 参考文献 | 相关文章 | 多维度评价
    38. 基于改进深度强化学习的边缘计算服务卸载算法
    曹腾飞, 刘延亮, 王晓英
    《计算机应用》唯一官方网站    2023, 43 (5): 1543-1550.   DOI: 10.11772/j.issn.1001-9081.2022050724
    摘要337)   HTML13)    PDF (2400KB)(124)    收藏

    在边缘计算(EC)网络中,针对边缘节点计算资源和存储空间有限的问题,提出一种基于改进深度强化学习(DRL)的边缘计算服务卸载(ECSO)算法,以降低节点处理时延和提高服务性能。具体来说,将边缘节点服务卸载问题转化为资源受限的马尔可夫决策过程(MDP),利用DRL算法解决边缘节点的请求状态转移概率难以精确预测的问题;考虑到边缘节点执行缓存服务的状态动作空间过大,定义新的动作行为替代原有动作,并依据提出的动作筛选算法得到最优动作集合,以改进计算动作行为奖励值的过程,进而大幅度降低动作空间大小,提高算法训练的效率以及收益。仿真实验结果表明,对比原深度Q网络(DQN)算法、邻近策略优化(PPO)算法以及传统的最流行(MP)算法,ECSO算法的总奖励值分别提升了7.0%、12.7%和65.6%,边缘节点服务卸载时延分别降低了13.0%、18.8%和66.4%,验证了算法的有效性,说明ECSO能有效提升边缘计算服务的卸载性能。

    图表 | 参考文献 | 相关文章 | 多维度评价
    39. 改进自组织映射的多无人机协同任务分配方法
    孙亚男, 吴杰宏, 石峻岭, 高利军
    《计算机应用》唯一官方网站    2023, 43 (5): 1551-1556.   DOI: 10.11772/j.issn.1001-9081.2022040592
    摘要249)   HTML4)    PDF (2598KB)(106)    收藏

    针对现有算法对多无人机(UAV)协同进行多任务分配时存在负载均衡和执行效率方面的不足,提出一种改进的自组织映射(ISOM)算法。该算法根据飞行时间和任务执行时间设计了UAV的负载均衡度,以提升任务完成的效率;还设计了新的非线性变化的学习率和邻域函数保证ISOM算法的稳定性和快速收敛。然后,在不同任务环境对ISOM算法进行了有效性验证。实验结果表明,与结合遗传算法的粒子群优化(GA-PSO)、Gurobi和ORTools算法相比,ISOM算法的任务完成时间可分别减少15.5%、12.7%和7.3%;在TSPLIB数据集的实例KroA100、KroA150、KroA200上进行航迹长度减小的有效性验证时,与杂草优化(IWO)算法、改进的单亲遗传算法(IPGA)和蚁群单亲遗传算法(AC-PGA)的对比结果表明,ISOM算法在无人机数量为2、3、4、5、8时,均获得了最小的航迹长度。由此可见,ISOM算法在解决多UAV协同多任务分配问题时效果显著。

    图表 | 参考文献 | 相关文章 | 多维度评价
    40. 概率故障条件下 k元( n-m)方体子网络的可靠性
    冯凯, 刘彤
    《计算机应用》唯一官方网站    2023, 43 (4): 1198-1205.   DOI: 10.11772/j.issn.1001-9081.2022030414
    摘要204)   HTML1)    PDF (894KB)(39)    收藏

    kn方体具有许多优良特性,已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时,系统子网络的保持能力对系统实际应用至关重要。为了精确度量kn方体中任意规模子网络的容错能力,研究了有故障发生时kn方体中k元(n-m)方体子网络的可靠性。当kk≥3)为奇整数时,在概率故障条件下得出了kn方体中存在无故障k元(n-m)方体子网络的概率的上界和下界,并给出了该可靠性的一种近似评估方法。实验结果表明,随着顶点可靠性的降低,k元(n-m)方体子网络可靠性的上下界趋于一致;当顶点可靠性较高时,利用近似评估方法得出的结果更为准确。

    图表 | 参考文献 | 相关文章 | 多维度评价
2024年 44卷 3期
刊出日期: 2024-03-10
文章目录
过刊浏览
荣誉主编:张景中
主  编:徐宗本
副主编
:申恒涛 夏朝晖

国内邮发代号:62-110
国外发行代号:M4616
地址:四川成都双流区四川天府新区
   兴隆街道科智路1369号
   中科信息(科学城园区) B213
   (计算机应用编辑部)
电话:028-85224283-803
   028-85222239-803
网址:www.joca.cn
E-mail: bjb@joca.cn
期刊微信公众号
CCF扫码入会