User Rating: 4 / 5

Star ActiveStar ActiveStar ActiveStar ActiveStar Inactive

Today, the project "Automated Algorithm Selection for Discrete Black-Box Optimization" with principal investigator Prof. Dr. Carola Doerr (Laboratoire d’Informatique de Paris 6 (LIP6), Sorbonne University, Paris, France), has been accepted for support from the Paris Region under the DIM-RFSI (Domaine d’Intérêt Majeur, Réseau Francilien en Sciences Informatiques) program. The partners involved in the project are Prof. Dr. Benjamin Doerr (LIX, École Polytechnique), Dr. Johann Dreo, (Researcher at Thales Research & Technology, Palaiseau), Dr. Pascal Kerschke (Westfälische Wilhelms-Universität Münster, Münster, Germany), Dr. Olivier Teytaud (Facebook Artificial Intelligence Lab, Paris), and Prof. Dr. Thomas Weise (of our Institute of Applied Optimization at Hefei University, China). The acceptance of this project shows that the interest in optimization algorithm selection, configuration, and benchmarking is ever-growing, and the presence of two industrial partners indicates that this is not just the case in the scientific community, but that the field has gained also very practical importance.

In the real world, a variety of planning, packing, scheduling, routing, or management problems emerge in many different scenarios. There are highly-efficient specialized algorithms for certain problems, e.g., the TSP or Satisfiability tasks, which have been developed over decades of research. The vast majority of practically relevant problems come with unique characteristics and constraints, rendering the specialized algorithms unsuitable for them, while the time available to deliver an algorithmic solution usually does not permit decades of research. Here, black-box algorithms (e.g., metaheuristics) are in order: General and flexible methods than treat the optimization task as black-box, i.e., require very little effort when adapting them to a virtually arbitrary task. However, there are many such metaheuristics and the question which one to use for the task at hand arises. The goal of this project is developing a suitable framework for training automated algorithm selectors and configurators for black-box optimization heuristics for discrete problems defined over a Boolean search space.

In this project, we will have the chance to collaborate more closely with many of our friends. The experiments will be done using the IOHprofiler, an open source optimization algorithm benchmarking tool. IOHprofiler is jointly developed by the teams of Prof. Dr. Carola Doerr, Thomas Bäck (Leiden University, The Netherlands) and Ofer Shir (Migal research institute, Israel), who, like most of the project team members, are already important members of the BB-DOB Workshop series. We are happy that our W-Model has been selected as one of the ingredients of the project, serving as a basic benchmark to investigate and test different fitness landscape measures to drive algorithm selection and configuration. The W-Model allows for defining a wide variety of different benchmark problem instances with different characteristics (scale, ruggedness, epistasis, neutrality, etc.) over the Boolean domain. As one of the modules of the project, we will evaluate for which problems a training based on the W-model provides accurate predictions and use this knowledge to extend the model together with Dr. Olivier Teytaud, the main developer of Facebook's nevergrad benchmarking platform.