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

Principe

Une solution $s(0)$ est initialisée aléatoirement et l'amplitude du bruit $b(0)$ est initialisée, selon une valeur fixée par l'utilisateur. La fonction objectif bruitée $f'$ est calculée à partir de la fonction objectif $f$ et du bruit $b(0)$, tel que $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 $s(t+1)$ est déterminée par application d'un méthode de descente à $s(t)$ par rapport à la fonction $f'$. L'amplitude du bruit à l'itération suivante $b(t+1)$ est diminuée, et la fonction objectif est de nouveau calculée, tel que $f'=f+b(t+1)$. La recherche d'une nouvelle solution est itérative, jusqu'à ce que $s(t)=s(t+1)$. La solution est alors considérée comme l'optimum de la fonction objectif $f$.

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, comme l'algorithme du recuit simulé.