Real-time algorithm configuration

Simple item page
dc.availability.bitstreamopenaccess
dc.contributor.advisorO'Sullivan, Barryen
dc.contributor.advisorBrown, Kennethen
dc.contributor.authorFitzgerald, Tadhg
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2021-05-13T09:07:30Z
dc.date.available2021-05-13T09:07:30Z
dc.date.issued2021-04
dc.date.submitted2021-04
dc.description.abstractThis dissertation presents a number of contributions to the field of algorithm configur- ation. In particular, we present an extension to the algorithm configuration problem, real-time algorithm configuration, where configuration occurs online on a stream of instances, without the need for prior training, and problem solutions are returned in the shortest time possible. We propose a framework for solving the real-time algorithm configuration problem, ReACT. With ReACT we demonstrate that by using the parallel computing architectures, commonplace in many systems today, and a robust aggregate ranking system, configuration can occur without any impact on performance from the perspective of the user. This is achieved by means of a racing procedure. We show two concrete instantiations of the framework, and show them to be on a par with or even exceed the state-of-the-art in offline algorithm configuration using empirical evaluations on a range of combinatorial problems from the literature. We discuss, assess, and provide justification for each of the components used in our framework instantiations. Specifically, we show that the TrueSkill ranking system commonly used to rank players’ skill in multiplayer games can be used to accurately es- timate the quality of an algorithm’s configuration using only censored results from races between algorithm configurations. We confirm that the order that problem instances arrive in influences the configuration performance and that the optimal selection of configurations to participate in races is dependent on the distribution of the incoming in- stance stream. We outline how to maintain a pool of quality configurations by removing underperforming configurations, and techniques to generate replacement configurations with minimal computational overhead. Finally, we show that the configuration space can be reduced using feature selection techniques from the machine learning literature, and that doing so can provide a boost in configuration performance.en
dc.description.statusNot peer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationFitzgerald, T. 2021. Real-time algorithm configuration. PhD Thesis, University College Cork.en
dc.identifier.endpage205en
dc.identifier.urihttps://hdl.handle.net/10468/11303
dc.language.isoenen
dc.publisherUniversity College Corken
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 2021, Tadhg Fitzgerald.en
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subjectOptimisationen
dc.subjectAlgorithm configurationen
dc.titleReal-time algorithm configurationen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD - Doctor of Philosophyen
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
react_thesis_final.pdf
Size:
5.37 MB
Format:
Adobe Portable Document Format
Description:
Full Text E-thesis
Download
Thumbnail Image
Name:
3. Tadhg Fitzgerald Thesis Submission Form - Tadhg Bartholomew Fitzgerald.pdf
Size:
528.07 KB
Format:
Adobe Portable Document Format
Description:
Submission for Examination Form
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
5.2 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Research Theses
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses
Insight Centre for Data Analytics - Doctoral Theses