A fitness landscape analysis of Pareto local search on bi-objective permutation flowshop scheduling problems

Arnaud Liefooghe (1, 2) , Bilel Derbel (1, 2) , Sebastien Verel (3) , Hernan Aguirre (4) , Kiyoshi Tanaka (4)

1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
2 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
3 LISIC - Laboratoire d'Informatique Signal et Image de la Côte d'Opale
4 Faculty of Engineering [Nagano]

We study the difficulty of solving different bi-objective formulations of the permutation flowshop scheduling problem by adopting a fitness landscape analysis perspective. Our main goal is to shed the light on how different problem features can impact the performance of Pareto local search algorithms. Specifically, we conduct an empirical analysis addressing the challenging question of quantifying the individual effect and the joint impact of different problem features on the success rate of the considered approaches. Our findings support that multi-objective fitness landscapes enable to devise sound general-purpose features for assessing the expected difficulty in solving permutation flowshop scheduling problems, hence pushing a step towards a better understanding of the challenges that multi-objective randomized search heuristics have to face.

Domaines: Intelligence artificielle [cs.AI]

Arnaud Liefooghe, Bilel Derbel, Sebastien Verel, Hernan Aguirre, Kiyoshi Tanaka. A fitness landscape analysis of Pareto local search on bi-objective permutation flowshop scheduling problems. 9th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2017), Mar 2017, Münster, Germany. ⟨10.1007/978-3-319-54157-0_29⟩. ⟨hal-01496357⟩