Unlimited Budget Analysis

Jun He; Thomas Jansen; Christine Zarges

doi:10.1145/3319619.3322009

Unlimited Budget Analysis

Jun He, Thomas Jansen, Christine Zarges

Department of Computer Science

Nottingham Trent University

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

6 Citations (Scopus)

258 Downloads (Pure)

Abstract

Performance analysis of randomised search heuristics is a rapidly growing and developing field. We contribute to its further development by introducing a novel analytical perspective that we call unlimited budget analysis. It has its roots in the very recently introduced approximation error analysis and bears some similarity to fixed budget analysis. The focus is on the progress an optimisation heuristic makes towards a set goal, not on the time it takes to reach this goal, setting it far apart from runtime analysis. We present the framework, apply it to simple mutation-based algorithms, covering both, local and global search. We provide analytical results for a number of simple example functions for unlimited budget analysis and compare them to results derived within the fixed budget framework for the same algorithms and functions.

Original language	English
Title of host publication	GECCO 2019 Companion
Subtitle of host publication	Proceedings of the 2019 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery
Pages	427-428
Number of pages	2
ISBN (Electronic)	9781450367486
DOIs	https://doi.org/10.1145/3319619.3322009
Publication status	Published - 13 Jul 2019
Event	GECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 https://gecco-2019.sigevo.org

Publication series

Name	Proceedings of the Genetic and Evolutionary Computation Conference

Conference

Conference	GECCO 2019: The Genetic and Evolutionary Computation Conference
Country/Territory	Czech Republic
City	Prague
Period	13 Jul 2019 → 17 Jul 2019
Internet address	https://gecco-2019.sigevo.org

Keywords

Performance measures
Theory
Working principles of evolutionary computing

Access to Document

10.1145/3319619.3322009

pos241s1-file1Accepted author manuscript, 506 KB

Permanent link

Persistent link

Cite this

@inproceedings{3687a9e8140a4304b707536fce31347a,

title = "Unlimited Budget Analysis",

abstract = "Performance analysis of randomised search heuristics is a rapidly growing and developing field. We contribute to its further development by introducing a novel analytical perspective that we call unlimited budget analysis. It has its roots in the very recently introduced approximation error analysis and bears some similarity to fixed budget analysis. The focus is on the progress an optimisation heuristic makes towards a set goal, not on the time it takes to reach this goal, setting it far apart from runtime analysis. We present the framework, apply it to simple mutation-based algorithms, covering both, local and global search. We provide analytical results for a number of simple example functions for unlimited budget analysis and compare them to results derived within the fixed budget framework for the same algorithms and functions.",

keywords = "Performance measures, Theory, Working principles of evolutionary computing",

author = "Jun He and Thomas Jansen and Christine Zarges",

note = "Funding Information: The work is supported by EPSRC under Grant No. EP/I009809/1. Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.; GECCO 2019: The Genetic and Evolutionary Computation Conference ; Conference date: 13-07-2019 Through 17-07-2019",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3322009",

language = "English",

series = "Proceedings of the Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery",

pages = "427--428",

booktitle = "GECCO 2019 Companion",

address = "United States of America",

url = "https://gecco-2019.sigevo.org",

}

He, J, Jansen, T & Zarges, C 2019, Unlimited Budget Analysis. in GECCO 2019 Companion: Proceedings of the 2019 Genetic and Evolutionary Computation Conference. Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, pp. 427-428, GECCO 2019: The Genetic and Evolutionary Computation Conference, Prague, Czech Republic, 13 Jul 2019. https://doi.org/10.1145/3319619.3322009

Unlimited Budget Analysis. / He, Jun; Jansen, Thomas ; Zarges, Christine.
GECCO 2019 Companion: Proceedings of the 2019 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, 2019. p. 427-428 (Proceedings of the Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - Unlimited Budget Analysis

AU - He, Jun

AU - Jansen, Thomas

AU - Zarges, Christine

N1 - Funding Information: The work is supported by EPSRC under Grant No. EP/I009809/1. Publisher Copyright: © 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.

PY - 2019/7/13

Y1 - 2019/7/13

N2 - Performance analysis of randomised search heuristics is a rapidly growing and developing field. We contribute to its further development by introducing a novel analytical perspective that we call unlimited budget analysis. It has its roots in the very recently introduced approximation error analysis and bears some similarity to fixed budget analysis. The focus is on the progress an optimisation heuristic makes towards a set goal, not on the time it takes to reach this goal, setting it far apart from runtime analysis. We present the framework, apply it to simple mutation-based algorithms, covering both, local and global search. We provide analytical results for a number of simple example functions for unlimited budget analysis and compare them to results derived within the fixed budget framework for the same algorithms and functions.

AB - Performance analysis of randomised search heuristics is a rapidly growing and developing field. We contribute to its further development by introducing a novel analytical perspective that we call unlimited budget analysis. It has its roots in the very recently introduced approximation error analysis and bears some similarity to fixed budget analysis. The focus is on the progress an optimisation heuristic makes towards a set goal, not on the time it takes to reach this goal, setting it far apart from runtime analysis. We present the framework, apply it to simple mutation-based algorithms, covering both, local and global search. We provide analytical results for a number of simple example functions for unlimited budget analysis and compare them to results derived within the fixed budget framework for the same algorithms and functions.

KW - Performance measures

KW - Theory

KW - Working principles of evolutionary computing

UR - http://www.scopus.com/inward/record.url?scp=85070623891&partnerID=8YFLogxK

U2 - 10.1145/3319619.3322009

DO - 10.1145/3319619.3322009

M3 - Conference Proceeding (Non-Journal item)

T3 - Proceedings of the Genetic and Evolutionary Computation Conference

SP - 427

EP - 428

BT - GECCO 2019 Companion

PB - Association for Computing Machinery

T2 - GECCO 2019: The Genetic and Evolutionary Computation Conference

Y2 - 13 July 2019 through 17 July 2019

ER -

Unlimited Budget Analysis

Abstract

Publication series

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this