Accéder directement au contenu Accéder directement à la navigation
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 Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 20:20:49
Dernière modification le : mardi 2 juin 2020 - 04:03:49

Lien texte intégral

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

19