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

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Generating Covering Arrays Using Ant Colony Optimization:Exploration and Mining
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61272079, 61321491, 91318301); Research Fund for the Doctoral Program of Higher Education of China (20130091110032)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Generation of covering arrays, which has been solved by many mathematical methods and greedy algorithms as well as search based algorithms, is one of significant problems in combinatorial testing. As an effective evolutionary search algorithm for solving combinatorial optimization problems, ant colony optimization has also been used to generate covering arrays. Existing research shows ant colony optimization suitable for generating general covering arrays, variable strength covering arrays and the prioritization of covering arrays. Unfortunately, compared with other methods, ant colony optimization doesn't have significant advantages. To further explore and mine the potential of ant colony optimization in generating covering arrays, this paper focuses on four levels of improvement:1) the integration of ant colony variants; 2) parameter tuning; 3) the adjustment of solution structure and the improvement of evolutionary strategy; 4) using parallel computing to save executing time. The experimental results show that ant colony optimization is much more effective in generating covering arrays after the improvements.

    参考文献
    相似文献
    引证文献
引用本文

曾梦凡,陈思洋,张文茜,聂长海.利用蚁群算法生成覆盖表:探索与挖掘.软件学报,2016,27(4):855-878

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-08-30
  • 最后修改日期:2015-10-15
  • 录用日期:
  • 在线发布日期: 2016-01-14
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号