计算机科学

47卷第8期目录

计算机科学. 2020, 47 (8): 0-0.

摘要 ( 160 )

PDF(167KB) ( 630 )

相关文章 | 多维度评价

高性能计算(High Performance Computing，HPC)是计算机科学的经典分支，主要指从体系结构、并行算法和软件开发等多个方面研究开发高性能计算机的技术。高性能计算已被公认为继理论科学和实验科学之后，人类认识世界、改造世界强有力的科学研究方法，是科技创新的重要手段，已成为国家科技综合实力的体现，对国家战略的发展有着重要影响。目前，高性能计算技术已经广泛应用于航空航天、汽车制造、核试验模拟、军事情报搜集处理、天气预报等多方面。我国早期的高性能计算机依赖于进口，极大地限制了应用，这也激发了我国自主研发高性能计算机的决心。我国自主研制的“天河”“神威”“曙光”等高性能计算机的不断问世，促进了我国高性能计算逐步走向世界前列。

并行计算学科发展历程

陈国良, 张玉杰

计算机科学. 2020, 47 (8): 1-4. doi:10.11896/jsjkx.200600027

摘要 ( 779 )

PDF(1062KB) ( 2011 )

参考文献 | 相关文章 | 多维度评价

计算科学已经与传统的理论科学和实验科学并列成为第三门科学, 它们相辅相成地推动着人类科技的发展和社会文明的进步。21世纪科学和经济上的关键问题研究前沿, 有可能通过熟练地掌握先进的计算技术并运用计算科学得到解决。高性能计算是一个国家综合国力的体现, 是支撑国家实力持续发展的关键技术之一, 在国防安全、高科技发展和国民经济建设中占有重要的战略地位。经过40多年的发展, 围绕并行计算机、并行算法和并行程序设计, 融合并行计算机体系结构、数值和非数值的并行算法设计及并行程序设计于一体, 形成了并行计算(Parallel Computing)“结构-算法-编程-应用”完整的学科体系与系统课程框架。文中回顾了作者在并行计算学科的发展方面所做的工作, 并对非数值计算中的计算方法和新型的非冯诺依曼结构计算机体系结构的研究进行了介绍。

异构混合并行计算综述

阳王东, 王昊天, 张宇峰, 林圣乐, 蔡沁耘

计算机科学. 2020, 47 (8): 5-16. doi:10.11896/jsjkx.200600045

摘要 ( 1260 )

PDF(3592KB) ( 5178 )

参考文献 | 相关文章 | 多维度评价

随着人工智能和大数据等计算机应用对算力需求的迅猛增长以及应用场景的多样化, 异构混合并行计算成为了研究的重点。文中介绍了当前主要的异构计算机体系结构, 包括CPU/协处理器、CPU/众核处理器、CPU/ASCI和CPU/FPGA等;简述了异构混合并行编程模型随着各类异构混合结构的发展而做出的改变, 异构混合并行编程模型可以是对现有的一种语言进行改造和重新实现, 或者是现有异构编程语言的扩展, 或者是使用指导性语句异构编程, 或者是容器模式协同编程。分析表明, 异构混合并行计算架构会进一步加强对AI的支持, 同时也会增强软件的通用性。文中还回顾了异构混合并行计算中的关键技术, 包括异构处理器之间的并行任务划分、任务映射、数据通信、数据访问, 以及异构协同的并行同步和异构资源的流水线并行等。根据这些关键技术, 文中指出了异构混合并行计算面临的挑战, 如编程困难、移植困难、数据通信开销大、数据访问复杂、并行控制复杂以及资源负载不均衡等。最后分析了异构混合并行计算面临的挑战, 指出目前关键的核心技术需要从通用与AI专用异构计算的融合、异构架构的无缝移植、统一编程模型、存算一体化、智能化任务划分和分配等方面进行突破。

基于新型语言机制的异构集群应用通信优化方法

崔翔, 李晓雯, 陈一峯

计算机科学. 2020, 47 (8): 17-15. doi:10.11896/jsjkx.200100124

摘要 ( 639 )

PDF(1901KB) ( 945 )

参考文献 | 相关文章 | 多维度评价

与传统集群相比, 异构集群具有较高的性价比。但相比迅速发展的硬件技术, 当前软件技术仍然落后, 不能适应不断更新的异构硬件和超大规模的并行计算环境。当前普遍采用的解决方案是直接使用针对不同硬件的并行编程工具, 这一组合方案的缺点是编程层次低, 开发、修改与调试困难。文中介绍了新型语言机制用于描述数据与线程的多维规则结构、排列方式以及通讯模式, 提出了基于新型语言机制的不同类型异构系统之间的软件移植和优化方法。以直接法湍流模拟为例, 实现了应用在不同异构系统上的通信优化和快速移植。

一种基于模拟退火的动态部分可重构系统划分-调度联合优化算法

王喆, 唐麒, 王玲, 魏急波

计算机科学. 2020, 47 (8): 26-31. doi:10.11896/jsjkx.200500110

摘要 ( 463 )

PDF(1476KB) ( 851 )

参考文献 | 相关文章 | 多维度评价

基于FPGA的动态部分可重构(Dynamically Partially Reconfigurable, DPR)技术因在处理效率、功耗等方面具有优势, 在高性能计算领域得到广泛应用。DPR系统中的重构区域划分和任务调度决定了整个系统的性能, 因此如何对DPR系统的逻辑资源划分和调度问题进行建模, 并设计高效的求解算法是保证系统性能的关键。在建立划分和调度模型的基础上, 设计了基于模拟退火(Simulated Annealing, SA)的DPR系统划分-调度联合优化算法, 用于优化重构区域的划分方案和任务调度。文中提出了一种新型新解产生方法, 可有效跳过不可行解及较差解, 加快了对解空间的搜索并提高了算法的收敛速度。实验结果表明, 与混合整数线性规划(Mixed Integral Linear Programming, MILP)和IS-k两种算法相比, 提出的基于SA的算法的时间复杂度更低;且针对大规模应用, 该算法能够在较短的时间内获得较好的划分与调度结果。

用数据驱动的编程模型并行多重网格应用

郭杰, 高希然, 陈莉, 傅游, 刘颖

计算机科学. 2020, 47 (8): 32-40. doi:10.11896/jsjkx.200500093

摘要 ( 444 )

PDF(3157KB) ( 1113 )

参考文献 | 相关文章 | 多维度评价

多重网格是数值计算领域中一种加速迭代收敛的重要技术, 被广泛应用。近年来, 大规模并行计算系统向多核化、异构众核化发展, 多重网格应用也亟须适应新的并行计算平台。文中采用一种数据驱动的任务并行语言AceMesh将遗产的NAS MG程序移植到“天河二号”和“神威·太湖之光”两种不同架构的国产超算平台上, 展示了使用该语言对计算循环、通信代码的任务并行方法, 验证了AceMesh语言的跨平台性能可移植性。文中定性地分析了该应用的任务图特征和计算-通信重叠的特点, 并分别在两个并行计算平台上将其与现有编程模型MPI/OpenMP和MPI/OpenACC进行性能对比, 分析了AceMesh任务图并行程序对访存性能和通信-计算重叠的优化效果。实验数据表明, 相比传统的并行编程方法, AceMesh在“神威·太湖之光”和“天河二号”平台上分别最高获得了1.19X和1.85X的性能加速。最后, 针对该应用在不同网格层的通信特点以及通信序列化导致大量通信不能隐藏的问题, 提出了未来的研究方向。

负载均衡的处理器运算资源分配方法

王国澎, 杨剑新, 尹飞, 蒋生健

计算机科学. 2020, 47 (8): 41-48. doi:10.11896/jsjkx.191000148

摘要 ( 389 )

PDF(1828KB) ( 924 )

参考文献 | 相关文章 | 多维度评价

现代超标量处理器通常设置有多套计算部件支持指令并行执行, 以提高程序的运行效率。运算资源分配策略在很大程度上决定了处理器能否充分利用计算部件并行加速计算, 具有重要作用。就指令调度以及运算资源分配问题而言, 当前的研究以软件编译优化方法居多。但编译优化是一种静态方法, 优化排布的指令无法再次改变次序, 且缺乏运行时信息, 灵活性不够。为了降低因运算资源分配不当导致的指令阻塞, 充分释放其运算能力, 从硬件自动调度和实现的角度分析了这个问题, 研究了对称情形和非对称情形下运算资源的细粒度自动分配方法, 进而提出了负载均衡的贪心分配策略。实验结果表明, 提出的运算资源分配方法可以有效减弱现代超标量处理器中指令发射不公平所带来的负面影响, 能更好地利用片上缓冲资源和计算资源, 且处理器中运算资源越多, 发射缓冲深度越大, 负载均衡方法获得的性能提升就越明显。

面向语音分离的深层转导式非负矩阵分解并行算法

李雨蓉, 刘杰, 刘亚林, 龚春叶, 王勇

计算机科学. 2020, 47 (8): 49-55. doi:10.11896/jsjkx.190900202

摘要 ( 502 )

PDF(2394KB) ( 872 )

参考文献 | 相关文章 | 多维度评价

非负矩阵分解(Non-negative Matrix Factorization, NMF)能保存语音信号的非负特征, 是用于语音分离的重要方法, 但该方法存在数据运算复杂、计算量太大的问题, 需要研究能减少计算时间的并行计算方法。针对语音分离预训练及分离过程的计算问题, 文中提出深层转导式非负矩阵分解并行算法, 综合考虑迭代更新过程的数据关联性, 设计了一种任务间和任务内多级并行算法。该并行算法在任务级将分解训练语音得到对应基矩阵的过程作为两个独立的任务进行并行计算;在任务内部进程级把矩阵按行列划分, 主进程把矩阵块分发到从进程, 从进程接收当前矩阵块并计算结果矩阵子块, 然后将当前进程矩阵块发送到下一进程, 实现第二个矩阵中每一个矩阵块在所有进程的遍历, 并计算结果矩阵对应子块的乘积, 最后由主进程收集从进程数据块;在线程级子矩阵乘法运算的过程中, 采取生成多线程, 通过共享内存交换数据计算子矩阵块的加速策略。该算法为首个实现深层转导式非负矩阵分解的并行算法。在天河二号平台上的测试结果表明, 在分离多说话人混合语音信号时, 相比串行程序, 所提出的并行算法能在不改变分离效果的前提下, 使得预训练过程中使用64个进程的加速比为18, 分离过程使用64个进程的对应加速比为24。相较于串行及MPI模型分离, 混合模型分离时间大大缩短, 从而证明了设计的并行算法可有效提高语音分离的效率。

基于定点压缩技术的双层粒子网格算法的设计与优化

程盛淦, 于浩然, 韦建文, 林新华

计算机科学. 2020, 47 (8): 56-61. doi:10.11896/jsjkx.200200112

摘要 ( 313 )

PDF(1841KB) ( 812 )

参考文献 | 相关文章 | 多维度评价

现代天体物理学的研究离不开大规模N-body模拟。N-body模拟常用的算法之一是粒子网格(Particle-Mesh, PM)算法, 但是PM算法需要消耗较多的内存容量。内存限制成为了N-body模拟在现代超算平台大规模扩展的瓶颈。因此, 文中使用了利用定点压缩技术减少内存消耗的方法, 将存储每个N-body粒子相空间的内存消耗减少到最低6个字节, 比传统PM算法低近一个数量级。文中实现了基于定点压缩技术的双层粒子网格算法, 并使用包括混合精度计算、通信优化在内的方法对其性能进行了优化。这些优化技术显著降低了定点压缩带来的性能损耗, 将压缩和解压在程序总耗时中的占比从21%降低至8%, 并且在核心计算热点上达到了最高2.3倍的加速效果, 使得程序在较低的内存消耗下保持较高的计算效率和扩展性。

基于神经网络的循环分块大小预测

池昊宇, 陈长波

计算机科学. 2020, 47 (8): 62-70. doi:10.11896/jsjkx.191200180

摘要 ( 755 )

PDF(2981KB) ( 1354 )

参考文献 | 相关文章 | 多维度评价

循环程序的优化一直是程序优化的重点, 循环分块作为一种典型的循环程序优化技术已被广泛地研究和应用。分块大小的选择对循环程序的性能有着重要影响, 分块大小的选择复杂多变且高度依赖程序和硬件。传统的静态分析和启发式经验搜索的人工和时间成本过高, 缺少通用性和可移植性。为此, 考虑使用有良好高维表示特性的神经网络方法来学习程序与硬件复杂交互过程中分块大小与程序性能的隐含关联。从问题规模、循环结构、循环内操作的局部性等方面抽取出一组新的29维特征, 对问题规模为1024~2048的随机大小的6类内核程序(3维循环、2维数据)的数十万行示例进行实验。串行模型(TSS-T6)相比GCC-O2默认优化实现了6.64倍的平均加速比, 相比穷尽搜索实现了98.5%的平均最大可用性能, 相比Pluto默认分块优化实现了平均9.9%的性能提升。并行模型(TSSP-T6-Search)相比OpenMP默认优化实现了2.41倍的平均加速比, 相比穷尽搜索实现了91.7%的平均最大可用性能, 同时与Pluto默认分块并行优化相比得到了平均9%的性能提升。

可变精度超越函数算法设计

郝江伟, 郭绍忠, 夏媛媛, 许瑾晨

计算机科学. 2020, 47 (8): 71-79. doi:10.11896/jsjkx.200200013

摘要 ( 474 )

PDF(3052KB) ( 1533 )

参考文献 | 相关文章 | 多维度评价

超越函数是基础数学函数库的主体部分, 其精度和性能决定着上层应用的精度和性能。针对超越函数的实现繁琐易错、应用精度需求各异等问题, 文中提出并实现兼顾通用性和函数数学特性的可变精度超越函数算法。依据超越函数的相似性, 构建“转换-归约-逼近-重建”算法模板, 实现常见的超越函数算法;并通过调整算法模板参数来控制误差, 生成不同精度版本的函数代码。实验验证, 所提算法能够生成常见超越函数的不同精度版本的函数代码, 且相对标准数学库超越函数具有性能优势。

基于智能放置策略的Cuckoo哈希表

金琪, 王俊昌, 付雄

计算机科学. 2020, 47 (8): 80-86. doi:10.11896/jsjkx.191200109

摘要 ( 498 )

PDF(2074KB) ( 968 )

参考文献 | 相关文章 | 多维度评价

由于查询时间复杂度为O(1), Cuckoo哈希表在大数据、云计算等领域得到了广泛应用。然而, 现有Cuckoo哈希表的写入操作在遇到写冲突时普遍采用随机替换策略来替换已有表项。一方面, 写入操作容易出现高迟插入和无限循环, 尤其是当哈希表负载率较高时, 甚至有重构整个哈希表的风险;另一方面, 由于现有随机替换策略将数据项尽量散布在哈希表的各个桶中, 哈希表项间缺乏良好的空间局部性, 降低了数据正向查询的效率。为解决以上问题, 提出了一种基于智能放置策略的Cuckoo哈希表。具体地, 为提升写入操作的效率, 提出了一种基于负载均衡的Cuckoo哈希表(Load-Balance Cuckoo Hash Table, LBCHT), 实时限制每个桶的负载, 并使用广度优先搜索寻找最佳Cuckoo路径, 实验结果表明LBCHT能有效减少高负载率下写入操作可能出现的长尾效应;为提升查询操作的效率, 提出了一种充分利用局部性原理的Cuckoo哈希表(Locality Principle Cuckoo Hash Table, LPCHT), 通过充分发掘哈希表项间的空间局部性, 来有效减小查询操作引起的CPU高速缓存缺失率, 提高正向查询的效率。实验结果证明, 在高负载率的压力测试环境中, 与libcuckoo相比, LBCHT的写入效率提升了50%, LPCHT的正向查询效率提升了7%。

大规模申威众核环境下二维数据计算的可扩展方法

庄园, 郭强, 张洁, 曾云辉

计算机科学. 2020, 47 (8): 87-92. doi:10.11896/jsjkx.191000011

摘要 ( 399 )

PDF(1963KB) ( 697 )

参考文献 | 相关文章 | 多维度评价

随着超级计算机及其编程环境的发展, 异构系统结构下的多级并行编程将成为趋势, 神威·太湖之光国产超级计算机就是其中的一个典型。自2016年神威·太湖之光运行以来, 国内外很多学者在其上进行了方法研究和应用验证, 为申威环境积累了比较丰富的众核化编程方法及优化方法。但是, 将全球系统模式CESM移植到申威众核环境时, 对于海洋分量模式POP中的一些二维数据计算, 常用的众核优化方法在1024进程规模下运行时具有较好的加速效果, 然而在16800大规模进程下运行时众核化会失效, 表现为负加速。针对上述问题, 文中提出了一种基于从核分区的并行计算方法, 一个核组内的64个从核被分成多个互不交叉的从核分区, 将可以独立计算的多个代码段计算任务分别分配到不同的从核分区上进行运行, 能够有效利用从核的计算能力, 还可以实现对多个独立的代码段进行计算时间隐藏。每个从核分区内的从核数量及从核号可以根据拟分配的计算任务情况进行适当选取, 使得每个从核都能达到较适宜的数据量和计算量。在采用前述从核分区方法的基础上, 结合使用循环合并和函数上提等方法增大程序并行粒度, 提高了二维数据计算在大规模进程下的可扩展性, CESM模式高分辨率G算例中POP分量模式在110万核心规模下的模拟速度提高了0.8模式年/天, 众核化的加速效果明显。

