Abstract
Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many different situations. However, the theory on these algorithms is still in its infancy. Here it is discussed how and why such a theory should be developed. Afterwards, some fundamental results on evolutionary algorithms are presented in order to show how theoretical results on randomized search heuristics can be proved and how they contribute to the understanding of evolutionary algorithms.
This work was supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Center “Computational Intelligence” (531).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bäck, T. (1998). An overview of parameter control methods by self-adaptation in evolutionary algorithms. Fundamenta Informaticae 32, 51–66.
Bäck, T., Fogel, D. B., and Michalewicz, Z. (Eds.) (1997). Handbook of Evolutionary Computation. Oxford Univ. Press, Oxford.
Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1990). Introduction to Algorithms. MIT Press.
Droste, S., Jansen, T., and Wegener, I. (1998). On the optimization of unimodal functions with the (1 + 1) evolutionary algorithm. Proc. of PPSN V (Parallel Problem Solving from Nature), LNCS 1648, 13–22.
Droste, S., Jansen, T., and Wegener, I. (2001). On the analysis of the (1 + 1) evolutionary algorithm. To appear: Theoretical Computer Science.
Fogel, D. B. (1995). Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press.
Forrest, S., and Mitchell, M. (1993). Relative building-block fitness and the building-block hypothesis. Proc. of FOGA’ 1993 (2nd Workshop Foundations of Genetic Algorithms), Morgan Kaufmann.
Garnier, J., Kallel, L., and Schoenauer, M. (1999). Rigorous hitting times for binary mutations. Evolutionary Computation 7, 173–203.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
Hochbaum, D. S. (Ed.) (1997). Approxiamtion Algorithms for NP-Hard Problems. PWS Publ. Co.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press.
Jansen, T., and Wegener, I. (1999). On the analysis of evolutionary algorithms-a proof that crossover really can help. Proc. of ESA’99 (European Symp. On Algorithms), LNCS 1643, 184–193.
Jansen, T., and Wegener, I. (2000a). On the choice of the mutation probability for the (1 + 1)EA. Proc. of PPSN VI (Parallel Problem Solving from Nature), LNCS 1917, 89–98.
Jansen, T., and Wegener, I. (2000b). Evolutionary algorithms-how to cope with plateaus of constant fitness and when to reject strings of the same fitness. To appear: IEEE Trans. on Evolutionary Computation.
Jansen, T., and Wegener, I. (2001a). Real royal road functions-where crossover provably is essential. To appear: GECCO’2001.
Jansen, T., and Wegener, I. (2001b). On the analysis of a dynamic evolutionary algorithm. Submitted: ESA’2001.
Mitchell, M., Forrest, S., and Holland, J. H. (1992). The Royal Road function for genetic algorithms: Fitness landscapes and GA performance. Proc. of 1st European Conf. on Artificial Life, 245–254, MIT Press.
Mitchell, M., Holland, J. H., and Forrest, S. (1994). When will a genetic algorithm outperform hill climbing. In J. Cowan, G. Tesauro, and J. Alspector (Eds.): Advances in Neural Information Processing Systems. Morgan Kaufman.
Motwani, R., and Raghavan, P. (1995). Randomized Algorithms. Cambridge Univ. Press.
Rabani, Y., Rabinovich, Y., and Sinclair, A. (1998). A computational view of population genetics. Random Structures and Algorithms 12, 314–334.
Schwefel, H.-P. (1995). Evolution and Optimum Seeking. Wiley.
Watson, R. A. (2000). Analysis of recombinative algorithms on a non-separable building-block problem. Proc. of FOGA’2000 (6.Workshop Foundations of Genetic Algorithms), to appear.
Wegener, I. (2000). On the expected runtime and the success probability of evolutionary algorithms. Proc. ofWG’2000 (26.Workshop on Graph-Theoretic Concepts in Computer Science), LNCS 1928, 1–10.
Wegener, I., and Witt, C. (2001). On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions. Submitted: Journal of Discrete Algorithms.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wegener, I. (2001). Theoretical Aspects of Evolutionary Algorithms. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48224-5_6
Download citation
DOI: https://doi.org/10.1007/3-540-48224-5_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42287-7
Online ISBN: 978-3-540-48224-6
eBook Packages: Springer Book Archive