Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Fixed budget computations : a different perspective on run time analysis

Tools
- Tools
+ Tools

Jansen, Thomas and Zarges, Christine (2012) Fixed budget computations : a different perspective on run time analysis. In: Fourteenth international conference on Genetic and evolutionary computation conference, Philadelphia, USA., 7-11 July 2012. Published in: Proceedings of the fourteenth international conference on genetic and evolutionary computation conference pp. 1325-1332. ISBN 9781450311779. doi:10.1145/2330163.2330347

Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1145/2330163.2330347

Request Changes to record.

Abstract

Randomised search heuristics are used in practice to solve difficult problems where no good problem-specific algorithm is known. They deliver a solution of acceptable quality in reasonable time in many cases. When theoretically analysing the performance of randomised search heuristics one usually considers the average time needed to find an optimal solution or one of a pre-specified approximation quality. This is very different from practice where usually the algorithm is stopped after some time. For a theoretical analysis this corresponds to investigating the quality of the solution obtained after a pre-specified number of function evaluations called budget. Such a perspective is taken here and two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on simple and well-known example functions. If the budget is significantly smaller than the expected time needed for optimisation the behaviour of the algorithms can be very different depending on the problem at hand. Precise analytical results are proven. They demonstrate novel and interesting challenges in the analysis of randomised search heuristics. The potential of this different perspective to provide a more practically useful theory is shown.

Item Type: Conference Item (Paper)
Divisions: Faculty of Science > Computer Science
Journal or Publication Title: Proceedings of the fourteenth international conference on genetic and evolutionary computation conference
Publisher: ACM
ISBN: 9781450311779
Book Title: Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference - GECCO '12
Official Date: 2012
Dates:
DateEvent
2012Published
Page Range: pp. 1325-1332
DOI: 10.1145/2330163.2330347
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Conference Paper Type: Paper
Title of Event: Fourteenth international conference on Genetic and evolutionary computation conference
Type of Event: Conference
Location of Event: Philadelphia, USA.
Date(s) of Event: 7-11 July 2012

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us