Title :

Time-Dependent Automatic Parameter Configuration of a Local Search Algorithm

Author(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]

Conference title :

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

Conference organizers(s) :

ACM

City :

Cancún

Country :

Mexique

Start date of the conference :

2020-07-08

Journal title :

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

Publication date :

2020-07-09

English keyword(s) :

Combinatorial Optimization
Local Search
Automatic Algorithm Configuration

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL