New Initialisation Techniques for Multi-objective Local Search

Blot, Aymeric; López-Ibáñez, Manuel; Kessaci, Marie-Eleonore; Jourdan, Laetitia

Application to the Bi-objective Permutation Flowshop

Document type :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

DOI :

10.1007/978-3-319-99253-2_26

Title :

New Initialisation Techniques for Multi-objective Local Search
Application to the Bi-objective Permutation Flowshop

Author(s) :

Blot, Aymeric [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Operational Research, Knowledge And Data [ORKAD]
López-Ibáñez, Manuel [Auteur]
University of Manchester [Manchester]
Kessaci, Marie-Eleonore [Auteur]

Operational Research, Knowledge And Data [ORKAD]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Jourdan, Laetitia [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Operational Research, Knowledge And Data [ORKAD]

Conference title :

Parallel Problem Solving from Nature - PPSN XV

City :

Coimbra

Country :

Portugal

Start date of the conference :

2018-09-08

English keyword(s) :

Flowshop scheduling
Local search
Heuristics
Multi-objective optimisation
Combinatorial optimisation

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

Given the availability of high-performing local search (LS) for single-objective (SO) optimisation problems, one successful approach to tackle their multi-objective (MO) counterparts is scalarisation-based local search ...
Show more >Given the availability of high-performing local search (LS) for single-objective (SO) optimisation problems, one successful approach to tackle their multi-objective (MO) counterparts is scalarisation-based local search (SBLS). SBLS strategies solve multiple scalarisations, i.e., aggregations of the multiple objectives into a single scalar value, with varying weights. They have been shown to work specially well as the initialisation phase of other types of multi-objective local search, such as Pareto local search (PLS). A major drawback of existing SBLS strategies is that the underlying SO optimiser is unaware of the MO nature of the problem and only returns a single solution, discarding any intermediate solutions that may be of interest. We propose here two new SBLS strategies (ChangeRestart and Change-Direction) that overcome this drawback by augmenting the underlying SO-LS method with an archive of nondominated solutions that is used to dynamically update the scalarisations. The new strategies produce better results on the bi-objective permutation flowshop problem than other five SBLS strategies from the literature, not only on their own but also when used as the initialisation phase of PLS.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :