Méthode du bruitage

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.

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 ${\displaystyle s}$, les solutions possibles ${\displaystyle s'}$ dans le voisinage ${\displaystyle N(s)}$ de la position précédente sont évaluées. La solution ${\displaystyle s'}$ à l'étape suivante est choisie comme celle qui permet de minimiser la fonction objectif (${\displaystyle f(s')<f(s)}$). 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 ${\displaystyle f'}$, égale à la somme de la fonction objectif à optimiser ${\displaystyle f}$ et d'un bruit additif aléatoire. A chaque itération, l'amplitude du bruit additif décroit jusqu'à être nulle.

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

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é.