利用蚁群算法生成覆盖表:探索与挖掘

来源：软件学报杂志2016年第4期北京时间：

作者：曾梦凡,陈思洋,张文茜,聂长海

单位：曾梦凡，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21009311,陈思洋，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21009302,张文茜，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21009303,聂长海，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21009304

摘要：覆盖表生成问题是组合测试的重要研究内容之一,目前已有许多数学方法、贪心算法、搜索算法用于求解这一问题.蚁群算法作为一种能够有效求解组合优化问题的演化搜索算法,已被应用到求解覆盖表生成问题中.已有的研究工作表明:蚁群算法适于求解一般覆盖表、变力度覆盖表生成以及覆盖表排序等问题,但算法结果与其他覆盖表生成方法相比并不具有优势.为了进一步探索与挖掘蚁群算法生成覆盖表的潜力,进行了如下4个层次的改进工作:(1)算法变种集成;(2)算法参数配置优化;(3)演化对象结构调整及演化策略改进;(4)利用并行计算优化算法时间开销.实验结果表明:通过以上4个层次的改进,蚁群算法生成覆盖表的性能有了显著提升.

关键词：覆盖表;蚁群算法;演化搜索算法;并行计算;组合测试;软件测试

基金资助：国家自然科学基金(61272079,61321491,91318301);教育部博士点基金(20130091110032)