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

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

Generating Covering Arrays Using Ant Colony Optimization:Exploration and Mining

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.