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.

  • Thomas Weise. "Results for Several Simple Algorithms on the W-Model for Black-Box Discrete Optimization Benchmarking," uploaded to Zenodo: doi:10.5281/zenodo.1256883.
  • Thomas Weise and Zijun Wu. Difficult Features of Combinatorial Optimization Problems and the Tunable W-Model Benchmark Problem for Simulating them. In Black Box Discrete Optimization Benchmarking (BB-DOB) Workshop of Companion Material Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2018), July 15th-19th 2018, Kyoto, Japan, pages 1769-1776, ISBN: 978-1-4503-5764-7. ACM.
    doi:10.1145/3205651.3208240 / pdf / slides / source codes / workshop website
    Additional experimental results with the W-Model, which were not used in this paper, can be found at doi:10.5281/zenodo.1256883.
  • Thomas Weise, Stefan Niemczyk, Hendrik Skubch, Roland Reichle, and Kurt Geihs. A Tunable Model for Multi-Objective, Epistatic, Rugged, and Neutral Fitness Landscapes. In Maarten Keijzer, Giuliano Antoniol, Clare Bates Congdon, Kalyanmoy Deb, Benjamin Doerr, Nikolaus Hansen, John H. Holmes, Gregory S. Hornby, Daniel Howard, James Kennedy, Sanjeev P. Kumar, Fernando G. Lobo, Julian Francis Miller, Jason H. Moore, Frank Neumann, Martin Pelikan, Jordan B. Pollack, Kumara Sastry, Kenneth Owen Stanley, Adrian Stoica, El-Ghazali, and Ingo Wegener, editors, Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO'08), pages 795-802, July 12-16, 2008, Renaissance Atlanta Hotel Downtown: Atlanta, GA, USA. ISBN: 978-1-60558-130-9, New York, NY, USA: ACM Press.
    doi:10.1145/1389095.1389252 / pdf / slides / new implementation [Java+Maven+JUnit]