Performance analysis of randomised search heuristics operating with a fixed budget

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid

60 Dyfyniadau (Scopus)
147 Wedi eu Llwytho i Lawr (Pure)


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.
Iaith wreiddiolSaesneg
Tudalennau (o-i)39-58
Nifer y tudalennau20
CyfnodolynTheoretical Computer Science
Rhif cyhoeddiC
Dyddiad ar-lein cynnar17 Meh 2013
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 14 Awst 2014

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Performance analysis of randomised search heuristics operating with a fixed budget'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn