Algorithm Configuration: Learning Policies for the Quick Termination of Poor Performers

Karapetyan, Daniel; Parkes, Andrew J.; St�tzle, Thomas

Abstract

One way to speed up the algorithm configuration task is to use short runs instead of long runs as much as possible, but without discarding the configurations that eventually do well on the long runs. We consider the problem of selecting the top performing configurations of Conditional Markov Chain Search (CMCS), a general algorithm schema that includes, for example, VNS. We investigate how the structure of performance on short tests links with those on long tests, showing that significant differences arise between test domains. We propose a “performance envelope” method to exploit the links; that learns when runs should be terminated, but that automatically adapts to the domain.

Citation

Karapetyan, D., Parkes, A. J., & Stützle, T. (2018, July). Algorithm Configuration: Learning Policies for the Quick Termination of Poor Performers. Presented at 12th International Conference, LION 12, Kalamata, Greece

• Presentation Conference Type: Edited Proceedings
• Conference Name: 12th International Conference, LION 12
• Start Date: Jul 10, 2018
• End Date: Jul 15, 2018
• Acceptance Date: May 14, 2018
• Online Publication Date: Dec 31, 2018
• Publication Date: Jan 1, 2019
• Deposit Date: Mar 17, 2019
• Publicly Available Date: Mar 18, 2019
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Pages: 220–224
• Series Title: Lecture notes in computer science
• Series Number: 11353
• Series ISSN: 1611-3349
• Book Title: Learning and Intelligent Optimization
• ISBN: 9783030053475
• DOI: https://doi.org/10.1007/978-3-030-05348-2_20
• Public URL: https://nottingham-repository.worktribe.com/output/1659549
• Publisher URL: https://link.springer.com/chapter/10.1007%2F978-3-030-05348-2_20
• Contract Date: Mar 17, 2019