{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:49:24Z","timestamp":1769975364521,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,2,9]],"date-time":"2012-02-09T00:00:00Z","timestamp":1328745600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s00453-012-9616-8","type":"journal-article","created":{"date-parts":[[2012,2,8]],"date-time":"2012-02-08T19:42:00Z","timestamp":1328730120000},"page":"623-642","source":"Crossref","is-referenced-by-count":159,"title":["Black-Box Search by Unbiased Variation"],"prefix":"10.1007","volume":"64","author":[{"given":"Per Kristian","family":"Lehre","sequence":"first","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,9]]},"reference":[{"key":"9616_CR1","first-page":"67","volume-title":"Proceedings of the 10th International Workshop on Foundations of Genetic Algorithms (FOGA\u201909)","author":"G. Anil","year":"2009","unstructured":"Anil, G., Wiegand, R.P.: Black-box search by elimination of fitness functions. In: Proceedings of the 10th International Workshop on Foundations of Genetic Algorithms (FOGA\u201909), pp. 67\u201378. ACM Press, New York (2009)"},{"key":"9616_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-15844-5_1","volume-title":"Proceedings of the 11th international conference on Parallel Problem Solving from Nature (PPSN\u201910)","author":"S. B\u00f6ttcher","year":"2010","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the leadingones problem. In: Proceedings of the 11th international conference on Parallel Problem Solving from Nature (PPSN\u201910), pp. 1\u201310. Springer, Berlin (2010)"},{"key":"9616_CR3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1145\/1967654.1967670","volume-title":"Proceedings of the 11th International Workshop on Foundations of Genetic Algorithms (FOGA\u201911)","author":"S. Cathabard","year":"2011","unstructured":"Cathabard, S., Lehre, P.K., Yao, X.: Non-uniform mutation rates for problems with unknown solution lengths. In: Proceedings of the 11th International Workshop on Foundations of Genetic Algorithms (FOGA\u201911), pp. 173\u2013180. ACM, New York (2011)"},{"issue":"3","key":"9616_CR4","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: The tail of the hypergeometric distribution. Discrete Math. 25(3), 285\u2013287 (1979)","journal-title":"Discrete Math."},{"key":"9616_CR5","doi-asserted-by":"crossref","first-page":"1457","DOI":"10.1145\/1830483.1830749","volume-title":"Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201910)","author":"B. Doerr","year":"2010","unstructured":"Doerr, B., Fouz, M., Witt, C.: Quasirandom evolutionary algorithms. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201910), pp. 1457\u20131464. ACM, New York (2010)"},{"key":"9616_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/b99492","volume-title":"Ant Colony Optimization","author":"M. Dorigo","year":"2004","unstructured":"Dorigo, M., St\u00fctzle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)"},{"key":"9616_CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S. Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) Evolutionary Algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9616_CR8","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S. Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39(4), 525\u2013544 (2006)","journal-title":"Theory Comput. Syst."},{"key":"9616_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-3-540-46239-2_3","volume-title":"Proceedings of Genetic Programming, European Conference","author":"S. Droste","year":"2000","unstructured":"Droste, S., Wiesmann, D.: Metric based evolutionary algorithms. In: Proceedings of Genetic Programming, European Conference. LNCS, vol. 1802, pp. 29\u201343. Springer, Berlin (2000)"},{"key":"9616_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00453-010-9391-3","volume":"59","author":"H. Fournier","year":"2011","unstructured":"Fournier, H., Teytaud, O.: Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns. Algorithmica 59, 387\u2013408 (2011)","journal-title":"Algorithmica"},{"key":"9616_CR11","first-page":"415","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201903)","author":"O. Giel","year":"2003","unstructured":"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\u201903), pp. 415\u2013426 (2003)"},{"issue":"3","key":"9616_CR12","doi-asserted-by":"crossref","first-page":"502","DOI":"10.2307\/1426671","volume":"13","author":"B. Hajek","year":"1982","unstructured":"Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 13(3), 502\u2013525 (1982)","journal-title":"Adv. Appl. Probab."},{"key":"9616_CR13","doi-asserted-by":"crossref","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1) (2004)","DOI":"10.1023\/B:NACO.0000023417.31393.c7"},{"issue":"3","key":"9616_CR14","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/j.tcs.2007.02.042","volume":"39","author":"J. J\u00e4gersk\u00fcpper","year":"2007","unstructured":"J\u00e4gersk\u00fcpper, J.: Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theor. Comput. Sci. 39(3), 329\u2013347 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9616_CR15","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1162\/106365605774666921","volume":"13","author":"T. Jansen","year":"2005","unstructured":"Jansen, T., De Jong, K.A., Wegener, I.: On the choice of the offspring population size in evolutionary algorithms. Evol. Comput. 13(4), 413\u2013440 (2005)","journal-title":"Evol. Comput."},{"key":"9616_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1162\/evco.2010.18.1.18101","volume":"18","author":"T. Jansen","year":"2010","unstructured":"Jansen, T., Sudholt, D.: Analysis of an asymmetric mutation operator. Evol. Comput. 18, 1\u201326 (2010)","journal-title":"Evol. Comput."},{"issue":"1","key":"9616_CR17","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9616_CR18","volume-title":"Swarm Intelligence","author":"J. Kennedy","year":"2001","unstructured":"Kennedy, J., Eberhart, R.C.: Swarm Intelligence. Morgan Kaufmann, San Mateo (2001)"},{"issue":"4598","key":"9616_CR19","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"key":"9616_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-1539-5","volume-title":"Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation","author":"P. Larra\u00f1aga","year":"2002","unstructured":"Larra\u00f1aga, P., Lozano, J.A.: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic, Dordrecht (2002)"},{"key":"9616_CR21","doi-asserted-by":"crossref","first-page":"1441","DOI":"10.1145\/1830483.1830747","volume-title":"Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201910)","author":"P.K. Lehre","year":"2010","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201910), pp. 1441\u20131448. ACM, New York (2010)"},{"key":"9616_CR22","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"9616_CR23","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F. Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9616_CR24","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-3-540-92695-5_12","volume-title":"Proceedings of Learning and Intelligent Optimization (LION\u201908)","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Witt, C.: Ant colony optimization and the minimum spanning tree problem. In: Proceedings of Learning and Intelligent Optimization (LION\u201908), pp. 153\u2013166 (2008)"},{"key":"9616_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"F. Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity, 1st edn. Springer, New York (2010)","edition":"1"},{"key":"9616_CR26","doi-asserted-by":"crossref","first-page":"1455","DOI":"10.1109\/CEC.2009.4983114","volume-title":"Proceedings of the 10th IEEE Congress on Evolutionary Computation (CEC\u201909)","author":"P.S. Oliveto","year":"2009","unstructured":"Oliveto, P.S., Lehre, P.K., Neumann, F.: Theoretical analysis of rank-based mutation\u2014combining exploration and exploitation. In: Proceedings of the 10th IEEE Congress on Evolutionary Computation (CEC\u201909), pp. 1455\u20131462. IEEE, New York (2009)"},{"key":"9616_CR27","doi-asserted-by":"crossref","first-page":"2035","DOI":"10.1145\/2001576.2001850","volume-title":"Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201911)","author":"J.E. Rowe","year":"2011","unstructured":"Rowe, J.E., Vose, M.D.: Unbiased black box search algorithms. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO\u201911), pp. 2035\u20132042. ACM, New York (2011)"},{"key":"9616_CR28","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/978-3-540-73482-6_7","volume-title":"Proceedings of the 9th International Workshop on Foundations of Genetic Algorithms (FOGA\u201907)","author":"J.E. Rowe","year":"2007","unstructured":"Rowe, J.E., Vose, M.D., Wright, A.H.: Neighborhood graphs and symmetric genetic operators. In: Proceedings of the 9th International Workshop on Foundations of Genetic Algorithms (FOGA\u201907). LNCS, vol. 4436, pp. 110\u2013122 (2007)"},{"key":"9616_CR29","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-642-15844-5_13","volume-title":"Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN\u201910)","author":"D. Sudholt","year":"2010","unstructured":"Sudholt, D.: General lower bounds for the running time of evolutionary algorithms. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN\u201910), pp. 124\u2013133. Springer, Berlin (2010)"},{"key":"9616_CR30","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/11844297_3","volume-title":"Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN\u201906)","author":"O. Teytaud","year":"2006","unstructured":"Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN\u201906). LNCS, vol. 4193, pp. 21\u201331. Springer, Berlin (2006)"},{"key":"9616_CR31","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/11844297_4","volume-title":"Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN\u201906)","author":"O. Teytaud","year":"2006","unstructured":"Teytaud, O., Gelly, S., Mary, J.: On the ultimate convergence rates for isotropic algorithms and the best choices among various forms of isotropy. In: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN\u201906). LNCS, vol. 4193, pp. 32\u201341. Springer, Berlin (2006)"},{"key":"9616_CR32","first-page":"349","volume-title":"Evolutionary Optimization","author":"I. Wegener","year":"2002","unstructured":"Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker, R., Mohammadian, M., Yao, X. (eds.) Evolutionary Optimization, pp. 349\u2013369. Kluwer Academic, Dordrecht (2002)"},{"issue":"1","key":"9616_CR33","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/S0963548304006650","volume":"14","author":"I. Wegener","year":"2005","unstructured":"Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Comb. Probab. Comput. 14(1), 225\u2013247 (2005)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"9616_CR34","first-page":"65","volume":"14","author":"C. Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the (\u03bc+1) EA on simple pseudo-Boolean functions. Evol. Comput. 14(1), 65\u201386 (2006)","journal-title":"Evol. Comput."},{"key":"9616_CR35","unstructured":"Zarges, C.: Theoretical foundations of artificial immune systems. PhD thesis, Technische Universit\u00e4t Dortmund (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9616-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9616-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9616-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T08:29:05Z","timestamp":1640680145000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9616-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,9]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["9616"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9616-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,9]]}}}