Abstract
We already observed that evolutionary algorithms are usually thought of as general problem solvers. This implies that they are designed according to a general idea of how search should be implemented. In the case of evolutionary algorithms this idea stems from an understanding of natural evolution. More importantly, they are not designed in a way tailored toward a specific kind of optimization problem. We call this way of doing optimization while being in this sense oblivious to the concrete problem instance at hand black-box optimization. In this chapter we make precise what we mean when talking of black-box optimization. This allows us to recognize general limitations on the performance of any algorithm tackling the problem of black-box optimization. On one hand this helps us to get a clearer picture of what we can and cannot expect from evolutionary algorithms. On the other hand it even yields practically useful lower bounds on the performance of evolutionary algorithms. This is surprising good news since we consider a very general framework without concrete references to evolutionary algorithms that covers an enormous array of optimization algorithms.
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
References
G. Anil, R.P. Wiegand, Black-box search by elimination of fitness functions, in 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2009), Orlando, ed. by I. Garibay, T. Jansen, R.P. Wiegand, A.S. Wu (ACM, New York, 2009), pp. 67–78
A. Auger, O. Teytaud, Continuous lunches are free! in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), London (ACM, New York, 2007), pp. 916–922
B. Doerr, C. Winzen, Playing Mastermind with constant-size memory, in 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, ed. by C. Dürr, T. Wilke. Leibniz International Proceedings in Informatics, vol. 14 (Dagstuhl Publishing, Saarbrücken, 2012), pp. 441–452
B. Doerr, C. Winzen, Reducing the arity in unbiased black-box complexity. in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), Philadelphia (ACM, New York, 2012), pp. 1309–1316
B. Doerr, J. Lengler, T. Kötzing, C. Winzen, Black-box complexity of combinatorial problems, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), Dublin (ACM, New York, 2011), pp. 981–988
B. Doerr, D. Johannsen, T. Kötzing, P.K. Lehre, M. Wagner, C. Winzen, Faster black-box algorithms through higher arity operators, in 11th ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2011), Schwarzenberg, ed. by H.-G. Beyer, W.B. Langdon (ACM, New York, 2011), pp. 163–172
S. Droste, T. Jansen, I. Wegener, Perhaps not a free lunch but at least a free appetizer, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), Orlando (Springer, Berlin, 1999), pp. 833–839
S. Droste, T. Jansen, I. Wegener, Optimization with randomized search heuristics – the (A)NFL theorem, realistic scenarios, and difficult functions. Theor. Comput. Sci. 287(1), 131–144 (2002)
S. Droste, T. Jansen, K. Tinnefeld, I. Wegener, A new framework for the valuation of algorithms for black-box optimization, in Foundations of Genetic Algorithms 7 (FOGA), Torremolinos, ed. by K.A. De Jong, R. Poli, J.E. Rowe (Morgan Kaufmann, San Francisco, 2003), pp. 253–270
S. Droste, T. Jansen, I. Wegener, Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39(4), 525–544 (2006)
E.A. Duéñez-Guzán, M.D. Vose, No free lunch and benchmarks. Evol. Comput. (2013). doi:10.1162/EVCO_a_00077
C. Igel, M. Toussaint, On classes of functions for which no free lunch results hold. Inf. Process. Lett. 86(6), 317–321 (2003)
C. Igel, M. Toussaint, A no-free-lunch theorem for non-uniform distributions of target functions. J. Math. Model. Algorithms 3(4), 313–322 (2004)
W.B. Langdon, R. Poli, Foundations of Genetic Programming (Springer, Berlin, 2002)
P.K. Lehre, C. Witt, Black box search by unbiased variation, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), Portland (ACM, New York, 2010), pp. 1441–1448
J.E. Rowe, M.D. Vose, A.H. Wright, Reinterpreting the no free lunch. Evol. Comput. 17(1), 117–129 (2009)
C. Schumacher, M.D. Vose, L.D. Whitley, The no free lunch and problem description length, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), San Francisco (Morgan Kaufmann, San Francisco, 2001), pp. 565–570
A. Valsecchi, L. Vanneschi, G. Mauri, Optimisation speed and fair sets of functions, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), Portland (ACM, New York, 2010), pp. 1475–1476
I. Wegener, Complexity Theory: Exploring the Limits of Efficient Algorithms (Springer, Berlin, 2005)
D.H. Wolpert, W.G. Macready, No free lunch theorems for search. Technical report SFI-TR-9502-010, Santa Fe Institute, 1995
D.H. Wolpert, W.G. Macready, No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jansen, T. (2013). General Limits in Black-Box Optimization. In: Analyzing Evolutionary Algorithms. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17339-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-17339-4_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17338-7
Online ISBN: 978-3-642-17339-4
eBook Packages: Computer ScienceComputer Science (R0)