MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression

Mohamed El Yafrani; Marcella Scoczynski; Inkyung Sung; Markus Wagner; Carola Doerr; Peter Nielsen

doi:10.1007/978-3-030-72904-2_4

MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression

Mohamed El Yafrani, Marcella Scoczynski, Inkyung Sung, Markus Wagner, Carola Doerr, Peter Nielsen

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

Abstract

In this paper, we introduce a Model-based Algorithm Tuning Engine, namely MATE, where the parameters of an algorithm are represented as expressions of the features of a target optimisation problem. In contrast to most static (feature-independent) algorithm tuning engines such as irace and SPOT, our approach aims to derive the best parameter configuration of a given algorithm for a specific problem, exploiting the relationships between the algorithm parameters and the features of the problem. We formulate the problem of finding the relationships between the parameters and the problem features as a symbolic regression problem and we use genetic programming to extract these expressions in a human-readable form. For the evaluation, we apply our approach to the configuration of the (1 + 1) EA and RLS algorithms for the OneMax, LeadingOnes, BinValue and Jump optimisation problems, where the theoretically optimal algorithm parameters to the problems are available as functions of the features of the problems. Our study shows that the found relationships typically comply with known theoretical results – this demonstrates (1) the potential of model-based parameter tuning as an alternative to existing static algorithm tuning engines, and (2) its potential to discover relationships between algorithm performance and instance features in human-readable form.

Original language	English
Title of host publication	Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings
Editors	Christine Zarges, Sébastien Verel
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	51-67
Number of pages	17
ISBN (Electronic)	9783030729042
ISBN (Print)	9783030729035
DOIs	https://doi.org/10.1007/978-3-030-72904-2_4
Publication status	Published - 2021
Externally published	Yes
Event	European Conference on Evolutionary Computation in Combinatorial Optimization 2021 - Online, United States of America Duration: 7 Apr 2021 → 9 Apr 2021 Conference number: 21st https://link.springer.com/book/10.1007/978-3-030-72904-2 (Proceedings) https://www.evostar.org/2021/evocop/#:~:text=The%2021st%20European%20Conference%20on,combinatorial%20optimisation%20problems%20appearing%20in (Website)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12692
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Evolutionary Computation in Combinatorial Optimization 2021
Abbreviated title	EvoCOP 2021
Country/Territory	United States of America
Period	7/04/21 → 9/04/21
Internet address	https://link.springer.com/book/10.1007/978-3-030-72904-2 (Proceedings) https://www.evostar.org/2021/evocop/#:~:text=The%2021st%20European%20Conference%20on,combinatorial%20optimisation%20problems%20appearing%20in (Website)

Keywords

Genetic programming
Model-based tuning
Parameter tuning

Access to Document

10.1007/978-3-030-72904-2_4

Cite this

El Yafrani, M., Scoczynski, M., Sung, I., Wagner, M., Doerr, C., & Nielsen, P. (2021). MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression. In C. Zarges, & S. Verel (Eds.), Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings (pp. 51-67). (Lecture Notes in Computer Science; Vol. 12692). Springer. https://doi.org/10.1007/978-3-030-72904-2_4

El Yafrani, Mohamed ; Scoczynski, Marcella ; Sung, Inkyung et al. / MATE : A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression. Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings. editor / Christine Zarges ; Sébastien Verel. Cham Switzerland : Springer, 2021. pp. 51-67 (Lecture Notes in Computer Science).

@inproceedings{b387bcf5877247cfb94267583d4f255e,

title = "MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression",

abstract = "In this paper, we introduce a Model-based Algorithm Tuning Engine, namely MATE, where the parameters of an algorithm are represented as expressions of the features of a target optimisation problem. In contrast to most static (feature-independent) algorithm tuning engines such as irace and SPOT, our approach aims to derive the best parameter configuration of a given algorithm for a specific problem, exploiting the relationships between the algorithm parameters and the features of the problem. We formulate the problem of finding the relationships between the parameters and the problem features as a symbolic regression problem and we use genetic programming to extract these expressions in a human-readable form. For the evaluation, we apply our approach to the configuration of the (1 + 1) EA and RLS algorithms for the OneMax, LeadingOnes, BinValue and Jump optimisation problems, where the theoretically optimal algorithm parameters to the problems are available as functions of the features of the problems. Our study shows that the found relationships typically comply with known theoretical results – this demonstrates (1) the potential of model-based parameter tuning as an alternative to existing static algorithm tuning engines, and (2) its potential to discover relationships between algorithm performance and instance features in human-readable form.",

keywords = "Genetic programming, Model-based tuning, Parameter tuning",

author = "{El Yafrani}, Mohamed and Marcella Scoczynski and Inkyung Sung and Markus Wagner and Carola Doerr and Peter Nielsen",

note = "Funding Information: Acknowledgements. M. Martins acknowledges CNPq (Brazil Government). M. Wagner acknowledges the ARC Discovery Early Career Researcher Award DE160100850. C. Doerr acknowledges support from the Paris Ile-de-France Region. Experiments were performed on the AAU{\textquoteright}s CLAUDIA compute cloud platform. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; European Conference on Evolutionary Computation in Combinatorial Optimization 2021, EvoCOP 2021 ; Conference date: 07-04-2021 Through 09-04-2021",

year = "2021",

doi = "10.1007/978-3-030-72904-2_4",

language = "English",

isbn = "9783030729035",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "51--67",

editor = "Christine Zarges and S{\'e}bastien Verel",

booktitle = "Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings",

url = "https://link.springer.com/book/10.1007/978-3-030-72904-2, https://www.evostar.org/2021/evocop/#:~:text=The%2021st%20European%20Conference%20on,combinatorial%20optimisation%20problems%20appearing%20in",

}