基于申威26010处理器的大规模量子傅里叶变换模拟

刘晓楠, 荆丽娜, 王立新, 王美玲

计算机科学. 2020, 47 (8): 93-97. doi:10.11896/jsjkx.200300015

摘要 ( 424 )

PDF(2381KB) ( 872 )

参考文献 | 相关文章 | 多维度评价

量子计算由于其纠缠性和叠加性具有天然的并行优势, 然而目前的量子计算设备受限于物理实现的工艺水平, 距离可发挥巨大计算能力并解决有现实意义的实际问题还需要一定时间的技术积累和突破。因此, 采用经典计算机对量子计算进行模拟成为验证量子算法的有效途径。量子傅里叶变换(Quantum Fourier Transform, QFT)是许多量子算法的关键组成部分, 它涉及相位估计、求阶、因子等问题。对量子傅里叶变换的研究和大规模模拟实现, 可以有效促进相关量子算法的研究、验证以及优化。文中使用我国自主研发的超级计算机——“神威·太湖之光”对大规模量子傅里叶变换进行模拟, 并根据申威26010处理器异构并行的特点, 采用MPI、加速线程库以及通信与计算隐藏技术进行优化。通过Shor算法中求解周期部分的运算来验证量子傅里叶变换模拟的正确性, 实现了46位量子比特QFT算法的模拟和优化, 为其他量子算法在超算平台上的验证优化以及新量子算法的提出提供了参考。

面向国产异构众核处理器SW26010的BFS优化方法

袁欣辉, 林蓉芬, 魏迪, 尹万旺, 徐金秀

计算机科学. 2020, 47 (8): 98-104. doi:10.11896/jsjkx.191000013

摘要 ( 427 )

PDF(3058KB) ( 1130 )

参考文献 | 相关文章 | 多维度评价

近年来, 人们越来越关注计算机对数据密集型课题的处理能力。宽度优先搜索(Breadth First Search, BFS)是一种典型的数据密集型课题, 被广泛应用于多种图算法。Graph 500 Benchmark以BFS搜索为核心算法, 已经成为评价计算机处理大数据能力的基准。神威太湖之光超级计算机从2016年6月至2017年11月连续4次荣登Top 500榜单榜首, 其处理器SW26010是首款由我国自主研制的异构众核处理器。文中研究了如何利用SW26010的体系结构特点加速BFS算法的问题, 在SW26010上实现了基于单个核组的方向优化的融合BFS算法, 使用字节图(bytemap)释放内层循环依赖性, 利用异步DMA隐藏计算与便签存储器的访问开销, 利用异构架构协同运算并对图做预处理。最终, 以Graph 500作为基准测试程序处理scale为22的图, SW26010处理器单核组BFS的性能达到457.54MTEPS。

基于GPU的实时SIFT算法

汪亮, 周新志, 严华

计算机科学. 2020, 47 (8): 105-111. doi:10.11896/jsjkx.190700036

摘要 ( 547 )

PDF(4602KB) ( 1097 )

参考文献 | 相关文章 | 多维度评价

针对SIFT特征提取算法过程复杂且实时性低的缺陷, 提出了一种基于GPU的实时尺度不变特征变换(Scale-inva-riant feature transform, SIFT)的优化算法——CUDA Optimized SIFT(CoSift)。该算法首先利用CUDA流并发构建SIFT尺度空间, 在此过程中充分利用了CUDA存储器模型中的高速存储器来提高数据访问速度, 并对二维高斯卷积核进行降维优化来减少计算量, 然后设计了基于warp的直方图算法策略, 重新平衡了特征描述过程中的工作负载。其与CPU版本的常用算法及GPU版本的改进算法的对比实验表明, CoSift算法在未降低特征提取准确性的前提下, 极大地提高了实时性能, 且对大尺寸图像有相对更高的优化效果, 在使用单块 GTX 1080Ti的GPU环境下, 该算法可以在7.7~8.6ms(116.28~129.87fps)内提取出关键点。CoSift算法有效降低了传统SIFT算法过程的复杂性, 提升了实时性能, 能较好地应用于对SIFT算法实时性要求较高的场景。

基于异构云计算的成本约束下的工作流能量高效调度算法

张龙信, 周立前, 文鸿, 肖满生, 邓晓军

计算机科学. 2020, 47 (8): 112-118. doi:10.11896/jsjkx.200300038

摘要 ( 490 )

PDF(1843KB) ( 706 )

参考文献 | 相关文章 | 多维度评价

云计算已成为各行业中十分重要的计算服务方式。传统的云计算研究主要侧重于云服务的定价方式、利润最大化、执行效率等服务质量, 而绿色计算成为了近年来分布式计算的发展趋势。针对异构云环境中满足云用户计算成本约束的工作流任务集调度问题, 提出了一种低时间复杂度、能量感知的预算等级调度(Energy-Aware Based on Budget Level Scheduling, EABL) 算法。EABL算法包含并行任务集任务优先级的建立、任务预算成本的分配及最优执行虚拟机和能量高效频率的确定3个主要阶段, 能在满足预算成本约束的同时最大限度地降低任务集执行过程中的能量消耗。采用真实世界的大规模工作流任务集对算法进行测试, 结果表明, 与著名的EA_HBCS和MECABP算法相比, EABL算法在充分利用预算成本的同时, 有效地降低了工作流任务集在云数据中心计算过程中的能量消耗。

ENLHS:一种基于抽样的Kafka自适应调优方法

谢文康, 樊卫北, 张玉杰, 徐鹤, 李鹏

计算机科学. 2020, 47 (8): 119-126. doi:10.11896/jsjkx.200300010

摘要 ( 547 )

PDF(2357KB) ( 1034 )

参考文献 | 相关文章 | 多维度评价

Kafka应用在生产环境中时, 除机器的硬件环境和系统平台影响其性能外, Kafka自身的配置项决定着其能否在硬件资源有限的情况下达到理想的性能, 但人为修改和调优配置项的效率极差。海量数据发送到Kafka后, 如果不针对实际资源环境进行调优, Kafka使用默认的配置参数无法保证其在每个生产环境下的性能。因为Kafka自身的配置项非常大, 传统的自适应算法在大规模生产系统中的性能较差。为了提高Kafka的自适应能力, 消除系统中的复杂性, 获得更好的运行性能, 提出一种针对Kafka的自适应性能调优方法。该方法充分考虑了Kafka特征参数与性能的影响权值, 并使用抽样的原理来提高数据集的生成效率并优化数据选取范围, 提高建模的效率并降低优化方法的复杂度。实验结果显示, 该算法对开源版本Kafka的吞吐率和时延进行了优化, 提高了Kafka在给定的系统资源下的吞吐性能, 并降低了时延。

二进制域上椭圆曲线密码ECC的高性能FPGA实现

尤文珠, 葛海波

计算机科学. 2020, 47 (8): 127-131. doi:10.11896/jsjkx.200600112

摘要 ( 512 )

PDF(2308KB) ( 1302 )

参考文献 | 相关文章 | 多维度评价

近年来, 通信领域得到了巨大的发展, 网上银行、移动通信等应用增加了资源受限环境下的安全需求。与传统密码算法相比, 椭圆曲线密码体制(Elliptic curve cryptography, ECC)提供了更好的安全标准, 为优化性能参数提供了更大的空间。为此, 文中提出了一种高效的椭圆曲线密码硬件设计方案。该方案在已有研究的基础上, 利用投影坐标系LD Montgomery阶梯算法对ECC中最核心的标量乘运算进行了研究, 并对群运算层采用并行调度来缩短延迟;对于有限域运算, 采用位并行乘法算法和改进的Euclidean求逆算法来实现;基于Xilinx Virtex-5和Virtex-7FPGA器件, 在二进制域域长分别为163, 233和283时实现了该体系结构。实验结果表明, 该方案所需现场可编程门阵列(Field-Programmable Gate Array, FPGA)资源消耗更少, 运算速度更快, 与其他方法相比, 硬件资源消耗减少了52.9%, 标量乘法运算速度提高了5倍, 能更好地适用于资源受限设备的应用。

