zbMATH — the first resource for mathematics

On the analysis of a dynamic evolutionary algorithm. (English) Zbl 1128.68118
Summary: Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the $$(1+1)$$ EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static $$(1+1)$$ EAs with a fixed mutation probability are compared with dynamic $$(1+1)$$ EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static $$(1+1)$$ EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic $$(1+1)$$ EA has exponential expected run time while a static $$(1+1)$$ EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.

MSC:
 68W40 Analysis of algorithms 68T05 Learning and adaptive systems in artificial intelligence 90C59 Approximation methods and heuristics in mathematical programming
Full Text:
References:
 [1] Bäck, T., Optimal mutation rates in genetic search, (), 2-8 [2] Bäck, T., An overview of parameter control methods by self-adaptation in evolutionary algorithms, Fundamenta informaticae, 35, 51-66, (1998) · Zbl 0941.68817 [3] Beyer, H.-G., Toward a theory of evolution strategies: some asymptotical results from the $$(1 + \lambda)$$-theory, Evol. comput., 1, 2, 165-188, (1993) [4] Droste, S.; Jansen, T.; Wegener, I., On the optimization of unimodal functions with the $$(1 + 1)$$ evolutionary algorithm, (), 13-22 [5] Droste, S.; Jansen, T.; Wegener, I., Dynamic parameter control in simple evolutionary algorithms, (), 275-294 · Zbl 0987.68098 [6] Droste, S.; Jansen, T.; Wegener, I., On the analysis of the $$(1 + 1)$$ evolutionary algorithm, Theoret. comput. sci., 276, 51-81, (2002) · Zbl 1002.68037 [7] Droste, S.; Jansen, T.; Rudolph, G.; Schwefel, H.-P.; Tinnefeld, K.; Wegener, I., Theory of evolutionary algorithms and genetic programming, (), 107-144 · Zbl 1102.68547 [8] Feller, W., An introduction to probability theory and its applications, vol. II, (1971), Wiley New York · Zbl 0219.60003 [9] Garnier, J.; Kallel, L.; Schoenauer, M., Rigorous hitting times for binary mutations, Evol. comput., 7, 2, 173-203, (1999) [10] Horn, J.; Goldberg, D.E.; Deb, K., Long path problems, (), 149-158 [11] Jansen, T.; Wegener, I., On the choice of the mutation probability for the $$(1 + 1)$$ EA, (), 89-98 [12] Mühlenbein, H., How genetic algorithms really work. mutation and hillclimbing, (), 15-25 [13] Rudolph, G., Convergence properties of evolutionary algorithms, (1997), Verlag Dr. Kovač Hamburg [14] Rudolph, G., How mutation and selection solve long path-problems in polynomial expected time, Evol. comput., 4, 2, 195-205, (1997) [15] I. Wegener, C. Witt, On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions, J. Discrete Algorithms (2005), in press · Zbl 1066.90143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.