El Yafrani, M, Scoczynski, M, Sung, I, Wagner, M, Doerr, C & Nielsen, P 2021, MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression. in C Zarges & S Verel (eds), Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings. Lecture Notes in Computer Science, vol. 12692, Springer, Cham Switzerland, pp. 51-67, European Conference on Evolutionary Computation in Combinatorial Optimization 2021, United States of America, 7/04/21. https://doi.org/10.1007/978-3-030-72904-2_4

MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression. / El Yafrani, Mohamed; Scoczynski, Marcella; Sung, Inkyung et al.
Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings. ed. / Christine Zarges; Sébastien Verel. Cham Switzerland: Springer, 2021. p. 51-67 (Lecture Notes in Computer Science; Vol. 12692).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - MATE

T2 - European Conference on Evolutionary Computation in Combinatorial Optimization 2021

AU - El Yafrani, Mohamed

AU - Scoczynski, Marcella

AU - Sung, Inkyung

AU - Wagner, Markus

AU - Doerr, Carola

AU - Nielsen, Peter

N1 - Conference code: 21st

PY - 2021

Y1 - 2021

N2 - In this paper, we introduce a Model-based Algorithm Tuning Engine, namely MATE, where the parameters of an algorithm are represented as expressions of the features of a target optimisation problem. In contrast to most static (feature-independent) algorithm tuning engines such as irace and SPOT, our approach aims to derive the best parameter configuration of a given algorithm for a specific problem, exploiting the relationships between the algorithm parameters and the features of the problem. We formulate the problem of finding the relationships between the parameters and the problem features as a symbolic regression problem and we use genetic programming to extract these expressions in a human-readable form. For the evaluation, we apply our approach to the configuration of the (1 + 1) EA and RLS algorithms for the OneMax, LeadingOnes, BinValue and Jump optimisation problems, where the theoretically optimal algorithm parameters to the problems are available as functions of the features of the problems. Our study shows that the found relationships typically comply with known theoretical results – this demonstrates (1) the potential of model-based parameter tuning as an alternative to existing static algorithm tuning engines, and (2) its potential to discover relationships between algorithm performance and instance features in human-readable form.

AB - In this paper, we introduce a Model-based Algorithm Tuning Engine, namely MATE, where the parameters of an algorithm are represented as expressions of the features of a target optimisation problem. In contrast to most static (feature-independent) algorithm tuning engines such as irace and SPOT, our approach aims to derive the best parameter configuration of a given algorithm for a specific problem, exploiting the relationships between the algorithm parameters and the features of the problem. We formulate the problem of finding the relationships between the parameters and the problem features as a symbolic regression problem and we use genetic programming to extract these expressions in a human-readable form. For the evaluation, we apply our approach to the configuration of the (1 + 1) EA and RLS algorithms for the OneMax, LeadingOnes, BinValue and Jump optimisation problems, where the theoretically optimal algorithm parameters to the problems are available as functions of the features of the problems. Our study shows that the found relationships typically comply with known theoretical results – this demonstrates (1) the potential of model-based parameter tuning as an alternative to existing static algorithm tuning engines, and (2) its potential to discover relationships between algorithm performance and instance features in human-readable form.

KW - Genetic programming

KW - Model-based tuning

KW - Parameter tuning

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

U2 - 10.1007/978-3-030-72904-2_4

DO - 10.1007/978-3-030-72904-2_4

M3 - Conference Paper

AN - SCOPUS:85107371096

SN - 9783030729035

T3 - Lecture Notes in Computer Science

SP - 51

EP - 67

BT - Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings

A2 - Zarges, Christine

A2 - Verel, Sébastien

PB - Springer

CY - Cham Switzerland

Y2 - 7 April 2021 through 9 April 2021

ER -

El Yafrani M, Scoczynski M, Sung I, Wagner M, Doerr C, Nielsen P. MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression. In Zarges C, Verel S, editors, Evolutionary Computation in Combinatorial Optimization - 21st European Conference, EvoCOP 2021 Held as Part of EvoStar 2021 Virtual Event, April 7–9, 2021 Proceedings. Cham Switzerland: Springer. 2021. p. 51-67. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-72904-2_4

MATE: A Model-Based Algorithm Tuning Engine: A proof of concept towards transparent feature-dependent parameter tuning using symbolic regression

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this