基于自然邻居的标记分布学习

姚成亮, 朱庆生

计算机科学. 2020, 47 (8): 132-136. doi:10.11896/jsjkx.190700012

摘要 ( 567 )

PDF(2100KB) ( 996 )

参考文献 | 相关文章 | 多维度评价

标记分布是一种新的机器学习范式, 能很好地解决某些标记多义性问题, 可看作多标记的泛化。传统的单标记学习和多标记学习均可看作标记分布学习的特例。已有的标记分布学习算法中, 基于算法改造的AA-KNN(Algorithm Adaptation-KNN)是一种高效的算法, 但任何涉及K近邻求解问题的算法在处理不同数据集时, 参数K值的选取都是一个难题, 不同的K值得到的结果明显不同。基于此, 将自然最近邻居的概念引入标记分布学习, 提出一种新的标记分布学习方法。对数据集使用自然最近邻居搜索算法查找每个样本的自然邻居, 取自然邻居的标记分布均值作为预测结果。搜索算法不需要人工设置任何参数, 同时搜索算法是一种被动搜索, 其自适应计算得到每个样本的邻居。在6个数据集上使用6个评价指标进行实验, 结果表明, 与AA-KNN相比, 结合自然最近邻居的标记分布学习算法不仅避免了人工设置参数的问题, 而且取得了更优的效果。

优势关系粗糙集增量属性约简算法

桑彬彬, 杨留中, 陈红梅, 王生武

计算机科学. 2020, 47 (8): 137-143. doi:10.11896/jsjkx.190700188

摘要 ( 422 )

PDF(2637KB) ( 818 )

参考文献 | 相关文章 | 多维度评价

在现实生活中, 数据不断累积增加, 原有准则和决策之间的相互关系也随之动态变化, 如何高效地计算属性约简是动态决策亟需解决的问题。增量更新方法可以有效地完成动态学习任务, 因为它可以在原有知识的基础上获取新的知识。文中利用优势粗糙集方法研究了在有优势关系的数据中添加单个对象时的增量属性约简方法。首先, 定义了优势集矩阵作为更新的目标, 用来计算新的优势条件熵;其次, 通过分析增加对象的3种不同情况, 提出了优势条件熵的增量学习机制;然后, 基于优势集矩阵设计了增量属性约简算法;最后, 对6种不同的UCI数据集进行实验, 用于比较增量和非增量算法的有效性和高效性。实验结果显示, 提出的增量属性约简算法不仅在有效性上与非增量属性约简算法保持一致, 而且在高效性上要远优于非增量属性约简算法。因此, 所提算法能有效且高效地完成动态优势关系数据中属性约简的任务。

基于直觉犹豫模糊集的三支决策模型及其应用

陈玉金, 徐吉辉, 史佳辉, 刘宇

计算机科学. 2020, 47 (8): 144-150. doi:10.11896/jsjkx.190800041

摘要 ( 412 )

PDF(1504KB) ( 690 )

参考文献 | 相关文章 | 多维度评价

决策者本身的能力限制以及被评价对象存在的不确定性, 导致三支决策模型在处理信息模糊以及由主观认知概念模糊而产生犹豫的决策问题时表现力不足。为解决上述问题, 文中引入直觉犹豫模糊集建立相应的三支决策模型。首先, 考虑到直觉犹豫模糊集包含多个隶属度的特性, 建立单一直觉模糊数的三支决策方法。基于此, 在风险代价矩阵确定的情况下, 以直觉犹豫模糊集为论域建立基于直觉犹豫模糊集的三支决策模型。然后, 考虑到特定应用环境的语义解释, 形成了乐观、悲观以及少数服从多数的决策规则。最后, 结合航空领域的安全风险评估方法, 给出了基于双评价函数的航空安全风险三支决策方法, 并通过算例说明所提模型的具体应用过程。

基于PE散度实例过滤的深度域适应方法

袁晨晖, 程春玲

计算机科学. 2020, 47 (8): 151-156. doi:10.11896/jsjkx.190600175

摘要 ( 313 )

PDF(1555KB) ( 727 )

参考文献 | 相关文章 | 多维度评价

深度域适应作为迁移学习最常见的问题之一, 已经在许多机器学习应用中获得了优异的性能。然而, 现有的深度域适应方法在减小域偏差时单一适配完全连接层, 忽视了卷积层的空间信息和语义上下文信息, 造成在知识迁移过程中丢失重要信息。为此, 文中将基于实例的域适应与基于特征的域适应相结合, 提出了基于PE散度实例过滤的深度域适应方法(Domain Adaptation Based on PE Divergence Instance Filtering, DAPEIF)。其基本思想是首先利用PE散度计算源域样本的相对权值, 删除易造成负迁移的源域样本, 选择相对权值较高的训练数据作为新的源域样本, 从而降低源域与目标域之间的差异性;然后基于AlexNet模型, 使用最大均值差异(Maximum Mean Discrepancy, MMD)准则, 将其作为正则化项纳入神经网络的学习中。与以往只关注完全连接层的域适应方法不同, 文中联合匹配卷积层和完全连接层的边缘概率分布以解决欠适配问题, 同时引入权值正则项, 通过梯度下降法学习网络参数, 进一步提高了域适应过程中模型的泛化性能。所提算法能同时对神经网络的卷积层和完全连接层的参数赋予领域自适应能力, 在域适应公开数据集Office-Caltech上的实验结果表明, 域适应对卷积层是有效的, 更重要的是卷积层的自适应可以进一步提高传统域适应的性能, 与主流的域适应算法DDC和DAN相比, 所提算法在精度上有所提高, 平均精度达到84.46%。

基于中心团的重叠社区检测算法

薛磊, 唐旭清

计算机科学. 2020, 47 (8): 157-163. doi:10.11896/jsjkx.200300034

摘要 ( 273 )

PDF(1985KB) ( 923 )

参考文献 | 相关文章 | 多维度评价

社区检测已经成为了了解复杂网络结构和网络动态的一个重要途径。针对传统的节点聚类和链接聚类在发现重叠社区方面存在的两种固有缺陷, 即参数依赖和结果不稳定, 文中提出了一种基于中心团的局部扩展改进算法CLEM, 用于检测重叠社区。该算法通过选取中心团为核心种子, 并在种子扩展过程中惩罚被多次删除的节点, 改善所得结果的稳定性;通过选取不依赖参数的适应度函数, 改进其迭代计算过程, 避免了适应度函数的参数限制, 并降低了计算复杂度。在合成网络和现实网络上测试的结果表明, 与已有算法相比, 所提算法在计算时间和准确度上均有很好的表现。

基于依赖联系分析的观点词对协同抽取

赵威, 林煜明, 王超强, 蔡国永

计算机科学. 2020, 47 (8): 164-170. doi:10.11896/jsjkx.190600153

摘要 ( 268 )

PDF(1695KB) ( 580 )

参考文献 | 相关文章 | 多维度评价

同一类商品下, 观点词对中包含的观点目标和观点词通常有着很强的观点依赖联系, 因此可以通过对评论句子中单词间的观点依赖联系进行分析来提取观点词对。首先, 构建评论句子的依赖联系分析模型来获取评论句子中每个单词之间的依赖联系信息, 文中选择的基本模型是LSTM神经网络;然后, 假设评论句子中所包含的观点词对中的一项是已知的, 并将该已知项作为模型的注意力信息, 使得模型能够从评论句子中有重点地提取出与该已知项具有强观点依赖联系的单词或词组, 并将其作为观点词对中的另一未知项;最后, 将观点依赖联系得分最高的词对作为观点词对并输出。文中进一步设计了一种复合模型, 通过结合两种包含不同已知项信息的上述模型, 来实现在不需要提前知道已知项的情况下观点词对的挖掘。

一种基于Q-学习算法的增量分类模型

刘凌云, 钱辉, 邢红杰, 董春茹, 张峰

计算机科学. 2020, 47 (8): 171-177. doi:10.11896/jsjkx.190600150

摘要 ( 562 )

PDF(1369KB) ( 916 )

参考文献 | 相关文章 | 多维度评价

大数据时代的数据信息呈现持续性、爆炸性的增长, 为机器学习算法带来了大量监督样本。然而, 这对信息通常不是一次性获得的, 且获得的数据标记是不准确的, 这对传统的分类模型提出了挑战, 而增量学习是一种重要的解决方法。但在增量学习中, 样本的标记顺序将严重影响分类器的性能, 特别是在分类器分类能力较弱的情况下, 传统的增量学习方法容易过早地将噪声数据添加到训练集上, 从而影响分类器的精度。为解决这个问题, 文中提出一种基于Q-学习算法的增量分类模型。该模型利用强化学习中经典的Q-学习算法来合理选择样本增量序列, 削弱噪声数据的负面影响, 并实现在学习过程中自主标记样本。同时, 为了解决当新增未标记样本集规模较大时, Q-学习中的状态空间与动作空间增大带来的计算复杂度和存储空间呈指数增长的问题, 文中进一步给出了批量增量分类模型, 有效降低了模型的计算复杂度并节约了存储空间。基于Q-学习算法的增量分类模型融合了增量学习及强化学习的思想, 具有分类精度高、实时性强等优点。最后, 在3个UCI数据集上进行实验来验证所提模型的有效性, 结果表明该模型通过选择新增训练集合的确有助于提升分类器的精度, 且由不同增量序列训练得到的分类器精度也有较大差异。基于Q-学习算法的增量分类模型可以利用已有的少量监督信息进行初始训练, 通过自主标记样本构造增量训练集, 并通过自监督的方式提高分类器的精度。因此, 基于Q-学习算法的增量分类模型可被用于解决监督信息缺乏的问题, 具有一定的应用价值。

基于遗传实例和特征选择的K近邻训练集优化方法

董明刚, 黄宇扬, 敬超

计算机科学. 2020, 47 (8): 178-184. doi:10.11896/jsjkx.190700089

摘要 ( 371 )

PDF(2327KB) ( 689 )

参考文献 | 相关文章 | 多维度评价

K近邻的分类性能依赖于训练集的质量。设计高效的训练集优化算法具有重要意义。针对传统的进化训练集优化算法效率较低、误删率较高的不足, 提出了一种遗传训练集优化算法。该算法采用基于最大汉明距离的高效遗传算法, 每次交叉保留父代并生成两个新的具有最大汉明距离的子代, 既提高了效率, 又保证了种群多样性。该算法将局部的噪声样本删除策略与特征选择策略相结合。首先使用决策树算法确定噪声样本存在的范围, 然后使用遗传算法精准删除此范围内的噪声样本和全局的噪声特征, 降低了误删率, 提高了效率。该算法采用基于最近邻规则的验证集选择策略, 进一步提高了遗传算法实例选择和特征选择的准确度。在15个标准数据集上, 该方法相较于协同进化实例特征选择算法IFS-CoCo、加权协同进化实例特征选择算法CIW-NN、进化特征选择算法EIS-RFS、进化实例选择算法PS-NN、K近邻算法KNN, 在分类精度上分别平均提升了2.18％, 2.06％, 5.61％, 4.06％和4.00％。实验结果表明, 所提方法的分类精度和优化效率优于当前的进化训练集优化算法。

FS-CRF:基于特征切分与级联随机森林的异常点检测模型

刘振鹏, 苏楠, 秦益文, 卢家欢, 李小菲

计算机科学. 2020, 47 (8): 185-188. doi:10.11896/jsjkx.190600162

摘要 ( 281 )

PDF(1697KB) ( 606 )

参考文献 | 相关文章 | 多维度评价

大数据时代, 攻击篡改、设备故障、人为造假等原因导致海量数据中潜藏着许多异常值。准确地检测出数据中的异常点, 实现数据清洗, 至关重要。文中提出一种结合特征切分与多层级联随机森林的异常点检测模型(outlier detection model based on Feature Segmentation and Cascaded Random Forest, FS-CRF)。利用滑动窗口与随机森林对原始特征进行细粒度切分, 生成类概率向量, 用于训练多层级联的随机森林;由级联层中最后一层的随机森林投票决定样本的最终类别。仿真实验结果表明, 新方法在基于多个UCI数据集进行的异常分类任务中均获得较高F1-measure评分;级联结构使新模型相比于经典的随机森林算法进一步提高了泛化能力;在高维数据集上所提方法比梯度提升决策树和XGBoost拥有更优的性能, 且超参数较少, 易于调优, 具有更好的综合性能。

基于可见性图网络的中国专利申请关注度分析

张梦月, 胡军, 严冠, 李慧嘉

计算机科学. 2020, 47 (8): 189-194. doi:10.11896/jsjkx.200300001

摘要 ( 388 )

PDF(2149KB) ( 622 )

参考文献 | 相关文章 | 多维度评价

专利是创新的重要体现, 很多人在进行专利申请之前会在网上对专利申请的过程进行查询, 了解专利申请的步骤, 这些人的搜索事实也是了解创新企业或个人对创新是否重视的一个手段。文中从一个全新的时间序列分析的视角即网络的角度, 分析了关键字为“专利申请”的百度搜索指数时间序列的动力学特征。利用可见性图算法的原理将百度搜索指数时间序列转化为复杂网络, 并计算其参数, 分析其网络的拓扑结构。首先, 通过计算2019年各省复杂网络的参数发现各省的专利关注度具有一定差异;其次, 研究表明大多数网络均为无标度网络, 原始时间序列具有分形的特征;最后通过聚类, 可根据复杂网络的参数把31个省分为3类。文中分析了2011－2018年全国的百度搜索指数数据, 通过社团结构的划分, 可以发现时间序列的周期和中心节点对搜索指数影响的范围。

基于3D全时序卷积神经网络的视频显著性检测

王教金, 蹇木伟, 刘翔宇, 林培光, 耿蕾蕾, 崔超然, 尹义龙

计算机科学. 2020, 47 (8): 195-201. doi:10.11896/jsjkx.190600148

摘要 ( 427 )

PDF(3008KB) ( 832 )

参考文献 | 相关文章 | 多维度评价

视觉是人类感知世界的重要途径之一。视频显著性检测旨在通过计算机模拟人类的视觉注意机制, 智能地检测出视频中的显著性物体。目前, 基于传统方法的视频显著性检测已经达到一定的水平, 但是在时空信息一致性利用方面仍不能令人满意。因此, 文中提出了一种基于全时序卷积神经网络的视频显著性检测方法。首先, 利用全时序卷积对输入视频进行空间信息和时间信息的时空特征提取;然后, 利用3D池化层进行降维;其次, 在解码层中用3D反卷积和3D上采样对前端特征进行解码;最后, 通过把时空信息有机地提取与融合, 来有效地提升显著图的质量。实验结果表明, 所提算法在3个广泛使用的视频显著性检测数据集(DAVIS, FBMS, SegTrack)上的性能优于当前主流的视频显著性检测方法。

基于密集卷积生成对抗网络的图像修复

孟丽莎, 任坤, 范春奇, 黄泷

计算机科学. 2020, 47 (8): 202-207. doi:10.11896/jsjkx.190700017

摘要 ( 414 )

PDF(3379KB) ( 832 )

参考文献 | 相关文章 | 多维度评价

图像修复是一项利用缺损图像中已知信息对缺损区域信息进行估计修复的技术。针对大面积语义信息缺失的图像进行修复时, 若训练数据集较小且图像背景相对复杂, 则基于生成模型的修复结果常出现模糊、伪影和视觉相似度差等问题。针对上述问题, 文中提出了一种基于密集卷积生成对抗网络的图像修复算法。该算法采用生成对抗网络作为图像修复的基本框架。首先, 利用密集卷积块构建具有编解码结构的生成网络, 不但加强了图像特征的提取, 提高了图像修复能力, 而且避免了深度增加引起的梯度消失问题。其次, 在编码和解码结构之间引入跳跃连接, 解决了网络层间信息传递丢失的问题。然后, 在网络优化过程中, 结合重建损失、对抗损失和TV损失来训练网络模型, 增强了网络稳定性。最后, 分别在CelebA和Car两个数据集上进行实验, 所提算法的修复结果在视觉效果、峰值信噪比PSNR和结构相似度SSIM 3个方面均优于3种代表性图像修复算法, 其有效性得到验证。

一种基于视频分析的高速公路交通异常事件检测算法

姚兰, 赵永恒, 施雨晴, 于明鹤

计算机科学. 2020, 47 (8): 208-212. doi:10.11896/jsjkx.191000165

摘要 ( 339 )

PDF(1787KB) ( 1847 )

参考文献 | 相关文章 | 多维度评价

交通领域的异常事件检测对于预防和及时处理交通事故有着重要作用。当前大多数交通异常事件检测都是通过人工完成的, 耗费了大量的人力, 同时实时性也较差。文中针对高速公路的交通场景特点, 利用深度学习中的目标检测算法, 对视频中的车辆目标进行提取, 提出了结合运动特征和表观特征的多目标追踪算法;在此基础上, 又提出了一种基于车辆轨迹特征的异常事件检测方法, 其中的追踪算法减少了轨迹提取过程对背景环境变化的依赖。在异常事件检测算法中充分结合高速公路实际场景, 加入滑动窗口机制, 提升了对远距离和复杂场景下异常事件的检测能力。利用面向真实交通视频的数据, 与现有的事件检测算法进行对比, 实验结果证明, 所提方法在事件检测的准确率、召回率和F值指标方面都有良好的性能表现, 能够有效地完成高速场景下的交通异常事件检测。

GNNI U-net：基于组归一化与最近邻插值的MRI左心室轮廓精准分割网络

高强, 高敬阳, 赵地

计算机科学. 2020, 47 (8): 213-220. doi:10.11896/jsjkx.190600026

摘要 ( 537 )

PDF(3633KB) ( 1155 )

参考文献 | 相关文章 | 多维度评价

心血管疾病已成为威胁人类健康的头号杀手。目前, 医生们通过左心室MRI成像技术对左心室轮廓进行手工标注来计算心脏的各项功能参数, 以监测和预防心血管疾病, 但此方法的标注工作量大、耗时且繁琐。目前, 深度学习在许多医疗影像分割领域取得了显著的成功, 但在左心室轮廓分割领域仍有提升的空间。文中提出了一种基于组归一化与最近邻插值的MRI左心室轮廓精确分割网络——GNNI U-net(U-net with Group Normalization and Nearest Interpolation), 该网络利用组归一化方法构建了能够快速、准确提取特征信息的卷积模块, 基于最近邻插值法构建了用于特征信息还原的上采样模块。在Sunnybrook与LVSC两个左心室分割数据集上采用了中心裁减ROI提取的预处理方法, 并对GNNI U-net进行了充分的对比实验。所提网络在Sunnybrook数据集上获得了Dice系数为0.937以及Jaccard系数为0.893的精度。在LVSC数据集上获得了Dice系数为0.957以及Jaccard系数为0.921的精度。GNNI U-net在左心室轮廓分割领域取得了比现有卷积网络分割方法更高的Dice系数精度。最后, 进一步讨论并验证了组归一化操作卷积模块能够加速网络的收敛并提高分割精度;采用最近邻插值法的上采样模块对左心室轮廓这类较小目标的分割效果更好, 能够在一定程度上加速网络的收敛。

基于残差连接的场景文本识别端到端网络结构优化

黄金星, 潘翔, 郑河荣

计算机科学. 2020, 47 (8): 221-226. doi:10.11896/jsjkx.190500017

摘要 ( 277 )

PDF(1897KB) ( 872 )

参考文献 | 相关文章 | 多维度评价

针对已有文本识别网络由于深度不够而识别准确率较低的问题, 文中提出一种改进的端到端文本识别网络结构。首先, 将文本作为序列, 采用残差模块将文本按列切分成特征向量输入循环层。这种残差结构增加了卷积网络的深度, 使网络保持对文本图像的最佳表征能力, 实现对文本信息的捕捉。另一方面, 残差模块采用堆叠层来学习残差映射, 在层数加深的情况下提高了网络的收敛性。然后, 采用循环层对这些文本特征序列进行上下文建模, 并把建模结果输入Softmax层以获得序列对应标签的预测, 实现了对任意长度文本的识别。循环层使用长短时记忆网络学习文本之间的依赖关系, 解决长序列训练过程中的“梯度消失”问题。最后, 通过最优路径方法进行文本标签转录。该方法找到一条路径使其概率最大, 并输出这条路径对应的序列为最优序列。改进的文本识别网络结构增加了深度, 提高了文本图像的特征描述能力和在噪声下的稳定性。在多个测试数据集(ICDAR2003, ICDAR2013, SVT和IIIT5K)上将所提算法与已有典型算法进行实验对比分析, 结果表明该网络结构能够得到更高的场景文本识别准确率, 验证了其有效性。

一种用于微表情自动识别的三维卷积神经网络进化方法

梁正友, 何景琳, 孙宇

计算机科学. 2020, 47 (8): 227-232. doi:10.11896/jsjkx.190700009

摘要 ( 495 )

PDF(1955KB) ( 832 )

参考文献 | 相关文章 | 多维度评价

由于微表情持续时间短、动作幅度小, 因此微表情自动识别一直是一个具有挑战性的问题。针对上述问题, 提出一种用于微表情识别的三维卷积神经网络进化(Three-Dimensional Convolutional Neural Network Evolution, C3DEvol)方法。该方法使用能有效提取动态信息的三维卷积神经网络(Three-Dimensional Convolutional Neural Network, C3D)来提取微表情在时域和空域上的特征;同时使用具有全局搜索和优化能力的遗传算法对C3D的网络结构进行优化, 以获取最优的C3D网络结构和避免局部优化。利用CASME2数据集在带有两块NVIDIA Titan X GPU的工作站上开展了实验, 结果表明C3DEvol微表情自动识别的准确率达到63.71%, 优于现有的微表情自动识别方法。

基于YOLOv3的施工场景安全帽佩戴的图像描述

徐守坤, 倪楚涵, 吉晨晨, 李宁

计算机科学. 2020, 47 (8): 233-240. doi:10.11896/jsjkx.190600109

摘要 ( 517 )

PDF(4631KB) ( 1150 )

参考文献 | 相关文章 | 多维度评价

近年来, 因工人未佩戴安全帽而造成的施工事故频繁发生, 为降低事故发生率, 对工人安全帽佩戴情况进行图像描述的研究。当前基于神经网络的图像描述方法缺乏可解释性且细节描述不充分, 施工场景图像描述的研究较为匮乏, 针对该问题, 提出采用YOLOv3(You Only Look Once)的检测算法, 以及基于语义规则和语句模板相结合的方法递进式地生成安全帽佩戴的描述语句。首先, 采集数据, 制作安全帽佩戴检测数据集和图像字幕数据集;其次, 使用K-means算法确定适用于该数据集的锚框参数值, 用以YOLOv3网络的训练与检测;再次, 预定义一个语义规则, 结合目标检测结果来提取视觉概念;最后, 将提取出的视觉概念填充进由图像字幕标注生成的语句模板, 以生成关于施工场景中工人安全帽佩戴的图像描述语句。使用Ubuntu16.04系统和Keras深度学习框架搭建实验环境, 在自制的安全帽佩戴数据集上进行不同算法的对比实验。实验结果表明, 所提方法不仅能够有效界定安全帽佩戴者和未佩戴者的数量, 而且在BLEU-1和CIDEr评价指标上的得分分别达到了0.722和0.957, 相比其他方法分别提高了6.9%和14.8%, 证明了该方法的有效性和优越性。

基于加权近红外图像融合的单幅图像除雾方法

朱珍, 黄锐, 臧铁钢, 卢世军

计算机科学. 2020, 47 (8): 241-244. doi:10.11896/jsjkx.200300068

摘要 ( 438 )

PDF(1702KB) ( 756 )

参考文献 | 相关文章 | 多维度评价

传统图像除雾方法存在无雾区域中图像对比度过高的问题, 导致在某些情况下生成的图像视觉效果不够自然。为了得到自然清晰的除雾图像, 提出了一种基于加权近红外(Near-InFrared, NIR)图像融合的新型单幅图像除雾方法, 通过将NIR图像的细节成分融合到同一场景的可见光图像中来恢复图像对比度, 并使用透射图对NIR图像进行加权, 从而防止无雾区域出现过度增强。实验结果表明, 相比传统的单幅图像除雾方法, 所提方法可以有效地恢复图像对比度, 并且不会过分强化无雾区域, 具有更高的PSNR值和SSIM值。

车辆跟随控制系统研究现状及发展趋势

章军辉, 陈大鹏, 李庆

计算机科学. 2020, 47 (8): 245-254. doi:10.11896/jsjkx.190700058

摘要 ( 625 )

PDF(2670KB) ( 1818 )

参考文献 | 相关文章 | 多维度评价

由于跟车行驶是日常道路交通环境中最主要的行车工况, 实现车辆智能跟随、列队行驶这种自动有序且快速高效的通行方式, 将是解决交通拥堵现象、交通安全状况、环境污染等交通问题的有效方法。文中概述了道路交通环境下国内外车辆跟随控制系统的发展历程, 主要从环境感知技术、期望车距策略、纵横向动力学建模、决策与控制算法等方面对车辆跟随控制系统的国内外最新研究成果进行概要论述, 并对车辆跟随控制系统研究的共性问题以及未来发展趋势进行了探讨与展望。

一种低频词词向量优化方法及其在短文本分类中的应用

程婧, 刘娜娜, 闵可锐, 康昱, 王新, 周扬帆

计算机科学. 2020, 47 (8): 255-260. doi:10.11896/jsjkx.191000163

摘要 ( 400 )

PDF(2059KB) ( 1274 )

参考文献 | 相关文章 | 多维度评价

众多自然语言处理(Natural Language Processing, NLP)任务受益于在大规模语料上训练的词向量。由于预训练的词向量具有大语料上的通用语义特征, 因此将这些词向量应用到特定的下游任务时, 往往需要通过微调进行一定的更新和调整, 使其更适用于目标任务。但是, 目标语料集中的低频词由于缺少训练样本, 导致在微调过程中无法获得稳定的梯度信息, 使得词向量无法得到有效更新。而在短文本分类任务中, 这些低频词对分类结果同样有着重要的指示性。因此, 在具体的短文本分类任务上获得一个更好的低频词词向量表示是有必要的。针对这个问题, 文中提出了一种与下游任务模型无关的低频词词向量更新算法, 通过基于K近邻的词向量偏移计算方法, 利用通用词向量中与低频词相似的高频词所获得的任务特征信息, 来指导低频词的信息更新, 从而获得更准确的且适用于当前任务语境的低频词词向量表示;并以TextCNN作为基准模型, 基于word2vec和GloVe得到的两个通用预训练词向量, 在3个公开的短文本数据集上进行了优化算法的效果验证。实验结果表明, 使用优化算法更新低频词词表示后, 模型分类准确率能达到84.3%~94%, 较更新前提升了0.4%~1.4%, 体现了优化算法的有效性, 也进一步证明了短文本分类任务中低频词对分类结果的影响, 为短文本分类的研究工作提供了一定的借鉴。

基于剪枝与量化的卷积神经网络压缩方法

孙彦丽, 叶炯耀

计算机科学. 2020, 47 (8): 261-266. doi:10.11896/jsjkx.190700062

摘要 ( 587 )

PDF(2523KB) ( 1909 )

参考文献 | 相关文章 | 多维度评价

随着深度学习的发展, 卷积神经网络作为其重要算法之一, 被广泛应用到计算机视觉、自然语言处理及语音处理等各个领域, 并取得了比传统算法更为优秀的成绩。但是, 卷积神经网络结构复杂, 参数量和计算量巨大, 使得很多算法必须在GPU上实现, 导致卷积神经网络难以应用在资源不足且实时性要求很高的移动端。为了解决上述问题, 文中提出通过同时优化卷积神经网络的结构和参数来对卷积神经网络进行压缩, 以使网络模型尺寸变小。首先, 根据权重对网络模型结果的影响程度来对权重进行剪枝, 保证在去除网络结构冗余信息的同时保留模型的重要连接;然后通过量化感知(quantization-aware-trai-ning)对卷积神经网络的浮点型权重和激活值进行完全量化, 将浮点运算转换成定点运算, 在降低网络模型计算量的同时减少网络模型的尺寸。文中选用tensorflow深度学习框架, 在Ubuntu16.04操作系统中使用Spyder编译器对所提算法进行验证。实验结果表明, 该算法使结构简单的LeNet模型从1.64M压缩至0.36M, 压缩比达到78%, 准确率只下降了了0.016;使轻量级网络Mobilenet模型从16.9M压缩至3.1M, 压缩比达到81%, 准确率下降0.03。实验数据说明, 在对卷积神经网络权重剪枝与参数量化之后, 该算法可以做到在准确率损失较小的情况下, 对模型进行有效压缩, 解决了卷积神经网络模型难以部署到移动端的问题。

智能3D打印路径规划算法

杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊

计算机科学. 2020, 47 (8): 267-271. doi:10.11896/jsjkx.190700184

摘要 ( 620 )

PDF(2628KB) ( 2834 )

参考文献 | 相关文章 | 多维度评价

大型工业制件在增材制造中的路径规划的优劣直接影响着制造质量和效率。现阶段常用的传统3D打印路径规划方法存在打印头转弯堆积和打印头起落次数较多等问题, 并不完全适用于大型工业制造。因此, 文中提出了一种智能路径规划方法。首先, 将切片后得到的二维平面进行凹多边形凸分解, 形成打印子区;然后, 对每个分区内部进行沿分区长轴打印以减少打印路径数量和总行程;最后, 将子分区的连接视作TSP旅行商问题, 使用遗传算法完成子分区间的打印路径规划。同时, 利用C#语言设计开发了一套智能3D打印路径规划系统, 该系统具有切片面输入和显示、打印宽度设置、智能路径规划和G-code代码输出的功能。分别与两种传统路径规划算法进行对比实验, 证明了智能路径规划算法生成的路径条数、空行程距离、打印头抬起次数均有明显减少。基于子分区的智能路径规划方法为大型工业制件的增材制造过程提供了新的思路。

基于改进Dijkstra算法的AGVs无碰撞路径规划

姜辰凯, 李智, 盘书宝, 王勇军

计算机科学. 2020, 47 (8): 272-277. doi:10.11896/jsjkx.190700138

摘要 ( 639 )

PDF(2282KB) ( 1387 )

参考文献 | 相关文章 | 多维度评价

针对多自动导引车(Automatic Guided Vehicle, AGV)在柔性制造系统中出现的路径规划与冲突问题, 提出了一种基于时间窗的改进Dijkstra算法, 实现多AGV的动态路径规划。首先, 利用传统Dijkstra算法为执行调度任务的多AGV规划路径, 并统计被规划路径的使用程度, 计算加权系数, 然后将加权后的路径长度更新到数据库中;其次, 计算AGV通过每个工位节点的时间, 通过时间窗的排布避免碰撞冲突;最后, 当产生冲突时, 通过计算并设置AGV的优先级, 对优先级较低的AGV重新进行路径规划。仿真实验结果表明, 该算法能够在最优路径下有效避免冲突与死锁, 不仅提高了系统效率, 而且使系统具有较好的鲁棒性。

基于混合整数规划的停机位优化调度研究

张红颖, 申荣苗, 罗谦

计算机科学. 2020, 47 (8): 278-283. doi:10.11896/jsjkx.190400154

摘要 ( 522 )

PDF(1792KB) ( 927 )

参考文献 | 相关文章 | 多维度评价

为有效缓解机场航空器延误现状, 系统地研究了机场停机位优化调度问题。通过深入剖析机场地面运行特性, 综合考虑航空器机型匹配、缓冲时间和航空器冲突等约束限制, 科学合理地权衡机场各种利益需求, 提出优化停机位调度问题的混合整数规划模型, 主要目标是在确保航空器安全运行的前提下, 使得航班延误的总时间最短。该模型引入了概率分布函数, 以避免航空器冲突的发生, 结合多目标优化及分支界定算法的基本理论, 寻求最优的分配方案。仿真实验表明, 模型对机场预计进港航空器时间进行优化排序, 通过优化调度方案调整停机位分配冲突, 得到最优的分配方案。该算法能够缩小搜索空间, 提高求解效率, 显著减低延误总时间, 提高机场停机位的资源利用率。与启发式算法相比, 所提算法可使航空器延误减少2.4%, 因此该方法能够有效降低机场地面航班延误率。

复杂网络社区发现的多目标五行环优化算法

张清琪, 刘漫丹

计算机科学. 2020, 47 (8): 284-290. doi:10.11896/jsjkx.190700082

摘要 ( 552 )

PDF(2556KB) ( 909 )

参考文献 | 相关文章 | 多维度评价

社区结构作为复杂网络的重要特性, 对理解网络的功能和结构具有重要意义。为了解决复杂网络的社区发现问题, 提出了一种多目标五行环优化算法(Multi-Objective Five-Elements Cycle Optimization, MOFECO)。首先, 将社区发现问题建模为多目标优化问题, 选取反比率关联(Inverse Ratio Association, IRA)和比例缩减(Ratio Cut, RC)这两个互相对立的目标作为目标函数;然后, 基于五行环模型(Five-Elements Cycle Model, FECM), 通过局部最优解和全局最优解实现元素的更新, 并引入交叉和变异算子对更新策略进行改进;最后, 使用快速非支配排序的方法获得Pareto最优社区划分集合, 有助于揭示复杂网络的层次结构。在人工合成网络和真实社会网络上进行实验, 与单目标算法(GA-Net, Meme-Net)以及多目标算法(MOGA-Net, MOCD, MOEA/D-Net, DMOPSO, DIM-MOEA/D, MOCD-ACO)进行对比得出, MOFECO算法弥补了传统单目标优化社区结构划分单一的缺陷, 在社区发现的准确度上有所提高。

基于莱维飞行和随机游动策略的灰狼算法

李阳, 李维刚, 赵云涛, 刘翱

计算机科学. 2020, 47 (8): 291-296. doi:10.11896/jsjkx.190600107

摘要 ( 849 )

PDF(2443KB) ( 1918 )

参考文献 | 相关文章 | 多维度评价

在标准灰狼优化算法寻优的中后期, 由于衰减因子减小, 灰狼群体中的个体均向领导层灰狼所在区域靠近, 导致算法的全局寻优能力差, 降低了寻优精度。针对该问题, 提出了一种改进灰狼优化算法(Improved Grey Wolf Optimization, IGWO)。该算法首先分析了衰减因子对灰狼算法(Grey Wolf Optimization, GWO)的影响, 提出了一种分段可调节衰减因子, 用于平衡算法的勘探能力与开发能力。其可以根据不同优化问题来寻找适当的参数, 实现更高精度的寻优, 并且保证了在寻优过程的中后期, 算法也具有一定的全局搜索能力。数值仿真实验表明, 提高勘探比例有利于提高算法的收敛精度。同时, 在寻优过程中, 根据概率选择对领导层灰狼分别进行莱维飞行操作或随机游动操作。利用莱维飞行短距离搜索与偶尔较长距离行走相间的搜索特点, 提高算法的全局寻优能力;利用随机游动相对集中的搜索特性, 提高局部寻优能力。最后, 对8个标准测试函数进行仿真实验, 并与其他几种算法进行比较, 实验结果表明, 所提算法在寻优精度、算法稳定性及收敛速度上都有较大优势。

集成随机惯性权重和差分变异操作的樽海鞘群算法

张志强, 鲁晓锋, 隋连升, 李军怀

计算机科学. 2020, 47 (8): 297-301. doi:10.11896/jsjkx.190700063

摘要 ( 423 )

PDF(1316KB) ( 746 )

参考文献 | 相关文章 | 多维度评价

为了提高樽海鞘群算法(Salp Swarm Algorithm, SSA)的收敛速度、计算精度和全局优化能力, 在分析总结粒子群优化(Particle Swarm Optimization, PSO)和差分进化(Differential Evolution, DE)算法相关研究成果后, 提出了一种集成PSO算法随机惯性权重和DE算法差分变异操作的改进SSA算法——iSSA。首先, 将PSO算法的随机惯性权重引入SSA算法的追随者位置更新公式中, 用于增强和平衡SSA算法的勘探与开发能力;其次, 用DE算法的变异操作替代SSA算法的领导者位置更新操作, 以提高SSA算法的收敛速度和计算精度。为了检验随机惯性权重和差分变异操作对SSA算法的改进效果, 在多个高维基准函数上进行了仿真实验, 并与其他改进SSA算法进行了比较。实验结果及分析表明, 与SSA算法和两个典型的改进SSA算法(ESSA和CASSA)相比, 集成随机惯性权重和差分变异操作的iSSA算法, 在没有增加算法时间复杂度的情况下, 显著地提高了SSA算法的收敛速度、计算精度和全局优化能力, 并且优于ESSA算法和CASSA 算法。

基于特征分类的链路预测方法综述

王慧, 乐孜纯, 龚轩, 武玉坤, 左浩

计算机科学. 2020, 47 (8): 302-312. doi:10.11896/jsjkx.190700136

摘要 ( 745 )

PDF(2715KB) ( 2358 )

参考文献 | 相关文章 | 多维度评价

复杂网络链路预测作为网络科学研究中一个重要的研究方向, 受到了越来越多来自各个学科领域专家的关注, 它可以利用现有的网络信息, 如节点和边缘的特征, 来预测未来可能形成的关系、网络中缺失的信息以及新的或正在消失的信息, 识别虚假交互, 评估网络演化机制, 进行网络重构等。当前链路预测的文献主要来自工程学、计算机科学与物理学的专家, 它们各自为政, 缺少合作, 结合多学科进行链路预测的综述论文少之又少。因此, 文中从计算机科学和物理学的视角全面回顾、分析和讨论基于特征分类的链路预测算法的研究进展, 介绍了该领域专家们提出的多种特征提取技术, 首次把分层的思想引入链路预测算法分类中, 将分类模型分为3层, 即元数据层、特征分类层和特征抽取层。该分类模型包括“2个大块7个方面”, 即把常用的链路预测算法分为2个大块(特征提取方法和特征学习方法)和7个方面(基于相似性的方法、基于似然分析的方法、基于概率模型的方法、矩阵分解方法、基于随机游走的方法、基于神经网络的方法和基于自定义损失函数的方法)。该分类方法覆盖了各学科中许多经典的和最新的链路预测技术, 包括当前最流行的图神经网络链路预测技术GNN(Graph Neural Network), GCN(Graph Convolutional Network), RNN(Recurrent Neural Network)和RL(Reinforcement Learning)。文中研究了这些算法的模型复杂性和预测性能的差异, 并对当前链路预测技术未来所面临的挑战进行了讨论。

基于最长连续间隔的未知二进制协议格式推断

陈庆超, 王韬, 冯文博, 尹世庄, 刘丽君

计算机科学. 2020, 47 (8): 313-318. doi:10.11896/jsjkx.190700031

摘要 ( 476 )

PDF(2057KB) ( 801 )

参考文献 | 相关文章 | 多维度评价

在未知二进制协议的格式推断过程中, 常常引入大量的先验知识, 实验操作复杂且准确率不高。为此, 文中提出了一种人为设定较少参数、操作简单、准确率较高的方法进行未知二进制协议格式推断, 将预处理的协议数据进行层次聚类, 以CH(Calinski-Harabasz)系数为评价标准获得最优聚类, 通过对聚类所得结果进行改进的序列对比以获得带有间隔的协议数据序列, 统计合并连续间隔, 以分析协议格式。实验结果表明, 提出的二进制协议格式推断方法能够推断出未知二进制协议80%以上的字段间隔, 相较于AutoReEngine算法中的格式推断方法, 所提方法的F1-Measure值整体上提升了约30%。

基于聚类分析算法和优化支持向量机的无线网络流量预测

曹素娥, 杨泽民

计算机科学. 2020, 47 (8): 319-322. doi:10.11896/jsjkx.190800075

摘要 ( 323 )

PDF(1748KB) ( 864 )

参考文献 | 相关文章 | 多维度评价

为了解决当前无线网络流量预测过程存在的一些问题, 以提高无线网络流量的预测精度为目标, 提出基于聚类分析算法和优化支持向量机的无线网络流量预测模型。首先, 采集无线网络流量数据集, 并采用聚类分析算法构建训练样本集合;然后, 采用支持向量机对无线网络流量训练样本进行学习, 并引入布谷鸟搜索算法对支持向量参数进行优化, 从而建立无线网络流量预测模型;最后, 通过具体无线网络流量预测实例分析模型的有效性。结果表明, 所提模型的无线网络流量预测精度高, 提升了无线网络流量建模效率, 而且其无线网络流量预测效果要优于当前经典无线网络流量预测模型, 具有比较显著的优越性。

基于流形学习的多源传感器体域网数据融合模型

张俊, 王杨, 李坤豪, 李昌, 赵传信

计算机科学. 2020, 47 (8): 323-328. doi:10.11896/jsjkx.191000012

摘要 ( 398 )

PDF(2573KB) ( 827 )

参考文献 | 相关文章 | 多维度评价

无线体域网多传感器由于采集的数据量大、数据类型冗杂, 难以有效进行多维度数据的融合。虽然传统流形及分解类型的数据融合方法(Isomap, MDS, PCA等)具备使距离较小点产生合理排斥梯度的能力和受异常影响较小的优点, 但是针对无线多传感器体域网的数据降维效果并不理想。对此, 提出了一种基于流形学习的T分布式随机邻域嵌入(T-SNE)算法对多传感器体域网数据进行融合。T-SNE算法首先将高维数据点与其对应的低维数据点间的欧氏距离转换为条件概率矩阵, 然后对处理好的低维概率集合进行有限次迭代, 最后更新低维概率矩阵, 使距离较小点间产生合理的排斥梯度, 从而构建了多维度体域网数据融合模型。实验结果表明, 在特定的体域网数据集下, T-SNE算法的精度为Isomap的1.11倍, MDS的1.33倍, PCA的1.21倍, 具有较好的数据降维效果。