Computing and Informatics, Vol. 36, 2017, 705–732, doi:10.4149/cai 2017 3 705 IMPROVED ANNEALING-GENETIC ALGORITHM FOR TEST CASE PRIORITIZATION Zan Wang, Xiaobin Zhao, Yuguo Zou School of Computer Software 92 Weijin Rd, Tianjin University Tianjin, 300072, China e-mail: {wangzan, zhaoxiaobin, zouyuguo}@tju.edu.cn Xue Yu(cid:63) College of Management and Economic 92 Weijin Rd, Tianjin University Tianjin, 300072, China e-mail: [email protected] Zhenhua Wang American Electric Power 700 Morrison Rd Gahanna, OH, 43230, USA e-mail: [email protected] Abstract. Regression testing, which can improve the quality of software systems, is a useful but time consuming method. Many techniques have been introduced to reduce the time cost of regression testing. Among these techniques, test case prioritization is an effective technique which can reduce the time cost by process- ing relatively more important test cases at an earlier stage. Previous works have demonstratedthatsomegreedyalgorithmsareeffectiveforregressiontestcasepri- oritization. Those algorithms, however, have lower stability and scalability. For ∗ Corresponding author 706 Z. Wang, X. Zhao, Y. Zou, X. Yu, Z. Wang this reason, this paper proposes a new regression test case prioritization approach basedontheimprovedAnnealing-GeneticalgorithmwhichincorporatesSimulated Annealing algorithm and Genetic algorithm to explore a bigger potential solution spacefortheglobaloptimum. ThreeJavaprogramsandfiveCprogramswereem- ployedtoevaluatetheperformanceofthenewapproachwithfiveformerapproaches suchasGreedy,AdditionalGreedy,GA,etc. Theexperimentalresultsshowedthat theproposedapproachhasrelativelybetterperformanceaswellashigherstability and scalability than those former approaches. Keywords: Regression testing, test case prioritization, meta-heuristics, genetic algorithm, simulated annealing algorithm, annealing-genetic algorithm (AG) Mathematics Subject Classification 2010: 68N30 1 INTRODUCTION Regression testing is a type of software testing that seeks to uncover new faults in existing software systems after changes have been made. It is a frequent testing activity and often time consuming [1, 2]. Research shows that the time cost of regression testing would account for more than one third of the total time cost of software maintenance [3, 4]. At present, the way to reduce the cost of this work has attracted much attention not only from software engineers but also academic researchers. Moreandmoretechniquestopursuelowercostinregressiontestinghave been proposed and these methods can be summarized as three categories which are testcaseselectiontechniques[5],testsuiteminimizationtechniques[6]andtestcase prioritization techniques [7]. As for lossless aspect of the testing capability method, thetestcaseprioritizationdoesnotdiscardanytestcasesandassumesthatdifferent test cases have different contributions for the testing goals. Those test cases which are more important for the testing goals will be higher scored and executed earlier. Previousresearcheshaveshowedthattestcaseprioritizationtechniquescanimprove the efficiency of regression testing by the early stopping when goals are achieved. As a result, it reduces testing time and costs [8, 9, 10, 11]. TheformaldefinitionofthetestcaseprioritizationproblemgivenbyRothermel etal.iswidelyacceptedinliterature[11]. Theyfirstemployafunctionf(T)toyield an award value for each ordering T of test cases, and then describe the problem as to find an ordered test suite with the highest award value. Rothermel et al. also discussed five possible improvement goals which testers intended to achieve by the test cases prioritization. They are the rate of fault detection of a test suite, the coverage of coverable code, their confidence in the reliability of the system, the rate at which high risk faults are detected and the likelihood of revealing faults related to specific code changes respectively [11]. To evaluate prioritization techniques in meeting these different goals, however, we need different evaluation criteria. If Improved AG for Test Case Prioritization 707 we focus on the first goal listed above, increasing the rate of fault detection of a test suite, APFD (Average of the Percentage of Faults Detected) should be used which is the widely used and effective prioritization technique evaluation criterion. But if our goal is to increase the coverage of coverable code in the system under test at a faster rate, coverage based evaluation criteria such as APSC (Average Percentage Statement Coverage), APBC (Average Percentage Block Coverage) and APDC (Average Percentage Decision Coverage) should be taken. In this work, we aim at the second goal listed above – the increasing the coverage of coverable code in the system under test at a faster rate and the APSC will be selected as the evaluation criterion to compare the performance of prioritization techniques. The APSC for ordering T(cid:48) is given as follows [10]: TB +TB +...+TB 1 APSC =1− 1 2 m + (1) nm 2n where we assume that a test suite T containing n test cases that covers a set S including m statements and TB is the first test case in the order T(cid:48) of T that i covers statement i. Heuristic algorithms can be employed to solve the test case prioritization prob- lem. Inthepreviouswork,manyheuristicsbasedtechniquesforregressiontestcase prioritizationhavebeenproposed. In[11,12,13,14,15,16,17,18],Rothermeletal. investigated several prioritization techniques, such as total statement/branch cov- erage prioritization and additional statement/branch coverage prioritization, which try to maximize the rate of fault detection. Li et al. applied various meta-heuristic algorithms for test case prioritization [10]. They compared random algorithm, Hill Climbing algorithm, Genetic Algorithm, Greedy algorithm, Additional Greedy al- gorithm and two-optimal Greedy algorithm and found that Additional Greedy al- gorithm can achieve better results than other four algorithms. Statement T 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 X X X X X X X X 2 X X X X X X 3 X X X 4 X X 5 X X X X X X X Table 1. A case in which Additional Greedy algorithm will not produce an optimal solu- tion Despite of the efficiency of Additional Greedy algorithm, some issues remained about reliability and scalability of additional greedy algorithm, especially when the coverage data matrix is sparse. To illustrate this problem, a simple example based on statement coverage is employed and shown in Table 1. If the aim is to increase thecoverageofcoverablecodeatafasterrateandtheevaluationcriterionisAPSC, 708 Z. Wang, X. Zhao, Y. Zou, X. Yu, Z. Wang Additional Greedy algorithm may select 1-2-3-4-5 as the “optimal” solution. How- ever, the optimal test case ordering for this example is 5-2-3-4-1 because the APSC value of test suite 5-2-3-4-1 is bigger than that of test suite 1-2-3-4-5 (the APSC value of test suite 5-2-3-4-1 is 72.3529 while the APSC value of test suite 1-2-3- 4-5 is 71.1765). Additional Greedy algorithm does not work well in this example mainly because greedy based algorithms are a type of avariciously searching algo- rithm and expect to find the global optimum by making the locally optimal choice at each stage. Unfortunately, they can only explore a smaller space and have less probabilitytoachievetheoptimalsolutionthanglobalsearchingalgorithmssuchas GeneticAlgorithm(GA).Wecallthisproblemas“LocalOptimaSyndrome(LOS)”. However, previous experiments showed that Additional Greedy algorithm had bet- ter results than Genetic Algorithm in many common cases. It is necessary to find a better algorithm which can not only explore the global searching space but also have at least equal performance compared with Additional Greedy algorithm. Inthispaper,weproposeanimprovedAGalgorithmfortestcaseprioritization. The new proposed algorithm is a robust optimizing algorithm which can overcome the shortcomings of Additional Greedy algorithm as well as to achieve good perfor- mance as Additional Greedy algorithm by three following ways. Firstly, Metropolis operator of SA will be incorporated into the iterative process to maintain diversity of the searching space of GA to alleviate the premature convergence problem. As aresult,thehybridalgorithmwillhavemorechancestoachievebetterresults. More- over, the optimization reserved strategy will be hired to accelerate the convergence rate by retaining the optimum of each generation. Thirdly, a local search operator will be employed with GA to improve the local search capability of the algorithm. These three improvement ways of GA will not only increase the performance of the algorithm but also accelerate its convergence speed. The rest of this paper is organized as follows. Section 2 describes related work. Section3describestheimprovedAGalgorithmforregressiontestcaseprioritization. Thenweevaluatetheproposedalgorithmandcompareitwithotherfivealgorithms in Section 4. Section 5 concludes and Section 6 gives the future works. 2 RELATED WORK Fromtheperspectiveofsoftwaretesterswhowishtomeetthegoalofregressiontest case prioritization, previous research can be roughly categorized into two classes, namelythoseforrateoffaultdetectionandtheotherforcodecoverage,respectively. 2.1 Prioritization for Rate of Fault Detection In the previous work on optimizing the fault detection, researchers focused on the first goal listed in Section 1: increasing the rate of fault detection of a test suite. Rothermel et al. explored some empirical studies of several prioritization techniques [11, 12, 13, 14, 15, 16, 17, 18] to reach this goal. They applied Greedy Improved AG for Test Case Prioritization 709 algorithmandAdditionalGreedyalgorithmwithdifferentfaultdetectionratesurro- gates. The considered surrogates were: branch-total, branch-additional, statement- total, statement-additional, Fault Exposing Potential (FEP)-total, and FEP-addi- tional. They also conducted several experiments to compare these techniques with no prioritization, random prioritization and optimal prioritization. The results showedthatalltheproposedtechniquesgethigherAPFDvaluesthanrandomorno prioritization,whichmeansthesetechniquescanimprovetherateoffaultdetection. AlthoughAdditionalGreedyalgorithmhasrelativelybetterperformance,Zhang et al. found that there is a weakness in the additional strategy. Because of the situation in which a test case covers a statement but does not reveal a fault in the statement,theadditionalstrategymaygreatlypostponethedetectionofthosefaults coveredbutnotrevealed. Incontrast,thetotalstrategydoesnothavethisweakness. Therefore, they proposed a test case prioritization approach that unifies the total strategyandtheadditionalstrategy[19]. Theyalsoperformedanempiricalstudyto compare their approach with greedy and additional greedy based approaches. The results demonstrate that the proposed approach can significantly outperform both the total and additional strategies. 2.2 Prioritization for Code Coverage Research on prioritization for code coverage aimed to increase the coverage of exe- cutable code at a faster rate. Li et al. investigated various meta-heuristics methods totestcaseprioritizationforfastercoverage[10]. Theyconductedanexperimentto comparerandomprioritization,HillClimbingalgorithm,GeneticAlgorithm,Greedy algorithm,AdditionalGreedyalgorithmandtwo-optimalGreedyalgorithm. Rather thanAPFD,threecoveragebasedmetricsincludingAPBC,APDCandAPSCwith Siemens suite programs and the program space were hired to evaluate the perfor- mance of each technique. The results indicated that Additional Greedy algorithm is the most efficient in general. The studies also showed that the applications of meta-heuristics, especially Genetic Algorithm, are effective for regression test case prioritization. Maia et al. applied another well-known meta-heuristic, GRASP (Greedy Ran- domized Adaptive Search Procedures), for test case prioritization and conducted an empirical evaluation to compare GRASP based approach with other four search based algorithms [20]. Their experimental results showed that the proposed ap- proach performed significantly better than Genetic Algorithm, Simulated Anneal- ing algorithm, and similarly to Additional Greedy algorithm in terms of coverage performance. Previous research of test case prioritization for code coverage mainly focus on greedy algorithms and meta-heuristics. However, seldom work has examined the adaption and flexibility of these algorithms. In addition, greedy algorithms are local search based algorithms and have lower scalability and stability as shown in Section 1. Thus, we need a better test case prioritization technique which can explore the global searching space and has good performance as Additional Greedy 710 Z. Wang, X. Zhao, Y. Zou, X. Yu, Z. Wang algorithm. In this paper, we propose a hybrid algorithm for test case prioritization to achieve better result with high stability and scalability. In addition, this paper willverifysomeprimaryfindingsinthepreviousresearchtosomeextentandanalyze the limitation of several widely used heuristic algorithms. 3 IMPROVED AG FOR TEST CASE PRIORITIZATION Genetic algorithm can achieve the global optimum by exploring a global candidate space rather than obtaining only local optimum for each stage. It has shown effec- tivenessandrobustnessfortestcaseprioritizationproblem[10]. However, thereare someinsufficiencies. OneofthemajorproblemsforGAisweakerperformancecom- paredwithAdditionalGreedyalgorithm. Thisissueismainlybecausethepremature convergencetosomelocaloptimaoftenoccurswithGA.Thetermofprematurecon- vergence means that a population for an optimization problem converges too early and leads to suboptimal results. This problem is mainly due to the loss of diversity of the GA’s population, being the cause of a decrease on the quality of solutions. To alleviate this problem and improve the performance of GA, Lin et al. proposed ahybridalgorithmAnnealing-Genetic(AG)bycombiningthelocalstochasticsearch fromsimulatedannealingalgorithmandtheglobalgeneticoperationsespeciallythe crossover operation from Genetic Algorithm effectively [21]. In this paper, the hy- brid algorithm AG will be hired to maintain a certain degree of genetic diversity for better test case prioritization. Moreover, two further strategies will be hired to accelerate the computing process for faster convergence. Firstly, local searching in each iterative evolution will be employed to search the local optimum much faster. And secondly, optimization reserved strategy will be adopted to hold the optimal solution in each step. To illustrate, consider Figure 1, and Table 2 that represent the computational framework and pseudo codes of the improved AG algorithm. As described in Ta- ble2,theproposedhybridalgorithmhassiximportantparts: individualgeneration and population initiation, fitness function, Metropolis criterion determination, ge- netic operators, optimization reserved strategy and stopping criteria. The detailed descriptions of these parts are listed as follows. 3.1 Individual Generation and Population Initialization Like GA, the new hybrid algorithm evolves a population including candidate solu- tions(calledindividuals)towardbetterindividualsbyaniterativeprocess,too. Each individual in the population is a candidate solution for the optimization problem. For TCP, one candidate solution can be represented as a string which is comprised of the executing sequence of test cases in a test suite. For example, “5-3-4-2-1” denotes an executing sequence of five test cases in a test suite, where the testing process follows a sequence of fifth, third, fourth, second and first test cases. After generating a fix number of individuals randomly, the algorithm will initialize the population. Improved AG for Test Case Prioritization 711 Pseudo code: Improved Annealing-Genetic Parameters: Initial Temperature – T 0 Cooling Rate – q Frozen Temperature – T end Population Size – NIND Generation Gap – GGAP Crossover Rate – P c Mutation Rate – P m 1 initialize population P 0 2 evaluate individuals in P 0 3 current point ← the individual with the highest evaluation value in P 0 4 solution point ←current point 5 current population ←P 0 6 T ←T 0 7 while (T >T ) do end 8 begin 9 no of point ←0 10 candidates ←{} 11 while (no of point < NIND) do 12 begin 13 generate next point from current point 14 // Metropolis criterion determination 15 df ←f(next point)−f(current point) 16 if min[1,exp(df/T)]>random[0,1) then 17 candidates ←{candidates,next point} 18 current point ←next point 19 no of point ←no of point+1 20 else 21 pick another point from current population as current point 22 end 23 select from candidates 24 crossover 25 mutate 26 reverse 27 re-insert to get new population P new 28 evaluate individuals in P new 29 current point ← the individual with the highest evaluation value in P new 30 if f(current point)>f(solution point) then 31 solution point ←current point 32 current population ←P new 33 T =q∗T 34 end Table 2. Pseudo code of Improved Annealing-Genetic algorithm 712 Z. Wang, X. Zhao, Y. Zou, X. Yu, Z. Wang Figure 1. Flow chart of improved AG 3.2 Fitness Function and Evaluation Criteria After each round of the iterative process, some worst solutions will be replaced by the new breeds. Therefore, each candidate solution needs to be awarded a measure indicator representing the distance from achieving the goal. The measure indica- tor can be generated by a fitness function and be employed to evaluate how good a candidate solution is. As described in Section 1, there are different evaluation criteria to meet different goals for TCP and different criteria leads different fitness function. Because increasing the coverage of coverable code in the system under test at a faster rate is the goal of this paper, APSC will be hired as the fitness function to evaluate each solution. The fitness function can be defined by For- mula (1). 3.3 Metropolis Criterion Determination As described above, GA has a shortage that it usually converges to some local optimum and has difficulty to reach the global one. This problem is usually be- cause the searching space is not large enough to achieve the optimum and does not have enough variance. To address this problem, the Metropolis criterion of SA will be introduced to accept some worse individuals with a probability to maintain the diversity of the population. The acceptance probability is defined as follows: Improved AG for Test Case Prioritization 713 (cid:40) 1, df >0, P = (2) exp(cid:0)df(cid:1), df ≤0 T where T is the current temperature, and df is the fitness difference of two individ- uals. 3.4 Genetic Operators Like GA, improved AG has similar genetic operators which make the individuals in the population go through a process of evolution. As an improved GA, it has fourtypesofoperators: selection,crossover,mutationandlocalsearch,respectively. Selection is the stage of a genetic algorithm in which individuals are chosen with a selecting probability from a population for further breeding operators such as crossover and mutation. Crossover is a genetic operator used to produce child solu- tionsfromparentindividualswhichwerechosenbytheselectionoperator. Mutation alters one or more gene values in a chromosome to maintain the genetic diversity of the population. In this paper, we redefine the traditional three operators for TCP and incorporate a local search operator before the computational process proceed to the next generation for better performance. Detailed operators are described as follows: Selection. Theroulettewheelselectionstrategyisemployedinthispapertoselect potentiallyusefulsolutionsforrecombination. LetNINDbethepopulationsize andfitness(i)bethefitnessvalueofindividualiinthepopulation,itsprobability of being selected is P =fitness(i)/(cid:80)NINDfitness(j). i j=1 Crossover. Therearetwostepsofcrossoverinthispaper. Firstly,twopointstobe selectedontheparentstringswillexchangeeachother. Everythingbetweenthe twopointswillbeswappedbetweentheparentstringsandtwochildindividuals will be rendered. Unlike binary strings, a candidate solution for TCP is a se- quence string and there may be conflict numbers in the child individuals. After that,anextraprocesstoamendthechildindividualswillbelunchedtodealwith the conflict for legal child individuals. For example, there are ten test cases in a test suite. Two executing sequences of the test suite, 1-5-7-2-3-4-9-6-8-10 and 10-2-8-3-6-5-9-1-7-4areselectedforcrossover. Afterexchangethesubstringsbe- tweenthethirdandsixthlocusofthetwoparentsinthisexample,thealgorithm will give two child chromosomes, 1-*-8-3-6-5-9-*-*-10 and 10-*-7-2-3-4-9-1-*-*. There are some conflict numbers in the two child individuals and partial map- ping method is hired to amend the child individuals. Then the amended child individuals are 1-4-8-3-6-5-9-2-7-10 and 10-6-7-2-3-4-9-1-8-5, respectively. Mutation. The mutation isperformed byexchanging thelocations of two selected points randomly. Local search. Theinterestonlocalsearchoperatorscomesfromthefactthatthey may effectively and quickly explore the basin of attraction of optimal solutions, 714 Z. Wang, X. Zhao, Y. Zou, X. Yu, Z. Wang achieving optimum more accurate and quickly. GA based algorithms, on the contrast, explore the global space by evolving the population for optimum and have low speed for evolution. In this paper, we will incorporate a neighbor- hood based local search operator – reverse – into AG for better individual after crossover and mutation. This operator could improve the local searching abil- ity of Genetic Algorithm and it is evolutionary because it is a single direction operation. That is, only accept the individual whose fitness has increased after reverse operation. Reverse means to select two positions in the test suite and then to reverse the suite between these two positions. The introduction of local searching into AG will not only improve the performance of the algorithm but also compensates the time which AG consumes for exploring a larger space. 3.5 Optimization Reserved Strategy Re-insert operator constructs the new population using the optimal individuals in the parent population and offspring produced by genetic operators. This operator ensures the realization of the optimization reserved strategy and keeps the popula- tion size constant. 3.6 Stopping Criteria As a hybrid algorithm of SA and GA, the new algorithm will stop when it reaches some stopping conditions. In this paper, the algorithm first assigns an initial tem- perature and then lowers the temperature in a decreasing rate for each generation. After exceeding the temperature threshold, the algorithm will stop. 4 EMPIRICAL EVALUATION Inordertoevaluatetheperformanceoftheproposedtestcaseprioritizationapproach based on improved AG, several empirical experiments are conducted. This section describes those studies, including experiments design, subjects’ description, results discussion and some shortcomings. 4.1 Research Questions We are interested in the following research questions. [RQ1:] Can improved AG based test case prioritization approach improve the ro- bustness? [RQ2:] How does the new proposed algorithm compare to some former algorithms in terms of performance? [RQ3:] How does the new proposed algorithm compare to some former algorithms in terms of the convergence speed?