文章快速检索 高级检索

1. 河北工程大学 资源学院, 河北 邯郸 056038;
2. 河北工程大学 信息与电气工程学院, 河北 邯郸 056038

Ant colony algorithm based on dynamic priority for distributed automation test scheduling
YANG Bensheng1 , YUAN Xiangmeng2 , HUANG Xiaoguang2
1. College of Resources, Hebei University of Engineering, Handan 056038, China ;
2. College of Information and Electrical Engineering, Hebei University of Engineering, Handan 056038, China
Abstract: Using the ant colony algorithm based on dynamic priority, the test task scheduling module in distributed automation test platform was analyzed. The algorithm mainly applies dynamic priority choice to the search of the optimal solution in the strategy of ant colony algorithm. The search time of the ant colony algorithm improves the search ability through implementation of test task priority and change of task waiting time increase, and high priority tasks to perform first. Through the simulation by GridSim, the results of experiment showed that this algorithm can improve the scheduling performance of the system, the utilization rate of test resources, and the efficiency of automated test system.
Key words: distributed automated testing     ant colony algorithm     task scheduling     GridSim

1 分布式自动化测试平台概述 1.1 分布式自动化测试的描述

 图 1 自动化测试基础设施 Fig. 1 Automation test infrastructure

1.2 分布式自动化测试平台的框架

 图 2 子系统结构图 Fig. 2 Subsystem structure

 图 3 状态机子系统的控制流程图 Fig. 3 Control flow chart of state machine system

2 蚁群算法的任务调度

2.1 蚁群算法模型

 $\Delta \tau _{ij}^k = \left\{ \begin{gathered} \frac{Q}{{{C_{ij}}}},第k{\text{只蚂蚁在}}(t,t + 1){\text{间过边}}\left( {i,j} \right) \hfill \\ 0,{\text{其他}} \hfill \\ \end{gathered} \right.$ (1)

 $p_{ij}^k\left( t \right) = \left\{ \begin{gathered} \frac{{{{[{\tau _{ij}}(t)]}^a} \times {{[{\eta _{ij}}(t)]}^\beta }}}{{\sum {_l{{[{\tau _{ij}}(t)]}^a} \times {{[{\eta _{il}}(t)]}^\beta }} }},ifj \in l \hfill \\ 0,其他 \hfill \\ \end{gathered} \right.$ (2)

2.2 基于动态优先权的蚁群调度算法

 $\Delta \tau _{ij}^k = \left\{ \begin{gathered} \frac{Q}{{{C_{ij}}}},第k{\text{个虚拟机上任务数}} \hfill \\ 0,{\text{其他}} \hfill \\ \end{gathered} \right.$ (3)

 $\sum {\Delta \tau _{ij}^k = \frac{{\sum Q }}{{{C_{ij}}}}} = Q$ (4)

 ${p_{ij}}\left( k \right) = \left\{ \begin{gathered} \frac{{{{[{\tau _{ij}}(k)]}^a} \times {{[\frac{1}{{{C_{ij}}}}(k)]}^\beta }}}{{\sum {_l{{[{\tau _{ij}}(k)]}^a} \times {{[\frac{1}{{{C_{il}}}}(k)]}^\beta }} }},ifj \in l \hfill \\ 0,其他 \hfill \\ \end{gathered} \right.$ (5)

 ${p_i}(k) = \sum\limits_{i = 1}^n {{x_{ki}}{p_{ij}}}$ (6)

 ${I_{ni}} = \sum\limits_{i = 1}^{m - 1} {{p_i}} (l) + \sum\limits_{j = 1}^{n - 1} {{W_{mj}}}$ (7)

 $p = \frac{{{W_{mj}} + {I_{ni}}}}{{{I_{ni}}}} + \pi w$ (8)

 $w = \frac{{{\tau _{ij}}(t + n) - \Delta {\tau _{ij}}}}{{{\tau _{ij}} - \Delta {\tau _{ij}}}}$ (9)

3 算法仿真结果与实验测试分析

 图 4 实验结果 Fig. 4 Experimental resules

 $HitValue = \sum\limits_{i = 1}^n {\frac{{{v_i}}}{{\sqrt {T\_{\text{finis}}{{\text{h}}_i} - {\text{submi}}{{\text{t}}_i}} }}}$ (10)

 图 5 动态优先权的蚁群算法和基本蚁群算法冲击值的比较曲线 Fig. 5 comparison curve between Hit value of ant colony algorithm based on dynamic priority and ant colony algorithm

4 结束语

 [1] MYERS G J, BADGETT T, SANDLER C. The art of software testing. 3rd ed. Wiley[M]. 2012 : 24 -29. [2] PINEDO M L. Scheduling: theory, algorithms, and systems. 4th ed. Springer[M]. 2012 : 391 -392. [3] PAGE A, JOHNSTON K, ROLLISON B. How we test software at Microsoft. Microsoft Press[M]. 2008 : 216 -218. [4] GU Wenquan, HUANG Chang. Distributed automatic test system research[C]//Proceedings of Computer Science and Network Technology. Harbin, China, 2011: 1834-1836. [5] CHAN T. Distributed automatic test pattern generation[C]//Proceedings of ASIC Conference and Exhibit. Rochester, NY, 1992: 698-702. [6] LESSING L, DUMITRESCU I. A new version of ant system for subset problem[C]//Proceedings of the Evolutionary Computation Congress. Washington, DC, USA, 1999:21-25. [7] 方甲永, 肖明清, 谢娟. 基于遗传蚁群算法的并行测试任务调度与资源配置[J]. 测试技术学报,2009, 23 (4) : 343 –349. FANG Jiayong, XIAO Mingqing, XIE Juan. Parallel test tasks scheduling and resources configuration based on GA-ACA[J]. Journal of Test And Measurement Technology,2009, 23 (4) : 343 –349. [8] 邓见光, 袁华强, 赵跃龙. 一种基于遗传—蚁群算法的网格任务调度策略[J]. 计算机应用研究,2011, 28 (12) : 4485 –4488. DENG Jianguang, YUAN Huaqiang, ZHAO Yuelong. Grid task scheduling strategy based on genetic-ant algorithm[J]. Application Research of Computers,2011, 28 (12) : 4485 –4488.
DOI: 10.3969/j.issn.1673-4785.

0

#### 文章信息

YANG Bensheng, YUAN Xiangmeng, HUANG Xiaoguang

Ant colony algorithm based on dynamic priority for distributed automation test scheduling

CAAI Transactions on Intelligent Systems, 2014, 9(6): 729-733
http://dx.doi.org/10.3969/j.issn.1673-4785.