Theory of Randomized Search Heuristics
- PDF / 139,474 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 199 Views
Theory of Randomized Search Heuristics Anne Auger · Carsten Witt
Received: 6 August 2012 / Accepted: 21 August 2012 / Published online: 29 August 2012 © Springer Science+Business Media, LLC 2012
Randomized search heuristics such as evolutionary algorithms, evolution strategies, ant colony optimizers etc. are optimization algorithms that can be applied to a wide class of problems ranging from combinatorial to continuous optimization. They are popular in practice because they are generally easy to implement, their application requires little assumptions on the function to be optimized and provide solutions to a problem in a comparatively short time. Their theoretical analysis has gained momentum over the past decade. Runtime analysis of various randomized search heuristics, using and adapting methods from the analysis of randomized algorithms, has emerged as a new line of research, and general theoretical tools that can be applied to different algorithms have been developed. In 2007, a theory track dedicated to analyses of this kind was established at the Genetic and Evolutionary Computation Conference (GECCO), one of the largest conference on randomized search heuristics. This special issue on Theory of Randomized Search Heuristics of Algorithmica contains papers that are extensions or follow-ups of papers from the theory track of the GECCO held July 7–11, 2010 in Portland, Oregon. Each article has undergone a new rigorous journal review process from which four papers have been selected. They contribute to improve our theoretical knowledge about randomized search heuristics as well as they enhance general tools and techniques for their analysis. The paper Black-Box Search by Unbiased Variation by Lehre and Witt (doi:10. 1007/s00453-012-9616-8) reconsiders and refines the black-box model of randomized search heuristics originally proposed by Droste, Jansen and Wegener (Theory A. Auger INRIA Saclay-Ile-de-France, University Paris XI, Bat. 490, 91405 Orsay, France e-mail: [email protected] C. Witt () DTU Informatics, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark e-mail: [email protected]
622
Algorithmica (2012) 64:621–622
Comput. Syst. 39(4):525–544, 2006). As a crucial restriction that is typically met by search heuristics, unbiasedness of the sampling distribution of variation operators is introduced. On classical test problems, upper and lower bounds on the black-box complexity are proved, which match the running time of basic search heuristics more closely than the original model. The paper A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems by Sudholt and Thyssen (doi:10.1007/s00453-011-9606-2) puts forward the running time analysis of ant colony optimization in combinatorial optimization. For the first time, optimization under noise is considered in this context. The dependency of running time and noise strength is investigated in different noise models. Moreover, results on the approximation capability are proved. The paper Multiplicative Drift Analysis by Doerr, Johannsen and W
Data Loading...
