{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T16:45:56Z","timestamp":1746204356355},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,1,9]],"date-time":"2010-01-09T00:00:00Z","timestamp":1262995200000},"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":[[2011,3]]},"DOI":"10.1007\/s00453-009-9384-2","type":"journal-article","created":{"date-parts":[[2010,1,8]],"date-time":"2010-01-08T14:10:37Z","timestamp":1262959837000},"page":"343-368","source":"Crossref","is-referenced-by-count":18,"title":["Hybridizing Evolutionary Algorithms with\u00a0Variable-Depth Search to Overcome Local Optima"],"prefix":"10.1007","volume":"59","author":[{"given":"Dirk","family":"Sudholt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,1,9]]},"reference":[{"key":"9384_CR1","doi-asserted-by":"crossref","first-page":"1574","DOI":"10.1057\/palgrave.jors.2602308","volume":"58","author":"U. Aickelin","year":"2007","unstructured":"Aickelin, U., Burke, E.K., Li, J.: An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. J. Oper. Res. Soc. 58, 1574\u20131585 (2007)","journal-title":"J. Oper. Res. Soc."},{"key":"9384_CR2","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, New York (2001)","edition":"2"},{"key":"9384_CR3","volume-title":"The Selfish Gene","author":"R. Dawkins","year":"1976","unstructured":"Dawkins, R.: The Selfish Gene. Oxford University Press, New York (1976)"},{"key":"9384_CR4","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, New York (2004)"},{"key":"9384_CR5","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":"1","key":"9384_CR6","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0304-3975(02)00094-4","volume":"287","author":"S. Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: Optimization with randomized search heuristics\u2014the (A)NFL theorem, realistic scenarios, and difficult functions. Theor. Comput. Sci. 287(1), 131\u2013144 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9384_CR7","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 3rd edn., vol. 1. Wiley, New York (1968)","edition":"3"},{"key":"9384_CR8","first-page":"1100","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201904)","author":"S. Fischer","year":"2004","unstructured":"Fischer, S.: A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201904), pp. 1100\u20131112. Springer, Berlin (2004)"},{"key":"9384_CR9","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1145\/1389095.1389276","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908)","author":"T. Friedrich","year":"2008","unstructured":"Friedrich, T., Oliveto, P.S., Sudholt, D., Witt, C.: Theoretical analysis of diversity mechanisms for global exploration. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908), pp. 945\u2013952. ACM Press, New York (2008)"},{"key":"9384_CR10","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. Springer, Berlin (2003)"},{"key":"9384_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu Search","author":"F.W. Glover","year":"1997","unstructured":"Glover, F.W., Laguna, M.: Tabu Search. Kluwer Academic, Amsterdam (1997)"},{"issue":"1","key":"9384_CR12","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1162\/evco.2003.11.1.29","volume":"11","author":"W.E. Hart","year":"2003","unstructured":"Hart, W.E.: Locally-adaptive and memetic evolutionary pattern search algorithms. Evol. Comput. 11(1), 29\u201351 (2003)","journal-title":"Evol. Comput."},{"key":"9384_CR13","series-title":"Studies in Fuzziness and Soft Computing","volume-title":"Recent Advances in Memetic Algorithms","year":"2004","unstructured":"Hart, W.E., Krasnogor, N., Smith, J.E. (eds.): Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, vol. 166. Springer, Berlin (2004)"},{"issue":"2","key":"9384_CR14","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1109\/TEVC.2003.810752","volume":"7","author":"H. Ishibuchi","year":"2003","unstructured":"Ishibuchi, H., Yoshida, T., Murata, T.: Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. Evol. Comput. 7(2), 204\u2013223 (2003)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"9384_CR15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.dam.2004.02.019","volume":"149","author":"T. Jansen","year":"2005","unstructured":"Jansen, T., Wegener, I.: Real royal road functions\u2014where crossover provably is essential. Discrete Appl. Math. 149, 111\u2013125 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"9384_CR16","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.tcs.2007.06.003","volume":"386","author":"T. Jansen","year":"2007","unstructured":"Jansen, T., Wegener, I.: A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation. Theor. Comput. Sci. 386(1\u20132), 73\u201393 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9384_CR17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M. Jerrum","year":"1998","unstructured":"Jerrum, M., Sorkin, G.B.: The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82(1\u20133), 155\u2013175 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9384_CR18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"B. Kernighan","year":"1970","unstructured":"Kernighan, B., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"issue":"1","key":"9384_CR19","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1023\/B:NACO.0000023419.83147.67","volume":"3","author":"N. Krasnogor","year":"2004","unstructured":"Krasnogor, N., Gustafson, S.: A study on the use of \u201cself-generation\u201d in memetic algorithms. Natural Comput. 3(1), 53\u201376 (2004)","journal-title":"Natural Comput."},{"issue":"5","key":"9384_CR20","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1109\/TEVC.2005.850260","volume":"9","author":"N. Krasnogor","year":"2005","unstructured":"Krasnogor, N., Smith, J.: A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Trans. Evol. Comput. 9(5), 474\u2013488 (2005)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"1","key":"9384_CR21","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.tcs.2006.03.007","volume":"358","author":"R. Kumar","year":"2006","unstructured":"Kumar, R., Banerjee, N.: Analysis of a multiobjective evolutionary algorithm on the 0\u20131 knapsack problem. Theor. Comput. Sci. 358(1), 104\u2013120 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"9384_CR22","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1057\/palgrave.jors.2601771","volume":"55","author":"J. Levine","year":"2004","unstructured":"Levine, J., Ducatelle, F.: Ant colony optimisation and local search for bin packing and cutting stock problems. J. Oper. Res. Soc. 55(7), 705\u2013716 (2004)","journal-title":"J. Oper. Res. Soc."},{"key":"9384_CR23","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"key":"9384_CR24","series-title":"International Series in Operations Research & Management Science","first-page":"321","volume-title":"Handbook of Metaheuristics","author":"H.R. Louren\u00e7o","year":"2002","unstructured":"Louren\u00e7o, H.R., Martin, O., St\u00fctzle, T.: Iterated local search. In: Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 57, pp. 321\u2013353. Kluwer Academic, Norwell (2002)"},{"key":"9384_CR25","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"issue":"11","key":"9384_CR26","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N. Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., Hansen, P.: Variable neighborhood search. Comput. OR 24(11), 1097\u20131100 (1997)","journal-title":"Comput. OR"},{"issue":"2","key":"9384_CR27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1109\/TCBB.2007.070202","volume":"4","author":"F. Neri","year":"2007","unstructured":"Neri, F., Toivanen, J., Cascella, G.L., Ong, Y.S.: An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE\/ACM Trans. Comput. Biol. Bioinform. 4(2), 264\u2013278 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9384_CR28","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/978-3-540-87700-4_8","volume-title":"Parallel Problem Solving from Nature (PPSN X)","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Reichel, J.: Approximating minimum multicuts by evolutionary multi-objective algorithms. In: Parallel Problem Solving from Nature (PPSN X). LNCS, vol. 5199, pp. 72\u201381. Springer, Berlin (2008)"},{"issue":"1","key":"9384_CR29","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":"9384_CR30","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1145\/1389095.1389250","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008)","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Reichel, J., Skutella, M.: Computing minimum cuts by randomized search heuristics. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), pp. 779\u2013786. ACM Press, New York (2008)"},{"key":"9384_CR31","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/978-3-540-87527-7_12","volume-title":"Proceedings of the Sixth International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201908)","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Rigorous analyses for the combination of ant colony optimization and local search. In: Proceedings of the Sixth International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201908). LNCS, vol. 5217, pp. 132\u2013143. Springer, Berlin (2008)"},{"key":"9384_CR32","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-540-87700-4_9","volume-title":"Parallel Problem Solving from Nature (PPSN X)","author":"P.S. Oliveto","year":"2008","unstructured":"Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Parallel Problem Solving from Nature (PPSN X). LNCS, vol. 5199, pp. 82\u201391. Springer, Berlin (2008)"},{"issue":"3","key":"9384_CR33","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s11633-007-0281-3","volume":"4","author":"P.S. Oliveto","year":"2007","unstructured":"Oliveto, P.S., He, J., Yao, X.: Computational complexity analysis of evolutionary algorithms for combinatorial optimization: a decade of results. Int. J. Autom. Comput. 4(3), 281\u2013293 (2007)","journal-title":"Int. J. Autom. Comput."},{"issue":"1","key":"9384_CR34","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/TSMCB.2005.856143","volume":"36","author":"Y.S. Ong","year":"2006","unstructured":"Ong, Y.S., Lim, M.H., Zhu, N., Wong, K.W.: Classification of adaptive memetic algorithms: a comparative study. IEEE Trans. Syst. Man Cybern., Part B 36(1), 141\u2013152 (2006)","journal-title":"IEEE Trans. Syst. Man Cybern., Part B"},{"key":"9384_CR35","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9384_CR36","first-page":"947","volume-title":"Proceedings of the Genetic and Evolutionary Compution Conference (GECCO\u201907)","author":"J. Reichel","year":"2007","unstructured":"Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. In: Proceedings of the Genetic and Evolutionary Compution Conference (GECCO\u201907), pp. 947\u2013954. ACM Press, New York (2007)"},{"key":"9384_CR37","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1007\/978-3-540-87700-4_81","volume-title":"Parallel Problem Solving from Nature (PPSN X)","author":"K. Sindhya","year":"2008","unstructured":"Sindhya, K., Deb, K., Miettinen, K.: A local search based evolutionary multi-objective optimization approach for fast and accurate convergence. In: Parallel Problem Solving from Nature (PPSN X). LNCS, vol. 5199, pp. 815\u2013824. Springer, Berlin (2008)"},{"issue":"1","key":"9384_CR38","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1109\/TSMCB.2006.883273","volume":"37","author":"J. Smith","year":"2007","unstructured":"Smith, J.: Coevolving memetic algorithms: A review and progress report. IEEE Trans. Syst. Man Cybern., Part B 37(1), 6\u201317 (2007)","journal-title":"IEEE Trans. Syst. Man Cybern., Part B"},{"key":"9384_CR39","doi-asserted-by":"crossref","unstructured":"Stoer, M., Wagner, F.: A simple min cut algorithm. In: Proceedings of the Second Annual European Symposium on Algorithms (ESA\u201994), pp. 141\u2013147 (1994)","DOI":"10.1007\/BFb0049404"},{"key":"9384_CR40","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1145\/1068009.1068202","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201905)","author":"D. Sudholt","year":"2005","unstructured":"Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201905), pp. 1161\u20131167. ACM Press, New York (2005)"},{"key":"9384_CR41","series-title":"LNCS","first-page":"359","volume-title":"Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC\u201906)","author":"D. Sudholt","year":"2006","unstructured":"Sudholt, D.: Local search in evolutionary algorithms: the impact of the local search frequency. In: Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC\u201906). LNCS, vol. 4288, pp. 359\u2013368. Springer, Berlin (2006)"},{"key":"9384_CR42","first-page":"493","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201906)","author":"D. Sudholt","year":"2006","unstructured":"Sudholt, D.: On the analysis of the (1+1)\u00a0memetic algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201906), pp. 493\u2013500. ACM Press, New York (2006)"},{"key":"9384_CR43","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/1389095.1389251","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908)","author":"D. Sudholt","year":"2008","unstructured":"Sudholt, D.: Memetic algorithms with variable-depth search to overcome local optima. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908), pp. 787\u2013794. ACM Press, New York (2008)"},{"issue":"26","key":"9384_CR44","doi-asserted-by":"crossref","first-page":"2511","DOI":"10.1016\/j.tcs.2009.03.003","volume":"410","author":"D. Sudholt","year":"2009","unstructured":"Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410(26), 2511\u20132528 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9384_CR45","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/11523468_48","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u201905)","author":"I. Wegener","year":"2005","unstructured":"Wegener, I.: Simulated annealing beats Metropolis in combinatorial optimization. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u201905). LNCS, vol. 3580, pp. 589\u2013601. Springer, Berlin (2005)"},{"key":"9384_CR46","series-title":"LNCS","first-page":"44","volume-title":"Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS\u201905)","author":"C. Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS\u201905). LNCS, vol. 3404, pp. 44\u201356. Springer, Berlin (2005)"},{"issue":"5","key":"9384_CR47","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1109\/TEVC.2006.888929","volume":"11","author":"Y. Zhou","year":"2007","unstructured":"Zhou, Y., He, J.: A runtime analysis of evolutionary algorithms for constrained optimization problems. IEEE Trans. Evol. Comput. 11(5), 608\u2013619 (2007)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9384-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9384-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9384-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:05Z","timestamp":1559123105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9384-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,9]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["9384"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9384-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,9]]}}}