期刊
THEORETICAL COMPUTER SCIENCE
卷 545, 期 -, 页码 39-58出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2013.06.007
关键词
Runtime analysis; Fixed budget computation; Random local search; (1+1) EA; OneMax; LeadingOnes; Jump; Ridge
资金
- German Academic Exchange Service (DAAD), University of Warwick in Coventry, UK
When for a difficult real-world optimisation problem no good problem-specific algorithm is available often randomised search heuristics are used. They are hoped to deliver good solutions in acceptable time. The theoretical analysis usually concentrates on the average time needed to find an optimal or approximately optimal solution. This matches neither the application in practice nor the empirical analysis since usually optimal solutions are not known and even if found cannot be recognised. More often the algorithms are stopped after some time. This motivates a theoretical analysis to concentrate on the quality of the best solution obtained after a pre-specified number of function evaluations called budget. Using this perspective two simple randomised search heuristics, random local search and the (1 + 1) evolutionary algorithm, are analysed on some well-known example problems. Upper and lower bounds on the expected quality of a solution for a fixed budget of function evaluations are proven. The analysis shows novel and challenging problems in the study of randomised search heuristics. It demonstrates the potential of this shift in perspective from expected run time to expected solution quality. (C) 2013 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据