Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
作者： Pietro S. Oliveto , Carsten Witt
DOI:
关键词:
摘要: This erratum points out an error in the simplified drift theorem (SDT) [Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification of one its conditions sufficient to establish valid result. In many respects, new more general than before. We no longer assume Markov process nor finite search space. Furthermore, proof compact previous ones. Finally, applications SDT are revisited. turns all these either meet modified condition directly or by means few additional arguments.
arxiv.org
harvard.edu
128.84.21.199参考文章(10)
Oliver Giel, Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem symposium on theoretical aspects of computer science. pp. 415- 426 ,(2003) , 10.1007/3-540-36494-3_37
Julia Handl, Simon C. Lovell, Joshua Knowles, Multiobjectivization by Decomposition of Scalar Cost Functions parallel problem solving from nature. ,vol. 5199, pp. 31- 40 ,(2008) , 10.1007/978-3-540-87700-4_4
Per Kristian Lehre, Xin Yao, Crossover can be constructive when computing unique input–output sequences Soft Computing. ,vol. 15, pp. 1675- 1687 ,(2011) , 10.1007/S00500-010-0610-2
Bruce Hajek, Hitting-time and occupation-time bounds implied by drift analysis with applications Advances in Applied Probability. ,vol. 14, pp. 502- 525 ,(1982) , 10.2307/1426671
Dirk Sudholt, Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima Algorithmica. ,vol. 59, pp. 343- 368 ,(2011) , 10.1007/S00453-009-9384-2
Philipp Rohlfshagen, Per Kristian Lehre, Xin Yao, Dynamic evolutionary optimisation Proceedings of the 11th Annual conference on Genetic and evolutionary computation - GECCO '09. pp. 1713- 1720 ,(2009) , 10.1145/1569901.1570131
Per Kristian Lehre, Carsten Witt, Black-box search by unbiased variation genetic and evolutionary computation conference. pp. 1441- 1448 ,(2010) , 10.1145/1830483.1830747
Tianshi Chen, Per Kristian Lehre, Ke Tang, Xin Yao, When is an estimation of distribution algorithm better than an evolutionary algorithm congress on evolutionary computation. pp. 1470- 1477 ,(2009) , 10.1109/CEC.2009.4983116
Pietro S. Oliveto, Jun He, Xin Yao, Analysis of the $(1+1)$ -EA for Finding Approximate Solutions to Vertex Cover Problems IEEE Transactions on Evolutionary Computation. ,vol. 13, pp. 1006- 1029 ,(2009) , 10.1109/TEVC.2009.2014362
V. Chvátal, The tail of the hypergeometric distribution Discrete Mathematics. ,vol. 25, pp. 285- 287 ,(1979) , 10.1016/0012-365X(79)90084-0