Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Article dans une revue

Alternative evaluation functions for the cyclic bandwidth sum problem

Abstract :

One essential element for the successful application of metaheuristics is the evaluation function. It should be able to make fine distinctions among the potential solutions in order to avoid producing wide plateaus (valleys) in the fitness landscape, on which detecting a promising search direction could be hard for certain local search strategies. In the specific case of the cyclic bandwidth sum (CBS) problem, the heuristics reported have used directly the objective function of the optimization problem to assess the quality of potential solutions. Nevertheless, such a conventional function does not allow to efficiently establish preferences among distinct potential solutions. In order to cope with this important issue, three new more refined evaluation functions for the CBS problem are introduced in this paper.

An in-depth comparative analysis considering the conventional and the three proposed evaluation functions is carried out and presented. It includes an assessment of their: (a) discrimination potential, (b) consistency with regard to the primary objective of the CBS problem, and (c) practical usefulness within two different algorithms, best improvement local search and iterated local search. A validation of the experimental results by means of a meticulous statistical significance analysis revealed that proposing more informative evaluation schemes for the CBS problem could be a useful means of improving the performance of metaheuristics. Indeed, our iterated local search implementation, using an alternative evaluation function, surpassed the best solutions yielded by the state-of-the-art algorithms and allow us to attain new better upper bounds for 14 out of 20 well-known benchmark instances.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715688
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 13 octobre 2021 - 11:08:09
Dernière modification le : lundi 14 novembre 2022 - 02:42:07
Archivage à long terme le : : vendredi 14 janvier 2022 - 18:45:12

Fichier

1-s2.0-S0377221718308075-main ...
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

Collections

Citation

Eduardo Rodriguez-Tello, Frédéric Lardeux, Abraham Duarte, Valentina Narvaez-Teran. Alternative evaluation functions for the cyclic bandwidth sum problem. European Journal of Operational Research, 2019, 273 (3), pp.904-919. ⟨10.1016/j.ejor.2018.09.031⟩. ⟨hal-02715688⟩

Partager

Métriques

Consultations de la notice

47

Téléchargements de fichiers

27