Detail of the student project

Topic:Automatická konfigurace a selekce optimalizačních algoritmů
Department:Katedra kybernetiky
Supervisor:Ing. David Woller
Announce as:Diplomová práce, Bakalářská práce, Semestrální projekt
Description:Optimization algorithms are often treated as universal "one size fits all" tools, that can be readily applied to any instance of a given problem. However, according to the No Free Lunch Theorem, no algorithm can dominate all others over all possible instances. Moreover, most algorithms have tunable parameters, which often remain untouched by the user after being tuned once. Selecting the best algorithm and best configuration is nevertheless a non-trivial task, that can bring drastic improvement in solution quality or solving time.

The goal of this project is to develop and test an approach to automatic algorithm configuration and selection, roughly consisting of the following steps:
Given an algorithm, optimization problem and a dataset of instances
1) Generate a bank of several well-performing parameter configurations using an existing tuning tool (irace, SMAC, ParamILS)
2) Design and extract suitable features of the problem instances
3) Using the proposed set of features and performance results from the tuning, train a configuration selector for a previously unseen instance

The approach can be then easily expanded from configuration selection to algorithm selection. It is desirable to compare different tuning tools in step 1) and machine learning approaches in step 3).
The developed tool will be applied to a currently studied research problem in the IMR laboratory.

Bibliography:López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. In Operations Research Perspectives (Vol. 3, pp. 43–58). Elsevier BV.

Kerschke, P., Hoos, H. H., Neumann, F., & Trautmann, H. (2019). Automated Algorithm Selection: Survey and Perspectives. In Evolutionary Computation (Vol. 27, Issue 1, pp. 3–45). MIT Press.

Lindauer, M., & Hutter, F. (2018). Warmstarting of Model-Based Algorithm Configuration. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 32, Issue 1). Association for the Advancement of Artificial Intelligence (AAAI).
Responsible person: Petr Pošík