主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王燕,聂长海,钮鑫涛,吴化尧,徐家喜.覆盖表生成的禁忌搜索算法.软件学报,2018,29(12):3665-3691
覆盖表生成的禁忌搜索算法
Tabu Search in Covering Array Generation
投稿时间:2017-03-28  修订日期:2017-05-31
DOI:10.13328/j.cnki.jos.005369
中文关键词:  基于搜索的软件工程  组合测试  覆盖表  禁忌搜索  并行化
英文关键词:search based software engineering  combinatorial testing  covering arrays  tabu search  parallelization
基金项目:国家自然科学基金(61272079,61321491,91318301);教育部博士点基金(20130091110032)
作者单位E-mail
王燕 南京晓庄学院 信息工程学院, 江苏 南京 211171 wangyan@njxzc.edu.cn 
聂长海 计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023  
钮鑫涛 计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023  
吴化尧 计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023  
徐家喜 南京晓庄学院 信息工程学院, 江苏 南京 211171  
摘要点击次数: 1113
全文下载次数: 813
中文摘要:
      组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中,覆盖表生成一直是关键问题之一,相关研究文献已达200多篇.作为一种有效的覆盖表生成算法,已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势,但其解的质量和运算速度仍有提升空间;同时,这些算法实际应用能力较差,既不支持约束处理,也无法生成可变力度覆盖表.针对以上问题,提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进:1)算法参数配置调优分pair-wise和爬山两阶段进行,确保使用较少配置条数最大程度击中最优配置,进一步提高算法生成覆盖表的规模;2)进行算法并行化,加速算法生成覆盖表的速度;3)增加约束处理和变力度处理,使算法可适应多种测试场景.实验结果表明,该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势,同时,并行化使算法平均加速2.6倍左右.
英文摘要:
      Combinatorial testing can effectively detect faults caused by the interaction among the parameters of the system under test. In its 30 years of the development, covering array generation has been one of the key research areas, and relevant research articles have reached more than 200. As effective algorithms to generate covering arrays, existing tabu search algorithms have some advantages on the size of covering array, but there is still much room for improving the solution quality and calculation speed. Furthermore, the practical application of the existing algorithms is poor, because they can neither take account of constrains nor generate variable strength covering arrays. To solve the above problems, this paper proposes a new tabu search algorithm. Three improved aspects are presented. 1) The process of parameter tuning is divided into two stages:pair-wise and climbing to ensure that the optimal configuration is hit with a minimum number of configurations so as to further improve the size of covering arrays. 2) In order to improve the speed, the algorithm is parallelized. 3) Constrains and variable strength handling are added to make the algorithm adapt to various test scenarios. Experimental results show that the proposed algorithm has the advantage on the size of various covering arrays, such as fixed strength covering arrays, variable strength covering arrays and covering arrays with constraints. At the same time, the parallelization results in the increase of average speed of the algorithm by about 2.6 times.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利