Analyzing Randomized Search Heuristics: Tools from Probability Theory
2011; World Scientific; Linguagem: Inglês
10.1142/9789814282673_0001
ISSN1793-849X
Autores Tópico(s)Data Management and Algorithms
ResumoSeries on Theoretical Computer ScienceTheory of Randomized Search Heuristics, pp. 1-20 (2011) No AccessAnalyzing Randomized Search Heuristics: Tools from Probability TheoryBenjamin DoerrBenjamin DoerrMax-Planck-Institut für Informatik, Campus E1 4, 66123 Saarbrücken, Germanyhttps://doi.org/10.1142/9789814282673_0001Cited by:33 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary material like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general interest, seem to be particularly useful in the analysis of randomized search heuristics. FiguresReferencesRelatedDetailsCited By 33On the integrality gap of binary integer programs with Gaussian dataSander Borst, Daniel Dadush, Sophie Huiberts and Samarth Tiwari25 May 2022 | Mathematical Programming, Vol. 197, No. 2Analysis of Evolutionary Algorithms on Fitness Function With Time-Linkage PropertyWeijie Zheng, Huanhuan Chen and Xin Yao1 Aug 2021 | IEEE Transactions on Evolutionary Computation, Vol. 25, No. 4Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsFeng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing and Frank Neumann20 July 2020 | Algorithmica, Vol. 82, No. 10Probabilistic Bounds for Binary Classification of Large Data SetsVěra Kůrková and Marcello Sanguineti3 April 2019Efficient randomized test-and-set implementationsGeorge Giakkoupis and Philipp Woelfel1 June 2019 | Distributed Computing, Vol. 32, No. 6Classification by Sparse Neural NetworksVera Kurkova and Marcello Sanguineti1 Sep 2019 | IEEE Transactions on Neural Networks and Learning Systems, Vol. 30, No. 9Optimal strong stationary times for random walks on the chambers of a hyperplane arrangementEvita Nestoridi25 September 2018 | Probability Theory and Related Fields, Vol. 174, No. 3-4Evolving boolean functions with conjunctions and disjunctions via genetic programmingBenjamin Doerr, Andrei Lissovoi and Pietro S. Oliveto13 July 2019Runtime analysis for self-adaptive mutation ratesBenjamin Doerr, Carsten Witt and Jing Yang2 July 2018Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problemAndrew M. Sutton2 July 2018On the runtime analysis of selection hyper-heuristics with adaptive learning periodsBenjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto and John Alasdair Warwicker2 July 2018OneMax in Black-Box Models with Several RestrictionsCarola Doerr and Johannes Lengler25 May 2016 | Algorithmica, Vol. 78, No. 2Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF FormulasBenjamin Doerr, Frank Neumann and Andrew M. Sutton29 August 2016 | Algorithmica, Vol. 78, No. 2Towards a Runtime Comparison of Natural and Artificial EvolutionTiago Paixão, Jorge Pérez Heredia, Dirk Sudholt and Barbora Trubenová19 September 2016 | Algorithmica, Vol. 78, No. 2Comparing Apples and Oranges: Query Trade-off in Submodular MaximizationNiv Buchbinder, Moran Feldman and Roy Schwartz1 May 2017 | Mathematics of Operations Research, Vol. 42, No. 2The Unrestricted Black-Box Complexity of Jump FunctionsMaxim Buzdalov, Benjamin Doerr and Mikhail Kever1 Dec 2016 | Evolutionary Computation, Vol. 24, No. 4Optimal Parameter Settings for the (1 + λ, λ) Genetic AlgorithmBenjamin Doerr20 July 2016The Right Mutation Strength for Multi-Valued Decision VariablesBenjamin Doerr, Carola Doerr and Timo Koetzing20 July 2016The Impact of Random Initialization on the Runtime of Randomized Search HeuristicsBenjamin Doerr and Carola Doerr23 June 2015 | Algorithmica, Vol. 75, No. 3Simple and optimal randomized fault-tolerant rumor spreadingBenjamin Doerr, Carola Doerr, Shay Moran and Shlomo Moran31 December 2014 | Distributed Computing, Vol. 29, No. 2Satisfiability on Mixed InstancesRuiwen Chen and Rahul Santhanam14 January 2016k-Bit Mutation with Self-Adjusting k Outperforms Standard Bit MutationBenjamin Doerr, Carola Doerr and Jing Yang31 August 2016The Compact Genetic Algorithm is Efficient under Extreme Gaussian NoiseTobias Friedrich, Timo Kotzing, Martin S. Krejca and Andrew M. Sutton1 Jan 2016 | IEEE Transactions on Evolutionary Computation, Vol. 75Evolutionary Computation for Real-World ProblemsMohammad Reza Bonyadi and Zbigniew Michalewicz28 June 2015Unbiased Black-Box Complexities of Jump FunctionsBenjamin Doerr, Carola Doerr and Timo Kötzing1 Dec 2015 | Evolutionary Computation, Vol. 23, No. 4A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMaxBenjamin Doerr and Carola Doerr11 July 2015Optimal Parameter Choices Through Self-AdjustmentBenjamin Doerr and Carola Doerr11 July 2015First Steps Towards a Runtime Comparison of Natural and Artificial EvolutionTiago Paixao, Jorge Pérez Heredia, Dirk Sudholt and Barbora Trubenova11 July 2015Money for NothingAxel de Perthuis de Laillevault, Benjamin Doerr and Carola Doerr11 July 2015Unbiased black-box complexities of jump functionsBenjamin Doerr, Carola Doerr and Timo Kötzing12 July 2014The impact of random initialization on the runtime of randomized search heuristicsBenjamin Doerr and Carola Doerr12 July 2014Discovery of Emergent Sorting Behavior using Swarm Intelligence and Grid-Enabled Genetic AlgorithmsDimitris Kalles, Alexis Kaporis, Vassiliki Mperoukli and Anthony Chatzinouskas1 Jan 2014Lower bounds for the runtime of a global multi-objective evolutionary algorithmBenjamin Doerr, Bojana Kodric and Marco Voigt1 Jun 2013 Theory of Randomized Search HeuristicsMetrics History PDF download
Referência(s)