Implementing Ant Colony Optimization For Test Case Information Technology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The maintenance phase of a software produce needs to go through the inevitable regression testing process. It is required to retest the existing test suite whenever any addition, deletion or modifications are made to the software. Re-running the test cases from the existing test suite to build confidence in the correctness of the modified software is referred to as regression testing. Quite often software developers encounter time and budget constraints, which makes it almost impossible to rerun all the test cases within the specified constraints. Thus we use test case minimization, selection and prioritization techniques for regression testing.

Regression test selection is a process of reducing the test suite by selecting a subset from the original test suite. This is a very cost effective (also mention that it can leave certain imp. Test cases)method for regression testing. Regression test prioritization means scheduling the test cases in an increasing or decreasing order to meet some performance goal [1]. Various prioritization criteria may be applied to the regression test suite with the objective of meeting those criteria. Test cases can be prioritized in terms of random, optimal, statement coverage total or additional, branch coverage total or additional, failure rates, or total fault exposing potential (FEP) [1] of the test cases.

We often perform regression test prioritization in a time constrained environment where testing is done for a fixed period of time. Walcott et al [2] in 1996 gave one such technique for time-aware test case prioritization. Time-aware prioritization intelligently schedules the test suite in terms of both the execution time and potential fault detection information. Walcott et al used Genetic Algorithms to solve this problem. In the year 2010, Y.Singh l [3] also proposed a time-constrained prioritization technique using Ant Colony Optimization (ACO). The results shown in the paper provides motivation for implementing the algorithm and automating the technique. In this paper we present a tool called ACO_TCSP for the same and show results for the execution of the tool on the same example as used by Singh [3]. The outcome of the execution provides near optimum results and further motivates to test the tool on various larger examples to confirm the generality of its achievements.


ACO is a meta heuristic approach introduced in [4]. It has been successfully used to solve many NP hard optimization problems. Artificial ants have now been successfully applied on a considerable number of applications leading to world class performances for problems like vehicle routing, quadratic assignment, scheduling, sequential ordering, routing in Internet-like networks etc( no need of etc . when like is used). [22, 26, 46, 47, 67, 85]

Rothermel [11] has addressed the issues related to prioritization. Prioritization for large software development environments was described by Rothermel [12] repeated reference just given in last line. Prioritization of test cases based on historical execution of test data has been proposed by Kim [13]. Also empirical study was performed by Li [14] using various greedy algorithms. Time-aware regression test prioritization has also been proposed [2] where testing is performed within a fixed period of time.

In 2010 Singh et al [3] combined the two techniques, i.e., proposed an algorithm for Test Case Prioritization using Ant Colony Optimization in a time constrained environment. This algorithm has been used as the basis of our paper. (this paragraph mention similar thing as in last para of intro. Either take it there or bring that here)


Ant colony optimization technique is a set of instructions based on search algorithms of artificial intelligence for optimal solutions; here the iconic member is ANT System, as proposed by Colorni, Dorigo and Maniezzo [15, 16, 17]. Ants are blind and small in size and still are able to find the shortest route to their food source. They make the use of antennas and pheromone liquid to be in touch with each other. ACO inspired from the behaviour of real ants, are capable of synchronization with searching solutions for local problem by maintaining array list to maintaining previous information gathered by each ant.

Moreover, [18] ACO deals with two important processes, namely: Pheromone deposition &(use this and) trail pheromone evaporation. Pheromone deposition is the phenomenon of ants adding the pheromone on all paths they follow. Pheromone trail evaporation means decreasing the amount of pheromone deposited on every path with respect to time. Updating the trail is performed when ants either complete their search or get the shortest path to reach the food source. Each combinatorial problem defines its own updating criteria depending on its own local search and global search respectively.

Overview of the ACO System (no need for this title)

Artificial ants leave a virtual trail accumulated on the path segment they follow. The path for each ant is selected at random and on the basis of amount of "trail" present on the possible paths starting from the current node of the ant.(read this line again) More pheromone trail on a path increases the probability of the path being followed. Ant then reaches the next node and again does the path selection process as described above. This process continues till the ant reaches the starting node. This finished tour gives us (don't use us) the solution for shortest or best path which can then be analyzed for optimality.

Singh [3] introduced a (don't repeat it again and again just give reference) new test case prioritization technique using Ant Colony Optimization within a time restricted framework. The technique uses the fault detection and execution time information of the regression test suite as an input. In the proposed algorithm, execution time acts as cost of executing the test case. Prioritization is done in order to achieve total fault detection and minimum cost of execution. We abbreviate the technique as ACO_TCSP.

The basic block diagram for the ACO_TCSP (Ant Colony Optimization for Test Case Selection & Prioritization) system is shown in Fig.1. The inputs to the system include details of the test suite i.e., the test cases along with the faults covered by them and their execution time. These inputs are generally tabulated and are to be entered by the tester. The User of the ACO_TCSP tool needs only to enter the time constraint details at the run time. The output then produced has path details for each iteration, pheromone details, best path details and the final selected & prioritized test suite.

The basic steps for the ACO technique applied to test case selection & prioritization are shown in the form of flow chart in Fig.2. Initially, ants are located in test cases from the test suite (reframe the line ) and we store the current test case in a set 'S'. Now in the next step we determine probabilistically (based on the amount of pheromone and randomly) which test case is the next to be visited by the ant. We now move on to the selected test case and add it in the set 'S'. Since, we aim to cover all the faults, thus we check here whether or not all faults have been covered. If not, then we again determine the next node to be visited in a similar manner, if yes (start new line after manner), then we record the execution time for the complete path of each ant and clear the set 'S'. Now we determine the best path in this iteration and update the pheromone on this path. Since our next aim is to achieve prioritization within the time constraint, thus we check whether 'TC' has been reached or not? If yes, then we stop the execution and end, else, we repeat the same algorithm for next iteration.

This is the module that actually runs the ACO algorithm's one iteration for all the ants. This module is called from the main() module and is called in a loop till the total time constraint (TC) is reached. The output for this module is the path for each ant and the best path for this particular iteration. The best path of this iteration is chosen according to total fault coverage and minimum execution time. (+1) pheromone is then added on all the edges covered by the best path of current iteration. Also (-10%) pheromone is reduced from all the edges on the graph, corresponding to the real life pheromone evaporation phenomenon in ant colonies.

Some of the screenshots for output screens of the tool are shown in Fig 3 and 4. In order to evaluate the efficacy of the ACO_TCSP tool for test case selection and prioritization within a time constrained environment, the tool was applied on the same example as taken by Singh [3] to propose the algorithm. We ran ACO_TCSP four times on the example with constant time constraint, TC=85 time units. The input to the ACO_TCSP assumes a priori knowledge of the faults detected and the execution time of all test cases. The same is tabulated in Table 1. The result of the simulation of Table 1 and TC as input for 4 sample runs are given in Table 2. In this table, for each run the best path and its execution time of all iterations are reported. Also the final weight on the edges and the path found in that run is shown. It can be inferred from the Table 2 that 3 out of 4 times, the optimal path was found by ACO_TCSP. Though different paths were explored by artificial ants in all he runs, still they could converge to the optimal path.

In this section of the paper( no need) we represent the final outcomes for the 4 sample runs of ACO_TCSP in graphical form. The final graphs for all the 4 sample runs on the chosen example [3] as given in Table 2 are represented in fig 5 - 8. Test cases are figured as the nodes in the graph and only those edges are shown which have some positive weight (pheromone). Red lines are used to outline the final path found after running the ACO algorithm and the selected test cases (ACO_ordering) have been underlined in red color.

It can be observed from the graphical representation that the nodes connected via the edges with maximum weight (pheromone) are selected as the final solution or the best path. Thus, we can also prioritize the remaining test suite on the basis of pheromone on the edges in reducing order. Also it can be observed that reduction in the test suite using ACO_TCSP is approximately 62.5%. Also (repetition of Also from last line) we find that all the paths need not be traversed to cover all faults in the specified time.

Ant colony Optimization is a promising technique for solving test case selection and prioritization problem. In this study we developed a tool ACO_TCSP for the same and applied it on an example. Though in these tests, the best solution was not found for all cases, still the results obtained are in close proximity to the optimal results. Also the reduction in test suite size is achieved to be 62.5% in all the 4 test runs. This encourages the use of the developed tool by testers. In future we plan to apply the tool on many more examples to prove the usability and effectiveness of the proposed technique.