research-article

Improved regression models for algorithm configuration

Authors:

Marcelo de Souza,

Marcus RittAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 222 - 231

https://doi.org/10.1145/3512290.3528750

Published: 08 July 2022 Publication History

Abstract

Offline algorithm configuration methods search for fixed parameter values for a given set of problem instances. For each parameter, such methods perform an equivalent to a constant regression, since the parameter value remains constant for any problem instance. However, optimal parameter values may depend on instance features, such as the instance size. In this paper, we represent parameters by non-constant models, which set the parameter values according to the instance size. Instead of searching for parameter values directly, the configuration process calibrates such models. In particular, we propose a simple yet effective linear model, which approximates linear relations between instance size and optimal parameter values. For modeling nonlinear relations, we propose piecewise and log-log linear models. The evaluation of the proposed methods on four configuration scenarios show good performance gains in comparison to traditional instance-independent algorithm configuration with comparable tuning effort.

References

[1]

Carlos Ansótegui, Joel Gabàs, Yuri Malitsky, and Meinolf Sellmann. 2016. MaxSAT by Improved Instance-Specific Algorithm Configuration. Artificial Intelligence 235 (2016), 26--39.

Digital Library

[2]

Carlos Ansótegui, Meinolf Sellmann, and Kevin Tierney. 2009. A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms. In Principles and Practice of Constraint Programming, CP 2009, Ian P. Gent (Ed.). Lecture Notes in Computer Science, Vol. 5732. Springer, Heidelberg, Germany, 142--157.

[3]

Thomas Bartz-Beielstein, C. Lasarczyk, and Mike Preuss. 2010. The Sequential Parameter Optimization Toolbox. In Experimental Methods for the Analysis of Optimization Algorithms, Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, and Mike Preuss (Eds.). Springer, Berlin, Germany, 337--360.

[4]

John E. Beasley. 1998. Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem. http://people.brunel.ac.uk/~mastjjb/jeb/bqp.pdf

[5]

Nacim Belkhir, Johann Dréo, Pierre Savéant, and Marc Schoenauer. 2016. Feature Based Algorithm Configuration: A Case Study with Differential Evolution. In Parallel Problem Solving from Nature - PPSN XIV (Lecture Notes in Computer Science, Vol. 9921), Julia Handl, Emma Hart, Peter R. Lewis, Manuel López-Ibáñez, Gabriela Ochoa, and Ben Paechter (Eds.). Springer, Cham, Switzerland, 156--166.

[6]

Nacim Belkhir, Johann Dréo, Pierre Savéant, and Marc Schoenauer. 2017. Per Instance Algorithm Configuration of CMA-ES with Limited Budget. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Peter A. N. Bosman (Ed.). ACM Press, New York, NY, 681--688.

Digital Library

[7]

Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. 2021. Machine Learning for Combinatorial Optimization: A Methodological Tour D'horizon. European Journal of Operational Research 290, 2 (2021), 405--421.

[8]

Mauro Birattari, Thomas Stützle, Luís Paquete, and Klaus Varrentrapp. 2002. A Racing Algorithm for Configuring Metaheuristics. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2002, William B. Langdon et al. (Eds.). Morgan Kaufmann Publishers, San Francisco, CA, 11--18.

[9]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal Fixed and Adaptive Mutation Rates for the LeadingOnes Problem. In Parallel Problem Solving from Nature - PPSN XI (Lecture Notes in Computer Science), Robert Schaefer, Carlos Cotta, Joanna Kołodziej, and Günther Rudolph (Eds.). Springer, Heidelberg, Germany, 1--10.

[10]

Michael J. Brusco and Hans-Friedrich Köhn. 2009. Clustering Qualitative Data Based on Binary Equivalence Relations: Neighborhood Search Heuristics for the Clique Partitioning Problem. Psychometrika 74, 4 (2009), 685--703.

[11]

Irène Charon and Olivier Hudry. 2006. Noising Methods for a Clique Partitioning Problem. Discrete Applied Mathematics 154, 5 (2006), 754--769.

[12]

Marcelo de Souza and Marcus Ritt. 2018. An Automatically Designed Recombination Heuristic for the Test-Assignment Problem. In Proceedings of the 2018 Congress on Evolutionary Computation (CEC 2018). IEEE Press, Piscataway, NJ, 2411--2418.

Digital Library

[13]

Marcelo de Souza and Marcus Ritt. 2018. HHTA: Hybrid Heuristic for the Test-Assignment Problem - Source Code. https://github.com/souzamarcelo/hhta

[14]

Marcelo de Souza and Marcus Ritt. 2022. ILSBQP: A Simple Iterated Local Search for the Unconstrained Binary Quadratic Programming - Source Code. https://github.com/souzamarcelo/ilsbqp

[15]

Marcelo de Souza and Marcus Ritt. 2022. Improved Regression Models for Algorithm Configuration - Source Code. https://github.com/souzamarcelo/regression-models-ac

[16]

Marcelo de Souza and Marcus Ritt. 2022. Improved Regression Models for Algorithm Configuration - Supplementary Material. https://github.com/souzamarcelo/supp-models-ac

