Automatically improving the anytime behaviour of optimisation algorithms

Manuel López-Ibáñez*, Thomas Stützle

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

187 Downloads (Pure)

Abstract

Optimisation algorithms with good anytime behaviour try to return as high-quality solutions as possible independently of the computation time allowed. Designing algorithms with good anytime behaviour is a difficult task, because performance is often evaluated subjectively, by plotting the trade-off curve between computation time and solution quality. Yet, the trade-off curve may be modelled also as a set of mutually nondominated, bi-objective points. Using this model, we propose to combine an automatic configuration tool and the hypervolume measure, which assigns a single quality measure to a nondominated set. This allows us to improve the anytime behaviour of optimisation algorithms by means of automatically finding algorithmic configurations that produce the best nondominated sets. Moreover, the recently proposed weighted hypervolume measure is used here to incorporate the decision-maker's preferences into the automatic tuning procedure. We report on the improvements reached when applying the proposed method to two relevant scenarios: (i) the design of parameter variation strategies for MAX-MIN Ant System and (ii) the tuning of the anytime behaviour of SCIP, an open-source mixed integer programming solver with more than 200 parameters.

Original languageEnglish
Pages (from-to)569-582
Number of pages14
JournalEuropean Journal of Operational Research
Volume235
Issue number3
DOIs
Publication statusPublished - 16 Jun 2014

Keywords

  • Anytime algorithms
  • Automatic configuration
  • Metaheuristics
  • Offline tuning

Fingerprint

Dive into the research topics of 'Automatically improving the anytime behaviour of optimisation algorithms'. Together they form a unique fingerprint.

Cite this