Regression Test Case Selection for Multi-Objective Optimization Using Metaheuristics

Full Text (PDF, 371KB), PP.50-56

Views: 0 Downloads: 0


Rahul Chaudhary 1,* Arun Prakash Agrawal 1

1. Amity School of Engineering and Technology, Amity University Noida, India

* Corresponding author.


Received: 21 Jun. 2014 / Revised: 23 Oct. 2014 / Accepted: 19 Jan. 2015 / Published: 8 Mar. 2015

Index Terms

Multi-Objective Optimization, Regression Testing, Test Case Selection, Metaheuristics, Heuristic Lab Tool, Heuristic Lab Problem Instances, Regression Test Case Selection etc.


A new heuristic algorithm is proposed by this paper, on multi-objective optimization using metaheuristics and TSP (travelling salesman problems). Basic thinking behind this algorithm is minimizing the TSP path or tour by dividing the entire tour into blocks that are overlapped to each other and then improve each individual block separately. Although it is unproven that a good solution have small improvement chances if a node moved far way to a position compared to its original solution. By intensively searching each block, further improvement is possible in TSP path or tour that never be supported in various search methods and genetic algorithm. Proposed algorithm and computational experiment performance was tested, and these tests are carried out with support of already present instances of problem. According to the results represented by paper, the computation verifies that proposed algorithm can solve TSPs efficiently. Proposed algorithm is then used for selecting optimal test cases, thousands of those test cases which are selected after confirming that they identify bugs and they itself selected from a repository of test cases; these thousand test cases are those test cases which are selected from several thousand test cases because they detect bugs. Few test cases from repository act as milestones (nodes) and having certain weight associated with each, proposed algorithm based on TSP implemented over selected result and select the optimal result or path or solution. These selected optimal test cases or selected path are further used to perform the regression testing, by applying those test cases selected by proposed algorithm in order to remove most of the faults or bugs effectively, i.e. take less time and identify almost all the bugs with few test cases. Hence this proposed algorithm assures most effective solution for regression testing test case selection.

Cite This Paper

Rahul Chaudhary, Arun Prakash Agrawal, "Regression Test Case Selection for Multi-Objective Optimization Using Metaheuristics", International Journal of Information Technology and Computer Science(IJITCS), vol.7, no.4, pp.50-56, 2015. DOI:10.5815/ijitcs.2015.04.05


[1]Lawler E.L. Lenstra J.K., Shmoys A.H.G. D.B. and Rinnooy Kan, The TSPs. Ed. Chichester: John Wiley & Sons, 1985.

[2]W.J. Cook, D.L. Applegate, V. Chvátal and R.E. Bixby, The TSPs: Princeton University Press, A computational study. Princeton: 2006.

[3]Garey M.R. and Johnson D.S. , Computers-and intractability: A guide to the theory of NP completeness.Freeman W.H., 1979.

[4]K.M. Ng, S.B Liu, Ong H.L.,“An overlapped neighborhood search method for general-sequencing problems”, 2007.

[5]Ng K.M., Ong H.L., Zeng L., and “A-generalized crossing -local- search method for solving vehicle routing problems”, 2007.

[6]J. Wright, G. Clarke, “Scheduling of vehicles from a central-depot to a number of delivery-points”, 1964

[7]P.M. Lewis, Sterns R.E., and Rosenkrantz D., “An analysis -of several-heuristics for the TSP”, 1977.

[8]Karp R.M,“Probabilistic analysis of partitioning _algorithms for_the TSP _in_ the_plane,” Mathematics of Operations Research, 1977.

[9]Christofides N, “Worst case analysis of a new heuristic- for the TSP,” , 1976 February.

[10]Lin S., “Computer solutions of-the TSP”, 1965.

[11]B.W. Kernighan and S. Lin, and, “An -effective heuristic-algorithm for the-TSP,” 1973.

[12]Or I. “Traveling- salesman type combinatorial problems and their relation to the logistics of regional blood-banking,” 1976.

[13]S.M Johnson, G.B. Dantzig, , S.M. and D.R. Fulkerson “SolutioN of a large scale TSP,” 1954.

[14]Held M., Karp R.M., “The TSP and minimum spanning trees”,1971.

[15]V. Srinivasan, G.L. Thompson AND T.H.C. Smith, “Computational performance of three subtour-elimination-algorithms for solving-asymmetric TSPs”, 1977.

[16]Eastman W.L. , “Linear-programming with pattern-constraints”,1958.

[17]Balas E., Christofides N., “A restricted-lagrangean approach to the TSP”,1981.

[18]Carpaneto G., and Toth P., “Some new-branching and bounding-criteria for the asymmetric TSP”,1980.

[19]Crowder H. , and Padberg M.W. , “Solving-large scale symmetric TSPs to optimality”,1980.

[20]Grötschel M. , and Holland O. , “Solution of -large scale TSPs”, Mathematical Programming, 1991.

[21]Padberg M.W., and Hong S., “On-the-symmetric TSPs”,1980.

[22]Lo C.C., Hus C.C. , “An Annealing-framework with learning memory”, IEEE Transactions, 1998.

[23]Bonomi E., and Lutton J. L., “The N-city TSP: Statistical mechanics and the Metropolis-algorithm”,1984.

[24]Golden B.L. , and Skiscim C. C. , “Using simulated annealing to solve routing and location problems”,1986.

[25]Nahar S. , Sahni S., and Shragowitz E. “Simulated-annealing and combinatorial-optimization,” ijc Aided VLSI Design, 1989.

[26]C.-N. ,Fiechter, “A parallel tabu-search algorithm for large scale TSP,” Fédérale de Lausanne, 1990.

[27]Knox J., “An-application of TABU search to the symmetric TSPs,” University of Colorado, 1988.

[28]Hartl R.F., Bullnheimer B, and Strauss C., “An-improved ant system algorithm for the vehicle -routing-problem”, 1999.

[29]Gomez O. , and Banan B., “Reasons-of ACO's success in Traveling salesman problem”, Ant Colony Optimization And Swarm Intelligence, 2004.

[30]Tsai C.W., Tsai C. F., Tseng C. C., “A new and efficient ant based heuristic method for solving the TSP,” 2003.

[31]Colorni A., Dorigo M., and Maniezzo V. “The ant-system: optimization by a colony of cooperating-agents,” IEEE Transactions, Man and Cycbernetics, 1996.

[32]Fuquay D., Starkweather T., and Whitley D., “Scheduling- problems and tsp: The genetic edge recombination operator,” 1989.

[33]Yoshihara I. ,Nguyen H.D., Yasunaga M. and Yamamori K. , “Implementation of an effective hybrid GA for large- scale TSPs,” IEEE Transactions on Systems, Man, and Cybernetic, 2007.

[34]VanGucht D., Rosmaita B., Gopal R, and Grefenstette J.J. , “Genetic- algorithms for the TSP”, 1985.

[35]dehrui satchidananda and Ghosh Ashish. , 2005 march. Evolutionary algorithms for multi-creation-optimization: survey. International -journal of computing and information- sciences.

[36]Antosiewicz Marek, Koloch Grzegorz, Bogumił Kamiński Warsaw School of Economics, ISSN 2299- 2634. Choice of best possible metaheuristic algorithm for the TSP with limited computational time: quality, uncertainty and speed. In Journal of Theoretical and Applied Computer Science, 2013.

[37]Ciavotta Michele, Ruiz Rubén,Minella Gerardo,A review- and- evaluation of multi-objective-algorithms for the flowshop -scheduling problem, IEEE Transaction, March 2007.

[38]Thiele Lothar And Zitzler Eckart, Multiobjective Evolutionary-Algorithms: A Comparative Case-Study and the Strength-Pareto-Approach. IEEE Transactions, 1999.

[39]Do Hyunsook & Rothermel Gregg & Kinneer Alex,Prioritizing-JUnit-Test-Cases: An Empirical-Assessment and Cost- Benefits Analysis, Empir-Software-Eng (2006).

[40]Harman Mark and Yoo Shin King’s-College-London, CREST, Department of Computer Science Strand, London, UK.

[41]L. GRAVES , Los TODD, HARROLD MARY JEAN, PORTER ADAM, KIM JUNG- MIN and ROTHERMEL GREGG,: An- Empirical- Study of Regression Test Selection Techniques, ACM Transactions on Software-Engineering and Methodology,” 2001.

[42]Harman M. and Yoo S., Regression-Testing Minimisation, Selection and Prioritisation : A Survey, SOFTWARE- TESTING, VERIFICATION AND RELIABILITY, 2007.

[43]MELAB N., CAHON S., ParadisEO ,TALBI E.-G.: A Framework-for the Reusable -Design of Parallel and Distributed- Metaheuristics, Journal-of-Heuristics, 2004 Kluwer Academic Publishers. Manufactured in The Netherlands.