Tabu Search in Covering Array Generation
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61272079, 61321491, 91318301); Ministry of Education PhD fund(20130091110032)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Combinatorial testing can effectively detect faults caused by the interaction among the parameters of the system under test. In its 30 years of the development, covering array generation has been one of the key research areas, and relevant research articles have reached more than 200. As effective algorithms to generate covering arrays, existing tabu search algorithms have some advantages on the size of covering array, but there is still much room for improving the solution quality and calculation speed. Furthermore, the practical application of the existing algorithms is poor, because they can neither take account of constrains nor generate variable strength covering arrays. To solve the above problems, this paper proposes a new tabu search algorithm. Three improved aspects are presented. 1) The process of parameter tuning is divided into two stages:pair-wise and climbing to ensure that the optimal configuration is hit with a minimum number of configurations so as to further improve the size of covering arrays. 2) In order to improve the speed, the algorithm is parallelized. 3) Constrains and variable strength handling are added to make the algorithm adapt to various test scenarios. Experimental results show that the proposed algorithm has the advantage on the size of various covering arrays, such as fixed strength covering arrays, variable strength covering arrays and covering arrays with constraints. At the same time, the parallelization results in the increase of average speed of the algorithm by about 2.6 times.

    Reference
    Related
    Cited by
Get Citation

王燕,聂长海,钮鑫涛,吴化尧,徐家喜.覆盖表生成的禁忌搜索算法.软件学报,2018,29(12):3665-3691

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 28,2017
  • Revised:May 31,2017
  • Adopted:
  • Online: December 05,2018
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063