Drift analysis and average time complexity of evolutionary algorithms

Ambati, 1991, Heuristic combinatorial optimization by simulated Darwinian evolution: A polynomial time algorithm for the traveling salesman problem, Biological Cybernetics, 65, 31, 10.1007/BF00197287

Droste, 1998, A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with boolean inputs, Evolutionary Computation, 6, 185, 10.1162/evco.1998.6.2.185

Eiben, 1999, Theory of evolutionary algorithms: A bird eye view, Theoret. Comput. Sci., 229, 3, 10.1016/S0304-3975(99)00089-4

Fogel, 1991

Fogel, 1993, Empirical estimation of the computation required to discover approximate solutions to the traveling salesman problem using evolutionary programming, 56

Goldberg, 1989

Hajek, 1982, Hitting time and occupation time bounds implied by drift analysis with applications, Adv. Appl. Probab., 14, 502, 10.2307/1426671

He, 1998, The computational time analysis of genetic algorithms, 440

He, 1999, The computational time of genetic algorithms for fully deceptive problem, Chinese J. Comput., 21, 999

He, 1999, On the convergence rate of genetic algorithms, Theoret. Comput. Sci., 229, 23, 10.1016/S0304-3975(99)00091-2

Holland, 1992

Karp, 1972, Reducibility among combinatorial problems, 85

Khuri, 1994, An evolutionary approach to combinatorial optimization problems, 66

Michalewicz, 1996

Neveu, 1975

Rudolph, 1996, How mutation and selection solve long path problem in polynomial expected time, Evolutionary Computation, 4, 195, 10.1162/evco.1996.4.2.195

Rudolph, 1997

Rudolph, 1998, Finite Markov chain results in evolutionary computation: A tour d'horizon, Fundamenta Informaticae, 35, 67, 10.3233/FI-1998-35123405

Schwefel, 1995

Sasaki, 1988, The time complexity of maximum matching by simulated annealing, J. ACM, 35, 387, 10.1145/42282.46160

Tweedie, 1976, Criteria for classifying general Markov chains, Adv. Appl. Probab., 8, 737, 10.2307/1425932

van Nimwegen, 1999, Statistical dynamics of the royal road genetic algorithm, Theoret. Comput. Sci., 229, 41, 10.1016/S0304-3975(99)00119-X

E. van Nimwegen, J.P. Crutchfield, Optimizing epochal evolutionary search: Population-size dependent theory, Machine Learning J., to appear