[17]

Jelle Duives, Andrea Lodi, and Enrico Malaguti. 2013. Test-Assignment: A Quadratic Coloring Problem. Journal of Heuristics 19, 4 (2013), 549--564.

Digital Library

[18]

Mohamed El Yafrani and Belaïd Ahiod. 2018. Efficiently Solving the Traveling Thief Problem Using Hill Climbing and Simulated Annealing. Information Sciences 432 (2018), 231--244.

[19]

Mohamed El Yafrani, Marcella Scoczynski, Inkyung Sung, Markus Wagner, Carola Doerr, and Peter Nielsen. 2021. MATE: A Model-Based Algorithm Tuning Engine. In Proceedings of EvoCOP 2021 - 21st European Conference on Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science, Vol. 12692), Christine Zarges and Sébastien Verel (Eds.). Springer, Cham, Switzerland, 51--67.

Digital Library

[20]

Alberto Franzin and Thomas Stützle. 2020. Towards Transferring Algorithm Configurations Across Problems. In Learning Meets Combinatorial Algorithms at NeurIPS2020, Marin Vlastelica et al. (Eds.). OpenReview. https://openreview.net/group?id=NeurIPS.cc/2020/Workshop/LMCA

[21]

Holger H. Hoos, Frank Hutter, and Kevin Leyton-Brown. 2021. Automated Configuration and Selection of SAT Solvers. In Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol. 336. IOS Press, Amsterdam, The Netherlands, 481--507.

[22]

Frank Hutter and Youssef Hamadi. 2005. Parameter Adjustment Based on Performance Prediction: Towards an Instance-Aware Problem Solver. Technical Report MSR-TR-2005-125 (2005).

[23]

Frank Hutter, Youssef Hamadi, Holger H. Hoos, and Kevin Leyton-Brown. 2006. Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms. In Principles and Practice of Constraint Programming, CP 2006 (Lecture Notes in Computer Science, Vol. 4204), Frédéric Benhamou (Ed.). Springer, Heidelberg, Germany, 213--228.

[24]

Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2010. Automated Configuration of Mixed Integer Programming Solvers. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Andrea Lodi, M. Milano, and P. Toth (Eds.). Lecture Notes in Computer Science, Vol. 6140. Springer, Heidelberg, Germany, 186--202.

Digital Library

[25]

Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2011. Sequential Model-Based Optimization for General Algorithm Configuration. In Learning and Intelligent Optimization, 5th International Conference, LION 5, Carlos A. Coello Coello (Ed.). Lecture Notes in Computer Science, Vol. 6683. Springer, Cham, Switzerland, 507--523.

Digital Library

[26]

Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Thomas Stützle. 2009. ParamILS: An Automatic Algorithm Configuration Framework. Journal of Artificial Intelligence Research 36 (Oct. 2009), 267--306.

[27]

Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tierney. 2010. ISAC: Instance-Specific Algorithm Configuration. In Proceedings of the 19th European Conference on Artificial Intelligence, H. Coelho, R. Studer, and Michael Wooldridge (Eds.). IOS Press, Amsterdam, The Netherlands, 751--756.

[28]

Pascal Kerschke, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike Trautmann. 2018. Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation 26, 4 (2018), 597--620.

Digital Library

[29]

Christian Kroer and Yuri Malitsky. 2011. Feature Filtering for Instance-Specific Algorithm Configuration. In 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, ICTAI 2011, Taghi M. Khoshgoftaar and Xingquan Zhu (Eds.). IEEE Press, Piscataway, NJ, 849--855.

Digital Library

[30]

N. Lesh and M. Mitzenmacher. 2006. BubbleSearch: A Simple Heuristic for Improving Priority-Based Greedy Algorithms. Inform. Process. Lett. 97, 4 (2006), 161--169.

[31]

Kevin Leyton-Brown, Eugene Nudelman, and Y. Shoham. 2002. Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions. In Principles and Practice of Constraint Programming, CP 2002 (Lecture Notes in Computer Science, Vol. 2470), Pascal Van Hentenryck (Ed.). Springer, Heidelberg, Germany, 556--572.

[32]

Arnaud Liefooghe, Bilel Derbel, Sébastien Verel, Hernán Aguirre, and Kiyoshi Tanaka. 2017. Towards Landscape-Aware Automatic Algorithm Configuration: Preliminary Experiments on Neutral and Rugged Landscapes. In Proceedings of EvoCOP 2017 - 17th European Conference on Evolutionary Computation in Combinatorial Optimization (Lecture Notes in Computer Science, Vol. 10197), Alan J. Hu and Manuel López-Ibáñez (Eds.). Springer, Cham, Switzerland, 215--232.

[33]

Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Thomas Stützle, and Mauro Birattari. 2016. The irace Package: Iterated Racing for Automatic Algorithm Configuration. Operations Research Perspectives 3 (2016), 43--58.

[34]

Yuri Malitsky. 2014. Instance-Specific Algorithm Configuration. Springer, Cham, Switzerland. 15--24 pages.

