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

被引：20

作者：

曾梦凡

陈思洋

张文茜

聂长海

机构：

[1] 计算机软件新技术国家重点实验室(南京大学)

来源：

软件学报 | 2016年 / 27卷 / 04期

关键词：

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

D O I：

10.13328/j.cnki.jos.004974

中图分类号：

TP311.53 []; TP18 [人工智能理论];

学科分类号：

081202 ; 0835 ; 081104 ; 0812 ; 1405 ;

摘要：

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

引用

页码：855 / 878

页数：24

共 7 条

[1] 覆盖表生成的遗传算法配置参数优化 [J].

梁亚澜 ;

聂长海 .

计算机学报, 2012, 35 (07) :1522-1538

[2]

组合测试[M]. 科学出版社 , 聂长海, 2015

[3]

软件测试的概念与方法[M]. 清华大学出版社 , 聂长海, 2013

[4] Randomized post-optimization of covering arrays [J].

Nayeri, Peyman ;

Colbourn, Charles. J. ;

Konjevod, Goran .

EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (01) :91-103

[5]

New bounds for binary covering arrays using simulated annealing[J] . Jose Torres-Jimenez,Eduardo Rodriguez-Tello.Information Sciences . 2011 (1)

[6] A Survey of Combinatorial Testing [J].

Nie, Changhai ;

Leung, Hareton .

ACM COMPUTING SURVEYS, 2011, 43 (02)

[7]

Ant colony optimization theory: A survey[J] . Marco Dorigo,Christian Blum.Theoretical Computer Science . 2005 (2-3)

← 1 →