7
M´ ethodes d’exploration locale et sch´ emas de
temp´ erature
7.1 Explosions combinatoires
Nous allons pr´ esenter dans cette section, une technique de recherche
al´ eatoire permettant de r´ esoudre des probl` emes d’optimisation combinatoire
redoutables. L’exemple le plus connu est celui du voyageur de commerce qui
doit visiter 365 villes dans l’ann´ ee. Ce dernier doit clairement optimiser ses
trajets, et ´ eviter de planifier chaque jour des visites de villes diam´ etralement
oppos´ ees. Pour trouver le plus court chemin lui permettant de parcourir ces
365 villes dans l’ann´ ee, une premi` ere id´ ee serait d’examiner toutes les configurations de trajets possibles. En utilisant une simple r` egle de multiplication, on
peut se convaincre qu’il y a 365 choix possibles pour commencer les visites,
puis 364 pour la seconde ´ etape, puis 363 choix possibles pour la troisi` eme,
etc. En r´ esum´ e, cette strat´ egie d’´ enum´ eration, le conduirait `
a examiner la
longueur de 365! trajets possibles. N´ eanmoins, en utilisant la formule d’approximation de Stirling, on peut montrer que cette strat´ egie d’´ enum´ eration
est simplement impossible `
a r´ ealiser en pratique
n!
√
2πn n
n e
−n
⇒ 365! 1, 6 × 10
160 trajets possibles
En examinant mille millions de trajets par jour, la mise en place d’une telle
strat´ egie n´ ecessiterait 1, 6.10
151 jours soit plus de 4, 4.10
142 millions d’ann´ ees
de calculs ! Ce probl` eme combinatoire peut aussi s’interpr´ eter comme une
r´ epartition de tˆ aches journali` eres. Il s’agit ici d’affecter une ville ` a chaque
jour de l’ann´ ee, ou inversement.
Dans un autre registre, supposons qu’un ing´ enieur de recherche de r´ eputation assez brute cherche ` a examiner une ` a une les performances de politiques
de tests de qualit´ e sur une chaˆ ıne de production form´ ee de 100 machines.
Sur chacune d’entre elles, il a simplement le choix entre faire ou non un test
sur la qualit´ e des pi` eces produites. Faire des tests sur chacune des machines
serait trop coˆ uteux, et ralentirait la production. En espa¸ cant d’un millim` etre
chacune d’entre elles sur une feuille, il n´ ecessiterait un rouleau de papier de
longueur
P. Del Moral and C. Vergé, Modèles et méthodes stochastiques,
Mathématiques et Applications 75, DOI: 10.1007/978-3-642-54616-7_7,
Ó Springer-Verlag Berlin Heidelberg 2014
1 9 3
M´ ethodes d’exploration locale et sch´ emas de
temp´ erature
7.1 Explosions combinatoires
Nous allons pr´ esenter dans cette section, une technique de recherche
al´ eatoire permettant de r´ esoudre des probl` emes d’optimisation combinatoire
redoutables. L’exemple le plus connu est celui du voyageur de commerce qui
doit visiter 365 villes dans l’ann´ ee. Ce dernier doit clairement optimiser ses
trajets, et ´ eviter de planifier chaque jour des visites de villes diam´ etralement
oppos´ ees. Pour trouver le plus court chemin lui permettant de parcourir ces
365 villes dans l’ann´ ee, une premi` ere id´ ee serait d’examiner toutes les configurations de trajets possibles. En utilisant une simple r` egle de multiplication, on
peut se convaincre qu’il y a 365 choix possibles pour commencer les visites,
puis 364 pour la seconde ´ etape, puis 363 choix possibles pour la troisi` eme,
etc. En r´ esum´ e, cette strat´ egie d’´ enum´ eration, le conduirait `
a examiner la
longueur de 365! trajets possibles. N´ eanmoins, en utilisant la formule d’approximation de Stirling, on peut montrer que cette strat´ egie d’´ enum´ eration
est simplement impossible `
a r´ ealiser en pratique
n!
√
2πn n
n e
−n
⇒ 365! 1, 6 × 10
160 trajets possibles
En examinant mille millions de trajets par jour, la mise en place d’une telle
strat´ egie n´ ecessiterait 1, 6.10
151 jours soit plus de 4, 4.10
142 millions d’ann´ ees
de calculs ! Ce probl` eme combinatoire peut aussi s’interpr´ eter comme une
r´ epartition de tˆ aches journali` eres. Il s’agit ici d’affecter une ville ` a chaque
jour de l’ann´ ee, ou inversement.
Dans un autre registre, supposons qu’un ing´ enieur de recherche de r´ eputation assez brute cherche ` a examiner une ` a une les performances de politiques
de tests de qualit´ e sur une chaˆ ıne de production form´ ee de 100 machines.
Sur chacune d’entre elles, il a simplement le choix entre faire ou non un test
sur la qualit´ e des pi` eces produites. Faire des tests sur chacune des machines
serait trop coˆ uteux, et ralentirait la production. En espa¸ cant d’un millim` etre
chacune d’entre elles sur une feuille, il n´ ecessiterait un rouleau de papier de
longueur
P. Del Moral and C. Vergé, Modèles et méthodes stochastiques,
Mathématiques et Applications 75, DOI: 10.1007/978-3-642-54616-7_7,
Ó Springer-Verlag Berlin Heidelberg 2014
1 9 3