Automatically Configuring Multi-objective Local Search Using Multi-objective Optimisation

Aymeric Blot (1, 2, 3, 4) , Alexis Pernet (1, 2, 3, 4) , Laetitia Jourdan (1, 2, 3, 4) , Marie-Éléonore Kessaci-Marmion (1, 2, 3, 4) , Holger H Hoos (5, 6)

1 ORKAD - Operational Research, Knowledge And Data
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
3 Université de Lille
4 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
5 Universiteit Leiden = Leiden University
6 UBC - University of British Columbia

Automatic algorithm configuration (AAC) is becoming an increasingly crucial component in the design of high-performance solvers for many challenging combinatorial optimisation problems. This raises the question how to most effectively leverage AAC in the context of building or optimising multi-objective optimisation algorithms, and specifically , multi-objective local search procedures. Because the performance of multi-objective optimisation algorithms cannot be fully characterised by a single performance indicator, we believe that AAC for multi-objective local search should make use of multi-objective configuration procedures. We test this belief by using MO-ParamILS to automatically configure a highly parametric iterated local search framework for the classical and widely studied bi-objective permutation flowshop problem. To the best of our knowledge, this is the first time a multi-objective optimisation algorithm is automatically configured in a multi-objective fashion, and our results demonstrate that this approach can produce very good results as well as interesting insights into the efficacy of various strategies and components of a flexible multi-objective local search framework.

Mots clés: Permutation Flowshop Scheduling; Algorithm Configuration; Multi-Objective Optimisation; Local Search

Domaines: Recherche opérationnelle [math.OC]

Aymeric Blot, Alexis Pernet, Laetitia Jourdan, Marie-Éléonore Kessaci-Marmion, Holger H Hoos. Automatically Configuring Multi-objective Local Search Using Multi-objective Optimisation. EMO 2017 - 9th International Conference on Evolutionary Multi-Criterion Optimization, Mar 2017, Münster, Germany. pp.61-73, ⟨10.1007/978-3-319-54157-0_5⟩. ⟨hal-01559690⟩