[35]

Yuri Malitsky and Meinolf Sellmann. 2010. Stochastic Offline Programming. International Journal on Artificial Intelligence Tools 19, 4 (2010), 351--371.

[36]

Franco Mascia, Mauro Birattari, and Thomas Stützle. 2013. Tuning Algorithms for Tackling Large Instances: An Experimental Protocol. In Learning and Intelligent Optimization, 7th International Conference, LION 7, Panos M. Pardalos and G. Nicosia (Eds.). Lecture Notes in Computer Science, Vol. 7997. Springer, Cham, Switzerland, 410--422.

Digital Library

[37]

Marius Muja and David G. Lowe. 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, VISAPP, Lisbon, Portugal, February 5-8, 2009, Alpesh Ranchordas and Helder Araújo (Eds.), Vol. 1. INSTICC Press, Lisbon, Portugal, 331--340.

[38]

Carl Edward Rasmussen. 2004. Gaussian Processes in Machine Learning. Lecture Notes in Computer Science, Vol. 3176. Springer, Berlin, Heidelberg, 63--71.

[39]

Kate Smith-Miles, Davaatseren Baatar, Brendan Wreford, and Rhyd M. R. Lewis. 2014. Towards Objective Measures of Algorithm Performance Across Instance Space. Computers & Operations Research 45 (2014), 12--24.

Digital Library

[40]

Éric Taillard. 1993. Benchmarks for Basic Scheduling Problems. European Journal of Operational Research 64, 2 (1993), 278--285.

[41]

Angelika Wiegele. 2007. Biq Mac Library - A Collection of Max-Cut and Quadratic 0-1 Programming Instances of Medium Size. Technical Report. Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Klagenfurt, Austria. http://biqmac.aau.at/biqmaclib.pdf

[42]

Angelika Wiegele. 2007. Biq Mac Library - Binary Quadratic and Max Cut Library. http://biqmac.aau.at/biqmaclib.html

[43]

A. Yarimcam, S. Asta, Ender Özcan, and Andrew J. Parkes. 2014. Heuristic Generation via Parameter Tuning for Online Bin Packing. In Evolving and Autonomous Learning Systems (EALS), 2014 IEEE Symposium on, Plamen Angelov et al. (Eds.). IEEE Press, New York, NY, 102--108.

[44]

Zhi-Hua Zhou, Jin-Kao Hao, and Adrien Goëffon. 2016. A Three-Phased Local Search Approach for the Clique Partitioning Problem. Journal of Combinatorial Optimization 32 (2016), 169--491.

Digital Library

[45]

Zhi-Hua Zhou, Jin-Kao Hao, and Adrien Goëffon. 2016. A Three-Phased Local Search Approach for the Clique Partitioning Problem - Supplementary Material. https://leria-info.univ-angers.fr/~jinkao.hao/cpp.html

[46]

Tadeu Zubaran and Marcus Ritt. 2013. A Simple, Adaptive Bubble Search for Improving Heuristic Solutions of the Permutation Flow Shop Scheduling Problem. In Proceedings of the XLV Brazilian Symposium on Operational Research - SBPO 2013, Luciano Ferreira and Mariana Rodrigues de Almeida (Eds.). SOBRAPO, Rio de Janeiro, RJ, Brazil, 1847--1856.

Cited By

Wolfengagen VIsmailova LKosikov SSlieptsov IDohrn SMarenkov AZaytsev V(2024)Semantic configuration model with natural transformationsCognitive Systems Research10.1016/j.cogsys.2023.10118583:COnline publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cogsys.2023.101185
Nikolikj ADžeroski SMuñoz MDoerr CKorošec PEftimov TSilva SPaquete L(2023)Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem InstancesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590424(529-537)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590424

Index Terms

Improved regression models for algorithm configuration

Recommendations

Algorithm configuration using GPU-based metaheuristics
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

In this paper, a GPU-based implementation of Differential Evolution (DE) and Particle Swarm Optimization (PSO) in CUDA is used to automatically tune the parameters of PSO.

The parameters were tuned over a set of 8 problems and then tested over 20 ...
ISAC --Instance-Specific Algorithm Configuration
Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with ...
Tuning metaheuristics by sequential optimisation of regression models
Abstract
Tuning parameters is an important step for the application of metaheuristics to specific problem classes. In this work we present a tuning framework based on the sequential optimisation of perturbed regression models. Besides providing ...
Highlights
- Tuning methods based on shrinkage regression can reveal the coefficients relevance.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Google Research Latin America
CNPq
Universidade do Estado de Santa Catarina

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 829 of 2,029 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
98
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wolfengagen VIsmailova LKosikov SSlieptsov IDohrn SMarenkov AZaytsev V(2024)Semantic configuration model with natural transformationsCognitive Systems Research10.1016/j.cogsys.2023.10118583:COnline publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cogsys.2023.101185
Nikolikj ADžeroski SMuñoz MDoerr CKorošec PEftimov TSilva SPaquete L(2023)Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem InstancesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590424(529-537)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590424

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents