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

Type de document :

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

Titre :

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

Auteur(s) :

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

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

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

Titre de la manifestation scientifique :

Parallel Problem Solving from Nature - PPSN XV

Ville :

Coimbra

Pays :

Portugal

Date de début de la manifestation scientifique :

2018-09-08

Mot(s)-clé(s) en anglais :

Flowshop scheduling
Local search
Heuristics
Multi-objective optimisation
Combinatorial optimisation

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :