Rangez-moi ces bouquins !

Piste rouge Le 24 avril 2012  - Ecrit par  Nils Berglund Voir les commentaires

C’est l’histoire de Thomas qui, en entreposant des livres pour une grande maison de vente en ligne, découvre l’intérêt des algorithmes stochastiques et la métastabilité.

Thomas travaille depuis peu pour une grande entreprise de vente de livres par internet. Son patron lui a assigné une nouvelle tâche : il doit stocker des livres dans l’entrepôt dont la construction vient d’être terminée. C’est un grand entrepôt carré, pouvant contenir plusieurs milliers de livres, rangés côte à côte comme sur un très grand échiquier (nous supposerons ici que tout se passe dans un plan). Les livres et les cases pouvant les contenir ont tous la même forme carrée.

PNG - 954 octets

Le patron a pour politique de payer ses employés en fonction de la qualité du travail accompli. Les règles imposées à Thomas sont simples : pour chaque livre entreposé, Thomas gagne $1$ euro ; cependant, le patron ayant horreur du désordre (et de la poussière), il décide de pénaliser lourdement les trous : pour chaque côté de livre voisin d’une case vide (on appellera cela une interface), Thomas devra payer une taxe de $2$ euros. Pour éviter des effets de bord indésirables, nous allons identifier les bords opposés de l’entrepôt. Ainsi, chaque case sur le bord droit est voisine d’une case sur le bord gauche, chaque case sur le bord supérieur est voisine d’une case sur le bord inférieur. Les quatre coins de l’entrepôt sont également voisins. On appelle cela des conditions au bord périodiques.

A première vue, la tâche de Thomas est très simple : il lui suffit de remplir complètement l’entrepôt. S’il y a de la place pour $N$ livres, il aura gagné $N$ euros, et ne devra rien payer pour des interfaces. Le problème est qu’il va falloir beaucoup de temps à Thomas pour remplir tout l’entrepôt, et que son patron lui demande des comptes régulièrement. Comme il veut éviter de trop s’endetter en cours de route, Thomas aura intérêt à limiter au maximum les pénalités pour interfaces. Question : quelle est la manière optimale de remplir l’entrepôt, et quel sera l’endettement maximal pour cette stratégie ?

Au début, l’entrepôt est vide. Thomas commence par placer un premier livre dans l’entrepôt. Où cela ? Les conditions au bord périodiques font que cela n’a pas d’importance. Disons qu’il le place comme ceci :

PNG - 964 octets

Combien a gagné Thomas ? Comme il a entreposé $1$ livre, il a gagné $1$ euro.
Mais il a aussi créé $4$ interfaces, qui lui coûtent chacun $2$ euros. En tout il a donc une dette de $4\cdot 2 − 1\cdot 1 = 7$ euros ! Mais Thomas n’a pas le choix, s’il veut à terme ranger tous les livres, il ne peut éviter de créer ces interfaces, du moins temporairement.

Pour placer son deuxième livre, Thomas a deux possibilités : il peut le placer loin (à distance au moins $1$) du premier, ou dans une case adjacente :

PNG - 970 octets
PNG - 962 octets

Dans le premier cas, il y a $2$ cases remplies et $8$ interfaces, Thomas devra
donc la somme de $8\cdot 2-2\cdot 1 = 14$ euros. Le second cas est plus
favorable, car il n’y a que $6$ interfaces, d’où une dette de seulement
$6\cdot 2-2\cdot 1 = 10$ euros. On voit donc qu’il est préférable de
ranger les livres côte à côte, ce qui est le résultat escompté par le
patron. Mieux que cela, comparons ces deux manières de ranger $4$ livres :

PNG - 963 octets
PNG - 964 octets

Dans le premier cas, il y a $10$ interfaces, alors que dans le second, il n’y en
a que $8$. La dette passe donc de $10\cdot 2-4\cdot 1 = 16$ euros dans le
premier cas à $8\cdot 2-4\cdot 1 = 12$ euros dans le second.

D’une manière générale, la forme optimale pour arranger les livres est le
carré, car c’est lui qui minimise le périmètre à aire constante
(ceci est dû au fait que les longueurs sont déterminées par le réseau
carré ; dans un plan sans directions privilégiées, la forme optimale
serait le disque [1]). Nous pouvons facilement calculer le coût d’un carré de
longueur $\ell$ : celui-ci a un périmètre de $4\ell$ et occupe $\ell^2$
cases, d’où un coût de
\[ 4\ell \cdot 2 - \ell^2 \cdot 1 = 8\ell - \ell^2 . \]
On remarquera que ce coût croît pour $\ell$ allant de $1$ à $4$, puis
décroît. Sa valeur maximale, atteinte pour $\ell=4$, est de $16$. Pour les
carrés plus grands, c’est l’aire qui l’emporte sur le périmètre.

Nous devons cependant tenir compte du fait qu’on ne peut pas passer directement
d’un carré à l’autre. La séquence suivante montre comment passer d’un
carré $3\times3$ à un rectangle $3\times4$ :

PNG - 965 octets
PNG - 973 octets
PNG - 973 octets
PNG - 969 octets

Les coûts sont donnés respectivement par $15, 18, 17$ et $16$. On peut
ensuite passer au carré $4\times 4$ en ajoutant une rangée :

PNG - 972 octets
PNG - 972 octets
PNG - 972 octets
PNG - 969 octets

Les coûts sont donnés par $19, 18, 17$ et $16$. En fait, c’est le premier
livre dans une nouvelle rangée qui fait augmenter le coût. Ceci est dû au
fait qu’on est obligé d’ajouter deux interfaces. Ensuite, la rangée peut
être complétée sans changer le périmètre, tout en augmentant l’aire
occupée.

Ainsi, pour passer au carré $5\times 5$, la suite des coûts est donnée par
$19$, $18$, $17$, $16$, $19$, $18$, $17$, $16$ puis $15$. Pour des carrés plus
grands, le coût ne dépasse plus jamais $18$. En fait, il suit un
comportement en dent de scie autour des valeurs $8\ell - \ell^2$ calculées
plus haut pour les carrés parfaits. Pour chaque nouvelle rangée, le coût
augmente de $3$, puis il diminue d’une unité par livre jusqu’à ce que la
rangée soit complète :

Coût minimal en fonction du nombre de livres

En continuant d’ajouter des livres, Thomas verra le coût devenir négatif, c’est-à-dire qu’il finira par gagner de l’argent (pouvez-vous déterminer à partir de quand ?)

La question que nous nous sommes posée est donc résolue : nous avons trouvé la stratégie optimale, et la dette maximale de Thomas sera de $19$ euros. On peut d’ailleurs assez facilement étendre le résultat à des valeurs
différentes des coûts par livre et par interface.

Algorithme stochastique

Mission accomplie — Thomas peut aller boire un café bien mérité. Ah non,
il y a un rebondissement : son patron lui demande maintenant de s’occuper du
stockage des livres dans le tout nouvel entrepôt, encore plus grand que le
précédent. Et à force d’avoir beaucoup marché, Thomas souffre de
courbatures !
En plus, le nouvel entrepôt va bientôt alimenter la vente par
correspondance, il s’agira donc de remplir en continu les cases libérées par
des livres vendus, dans un ordre et à des moments totalement imprévisibles.
Il faut donc à Thomas un algorithme de rangement automatisé et robuste au
bruit.

Thomas se dit qu’il pourrait se servir des robots qui parcourent les rayons pour
aller chercher des livres à envoyer. Ces robots peuvent se déplacer très
vite vers n’importe quelle case qu’on leur spécifie, pour y prendre ou y
déposer un livre. Malheureusement, leur cerveau électronique étant rudimentaire (il est inspiré de celui des Shadoks), leurs capacités intellectuelles sont limitées : ils ne sont capables ni de voir l’entrepôt dans son ensemble, ni de garder en mémoire son état. En fait, à tout moment ils ne discernent que ce qui se passe dans la case où ils se trouvent, ainsi que dans les $4$ cases voisines.

Thomas se souvient alors de son cours de processus aléatoires, suivi au
master professionnalisant de mathématiques à l’université d’O. Il y avait
appris que les algorithmes stochastiques [2] étaient souvent plus performants que
les algorithmes déterministes, surtout si l’on ne dispose que d’une
connaissance imparfaite du système [3]. Pour l’instant, la vente par correspondance n’ayant pas encore commencé, les robots n’ont rien à faire. Thomas reprogramme l’un d’eux avec l’algorithme suivant :

  1. choisis au hasard l’une des $N$ cases
    de l’entrepôt (chaque case ayant la même probabilité $1/N$) ;
  2. rends-toi à cette case ; si la case est vide, détermine le coût d’y
    déposer un livre, et si elle est pleine, détermine le coût d’enlever le
    livre qui s’y trouve ; ce calcul ne nécessite de connaître que l’état de
    la case et de ses $4$ voisines ;
  3. si l’opération a pour effet de diminuer le coût, alors effectue-la ;
    sinon, ne fais rien ;
  4. recommence à l’étape 1.

