Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Worst Improvement based Iterated Local Search

Abstract :

To solve combinatorial optimization problems, many metaheuristics use first or best improvement hill-climbing as intensification mechanism in order to find local optima. In particular, first improvement offers a good tradeoff between computation cost and quality of reached local optima. In this paper, we investigate a worst improvement-based moving strategy, never considered in the literature. Such a strategy is able to reach good local optima despite requiring a significant additional computation cost. Here, we investigate if such a pivoting rule can be efficient when considered within metaheuristics, and especially within iterated local search (ILS). In our experiments, we compare an ILS using a first improvement pivoting rule to an ILS using an approximated version of worst improvement pivoting rule. Both methods are launched with the same number of evaluations on bit-string based fitness landscapes. Results are analyzed using some landscapes’ features in order to determine if the worst improvement principle should be considered as a moving strategy in some cases.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715054
Contributeur : Okina Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 19:56:25
Dernière modification le : vendredi 19 juin 2020 - 13:18:05

Identifiants

Collections

Citation

Sara Tari, Matthieu Basseur, Adrien Goëffon. Worst Improvement based Iterated Local Search. European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP), 2018, Parme, Italy. pp.50-66, ⟨10.1007/978-3-319-77449-7_4⟩. ⟨hal-02715054⟩

Partager

Métriques

Consultations de la notice

25