Runtime analysis of search heuristics on software engineering problems

Harman M. The current state and future of search based software engineering. In: Proceedings of International Conference on Software Engineering / Future of Software Engineering 2007 (ICSE/FOSE 2007), IEEE Computer Society, 2007, 342–357

Sarker R, Mohammadian M, Yao X, eds. Evolutionary Optimization. Kluwer Academic Publishers, 2002

McMinn P. Search-based software test data generation: A survey. Software Testing, Verification and Reliability, 2004, 14(2): 105–156

Clark J A, Dolado J J, Harman M, Hierons R M, Jones B, Lumkin M, Mitchell B, Mancoridis S, Rees K, Roper M, Shepperd M. Reformulating software engineering as a search problem. IEEE Proceedings-Software, 2003, 150(3): 161–175

Poulding S, Emberson P, Bate I, Clark J A. An efficient experimental methodology for configuring search-based design algorithms. In: Proceedings of 10th IEEE High Assurance System Engineering Symposium (HASE’2007), 2007, 53–62

Wolpert D H, Macready W G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67–82

Harman M, McMinn P. A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation. In: Proceedings of the ISSTA 2007 Symposium, 2007, 73–84

Rudolph G. Finite markov chain results in evolutionary computation: A tour d’horizon. Fundamenta Informaticae, 1998, 35(1): 67–89

Droste S, Jansen T, Wegener I. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, 2006, 39(4): 525–544

Droste S, Jansen T, Wegener I. On the analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science, 2002, 276: 51–81

He J, Yao X. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 2004, 3(1): 21–35

Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In: Sarker R, Mohammadian M, Yao X, eds. Evolutionary Optimization. Dordrecht: Kluwer, 2002, 349–369

Oliveto P, Witt C. Simplified drift analysis for proving lower bounds in evolutionary computation. In: Proceedings of Parallel Problem Solving from Nature (PPSN’X). Berlin: Springer, LNCS, 2008, 5199: 82–91

Motwani R, Raghavan P. Randomized Algorithms. Cambridge: Cambridge University Press, 1995

Droste S, Jansen T, Wegener I. On the optimization of unimodal functions with the (1+1) evolutionary algorithm. In: Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN’V). London: Springer-Verlag, 1998, 13–22

Wegener I, Witt C. On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions. Journal of Discrete Algorithms, 2005, 3(1): 61–78

Jansen T, Wegener I. Real royal road functions-where crossover provably is essential. Discrete Applied Mathematics, 2005, 149(1–3): 111–125

Storch T, Wegener I. Real royal road functions for constant population size. Theoretical Computer Science, 2004, 320(1): 123–134

Witt C. Population size versus runtime of a simple evolutionary algorithm. Theoretical Computer Science, 2008, 403(1): 104–120

Giel O, Lehre P K. On the effect of populations in evolutionary multiobjective optimization. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation (GECCO’06). New York: ACM, 2006, 651–658

Friedrich T, Oliveto P S, Sudholt D, Witt C. Theoretical analysis of diversity mechanisms for global exploration. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation (GECCO’08). New York: ACM, 2008, 945–952

Friedrich T, Hebbinghaus N, Neumann F. Rigorous analyses of simple diversity mechanisms. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO’07), 2007, 1219–1225

Neumann F, Witt C. Runtime analysis of a simple ant colony optimization algorithm. In: Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC’2006). Berlin: Springer, LNCS, 2006, 4288: 618–627

Sudholt D, Witt C. Runtime analysis of binary pso. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation (GECCO’08). New York: ACM, 2008, 135–142

Giel O. Zur Analyse von randomisierten Suchheuristiken und Online-Heuristiken. PhD thesis. Dortmund: Universität Dortmund, 2005

Neumann F. Combinatorial Optimization and the Analysis of Randomized Search Heuristics. PhD thesis. Kiel: Christian-Albrechts-Universität zu Kiel, 2006

Jägersküpper J. P Probabilistic Analysis of Evolution Strategies Using Isotropic Mutations. PhD thesis. Dortmund: Universität Dortmund, 2006

Oliveto P S, He J, Yao X. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 2007, 4(1): 100–1

Giel O, Wegener I. Evolutionary algorithms and the maximum matching problem. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), 2003, 415–426

Scharnow J, Tinnefeld K, Wegener I. Fitness landscapes based on sorting and shortest paths problems. In: Proceedings of 7th Conference on Parallel Problem Solving from Nature (PPSN-VII). Berlin: Springer, LNCS, 2002, 2439: 54–63

Neumann F, Wegener I. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 2007, 378(1): 32–40

Doerr B, Klein C, Storch T. Faster evolutionary algorithms by superior graph representation. In: Proceedings of the 1st IEEE Symposium on Foundations of Computational Intelligence (FOCI’2007), 2007, 245–250

Oliveto P, He J, Yao X. Analysis of population-based evolutionary algorithms for the vertex cover problem. In: Proceedings of IEEE World Congress on Computational Intelligence (WCCI’08), 2008, 1563–1570

Witt C. Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS’05), LNCS, 2005, 3404: 44–56

Friedrich T, Hebbinghaus N, Neumann F, He J, Witt C. Approximating covering problems by randomized search heuristics using multiobjective models. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO’07). New York: ACM Press, 2007, 797–804

Lee D, Yannakakis M. Principles and methods of testing finite state machines-a survey. In: Proceedings of the IEEE, 1996, 84(8): 1090–1123

Lee D, Yannakakis M. Testing finite-state machines: state identification and verification. IEEE Transactions on Computers, 1994, 43(3): 306–320

Guo Q, Hierons R M, Harman M, Derderian K A. Computing unique input/output sequences using genetic algorithms. In: Proceedings of the 3rd International Workshop on Formal Approaches to Testing of Software (FATES’2003), LNCS, 2004, 2931: 164–177

Derderian K A, Hierons R M, Harman M, Guo Q. Automated unique input output sequence generation for conformance testing of fsms. The Computer Journal, 2006, 49(3): 331–344

Lehre P K, Yao X. Runtime analysis of (1+1) EA on computing unique input output sequences. In: Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC’07). IEEE Press, 2007, 1882–1889

Lehre P K, Yao X. Crossover can be constructive when computing unique input output sequences. In: Proceedings of the 7th International Conference on Simulated Evolution and Learning (SEAL’08), LNCS, 2008, 5361: 595–604

Arcuri A, Lehre P K, Yao X. Theoretical runtime analyses of search algorithms on the test data generation for the triangle classification problem. In: Proceedings of the 1st International Workshop on Search-Based Software Testing, 2008, 161–169

Droste S. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing, 2006, 5(3): 257–283

Chen T, Tang K, Chen G, Yao X. On the analysis of average time complexity of estimation of distribution algorithms. In: Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC’07). IEEE Press, 2007, 453–460

Sagarna R, Arcuri A, Yao X. Estimation of distribution algorithms for testing object oriented software. In: Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC’07). 2007, 438–444

Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, 2001

Wang Z, Tang K, Yao X. A multi-objective approach to testing resource allocation in modular software systems. In: Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC’08). IEEE Press, 2008, 1148–1153

Harman M, Lakhotia K, McMinn P. A multi-objective approach to search-based test data generation. In: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO’07). ACM, 2007, 1098–1105

Yoo S, Harman M. Pareto efficient multi-objective test case selection. In: Proceedings of the 2007 International Symposium on Software Testing and Analysis (ISSTA’ 07). ACM, 2007, 140–150

Zhang Y, Harman M, Mansouri S A. The multi-objective next release problem. In: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO’ 07). ACM, 2007, 1129–1137

Laumanns M, Thiele L, Zitzler E. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 170–182

Giel O. Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC’03). IEEE Press, 2003, 3: 1918–1925

Neumann F. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. In: Proceedings of Parallel Problem Solving from Nature (PPSN’VIII), 2004, 81–90

Arcuri A, Yao X. Coevolving programs and unit tests from their specification. In: Proceedings of IEEE International Conference on Automated Software Engineering (ASE), 2007, 397–400

Jansen T, Wiegand R P. The cooperative coevolutionary (1+1) EA. Evolutionary Computation, 2004, 12(4): 405–434