Thomas lance le robot dans l’entrepôt vide, et va boire son café.
Lorsqu’il revient une demi-heure plus tard, il trouve l’entrepôt aussi
désespérément vide qu’auparavant. En observant le robot, il comprend vite
ce qui se passe : le robot choisit bien une case au hasard, s’y rend, et fait
le raisonnement suivant. La case étant vide, sa seule possibilité est d’y
déposer un livre. Mais à cause des interfaces que cela crée, l’opération
aurait pour effet d’augmenter le coût de $7$ euros. Donc il décide de ne
rien faire.

Evidemment, on s’était déjà aperçu plus haut qu’il était impossible
d’atteindre l’état optimal sans augmenter temporairement le coût. Après
avoir réfléchi quelque temps, Thomas décide de modifier son algorithme de
la façon suivante :

  • 3. si le fait d’ajouter ou d’enlever un livre diminue le coût, alors
    fais-le ; sinon, effectue l’opération avec une probabilité qui est d’autant
    plus petite que l’augmentation du coût est forte.

De cette manière, le robot va effectuer de temps en temps des opérations
qui augmentent le coût, tout en privilégiant celles qui l’augmentent le
moins possible. Reste à choisir la probabilité. Si $\Delta H$ désigne le
coût de l’opération (ajouter ou enlever un livre), un choix courant [4] pour la
probabilité $p$ d’accepter l’opération est
\[ p = e^{-b \Delta H} . \]
Ici $b$ est un paramètre ajustable qui s’interprète comme l’inverse
d’une température. Il doit être bien choisi. En effet,

  • Si $b$ est trop petit, toutes les opérations seront choisies avec
    grande probabilité. Le robot va déposer des livres n’importe où, et en
    enlever aussi, ce qui conduira à un entrepôt très mal rangé, avec
    beaucoup de trous. C’est ce qu’on appelle un comportement à haute
    température
    .
  • Si $b$ est trop grand, même les opérations raisonnables
    (déposer un livre à côté d’une case pleine) seront rejetées par le
    robot avec grande probabilité, et on se retrouve dans la situation
    précédente d’un entrepôt restant vide, du moins pendant un temps très
    long. On parle d’un comportement de basse température, ou encore
    métastable.

Lorsque le robot est lancé dans l’entrepôt vide, il va parfois déposer des livres, parfois en enlever. Le coût augmente et diminue donc de manière aléatoire. Cependant, il ne peut devenir négatif tant qu’il n’existe pas d’amas de livres ayant au moins la taille critique. Après quelque temps, le coût va atteindre une valeur maximale, qui est nécessairement supérieure ou égale à la valeur $19$ déterminée plus haut. Ensuite, le coût aura tendance à diminuer, et va finir par devenir négatif alors que l’entrepôt se remplit peu à peu de livres.

Les simulations suivantes montrent la configuration de coût maximal produite par
l’algorithme de Thomas. Les paramètres sont les mêmes que ci-dessus
(déposer un livre diminue le coût d’un euro, chaque interface coûte $2$
euros), et le paramètre $b$ prend des valeurs de $0.1$ à $0.8$, avec
des incréments de $0.1$ :

PNG - 24.6 ko
b = 0.1
PNG - 22.1 ko
b = 0.2
PNG - 19.6 ko
b = 0.3
PNG - 16.5 ko
b = 0.4
PNG - 12.3 ko
b = 0.5
PNG - 8.8 ko
b = 0.6
PNG - 6.6 ko
b = 0.7
PNG - 3.5 ko
b = 0.8

Pour $b$ inférieur ou égal à $0.3$, l’algorithme produit un
résultat beaucoup trop désordonné. A partir de $b=0.4$, on voit tout
de même apparaître des amas de livres plus grands. Pour $b=0.7$,
le résultat commence à ressembler plus au résultat optimal déterminé
plus haut. Du moins on observe bien l’apparition d’un ou plusieurs grands amas
de livres. Au-delà de $b=0.8$, l’algorithme commence à devenir trop
lent pour être efficace. C’est surtout pour un entrepôt vide qu’il peine
à former des amas de livres.

La séquence suivante de simulations a été effectuée lorsque le bonus
pour chaque livre rangé est de $50$ centimes au lieu d’un euro. On peut voir que dans ce cas la stratégie optimale fournit un coût maximal de $35.5$ euros, obtenu pour un carré de $8\times8$ livres plus un livre, ou un rectangle de $8\times9$ livres plus un livre.

PNG - 24.9 ko
b = 0.1
PNG - 23.1 ko
b = 0.2
PNG - 19.7 ko
b = 0.3
PNG - 16.9 ko
b = 0.4
PNG - 11.7 ko
b = 0.5
PNG - 6.7 ko
b = 0.6
PNG - 4.1 ko
b = 0.7
PNG - 3.3 ko
b = 0.8

On sait montrer [NS] que dans la limite de $b$ tendant vers l’infini, cet algorithme
fournit la solution optimale déterminée plus haut [5]. Toutefois, cela prend un
temps très long, de l’ordre $e^{bH}$, où $H$ est le coût maximal par rapport à celui de l’entrepôt vide, donc $H=19$ dans notre premier exemple, et $H=35.5$ dans le second. En pratique, on ne peut pas choisir un $b$ trop grand, et donc on n’obtiendra qu’une approximation de la
solution optimale. Deux avantages de cet algorithme sont qu’il ne nécessite
que peu de mémoire, et qu’il est robuste au bruit : il continue de fonctionner
si l’on vend des livres, tant que le taux de vente n’est pas trop élevé.

Voici quelques animations illustrant le fonctionnement de l’algorithme.
Les paramètres sont ceux du premier exemple.

Dans le cas $b=0.1$, le comportement est trop désordonné pour réussir à
remplir l’entrepôt :

Pour $b=0.6$, c’est déjà nettement mieux. Les livres tendent à être
mieux regroupés, et bien qu’il y ait encore du désordre, l’entrepôt
finit par se remplir :

Voici enfin une simulation pour $b=1$. Observez comment les livres se
regroupent par amas de forme à peu près carrée, alors que les livres
isolés sont rares. Au début le nombre de livres a de la peine à croître.
Une fois que les amas ont dépassé la taille critique, l’entrepôt se
remplit rapidement :

Au-delà des livres

L’histoire de Thomas n’est bien entendu qu’un prétexte qui nous a permis d’illustrer des idées importantes issues de la physique statistique, et couramment utilisées dans certains algorithmes stochastiques (de la famille des algorithmes dits de Monte-Carlo, où encore MCMC, pour Monte-Carlo Markov chain).

L’algorithme aléatoire décrit ici s’appelle un algorithme de Metropolis—Hastings. Il fut originalement introduit en 1953 par Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, et Edward Teller [MRRTT], et généralisé en 1970 par W. Keith Hastings [H].
On se donne un ensemble de configurations possibles (les $2^N$ états de
l’entrepôt), et on associe à chaque configuration un coût (ou une
énergie). On spécifie de plus un ensemble de transitions permises, comme
dans notre cas le fait de déposer ou d’enlever un livre. Dans ce cas on parle
de dynamique de Glauber. L’algorithme de Metropolis—Hastings consiste à choisir au
hasard l’une des transitions permises, de l’accepter si elle fait baisser
l’énergie, et de l’accepter avec une probabilité exponentielle de la forme
$e^{-b\Delta H}$ si elle augmente l’énergie de $\Delta H$.

Le modèle de l’entrepôt de livres est en fait équivalent au modèle
d’Ising de la physique statistique [6]. C’est un modèle pour des matériaux
ferromagnétiques (qui s’aimantent sous l’influence d’un champ magnétique extérieur). Les états « case vide » et « case
contenant un livre
 » correspondent respectivement aux états « spin
vers le bas
 » et « spin vers le haut » du modèle
d’Ising. Dans le modèle on pénalise les interfaces, et le fait de
privilégier l’un des états correspond à l’existence d’un champ
magnétique extérieur. Le modèle d’Ising est intéressant entre autres
parce que l’on sait démontrer l’existence de transitions de phase (semblables à la fusion de la glace, la vaporisation de l’eau...), en faisant
varier la température ou le champ magnétique.

La dynamique de Metropolis—Glauber décrit la dynamique du modèle d’Ising à
la température spécifiée. Le régime à très basse température
($b\gg 1$) est appelé métastable. Dans ce cas, le système passe un
temps très long dans des minima locaux de la fonction énergie (un entrepôt vide), qui peuvent être différents du minimum global (l’entrepôt plein). Le même phénomène apparaît dans des gaz supersaturés (qui devraient condenser mais ne le font pas
pendant longtemps), et les liquides en surfusion (qui devraient se solidifier).
C’est dû au fait que la condensation ou la solidification se fait par croissance d’une goutte ou d’un cristal (on parle de nucléation), dont la frontière coûte de l’énergie.
La transition est accélérée par la présence d’impuretés, de même
que le dépôt d’un premier livre dans l’entrepôt diminue le
coût des livres suivants. C’est pour la même raison que la pollution
atmosphérique favorise les précipitations : les impuretés font office de germes autour desquels les gouttes de pluie se forment plus facilement.

L’algorithme du recuit simulé est une variante de l’algorithme de Metropolis,
dans laquelle on baisse petit à petit la température. On permet ainsi au
système d’explorer l’espace des configurations, tout en se dirigeant vers les
énergies plus basses, dans l’espoir qu’il trouvera la configuration
d’énergie minimale, ou du moins une approximation de celle-ci [KGV, C].

Pour en savoir plus

  • Tapez « surfusion de l’eau » ou « supercooled water » dans un moteur de
    recherche, et vous trouverez des vidéos
    amusantes sur la solidification spontanée d’eau (ou de bière !).
  • L’article de revue [dH] discute les propriétés de métastabilité établies pour différents modèles faisant intervenir une dynamique de Metropolis, ainsi que des questions ouvertes.
  • On trouvera ici des explications de l’algorithme du recuit simulé, illustrées de très jolis applets java, notamment pour le problème du voyageur de commerce. Voir également l’annexe de cet article sur Images des Mathématiques.
  • Une autre situation intéressante se présente si le champ magnétique extérieur varie au cours du temps. Cela revient à supposer que le patron privilégie tantôt un entrepôt plein, tantôt un entrepôt vide, en changeant d’avis périodiquement. L’état réel de l’entrepôt suivra l’état prescrit avec un certain retard, on parle d’un comportement d’hystérèse. On trouvera ici et des simulations (d’un modèle légèrement différent).
  • Pour des notes de cours sur des algorithmes stochastiques, voir
    ici.

Références

[C] V. Černý, Thermodynamical approach to the traveling salesman problem : An efficient simulation algorithm, Journal of Optimization Theory and Applications 45 (1985), 41—51.

[dH]
F. den Hollander, Metastability under stochastic dynamics, Stochastic
Processes and their Applications 114 (2004) 1-26. (Version Prépublication.)

[H] W. K Hastings, Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika 57 (1970), 97—109.

[KGV] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing, Science 220 (1983) 671—680.

[MRRTT] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, Equations of State Calculations by Fast Computing Machines, Journal of Chemical Physics 21 (1953), 1087—1092.

[NS] E. J. Neves, R. H. Schonmann, Critical droplets and metastability for a Glauber dynamics at very low temperature, Communications in Mathematical Physics 137 (1991), 209—230.

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : amic, Irène Marcovici, Bruno Martin et Karim Drifi.

L’auteur tient également à remercier Cécile Louchet et Pierre Debs de
leur lecture attentive d’une première version de cet article.

Article édité par Aurélien Alvarez

Notes

[1Voir par exemple cet article dans Images des Mathématiques sur l’inégalité isopérimétrique.

[2Synonyme d’aléatoire. Du grec stochos ($\sigma\tau\acute{o}\chi o\varsigma$), la cible, la supposition.
Stochazomai ($\sigma\tau o\chi\acute{\alpha}\zeta o\mu\alpha\iota$)
se traduit « je vise la cible », qui est devenu « je mets en place une stratégie », puis « je réfléchis » et enfin « j’imagine ».
Stochastikē technē ($\sigma\tau o\chi\alpha\sigma\tau\iota\kappa \grave{\eta}$ $\tau\acute{\varepsilon}\chi\nu\eta$) signifie « l’art de la conjecture », ou Ars Conjectandi en latin, qui est le titre d’un livre de Jakob Bernoulli sur la théorie des probabilités, paru (à titre posthume) en 1713. (Merci à Athanasios Batakis pour les éclaircissements étymologiques.)

[3...comme l’explique Denis Talay dans ce billet d’Images des Mathématiques.

[4...mais toute fonction décroissante du coût ferait l’affaire. La fonction exponentielle provient de la physique statistique, où elle définit la distribution de Gibbs.

[5L’analyse se sert de l’inégalité isopérimétrique. Diverses améliorations du résultat sont discutées dans l’article de revue [dH].

[6...dont il est également question dans cet article d’Images des Mathématiques.

Partager cet article

Pour citer cet article :

Nils Berglund — «Rangez-moi ces bouquins !» — Images des Mathématiques, CNRS, 2012

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM