《计算机应用》唯一官方网站

左雨星, 郭爱煌, 黄博, 王露

2017, 37(12): 3345-3350. DOI: 10.11772/j.issn.1001-9081.2017.12.3345

摘要 ( )

PDF (1105KB) ( )

参考文献 | 相关文章 | 计量指标

针对车联网（IoV）中车流密度增加到一定程度时，即使无线信道中只有信标消息，信道拥塞也会发生的问题，提出一种分布式加权公平功率控制（D-WFPC）算法。首先，考虑车联网的实际信道特性，采用Nakagami-m衰落信道模型建立随机信道模型；然后，考虑车联网中节点的移动性，基于网络效用最大化（NUM）模型建立功率控制优化问题，控制本地信道负载在阈值之下，从而避免拥塞；最后，通过对偶分解和迭代法解决该问题，设计分布式算法，每辆车根据周围环境的邻居车辆的信标消息，动态调整发射功率。仿真实验中，与固定发射功率方案相比，随着车流密度增大，D-WFPC算法能有效降低时延和丢包率，最高降幅分别达到24%和44%；与公平分布式发射功率拥塞控制（FCCP）算法相比，D-WFPC算法全程性能占优，时延和丢包率的最高降幅分别达到10%和4%。仿真结果表明，D-WFPC算法能快速收敛，保证车联网中消息的低时延、高可靠传输。

基于软件定义网络的分层式控制器负载均衡机制

朱世珂, 束永安

2017, 37(12): 3351-3355. DOI: 10.11772/j.issn.1001-9081.2017.12.3351

摘要 ( )

PDF (1030KB) ( )

参考文献 | 相关文章 | 计量指标

针对软件定义网络（SDN）多控制器负载均衡过程中控制器之间通信开销大以及控制器吞吐量低等问题，提出一种分层式控制器负载均衡机制。基于分层式架构，通过超级控制器与域控制器协作完成负载均衡，并采用预定义负载阈值以减少域控制器与超级控制器之间的消息交换开销；同时，该机制可以有效选择出过载最重的域控制器，并从该过载域控制器所控制的交换机中选取多个符合迁移标准的交换机，将其同时分别迁移到多个综合性能高的域控制器上，从而解决多控制器间负载不均衡问题。实验结果表明，与层次式SDN控制器协同负载均衡方案（COLBAS）以及用于控制器负载均衡的动态和自适应算法（DALB）相比，所提机制系统的消息数量降低了约79个百分点，且该系统的吞吐量分别比DALB、COLBAS分别提高了约8.57%、52.01%。所提机制能够有效降低通信开销，并提高系统吞吐量，有更好的负载均衡效果。

基于图着色的大规模MIMO系统中动态导频分配

樊自甫, 胡敏, 李悦宁

2017, 37(12): 3356-3360. DOI: 10.11772/j.issn.1001-9081.2017.12.3356

摘要 ( )

PDF (785KB) ( )

参考文献 | 相关文章 | 计量指标

针对大规模多输入多输出（MIMO）系统中存在的导频污染问题，提出一种基于图着色的动态导频分配方案。为了更加合理地分配导频、减小导频污染，首先，利用小区间协作，将不同小区的用户通过带权值的边相连来构建边权值干扰图，以此来描述多小区用户间的导频污染程度；然后，在传统的图着色理论基础上，利用相连用户边权值不同的特点，优先为受导频污染严重的用户分配导频资源。理论分析和仿真结果表明，所提的导频分配方案不同于现有的分布式导频分配方案，在考虑所有小区导频复用的情况下，基于图着色集中式地分配导频，能够减小小区间用户的干扰，提升大规模MIMO系统的上行可达和速率。

基于非正交多址的认知MIMO网络次用户系统容量优化

廖晗, 马东亚, 尹礼欣

2017, 37(12): 3361-3367. DOI: 10.11772/j.issn.1001-9081.2017.12.3361

摘要 ( )

PDF (1016KB) ( )

参考文献 | 相关文章 | 计量指标

针对未来移动通信系统对大容量、高频谱利用率的需求，提出基于非正交多址（NOMA）技术的认知多输入多输出（MIMO）网络次用户系统容量优化方法。首先对发送信号进行预编码，随后按照信道质量增益对认知用户进行分簇，再对分簇之后的用户进行功率分配，最后将得到的NP-hard型多簇目标函数转化为求各子簇的容量；同时兼顾认知用户服务质量（QoS）及满足串行干扰消除（SIC）的条件，利用Lagrange函数结合Karush-Kuhn-Tucker （KKT）条件求解出分簇之后的最优功率分配系数，且该系数是0到1之间的常数。仿真结果表明，所提方法优于平均功率分配方法，并且在信道质量较差时，相比基于正交多址（OMA）技术的认知MIMO，显著提高了次用户系统容量。

密集小蜂窝网络中基于负载均衡的能效方案

韦世红, 张丽, 黄晓舸

2017, 37(12): 3368-3373. DOI: 10.11772/j.issn.1001-9081.2017.12.3368

摘要 ( )

PDF (1045KB) ( )

参考文献 | 相关文章 | 计量指标

针对密集小蜂窝网络中断概率高、负载不均衡的问题，提出了一种基于负载均衡的能效方案。在保证用户中断概率、最小速率等约束条件下通过联合优化负载均衡和基站开关模式，最大化网络能效，优化问题是一个非凸的NP-hard问题，求得最优解是相当复杂的，因此把原最优问题分解成两个次优化子问题：首先，负载均衡方案在给定的基站开关模式下给出最优负载均衡策略；其次，在满足用户最小速率约束条件下设计最优基站开关模式。实验结果表明，当用户数少于180时所提方案中断概率为零，而传统的最大信干噪比（Max-SINR）算法中断概率达到11%，在网络能效方面，所提方案均高于基站任意关闭（Ran-off）算法和基站不关闭（No-off）算法。所提方案能够提高网络能效且保证负载均衡。

基于最优簇数和改进引力搜索的WSN路由算法

李新春, 高佰胜

2017, 37(12): 3374-3380. DOI: 10.11772/j.issn.1001-9081.2017.12.3374

摘要 ( )

PDF (1066KB) ( )

参考文献 | 相关文章 | 计量指标

为了提高无线传感器网络（WSN）的能量利用效率，提出一种基于最优簇数和改进引力搜索的WSN路由算法（ONCIGS）。首先，根据非均匀分簇的思想计算最优簇数，并采用改进的凝聚嵌套（AGNES）算法实现网络的合理分簇；其次，将反向学习机制和精英策略思想引入到引力搜索算法中，并基于种群密度对作用力进行自适应调整，以提高搜索精度，加快收敛；然后，将簇头剩余能量的标准差作为目标函数，搜索能量均衡的簇间数据转发路径。实验结果表明，相比低功耗自适应集簇分层型（LEACH）路由算法和分布式能量均衡非均匀成簇（DEBUC）路由算法，ONCIGS在100 m×100 m网络规模下将网络生命周期分别延长41.94%和5.77%，在200 m×200 m网络规模下分别延长76.60%和7.82%。ONCIGS能够有效地延长网络寿命，提高能量效率。

基于观测矩阵优化的自适应压缩感知算法

胡强, 林云

2017, 37(12): 3381-3385. DOI: 10.11772/j.issn.1001-9081.2017.12.3381

摘要 ( )

PDF (780KB) ( )

参考文献 | 相关文章 | 计量指标

为提高传统压缩感知（CS）恢复算法的抗噪性能，结合观测矩阵优化和自适应观测的思想，提出一种自适应压缩感知（ACS）算法。该算法将观测能量全部分配在由传统CS恢复算法估计的支撑位置，由于估计支撑集中包含支撑位置，这样可有效提高观测信噪比（SNR）；再从优化观测矩阵的角度推导出最优的新观测向量，即其非零部分设计为Gram矩阵的特征向量。仿真结果表明，随着观测数增大，Gram矩阵非对角元素的能量增速小于传统CS算法，并且分别在观测次数、稀疏度和SNR相同的条件下，所提算法的重构归一化均方误差低于传统CS恢复算法10 dB以上，低于典型的贝叶斯方法5 dB以上。分析表明，所提自适应观测机制可有效提高传统CS恢复算法的能量利用效率和抗噪性能。

基于资源需求分布特征的异构云环境虚拟机放置算法

薛弘晔, 朱天磊, 罗香玉, 冯健

2017, 37(12): 3386-3390. DOI: 10.11772/j.issn.1001-9081.2017.12.3386

摘要 ( )

PDF (760KB) ( )

参考文献 | 相关文章 | 计量指标

针对异构云环境中的虚拟机放置（VMP）问题，提出一种基于虚拟机资源需求分布特征的放置算法（RDDFPA）。首先，建立基于CPU资源和内存资源比例系数的虚拟机需求和物理机配置描述方法，并根据该比例系数对所有虚拟机进行排序；其次，通过分析虚拟机需求与物理机配置各自在CPU资源和内存资源比例方面的关系，确定比例分界点，完成虚拟机集合的划分，每个虚拟机子集合的规模反映出对相匹配的不同配置物理机的需求比例；最后，利用启发式算法如首次适应（First Fit）算法完成虚拟机子集合在相匹配配置的物理机子集合上的放置。理论分析和仿真实验结果表明，与采用任意单一配置的物理机总数量相比，所提算法所需物理机的总台数减少了2%~17%。RDDFPA能够根据虚拟机资源需求分布的不同，确定各类配置物理机的数量，高效完成虚拟机的放置，在提高资源利用率的同时，降低了系统能耗。

多粒度粗糙集粒度约简的高效算法

胡善忠, 徐怡, 何明慧, 王冉

2017, 37(12): 3391-3396. DOI: 10.11772/j.issn.1001-9081.2017.12.3391

摘要 ( )

PDF (888KB) ( )

参考文献 | 相关文章 | 计量指标

针对已有多粒度粗糙集粒度约简算法效率较低的问题，提出一种多粒度粗糙集粒度约简的高效算法（EAGRMRS）。首先，以决策信息系统为对象，定义决策类下近似布尔矩阵，该矩阵能够将粒度约简过程中过多且有重复的集合运算转换为布尔运算，基于该矩阵给出计算决策类下近似算法和计算粒度重要度算法。然后，针对计算粒度重要度时存在冗余计算的问题，提出粒度动态增加时快速计算粒度重要度的算法，并在此基础上，提出EAGRMRS，该算法的时间复杂度为O（|A|·|U|²+|A|²·|U|），其中|A|表示粒度集合大小，|U|表示决策信息系统中实例数。在UCI数据集上的实验结果验证了所提算法的有效性和高效性，并且随着数据集的增大，EAGRMRS相较于多粒度粗糙集粒度约简的启发式算法（HAGSS）效率优势更加明显。

三角形的并行枚举算法

王卓, 索勃, 潘巍

2017, 37(12): 3397-3400. DOI: 10.11772/j.issn.1001-9081.2017.12.3397

摘要 ( )

PDF (613KB) ( )

参考文献 | 相关文章 | 计量指标

经典GT算法是三角形并行枚举算法的MapReduce实现，然而该算法只能枚举全图的三角形结构，对部分顶点构成的三角形结构无法直接进行枚举。针对此问题，提出一种直接枚举部分顶点构成三角形结构的并行算法。首先，通过分析被选点的分布，给出被选点构成三角形的所有组合集合；然后，通过对该集合的筛选，实现对部分点构成三角形结构的直接枚举；最后，将该算法在Spark系统实现，以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验，实验结果表明，所提改进算法的运行时间只有GT算法运行时间的1/3，在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。

改进的Spark Shuffle内存分配算法

侯伟凡, 樊玮, 张宇翔

2017, 37(12): 3401-3405. DOI: 10.11772/j.issn.1001-9081.2017.12.3401

摘要 ( )

PDF (909KB) ( )

参考文献 | 相关文章 | 计量指标

Shuffle性能是影响大数据集群性能的重要指标，Spark自身的Shuffle内存分配算法试图为内存池中的每一个Task平均分配内存，但是在实验中发现，由于各Task对于内存需求的不均衡导致了内存的浪费和运行效率较低的问题。针对上述问题，提出一种改进的Spark Shuffle内存分配算法。该算法根据Task的内存申请量和历史运行数据将Task按内存需求分为大小两类，对小内存需求型Task作"分割化"处理，对大内存需求型Task基于Task溢出次数和溢出后等待时间分配内存。该算法充分利用内存池的空闲内存，可以在数据倾斜导致的Task内存需求不均衡的情况下进行Task内存分配的自适应调节。实验结果表明，改进后算法较原算法降低了Task的溢出率，减少了Task的周转时间，提高了集群的运行性能。

蜜罐加密技术在私密数据保护中的应用

银伟, 周红建, 邢国强

2017, 37(12): 3406-3411. DOI: 10.11772/j.issn.1001-9081.2017.12.3406

摘要 ( )

PDF (1022KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统加密技术脆弱性问题，将蜜罐加密技术应用到身份证号码、手机号码和银行卡密码的保护中以保证数据存储安全。首先，分析阐述了蜜罐加密技术原理，并设计了对蜜罐加密系统分布式转换加密器；然后，抽象了消息空间，对系统进行实现和性能评估，发现性能开销问题并提出增强型机制。在蜜罐加密设计与实现中，考虑到均衡分布和随机分布的消息空间，并将其运用到对称加密算法和公钥加密机制。通过所提设计、系统实现和实验结果得出以下结论：1）由于性能问题，蜜罐加密技术更适合小的消息空间；2）设计消息空间时需要考虑周全，不能带来指纹特征，否则不能解决暴力破解脆弱性问题；3）蜜罐加密的保护能力随应用的不同而不同；4）对于不同的应用，蜜罐加密技术的实现需要定制。

基于混沌序列的双重加密安全网络编码方案设计

徐光宪, 赵越, 公忠盛

2017, 37(12): 3412-3416. DOI: 10.11772/j.issn.1001-9081.2017.12.3412

摘要 ( )

PDF (878KB) ( )

参考文献 | 相关文章 | 计量指标

针对当前对抗全局窃听的网络编码方案计算量大、占用带宽大、安全性不高等问题，提出一种基于混沌序列的双重加密方案。首先，利用密钥对传输数据的最后一维进行加密，加密时用数据本身扰动混沌序列；然后，用另一密钥和随机数密钥生成编码系数矩阵，此时用m序列对混沌序列进行扰动；最后，用得到的编码系数矩阵对未加密消息和加密消息进行线性组合，实现对抗全局窃听。由于编码系数矩阵是由密钥生成的，不需要在信道中传输编码系数，相对于实体网络编码（SPOC）方案，所提方案节省了网络中对编码系数传输的带宽开销。分析和实验结果表明，该方案提高了网络的安全性能，对唯密文攻击和已知明文攻击都能起到作用，并且提高了传输效率，算法复杂度适中。

支持用户追溯和轻量的共享云数据审计方案

金瑜, 蔡超, 何亨

2017, 37(12): 3417-3422. DOI: 10.11772/j.issn.1001-9081.2017.12.3417

摘要 ( )

PDF (996KB) ( )

参考文献 | 相关文章 | 计量指标

在云计算中，数据通常由一组用户共享。由于第三方审计可以通过数据块的签名获取组成员的身份，为了保护群组成员的身份，现有对共享数据的公共审计方案都隐藏了组成员的身份。然而，身份的匿名性将导致一个组的成员可以恶意修改共享数据而不被发现，而且对于资源受限的设备，用户在产生签名的过程中计算量大。因此现有公共审计方案存在数据块身份的不可追溯、用户产生共享数据块签名的计算量大等问题。针对上述问题，提出了一种支持用户追溯和轻量的共享云数据审计方案（ASDA）。该方案利用安全中介者代替用户签名，保护了群组成员的身份，在签名的同时保存用户的信息，通过这些信息，可以追溯到数据块是由哪一个组成员修改，从而保证数据块身份可追溯性；而且利用新的数据块致盲技术，减少用户端计算量。实验结果表明，所提方案与利用第三方媒介存储共享云数据（SDVS）方案相比，减少了用户端计算时间，并且能够实现共享数据块身份的可追溯性。

支持带权属性撤销的密文策略属性基加密方案

王经纬, 殷新春

2017, 37(12): 3423-3429. DOI: 10.11772/j.issn.1001-9081.2017.12.3423

摘要 ( )

PDF (1079KB) ( )

参考文献 | 相关文章 | 计量指标

针对目前大部分密文策略属性基加密（CP-ABE）方案都不支持属性的多状态表示，加密、解密阶段计算开销庞大的问题，提出一种支持带权属性撤销的CP-ABE方案（CPABEWAR）。一方面，通过引入带权属性的概念，增强了属性的表达能力；另一方面，为了降低计算开销，在保证数据安全的情况下将部分计算过程外包给云服务提供商（CSP）。分析结果表明，所提方案基于判定双线性DH （DBDH）假设是选择明文安全的（CPS）。所提方案以增加少量存储空间为代价简化了访问树结构，提高了系统效率和访问控制的灵活性，适合计算能力受限的云用户。

无高斯噪声的全同态加密方案

李明祥, 刘照, 张明艳

2017, 37(12): 3430-3434. DOI: 10.11772/j.issn.1001-9081.2017.12.3430

摘要 ( )

PDF (747KB) ( )

参考文献 | 相关文章 | 计量指标

基于带舍入学习（LWR）问题，一个分级全同态加密方案最近被提出。LWR问题是带误差学习（LWE）问题的变型，但它省掉了代价高昂的高斯噪声抽样，因此与现有基于LWE问题的全同态加密方案相比，该基于LWR问题的全同态加密方案具有更高的计算效率。然而，该基于LWR问题的全同态加密方案在同态运算时需要输入用户的运算密钥。因此，基于LWR问题构造了一个新的分级全同态加密方案，该方案在同态运算时不需要输入用户的运算密钥。鉴于所提方案可应用于构造基于身份的全同态加密方案、基于属性的全同态加密方案等，它具有比最近所提出的基于LWR问题的全同态加密方案更广泛的应用场景。

基于带权超图的跨网络用户身份识别方法

徐乾, 陈鸿昶, 吴铮, 黄瑞阳

2017, 37(12): 3435-3441. DOI: 10.11772/j.issn.1001-9081.2017.12.3435

摘要 ( )

PDF (1259KB) ( )

参考文献 | 相关文章 | 计量指标

随着各种社交网络的不断涌现，越来越多的研究者开始从多源的角度分析社交网络数据，多社交网络的数据融合依赖于跨网络用户身份识别。针对现有的基于好友关系（FRUI）算法对社交网络中的异质关系利用率不高的问题，提出了基于带权超图的跨网络用户身份识别（WHUI）算法。首先，通过在好友关系网络上构建带权超图来准确地描述同一网络中的好友关系及异质关系，以此提高表示节点所处拓扑环境的准确性；然后，在构建好的带权超图的基础上，根据节点所处拓扑环境在不同网络中大致相同这一特性，定义节点之间的跨网络相似性；最后，结合迭代匹配算法，每次选取跨网络相似性最高的用户对进行匹配，并加入双向认证和结果剪枝来保证识别准确率。在合作网络DBLP和真实社交网络上进行了实验，实验结果表明，在真实社交网络上，所提算法相比FRUI算法，平均准确率提高了5.5个百分点，平均召回率提高了3.4个百分点，平均F值提高了4.6个百分点。在只有网络拓扑信息的情况下，所提WHUI算法有效提高了实际应用中身份识别的准确率和召回率。

基于Linux名字空间的Web服务器动态防御方法

陈刚, 郭玉东, 魏小锋

2017, 37(12): 3442-3446. DOI: 10.11772/j.issn.1001-9081.2017.12.3442

摘要 ( )

PDF (811KB) ( )

参考文献 | 相关文章 | 计量指标

Web服务器广泛部署在以Docker容器为代表的云计算平台上，面临着严峻的安全挑战。为了提高此类Web服务器的安全防御能力，提出一种基于Linux名字空间的Web服务器动态防御方法。该方法能够保证在Web服务正常工作的前提下，首先使用名字空间构建Web服务器运行环境；其次，通过多环境的交替运行来实现Web服务器的动态变换以迷惑入侵者，增加入侵者对Web服务器的攻击难度；最后，通过定期主动清除并重建Web服务器的运行环境来消除入侵行为对Web服务器的影响，最终实现有效提高Web服务器的动态防御能力。实验结果表明，所提方法能够有效增强Web服务器的安全性，同时对系统性能影响很小，请求响应100 KB数据的时间损耗为0.02~0.07 ms。

基于尺度不变特征变换的快速图像拷贝检测

郑丽君, 李新伟, 卜旭辉

2017, 37(12): 3447-3451. DOI: 10.11772/j.issn.1001-9081.2017.12.3447

摘要 ( )

PDF (946KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统基于尺度不变特征变换（SIFT）特征的图像拷贝检测算法特征提取速度慢、匹配效率不高的问题，提出了一种基于SIFT特征点位置分布与方向分布特征的快速图像拷贝检测算法。首先，提取SIFT特征点二维位置信息，通过计算各个特征点与图像中心点的距离、角度，分块统计各区间的特征点数量，依据数量关系量化生成二值哈希序列，构成一级鲁棒特征；然后，根据特征点一维方向分布特征分块统计各方向子区间特征点数量，依据数量关系构成二级图像特征；最后，拷贝检测时采用级联式过滤框架作出是否为拷贝的判断。仿真实验结果表明，与传统SIFT以128维特征描述子为基础构建哈希序列的图像拷贝检测算法相比，所提算法在保证鲁棒性与独特性不降低的同时，特征提取时间缩短为原来的1/20，匹配时间也缩短了1/2以上，可满足在线拷贝检测的需求。

基于噪声一致性的数字语音异源拼接篡改检测算法

阳帆, 严迪群, 徐宏伟, 王让定, 金超, 向立

2017, 37(12): 3452-3457. DOI: 10.11772/j.issn.1001-9081.2017.12.3452

摘要 ( )

PDF (908KB) ( )

参考文献 | 相关文章 | 计量指标

异源拼接是一种常见的数字语音篡改行为，其主要借助音频编辑软件将不同场景中录制的语音片段拼接在一起，以达到改变语音语义的目的。考虑到不同场景中所包含的背景噪声特性往往存在差异，提出了一种基于噪声一致性的数字语音异源拼接篡改检测算法。首先，采用时间递归平均（TRA）算法提取待检测语音中所含噪声；然后，通过突变点检测（CPD）算法检测噪声方差是否存在突变来判定待检测语音是否经过篡改，并对篡改位置作出定位。实验仿真结果表明，所提算法能对数字语音中的异源篡改位置进行有效检测。

面向RGB-D场景解析的三维空间结构化编码深度网络

王泽宇, 吴艳霞, 张国印, 布树辉

2017, 37(12): 3458-3466. DOI: 10.11772/j.issn.1001-9081.2017.12.3458

摘要 ( )

PDF (11074KB) ( )

参考文献 | 相关文章 | 计量指标

有效的RGB-D图像特征提取和准确的3D空间结构化学习是提升RGB-D场景解析结果的关键。目前，全卷积神经网络（FCNN）具有强大的特征提取能力，但是，该网络无法充分地学习3D空间结构化信息。为此，提出了一种新颖的三维空间结构化编码深度网络，内嵌的结构化学习层有机地结合了图模型网络和空间结构化编码算法。该算法能够比较准确地学习和描述物体所处3D空间的物体分布。通过该深度网络，不仅能够提取包含多层形状和深度信息的分层视觉特征（HVF）和分层深度特征（HDF），而且可以生成包含3D结构化信息的空间关系特征，进而得到融合上述3类特征的混合特征，从而能够更准确地表达RGB-D图像的语义信息。实验结果表明，在NYUDv2和SUNRGBD标准RGB-D数据集上，该深度网络较现有先进的场景解析方法能够显著提升RGB-D场景解析的结果。

基于随机矩阵理论的高维数据特征选择方法

王妍, 杨钧, 孙凌峰, 李玉诺, 宋宝燕

2017, 37(12): 3467-3471. DOI: 10.11772/j.issn.1001-9081.2017.12.3467

摘要 ( )

PDF (734KB) ( )

参考文献 | 相关文章 | 计量指标

传统特征选择方法多是通过相关度量来去除冗余特征，并没有考虑到高维相关矩阵中会存在大量的噪声，严重地影响特征选择结果。为解决此问题，提出基于随机矩阵理论（RMT）的特征选择方法。首先，将相关矩阵中符合随机矩阵预测的奇异值去除，从而得到去噪后的相关矩阵和选择特征的数量；然后，对去噪后的相关矩阵进行奇异值分解，通过分解矩阵获得特征与类的相关性；最后，根据特征与类的相关性和特征之间冗余性完成特征选择。此外，还提出一种特征选择优化方法，通过依次将每一个特征设为随机变量，比较其奇异值向量与原始奇异值向量的差异来进一步优化结果。分类实验结果表明所提方法能够有效提高分类准确率，减小训练数据规模。

基于边界矩阵低阶近似和近邻模型的协同过滤算法

温占考, 易秀双, 田申申, 李婕, 王兴伟

2017, 37(12): 3472-3476. DOI: 10.11772/j.issn.1001-9081.2017.12.3472

摘要 ( )

PDF (945KB) ( )

参考文献 | 相关文章 | 计量指标

为解决矩阵分解应用到协同过滤算法的局限性和准确率等问题，提出基于边界矩阵低阶近似（BMA）和近邻模型的协同过滤算法（BMAN-CF）来提高物品评分预测的准确率。首先，引入BMA的矩阵分解算法，挖掘子矩阵的隐含特征信息，提高近邻集合查找的准确率；然后，根据传统基于用户和基于物品的协同过滤算法分别预测出目标用户对目标物品的评分，利用平衡因子和控制因子动态平衡两个预测结果，得到目标用户对物品的评分；最后，利用MapReduce计算框架的特点，对数据进行分块，将该算法在Hadoop环境下并行化。实验结果表明，BMAN-CF比其他矩阵分解算法有更高的评分预测准确率，且加速比实验验证了该算法具有较好的可扩展性。

面向不等长多维时间序列的聚类改进算法

霍纬纲, 程震, 程文莉

2017, 37(12): 3477-3481. DOI: 10.11772/j.issn.1001-9081.2017.12.3477

摘要 ( )

PDF (840KB) ( )

参考文献 | 相关文章 | 计量指标

针对已有基于模型的多维时间序列（MTS）聚类算法处理不等长MTS速度较慢的问题，提出了一种基于LR分量提取的MTS聚类算法（MUTSCA〈LRCE〉）。首先，采用等频离散化方法符号化MTS；然后，计算用于表达MTS样本各维时间序列之间时序模式的LR向量，对每个LR向量进行排序后从其两端提取固定数目的不同关键分量，所有提取的关键分量拼接形成表示MTS样本的模型向量，该过程将不等长MTS样本集转换为等长的模型向量集；最后，采用k-means算法对生成的等长模型向量集进行聚类分析。在多个公共数据集上的实验结果表明，与基于模型的MTS聚类算法——MUTSCA〈LR〉相比，所提算法能够在保证聚类效果的前提下，显著提高不等长MTS数据集的聚类速度。

快速识别密度骨架的聚类算法

邱保志, 唐雅敏

2017, 37(12): 3482-3486. DOI: 10.11772/j.issn.1001-9081.2017.12.3482

摘要 ( )

PDF (810KB) ( )

参考文献 | 相关文章 | 计量指标

针对如何快速寻找密度骨架、提高高维数据聚类准确性的问题，提出一种快速识别高密度骨架的聚类（ECLUB）算法。首先，在定义了对象局部密度的基础上，根据互k近邻一致性及近邻点局部密度关系，快速识别出高密度骨架；然后，对未分配的低密度点依据邻近关系进行划分，得到最终聚类。人工合成数据集及真实数据集上的实验验证了所提算法的有效性，在Olivetti Face数据集上的聚类结果显示，ECLUB算法的调整兰德系数（ARI）和归一化互信息（NMI）分别为0.8779和0.9622。与经典的基于密度的聚类算法（DBSCAN）、密度中心聚类算法（CFDP）以及密度骨架聚类算法（CLUB）相比，所提ECLUB算法效率更高，且对于高维数据聚类准确率更高。

基于动态奖惩的分支策略的SAT完备算法

刘燕丽, 徐振兴, 熊丹

2017, 37(12): 3487-3492. DOI: 10.11772/j.issn.1001-9081.2017.12.3487

摘要 ( )

PDF (911KB) ( )

参考文献 | 相关文章 | 计量指标

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题，提出了基于动态奖惩的分支策略。首先，对每次单子句传播的变元进行惩罚，依据变元是否产生冲突和产生冲突的间隔，确立不同的惩罚函数；其次，在学习阶段，利用学习子句确定对构造冲突有益的变元，非线性增加它们的活跃度；最后，选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上，完成了改进的动态奖惩算法——AP7。实验结果表明，相比glucose3.0算法，AP7算法的剪枝率提高了14.2%~29.3%，少数算例剪枝率的提高可达51%，且改进后的AP7算法相比glucose3.0算法，运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模，使搜索树更加平衡，减少计算时间。

采用动态权重和概率扰动策略改进的灰狼优化算法

陈闯, Ryad Chellali, 邢尹

2017, 37(12): 3493-3497. DOI: 10.11772/j.issn.1001-9081.2017.12.3493

摘要 ( )

PDF (769KB) ( )

参考文献 | 相关文章 | 计量指标

针对基本灰狼优化（GWO）算法存在易陷入局部最优，进而导致搜索精度偏低的问题，提出了一种改进的GWO （IGWO）算法。一方面，通过引入由GWO算法系数向量构成的权值因子，动态调整算法的位置向量更新方程；另一方面，通过采用概率扰动策略，增强算法迭代后期的种群多样性，从而提升算法跳出局部最优的能力。对多个基准测试函数进行仿真实验，实验结果表明，相对于GWO算法、混合GWO （HGWO）算法、引力搜索算法（GSA）和差分进化（DE）算法，所提IGWO算法有效摆脱了局部收敛，在搜索精度、算法稳定性以及收敛速度上具有明显优势。

结合语义扩展和卷积神经网络的中文短文本分类方法

卢玲, 杨武, 杨有俊, 陈梦晗

2017, 37(12): 3498-3503. DOI: 10.11772/j.issn.1001-9081.2017.12.3498

摘要 ( )

PDF (928KB) ( )

参考文献 | 相关文章 | 计量指标

中文新闻标题通常包含一个或几十个词，由于字符数少、特征稀疏，在分类问题中难以提升正确率。为解决此问题，提出了基于Word Embedding的文本语义扩展方法。首先，将新闻标题扩展为（标题、副标题、主题词）构成的三元组，用标题的同义词结合词性过滤方法构造副标题，对多尺度滑动窗口内的词进行语义组合，提取主题词；然后，针对扩展文本构造卷积神经网络（CNN）分类模型，该模型通过max pooling及随机dropout进行特征过滤及防止过拟合；最后，将标题、副标题拼接为双词表示，与多主题词集分别作为模型的输入。在2017自然语言处理与中文计算评测（NLP&CC2017）的新闻标题分类数据集上进行实验。实验结果表明，用三元组扩展结合相应的CNN模型在18个类别新闻标题上分类的正确率为79.42%，比未经扩展的CNN模型提高了9.5%，且主题词扩展加快了模型的收敛速度，验证了三元组扩展方法及所构建CNN分类模型的有效性。

卷积神经网络诊断阿尔兹海默症的方法

林伟铭, 高钦泉, 杜民

2017, 37(12): 3504-3508. DOI: 10.11772/j.issn.1001-9081.2017.12.3504

摘要 ( )

PDF (844KB) ( )

参考文献 | 相关文章 | 计量指标

针对阿尔兹海默症（AD）通常会导致海马体区域萎缩的现象，提出一种使用卷积神经网络（CNN）对脑部磁共振成像（MRI）的海马体区域进行AD识别的方法。测试数据来自ADNI数据库提供的188位患者和229位正常人的脑部MRI图像。首先，将所有脑图像进行颅骨剥离，并配准到标准模板；其次，使用线性回归进行脑部萎缩的年龄矫正；然后，经过预处理后，从每个对象的3D脑图像的海马体区域提取出多幅2.5D的图像；最后，使用CNN对这些图像进行训练和识别，将同一个对象的图像识别结果用于对该对象的联合诊断。通过多次十折交叉验证方式进行实验，实验结果表明所提方法的平均识别准确率达到88.02%。与堆叠自动编码器（SAE）方法进行比较，比较结果表明，所提方法在仅使用MRI进行诊断的情况下效果比SAE方法有较大提高。

基于图像的面部表情识别方法综述

徐琳琳, 张树美, 赵俊莉

2017, 37(12): 3509-3516. DOI: 10.11772/j.issn.1001-9081.2017.12.3509

摘要 ( )

PDF (1504KB) ( )

参考文献 | 相关文章 | 计量指标

近年来，面部表情识别在教育、医学、心理分析以及商业领域得到了广泛关注。针对目前表情识别方法不够系统、概念模糊的问题，对面部表情识别的步骤及其方法进行了综述探讨。首先，介绍了目前常用的人脸表情数据集，并回顾了面部表情识别的发展历程；然后，介绍了人脸表情识别的面部表情编码和面部表情识别过程这两个方面，归纳了人脸面部表情识别的四个过程，重点总结了特征提取和表情分类两个过程中的经典算法以及这些算法的基本原理和优劣比较；最后，指出了目前面部表情识别存在的问题和未来可能的发展趋势。

基于多尺度特征融合Hessian稀疏编码的图像分类算法

刘盛清, 孙季丰, 余家林, 宋治国

2017, 37(12): 3517-3522. DOI: 10.11772/j.issn.1001-9081.2017.12.3517

摘要 ( )

PDF (1033KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统稀疏编码图像分类算法提取单一类型特征，忽略图像的空间结构信息，特征编码时无法充分利用特征拓扑结构信息的问题，提出了基于多尺度特征融合Hessian稀疏编码的图像分类算法（HSC）。首先，对图像进行空间金字塔多尺度划分；其次，在各个子空间层将方向梯度直方图（HOG）和尺度不变特征转换（SIFT）进行有效的融合；然后，为了充分利用特征的拓扑结构信息，在传统稀疏编码目标函数中引入二阶Hessian能量函数作为正则项；最后，利用支持向量机（SVM）进行分类。在Scene15数据集上的实验结果表明，HSC的准确率比局部约束线性编码（LLC）高了3~5个百分点，比支持区别性字典学习（SDDL）等对比方法高了1~3个百分点；在Caltech101数据集上的耗时实验结果表明，HSC的用时比多核学习稀疏编码（MKLSC）少40%左右。所提HSC可以有效提高图像分类准确率，算法的效率也优于对比算法。

基于Snake模型的图像分割新算法

胡学刚, 邱秀兰

2017, 37(12): 3523-3527. DOI: 10.11772/j.issn.1001-9081.2017.12.3523

摘要 ( )

PDF (894KB) ( )

参考文献 | 相关文章 | 计量指标

针对目前基于Snake模型的图像分割算法普遍存在噪声鲁棒性差、适用范围受限、易发生弱边缘泄露以及轮廓曲线难以收敛到细小深凹边界的缺陷，提出了一种基于Snake模型的图像分割新算法。首先，选取新的扩散项代替具有各向同性光滑作用的拉普拉斯算子；其次，引入p-拉普拉斯泛函到平滑能量项中强化法线方向外力；最后，利用边缘保护项使外力场方向与边缘方向一致，以防止弱边缘泄漏并促使轮廓线收敛到细小深凹边界。实验结果表明，所提模型不仅克服了现有基于Snake模型的图像分割算法的缺陷，具有更好的分割效果，明显提高了抗噪性能和角点定位精度，而且耗时更少，适用于噪声图像、医学图像以及含有很多弱边缘的自然图像分割。

群智能算法优化的结合熵的最大类间方差法与脉冲耦合神经网络融合的图像分割算法

程述立, 汪烈军, 秦继伟, 杜安钰

2017, 37(12): 3528-3535. DOI: 10.11772/j.issn.1001-9081.2017.12.3528

摘要 ( )

PDF (1350KB) ( )

参考文献 | 相关文章 | 计量指标

针对最大类间方差准则下的图像分割结果携带原图信息量不足、实时性差和脉冲耦合神经网络（PCNN）模型中循环迭代次数难以确定的问题，提出了群智能算法优化的结合熵的最大类间方差法（OTSU-H）与PCNN融合的自动图像分割算法。首先，充分利用图像的灰度分布信息和相关信息，将图像信息中冗余度、竞争性以及互补性有效地融合，构造二维和三维观测空间，提出了OTSU-H准则的快速递归算法；其次，将快速递推算法的目标函数分别作为布谷鸟搜索（CS）算法、萤火虫算法（FA）、粒子群优化（PSO）算法和遗传算法（GA）四种群智能算法的适应度函数；最后，将优化之后的OTSU-H引入PCNN模型中自动获取循环迭代次数。实验结果表明，与原始的最大类间方差法（OTSU）、最大熵准则以及基于图论分割、像素的聚类分割和候选区域语义分割的图像分割算法相比，所提算法具有较好的图像分割效果，同时降低了计算复杂度，节约了计算机的存储空间，具有较强的抗噪能力。所提算法时间损耗少、不需要训练的特性使得算法的运用范围较广。

基于贝塞尔滤波改进的测地活动轮廓图像分割模型

刘国奇, 李晨静

2017, 37(12): 3536-3540. DOI: 10.11772/j.issn.1001-9081.2017.12.3536

摘要 ( )

PDF (982KB) ( )

参考文献 | 相关文章 | 计量指标

活动轮廓模型广泛应用于图像分割和目标轮廓提取，基于边缘的测地活动轮廓（GAC）模型在提取边缘明显的物体时得到广泛的应用，但GAC演化过程中，迭代次数较多，耗时较长。针对这一问题，结合贝塞尔滤波理论，对GAC模型改进。首先，利用贝塞尔滤波对图像进行平滑处理，降低噪声；其次，基于贝塞尔滤波的边缘检测函数，构建新的边缘停止项，且并入到GAC模型中；最后，在构造的模型中同时加入反应扩散（RD）项以避免水平集重新初始化。实验结果表明，与多个基于边缘的模型相比，所提模型在保证分割结果精确度的同时，提高了时间效率，更适用于实际应用。

划分特征子区域的图像修复算法

李梦雪, 翟东海, 孟红月, 曹大命

2017, 37(12): 3541-3546. DOI: 10.11772/j.issn.1001-9081.2017.12.3541

摘要 ( )

PDF (991KB) ( )

参考文献 | 相关文章 | 计量指标

为了解决含有丰富纹理信息和复杂结构信息的大破损区域中的缺失信息修复的问题，提出了一种划分特征子区域的图像修复算法。首先，根据图像中包含的不同特征，运用特征公式进行特征提取，再通过统计特征值划分特征子区域，提高了图像修复的速度；其次，在原Criminisi算法的基础上改进了优先级的计算，通过增大结构项的影响，避免结构断裂的产生；然后，通过目标块和其最佳邻域相似块共同约束样本块的选取，确定最佳样本块集；最后，利用权值分配法合成最佳样本块。实验结果表明，所提算法相比原Criminisi算法，其峰值信噪比（PSNR）提升了2~3 dB，相比基于稀疏表示的块优先权值计算的算法，其修复效率有明显的提高。所提算法不但适用于一般小尺度的破损图像的修复，而且对于含有丰富纹理信息和复杂结构信息的大破损图像的修复效果也更佳，并且修复后的图像更加符合人们视觉上的连通性。

基于中心环绕滤波器检测的图像特征点匹配算法

孙增友, 段玉帅, 李亚

2017, 37(12): 3547-3553. DOI: 10.11772/j.issn.1001-9081.2017.12.3547

摘要 ( )

PDF (1171KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统图像匹配算法特征点检测稳定性和准确性差的问题，提出一种尺度不变性的基于中心环绕滤波器检测（SCFD）的图像特征点匹配算法。首先，构建多尺度空间，利用中心环绕滤波器检测图像在不同尺度下的特征点，采用Harris方法和亚像素插值获得稳定的特征点；其次，联合快速定向旋转二进制稳健基元独立特征（BRIEF）（ORB）算法确定特征点的主方向，构建特征点描述算子；最后，采用汉明距离完成匹配，通过最小平方中值（LMedS）定理和最大似然（ML）估计剔除误匹配点。实验结果表明，在尺度变化时，所提算法的匹配精度达到96.6%，是ORB算法的2倍；其运行时间是尺度不变特征变换（SIFT）的19.8%，加速鲁棒性特征（SURF）的28.3%。所提算法能够有效提高特征点检测的稳定性和准确性，在视角、尺度缩放、旋转、亮度等变化的情况下具有较好的匹配效果。

基于连接突触计算网络的医学图像融合算法

高媛, 贾紫婷, 秦品乐, 王丽芳

2017, 37(12): 3554-3557. DOI: 10.11772/j.issn.1001-9081.2017.12.3554

摘要 ( )

PDF (871KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统的脉冲耦合神经网络（PCNN）融合方法中参数过多，以及参数和网络迭代次数难以准确设置、融合效果差等缺点，提出了一种用连接突触计算网络（LSCN）模型的连接项（L项）进行图像融合的算法。首先，把两幅待融合图像分别输入到LSCN模型中；其次，使用L项代替传统PCNN中的点火频率作为输出；然后，使用多通工作方式终止迭代；最后，通过比较L项的值得到融合后图像的像素。理论分析与实验结果表明，与改进的PCNN模型和在PCNN模型的基础上提出的新模型进行图像融合的算法进行比较，所提算法得到的融合图像更有利于人眼观察；特别是与点火频率作为输出的LSCN方法相比，所提算法在边缘信息评价因子、信息熵、标准差、空间频率、平均梯度上均较优。该算法简单易行，不仅减少了待定参数数目，降低了计算复杂度，而且解决了传统模型中迭代次数难以确定的问题。

球面凸类图形Delaunay三角剖分再分算法及其收敛性分析

夏俊, 李映华

2017, 37(12): 3558-3562. DOI: 10.11772/j.issn.1001-9081.2017.12.3558

摘要 ( )

PDF (738KB) ( )

参考文献 | 相关文章 | 计量指标

在计算曲面Ricci Flow时，会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题，提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先，给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个：1）如果某条Delaunay劣弧被"侵占"，通过添加Delaunay劣弧中点分割Delaunay劣弧；2）如果存在"瘦"球面三角形，通过添加球面三角形外接球面小圆圆心分解球面三角形。然后，利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证，所提算法网格生成的球面三角形没有狭小的角，适合用来计算Ricci Flow。

马尔可夫随机场的空间相关模型在非负矩阵分解线性解混中的应用

袁博

2017, 37(12): 3563-3568. DOI: 10.11772/j.issn.1001-9081.2017.12.3563

摘要 ( )

PDF (1038KB) ( )

参考文献 | 相关文章 | 计量指标

针对基于非负矩阵分解（NMF）的高光谱解混存在的初始化与"局部极小"等问题，提出一种基于马尔可夫随机场（MRF）的空间相关约束NMF线性解混算法（MRF-NMF）。首先，通过基于最小误差的高光谱信号识别（HySime）法估算端元数量，同时利用顶点成分分析（VCA）和全约束最小二乘法（FCLS）初始化端元矩阵与丰度矩阵；其次，利用MRF模型建立描述地物空间分布规律的能量函数，以此描述地物分布的空间相关特征；最后，将基于MRF的空间相关约束函数与NMF标准目标函数以交替迭代的形式参与解混，得出高光谱数据的端元信息与丰度分解结果。理论分析和真实数据实验结果表明，在高光谱数据空间相关程度较低的情况下，相比最小体积约束的NMF （MVC-NMF）、分段平滑和稀疏约束的NMF （PSNMFSC）和交互投影子梯度非负矩阵分解（APS-NMF）三种参考算法，所提算法的端元分解精度仍分别提高了7.82%、12.4%和10.1%，其丰度分解精度仍分别提高了8.34%、12.6%和9.87%。MRF-NMF能够弥补NMF对于空间相关特征描述能力的不足，减小解混结果中地物的空间能量分布误差。

移动应用众包测试人员评价模型

刘莹, 张涛, 李坤, 李楠

2017, 37(12): 3569-3573. DOI: 10.11772/j.issn.1001-9081.2017.12.3569

摘要 ( )

PDF (937KB) ( )

参考文献 | 相关文章 | 计量指标

移动应用众包测试人员具有匿名、非契约的特性，这使得任务发布者难以准确评估众包测试人员的能力与测试质量。针对该问题，提出了一种移动应用众包测试人员层次分析法（AHP）评价模型。该模型从活跃度、测试能力、诚信度等多指标分层综合评估众包测试人员能力，通过构造判断矩阵、一致性检验计算各层次指标的组合权重向量，并引入需求列表与描述列表改进本模型，使测试人员与众包任务更加匹配。实验结果表明，所提模型能够实现对测试人员能力的准确评估，支持基于评估结果的众包测试人员选择与推荐，提高了移动应用众包测试效率与质量。

基于状态转换的PLC程序模型构建方法

常天佑, 魏强, 耿洋洋

2017, 37(12): 3574-3580. DOI: 10.11772/j.issn.1001-9081.2017.12.3574

摘要 ( )

PDF (1124KB) ( )

参考文献 | 相关文章 | 计量指标

针对可编程逻辑控制器（PLC）程序在进行NuSMV模型检测时需要手工对程序进行建模，不仅浪费人力且容易出错的问题，提出一种基于状态转移的PLC程序模型自动化构建方法。该方法首先分析结构化文本（ST）语言特性并解析ST程序为抽象语法树；其次，在抽象语法树基础上，根据不同的文法结构进行控制流分析生成控制流图；然后，通过数据流分析得到程序依赖图；最后，根据程序依赖图生成NuSMV的输入模型。实验结果表明，所提方法实现了ST程序到NuSMV输入模型的自动化构建，并且构建的NuSMV输入模型既保留了ST程序的原有特性又符合NuSMV模型检测工具输入的规范，与传统手工模型构建方法相比，提高了模型生成的效率和准确率。

PLC程序控制流分析方法

张晔, 陆余良

2017, 37(12): 3581-3585. DOI: 10.11772/j.issn.1001-9081.2017.12.3581

摘要 ( )

PDF (723KB) ( )

参考文献 | 相关文章 | 计量指标

可编程逻辑控制器（PLC）是工业控制系统的重要组成部分，控制着各类物理设备及工艺流程。无论是攻击者的恶意篡改还是内部人员的编程错误所造成的PLC控制程序错误都将严重威胁设备及人身安全。为解决该问题，提出了针对PLC程序的控制流分析方法。首先，利用flex和bison分析了源代码的词法及语法结构；其次，通过分析抽象语法树（AST）生成并优化了不含指令副作用的中间表示；最后，在中间表示的基础上划分基本块，并以此为基本单元构建了程序的控制流图。实验结果表明，所提方法能够恢复语句表形式PLC程序的控制流结构，为程序理解和安全性分析提供了基础。

基于学习的容器环境Spark性能监控与分析

皮艾迪, 喻剑, 周笑波

2017, 37(12): 3586-3591. DOI: 10.11772/j.issn.1001-9081.2017.12.3586

摘要 ( )

PDF (985KB) ( )

参考文献 | 相关文章 | 计量指标

Spark计算框架被越来越多的企业用作大数据分析的框架，由于通常部署在分布式和云环境中因此增加了该系统的复杂性，对Spark框架的性能进行监控并查找导致性能下降的作业向来是非常困难的问题。针对此问题，提出并编写了一种针对分布式容器环境中Spark性能的实时监控与分析方法。首先，通过在Spark中植入代码和监控Docker容器中的API文件获取并整合了作业运行时资源消耗信息；然后，基于Spark作业历史信息，训练了高斯混合模型（GMM）；最后，使用训练后的模型对Spark作业的运行时资源消耗信息进行分类并找出导致性能下降的作业。实验结果表明，所提方法能检测出90.2%的异常作业，且其对Spark作业性能的影响仅有4.7%。该方法能减轻查错的工作量，帮助用户更快地发现Spark的异常作业。

基于变异分析的测试用例约简方法

王曙燕, 陈朋媛, 孙家泽

2017, 37(12): 3592-3596. DOI: 10.11772/j.issn.1001-9081.2017.12.3592

摘要 ( )

PDF (825KB) ( )

参考文献 | 相关文章 | 计量指标

针对回归测试过程中由于测试需求的变更导致测试用例规模不断扩大、测试成本不断增加的问题，提出一种基于变异分析的测试用例约简方法（RTM）。首先，以测试用例能否检测到指定变异体为依据，对测试用例进行划分并创建二进制数值形式的变异体事务集矩阵；然后，应用改进的关联挖掘算法获取测试用例间的关联关系；最后，根据这些关联关系有效约简测试用例。6个经典程序仿真实验结果表明，RTM能够使约简后的测试用例约简率达到37%，与传统贪心算法和启发式算法相比，测试用例约简率提高了6%，且在提高测试用例约简率的同时，保证了测试覆盖率，单个测试用例的测试覆盖率平均提高了11%。所提方法能够利用尽可能少的测试用例满足更多的测试需求，有效提高了测试效率，降低了测试成本。

基于地面场粒子群优化算法的高密度人群应急疏散建模

王超, 王坚

2017, 37(12): 3597-3601. DOI: 10.11772/j.issn.1001-9081.2017.12.3597

摘要 ( )

PDF (980KB) ( )

参考文献 | 相关文章 | 计量指标

针对非常规突发事件环境下高密度人群的拥挤管理和快速疏散问题，提出一种由感知层、传输层、计算层和应用层构成的多层结构人群疏散信息物理系统（E-CPS）体系框架。在E-CPS体系框架计算层中将静态地面场（FF）建模规则引入经典粒子群优化（PSO）模型，提出地面场PSO （FF-PSO）人群疏散模型，该模型同时具备静态场规则简单、计算快和PSO模型快速搜索、快速收敛的优点。此外，FF-PSO模型中构建了一种新的适应度函数，实现了疏散策略的动态选择，并通过数值仿真及实例仿真验证了FF-PSO模型在拥挤管理中的可行性和有效性。国家会展中心（上海）的实例仿真结果表明，考虑拥堵管理比仅考虑距离最短平均每分钟可多疏散66人，疏散时间节省19 min，疏散效率提升13.4%。

易腐生鲜货品车辆路径问题的改进混合蝙蝠算法

殷亚, 张惠珍

2017, 37(12): 3602-3607. DOI: 10.11772/j.issn.1001-9081.2017.12.3602

摘要 ( )

PDF (944KB) ( )

参考文献 | 相关文章 | 计量指标

针对配送易腐生鲜货品的车辆其配送路径的选择不仅受货品类型、制冷环境变化、车辆容量限制、交货时间等多种因素的影响，而且需要达到一定的目标（如：费用最少、客户满意度最高），构建了易腐生鲜货品车辆路径问题（VRP）的多目标模型，并提出了求解该模型的改进混合蝙蝠算法。首先，采用时间窗模糊化处理方法定义客户满意度函数，细分易腐生鲜货品类型并定义制冷成本，建立了最优路径选择的多目标模型；然后，在分析蝙蝠算法求解离散问题易陷入局部最优、过早收敛等问题的基础上，精简经典蝙蝠算法的速度更新公式，并对混合蝙蝠算法的单多点变异设定选择机制，提高算法性能；最后，对改进混合蝙蝠算法进行性能测试。实验结果表明，与基本蝙蝠算法和已有混合蝙蝠算法相比，所提算法在求解VRP时能够提高客户满意度1.6%~4.2%，且减小平均总成本0.68%~2.91%。该算法具有计算效率高、计算性能好和较高的稳定性等优势。

基于情景萤火虫算法的机器人路径规划

罗天洪, 梁爽, 何泽银, 张霞

2017, 37(12): 3608-3613. DOI: 10.11772/j.issn.1001-9081.2017.12.3608

摘要 ( )

PDF (946KB) ( )

参考文献 | 相关文章 | 计量指标

针对传统非结构环境下路径规划时机器人运动状态振荡和适应性差等问题，提出了一种基于情景萤火虫算法（SGSO）的机器人路径规划策略。该算法基于混沌系统的规律性、随机性和历遍性以实现初始化，并利用黄金比分割法进行后期优化，以提高种群的多样性，抑制算法的早熟和局部收敛；同时，引入关于萤火虫"天敌"的情景理解，改进萤火虫种群的选择机制，解决萤火虫在非结构环境下寻迹过程中的搁浅现象，增强了算法的适应性和鲁棒性。四个测试函数的仿真实验结果表明，所提算法的求解精度、收敛效率优于基本萤火虫种群优化（GSO）算法；将该算法应用于非结构环境下移动机器人的路径规划中，检测结果表明，基于SGSO的规划路径更短，且转角处更光滑，有效避免了机器人大角度转向对动力系统造成的额外负荷，验证了所提算法的可行性和有效性。

基于头脑风暴优化算法的多机器人气味源定位

梁志刚, 顾军华, 董永峰

2017, 37(12): 3614-3619. DOI: 10.11772/j.issn.1001-9081.2017.12.3614

摘要 ( )

PDF (1048KB) ( )

参考文献 | 相关文章 | 计量指标

针对现有室内湍流环境下多机器人气味源搜索算法存在历史浓度信息利用率不高、缺少调节全局与局部搜索的机制等问题，提出头脑风暴优化（BSO）算法与逆风搜索结合的多机器人协同搜索算法。首先，将机器人已搜索位置初始化为个体，以机器人位置为中心聚类，有效利用了历史信息的指引作用；然后，将逆风搜索作为个体变异操作，动态调节选中一个类中个体或两个类中个体融合生成新个体的数量，有效调节了全局和局部搜索方式；最后，根据浓度和持久性两个指标对气味源进行确认。在有障碍和无障碍两个环境中将所提算法与三种群体智能多机器人气味源定位算法进行定位对比仿真实验，实验结果表明，所提算法的平均搜索时间减少33%以上，且定位准确率达到100%。该算法能够有效调节机器人全局和局部搜索关系，快速准确定位气味源。

基于帕累托改进的多机器人动态任务分配算法

姜栋, 徐欣

2017, 37(12): 3620-3624. DOI: 10.11772/j.issn.1001-9081.2017.12.3620

摘要 ( )

PDF (813KB) ( )

参考文献 | 相关文章 | 计量指标

针对多机器人系统动态任务分配中存在的优化问题，在使用合同网初始任务分配的基础上提出了一种使用帕累托改进的任务二次分配算法。多机器人系统并行执行救火任务时，首先通过初始化任务分配将多机器人划分为若干子群；然后，每个子群承包某一救火任务，子群在执行任务的同时与就近子群进行帕累托改进确定需要迁移的机器人，实现两子群之间帕累托最优；最后，使用后序二叉树遍历对所有子群进行帕累托改进实现全局帕累托最优。理论分析和仿真结果表明，相较于强化学习算法和蚁群算法，所提算法的救火任务时间分别减少26.18%和37.04%；相较于传统合同网方法，所提算法在时间方面能够高效完成救火任务，在系统收益方面也具有明显优势。

基于变换步长的车辆压线声信号包络提取算法

蓝章礼, 黄芬

2017, 37(12): 3625-3630. DOI: 10.11772/j.issn.1001-9081.2017.12.3625

摘要 ( )

PDF (812KB) ( )

参考文献 | 相关文章 | 计量指标

车辆经过减速带时与其在路面正常行驶时的声信号波形明显不同，其特征参数的提取对车辆数量、速度、类型等的自动判断至关重要，声信号包络曲线对其特征参数的提取相比原始信号有诸多优势，但传统包络提取算法在此类交通领域声信号包络提取方面存在毛刺多、特征参数难以真正体现信号性质和特征的问题。为解决此问题，结合车辆经过减速带时的声信号特点，提出一种基于变换步长的车辆压线声信号包络提取算法。该算法通过设置不同步长遍历信号，以每个步长内的最大值点绘制曲线并与原信号波形对比，以轮廓清晰度和特征点提取误差值为判断依据实现声信号包络的有效提取。实验结果表明，在相同采样点数条件下，所提算法比传统包络提取算法提取的包络曲线轮廓更清晰、毛刺少，且特征参数提取误差小。

当期目录