The noising methods : a survey

Irène Charon*, ENST
Olivier Hudry*, ENST et CERMSEM

Résumé. L'objectif de cet article est de résumer les principes et les applications des méthodes de bruitage, une récente famille de métaheuristiques en optimisation combinatoire. Nous décrivons leurs caractéristiques communes et leurs variantes, puis nous donnons la liste de leurs applications à des problèmes d'optimisation combinatoire. Nous montrons aussi comment le recuit simulé et les algorithmes d'acceptation à seuil peuvent être considérés comme des méthodes de bruitage quand les ingrédients de celles-ci sont choisies de manière adéquate.
Mots clés : Optimisation combinatoire, métaheuristiques, méthodes de bruitage, recuit simulé, algorithmes d'acceptation à seuil.

Abstract. The aim of this paper is to summarize the principles and the applications of the noising methods, a recent family of combinatorial optimization metaheuristics. We describe their commons features and their variants and we give the list of their applications to different combinatorial optimization problems. We also show how the simulated annealing algorithm and the threshold accepting algorithm can be considered as noising methods when the components of the noising methods are properly chosen.
Keywords : Combinatorial optimization, metaheuristics, noising methods, simulated annealing, threshold accepting algorithm.

AMS Classification : 90C27, 90C59.

*Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634 Paris cedex 13.