Accueil🇫🇷Chercher

MĂ©thode du bruitage

La méthode du bruitage est une métaheuristique, c'est-à-dire un algorithme d'optimisation visant à résoudre des problèmes d'optimisation difficile (au sens de la théorie de la complexité) pour lesquels on ne connaît pas de méthode classique plus efficace.

Historique

La méthode de bruitage a premièrement été appliqué par I. Charon et O. Hudry[1] (1192) sur des problèmes d'optimisation combinatoire liés au partitionnement, avant d'être étendus à d'autres problèmes classiques comme celui du voyageur de commerce.

Approche intuitive

La méthode du bruitage est un algorithme de descente, qui permet de déterminer l'optimum d'une fonction objectif. A partir d'une solution initiale , les solutions possibles dans le voisinage de la position précédente sont évaluées. La solution à l'étape suivante est choisie comme celle qui permet de minimiser la fonction objectif (). L'algorithme procède de façon itérative, jusqu'à ce que la solution considérée minimise la fonction objectif par rapport à l'ensemble des autres solutions possibles de son voisinage. La solution est alors considérée comme un optimum local de la fonction objectif. La particularité de la méthode du bruitage est que la solution est évaluée sur une fonction objectif bruitée , égale à la somme de la fonction objectif à optimiser et d'un bruit additif aléatoire. A chaque itération, l'amplitude du bruit additif décroit jusqu'à être nulle.

Principe

Une solution est initialisée aléatoirement et l'amplitude du bruit est initialisée, selon une valeur fixée par l'utilisateur. La fonction objectif bruitée est calculée à partir de la fonction objectif et du bruit , tel que . Tant qu'un critère d'arrêt sur la qualité de la solution n'est pas atteint, la nouvelle solution est déterminée par application d'un méthode de descente à par rapport à la fonction . L'amplitude du bruit à l'itération suivante est diminuée, et la fonction objectif est de nouveau calculée, tel que . La recherche d'une nouvelle solution est itérative, jusqu'à ce que . La solution est alors considérée comme l'optimum de la fonction objectif .

Performances

Sur le problème étudié par ses auteurs, la méthode de bruitage a démontré des performances équivalentes à d'autres méta-heuristiques[2], comme l'algorithme du recuit simulé.

Notes et références

  1. Irène Charon et Olivier Hudry, « The noising method: a new method for combinatorial optimization », Operations Research Letters, vol. 14, no 3,‎ , p. 133–137 (ISSN 0167-6377, DOI 10.1016/0167-6377(93)90023-A, lire en ligne, consulté le )
  2. (en) Irène Charon et Olivier Hudry, « The noising methods: A generalization of some metaheuristics », European Journal of Operational Research, vol. 135, no 1,‎ , p. 86–101 (DOI 10.1016/S0377-2217(00)00305-2, lire en ligne, consulté le )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.