Titre :

Time-Dependent Automatic Parameter Configuration of a Local Search Algorithm

Auteur(s) :

Sae-Dan, Weerapan [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Kessaci, Marie-Eleonore [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Veerapen, Nadarajen [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Jourdan, Laetitia [Auteur]
Operational Research, Knowledge And Data [ORKAD]

Titre de la manifestation scientifique :

GECCO '20 Companion: Companion Conference on Genetic and Evolutionary Computation

Organisateur(s) de la manifestation scientifique :

ACM

Ville :

Cancún

Pays :

Mexique

Date de début de la manifestation scientifique :

2020-07-08

Titre de la revue :

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Date de publication :

2020-07-09

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

Combinatorial Optimization
Local Search
Automatic Algorithm Configuration

Discipline(s) HAL :

Informatique [cs]/Intelligence artificielle [cs.AI]
Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In combinatorial optimization, where problems are often NP-hard, metaheuristics and other approximation algorithms frequently have many parameters in order to adapt to a wide range of scenarios. Very often, obtaining good ...
Lire la suite >In combinatorial optimization, where problems are often NP-hard, metaheuristics and other approximation algorithms frequently have many parameters in order to adapt to a wide range of scenarios. Very often, obtaining good values for these parameters is a long and tedious manual task but automatic algorithm configuration has been shown to overcome this issue. At the same time, it may also be useful for parameter values to change during the search in order to fine-tune the search process. These parameters include low-level heuristic components. In this article, we propose to use automatic parameter configuration coupled with a control mechanism that switches between parameter configurations at specific times during the search, as an in-between classic parameter tuning and selection hyperheuristics. We test this idea on a local search algorithm, whose parameters allow for selecting different design components, and three combinatorial problems: the Permutation Flowshop Problem, the Traveling Salesman Problem, and the Quadratic Assignment Problem. In comparisons with traditional static automatic parameter configuration, the proposed approach time-dependent is shown to perform better. Additionally, better-performing local search component configurations are identified and discussed.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL