A Genetic Approach to Analyze Algorithm Performance Based on the Worst-Case Instances

So-Yeong Jeon, Yong-Hyuk Kim

.

DOI: 10.4236/jsea.2010.38089                

Abstract

Search-based software engineering has mainly dealt with automated test data generation by metaheuristic search techniques. Similarly, we try to generate the test data (i.e., problem instances) which show the worst case of algorithms by such a technique. In this paper, in terms of non-functional testing, we re-define the worst case of some algorithms, respectively. By using genetic algorithms (GAs), we illustrate the strategies corresponding to each type of instances. We here adopt three problems for examples; the sorting problem, the 0/1 knapsack problem (0/1KP), and the travelling salesperson problem (TSP). In some algorithms solving these problems, we could find the worst-case instances successfully; the successfulness of the result is based on a statistical approach and comparison to the results by using the random testing. Our tried examples introduce informative guidelines to the use of genetic algorithms in generating the worst-case instance, which is defined in the aspect of algorithm performance.

Keywords

Search-Based Software Engineering, Automated Test Data Generation, Worst-Case Instance, Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. McMinn, “Search-Based Software Test Data Genera- tion: A Survey,” Software Testing Verification And Reliability, Vol. 14, No. 2, 2004, pp. 105-156.
[2]	M. Johnson and A. Kosoresow, “Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms,” Lecture Notes in Computer Science, Vol. 2557, 2002, pp. 344-355.
[3]	C. Cotta and P. Moscato, “A Mixed-Evolutionary Statis- tical Analysis of an Algorithm’s Complexity,” Applied Mathematics Letters, Vol. 16, No. 1, 2003, pp. 41-47.
[4]	D. Goldberg, “Genetic Algorithms in Search, Optimi- zation, and Machine Learning,” Kluwer Academic Publi- shers, Boston, 1989.
[5]	P. Moscato, “Memetic Algorithms: A Short Introduc- tion,” In: D. Corne, M. Dorigo and F. Glover, Eds., New ideas in optimization, Mcgraw-Hill, London, 1999, pp. 219-234.
[6]	M. Main and W. Savitch, “Data Structures and Other Objects Using C++,” 3rd Edtion, Pearson/Addison- Wesley, 2004.
[7]	R. Sedgewick, “Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching,” 3rd Edtion, Addison-Wesley, 1998.
[8]	D. Knuth, “The Art of Computer Programming, Volume 3: Sorting and Searching,” 2nd Edtion, Addison-Wesley, New York, 1998.
[9]	R. Neapolitan and K. Naimipour, “Foundations of Algorithms Using C++ Pseudocode,” 3rd Edtion, Jones and Bartlett Publishers, Inc., 2008.
[10]	C. Papadimitriou and K. Steiglitz, “Combinatorial Opti- mization: Algorithms and Complexity,” Prentice-Hall, New Haven, 1981.
[11]	L. Eshelman, “The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Non- traditional Genetic Recombination,” In: G. Rawlins, Ed., Foundations of Genetic Algorithms, Morgan Kauffman, San Mateo, 1991, pp. 265-283.
[12]	G. Harik, F. Lobo and D. Goldberg, “Compact Genetic Algorithm,” IEEE Transactions on Evolutionary Compu- tation, Vol. 3, No. 4, 1999, pp. 287-297.
[13]	J. Grefenstette, “Genetic Algorithms for Changing Enviro- nments,” Proceedings Parallel Problem Solving from Nature, Amsterdam, Vol. 2, 1992, pp. 137-144.
[14]	D. Goldberg and R. Lingle, “Alleles, Loci, and the Traveling Salesperson Problem,” Proceedings of the International Conference on Genetic Algorithms, Hills- dale, 1985, pp. 154-159.
[15]	S. Choi and B. Moon, “Normalization in Genetic Algorithms,” Genetic and Evolutionary Computation— GECCO-2003, Lecture Notes in Computer Science, Vol. 2723, Springer-Verlag, Berlin, 2003, pp. 862-873.
[16]	T. Bui, B. Moon, “On Multi-Dimensional Encoding/ Crossover,” Proceedings of the 6th International Confe- rence on Genetic Algorithms, San Francisco, 1995, pp. 49-56.
[17]	B. Kahng and B. Moon, “Toward More Powerful Recombinations,” Proceedings of the 6th International Conference on Genetic Algorithms, San Francisco, 1995, pp. 96-103.
[18]	C. Im, H. Jung and Y. Kim, “Hybrid Genetic Algorithm for Electromagnetic Topology Optimization,” IEEE Transactions on Magnetics, Vol. 39, No. 1, 2003, pp. 2163-2169.