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

• 作者: 张文茜 曾梦凡 聂长海 陈思洋
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 覆盖表 蚁群算法 演化搜索算法 并行计算 组合测试 软件测试
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 基于搜索的软件工程研究专题
• 页码范围: 855-878
• 页数: 24页
• 分类号: TP311
• 字数: 18652字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004974

摘要

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