Using simulated annealing for locating array construction
Using simulated annealing for locating array construction
复制标题
DOI：
10.1016/j.infsof.2020.106346
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Tatsuya Konishi;Hideharu Kojima;Hiroyuki Nakagawa;Tatsuhiro Tsuchiya
中科院分区：
文献类型：
--
作者：
Tatsuya Konishi;Hideharu Kojima;Hiroyuki Nakagawa;Tatsuhiro Tsuchiya
上下文组合交互测试被认为是计算和信息系统的一种有效测试策略。定位数组是对这种测试策略有用的数学对象，因为它们可以用作允许故障定位和故障检测的测试套件。在这种应用中，数组的每一行都被用作一个单独的测试。本文提出了一种构造行数较少的定位数组的算法。测试成本的增加，因为测试的数量增加，从而找到定位阵列的小sizes.MethodThe所提出的算法使用模拟退火，一个元启发式算法，找到定位阵列的一个给定的大小的问题是有实际意义的。整个算法重复执行模拟退火算法的输入数组大小是动态变化的。ResultsExperimental结果表明：（1）该算法是能够构建定位阵列的问题实例的大规模和（2），对于问题的实例，其中非平凡定位阵列是已知的，该算法通常能够产生小于或至少等于已知阵列的定位阵列。结论基于结果，我们得出结论，该算法可以产生小的定位阵列和规模的实际问题。
ContextCombinatorial interaction testing is known to be an efficient testing strategy for computing and information systems. Locating arrays are mathematical objects that are useful for this testing strategy, as they can be used as a test suite that permits fault localization as well as fault detection. In this application, each row of an array is used as an individual test.ObjectiveThis paper proposes an algorithm for constructing locating arrays with a small number of rows. Testing cost increases as the number of tests increases; thus the problem of finding locating arrays of small sizes is of practical importance.MethodThe proposed algorithm uses simulated annealing, a meta-heuristic algorithm, to find locating array of a given size. The whole algorithm repeatedly executes the simulated annealing algorithm with the input array size being dynamically varied.ResultsExperimental results show (1) that the proposed algorithm is able to construct locating arrays for problem instances of large sizes and (2) that, for problem instances for which nontrivial locating arrays are known, the algorithm is often able to generate locating arrays that are smaller than or at least equal to the known arrays.ConclusionBased on the results, we conclude that the proposed algorithm can produce small locating arrays and scale to practical problems.