Mesurer et comparer des méthodes

Une question, cinq règles, un plan

Une cheffe d'atelier demande : « le recuit est-il meilleur que les redémarrages ? ». La réponse n'est pas un nombre. Au chapitre 8, cinq graines de recuit sur la plaque P-217 donnent de 633,23 à 647,35 mm, cinq graines de descente 633,23 ou 645,65 : avec une seule graine, on aurait pu conclure ce qu'on voulait. Une méthode qui tire au hasard a une distribution de résultats, et c'est cette distribution qu'on compare.

Ces règles s'appliquent par un plan d'expérience : la description, écrite avant le premier lancer, de ce que l'expérience fait varier, garde fixe et mesure, une expérience étant le lancer d'une méthode sur une graine. Pour la question de la cheffe d'atelier, posée sur la grande plaque P-600, il fixe cinq choses.

• Les facteurs, ce qu'on fait varier exprès : la méthode (le recuit, deux variantes de redémarrages) et le budget (100 000, 300 000 et un million d'évaluations).
• Ce qui reste fixe : l'instance, le voisinage (le 2-opt), l'unité du budget, les réglages une fois choisis ; ce qui changerait avec un facteur se mêlerait à son effet.
• Ce qu'on mesure : pour chaque lancer, la meilleure tournée vue et son écart à l'optimum ; pour chaque méthode, le temps de calcul, qui se rapporte sans servir à égaliser.
• Les répétitions : les graines 0 à 9 pour chaque méthode, quand le réglage du recuit a pris les graines 100 à 129 (chapitre 8). Un même réglage donne, d'une graine à l'autre, des tournées qui s'étalent sur 100 à 150 mm : un écart entre méthodes ne se lit que s'il dépasse ce que les graines font bouger.
• Ce qu'on pourra conclure : un classement sur cette plaque, à ces budgets, dans cette unité ; pas un classement des méthodes en général.

Choisi après avoir vu les résultats, un plan devient un moyen de leur faire dire ce qu'on voulait. L'unité du budget en fait partie : ici les évaluations, qui ne dépendent ni de la machine ni du langage ; les secondes viennent plus loin, et la conclusion change de l'une à l'autre.

Une première comparaison : le recuit et les redémarrages

Sur la grande plaque

Le programme suivant applique ce plan à 100 000 évaluations ; l'optimum de P-600, 2 788,70 mm, est démontré. Le recuit part du plus proche voisin, réglé à 5 % de dégradations acceptées au départ, une proportion mesurée sur 1 000 voisins (chapitre 8) dont les évaluations se retirent de son budget. Les redémarrages du chapitre 7 sont mesurés dans deux variantes, au meilleur voisin et au premier voisin qui raccourcit, pour ne pas juger un concurrent sur sa variante la plus faible ; une descente que la fin du budget interrompt compte pour ce qu'elle a atteint. Un bloc du site s'arrête au bout de huit secondes : les lignes de 300 000 et d'un million d'évaluations viennent du même programme, lancé hors du navigateur.

Les pourcentages sont les écarts à l'optimum.

• À 100 000 évaluations, les redémarrages ne finissent pas une descente : depuis un ordre tiré au hasard, il en faut une centaine de milliers, et 0,1 descente en moyenne arrive à son optimum local. Le budget est trop court pour eux, pas pour le recuit, qui n'évalue qu'un voisin par itération.
• À 300 000 évaluations, la médiane du recuit est à 1,5 % de l'optimum, contre 4,6 % (meilleur voisin) et 2,5 % (premier voisin), et son pire résultat, 2,2 %, bat leurs médianes.
• À un million d'évaluations, le meilleur tirage atteint l'optimum pour le recuit comme pour les redémarrages au meilleur voisin : à ne regarder que lui, on conclurait à l'égalité. La médiane et le pire disent autre chose, 0,3 % et 1,8 % pour le recuit contre 2,2 % et 4,2 % (meilleur voisin), 1,6 % et 3,4 % (premier voisin). Le recuit est plus régulier : c'est ce que protège la règle 2.

Combien de graines ? La figure à neuf méthodes, plus loin, reprend ces programmes sur vingt graines, dont les dix premières sont celles du tableau ; une mesure hors du navigateur en a pris trente. À 100 000 évaluations, la médiane du recuit ne bouge pas de dix à vingt graines (2 850,8 mm, 2,23 %) et vaut 1,9 % sur trente ; celle des redémarrages au meilleur voisin passe de 8,3 % à 7,26 %, puis à 6,8 %. Le classement tient, mais une médiane peut bouger d'un point et demi quand on ajoute des graines : un écart plus petit ne se lit pas.

Sur un petit problème : huit postes

Le second problème est l'affectation de huit opérateurs à huit postes, d'optimum 95 minutes (la meilleure de 40 320 affectations). Le voisinage est l'échange de deux postes, 28 voisins. Le recuit est mesuré à trois réglages, 5 %, 20 % et 50 % de dégradations acceptées au départ, donnés tous les trois pour qu'aucun ne soit choisi après coup ; sa température se mesure sur une graine à part. Les redémarrages descendent au meilleur voisin depuis des ordres tirés au hasard. Vingt graines par méthode.

Ici, les redémarrages font au moins aussi bien, même contre le meilleur réglage du recuit. Vingt graines ne suffisent pas à l'établir (15 optimums contre 11 à 1 000 évaluations, 20 contre 19 à 3 000) ; deux cents graines, hors du navigateur, le confirment : 156 contre 115 au recuit à 50 % à 1 000 évaluations, 199 contre 184 à 3 000. L'espace est petit, et 1 000 évaluations font six descentes en moyenne, 3 000 près de vingt, quand le recuit a besoin de son budget pour refroidir ; une de ses itérations coûte en outre plus de deux fois le temps d'une évaluation de descente.

Le réglage ne se transporte pas tel quel. Sur la plaque, les proportions de 2 % à 50 % se valent ; sur les postes, dont les dégradations sont de quelques minutes, 5 % et 20 % font nettement moins bien (sur deux cents graines, à 3 000 évaluations : 19 et 67 optimums, contre 184 à 50 %, et de 184 à 187 de 50 % à 95 %). Un pourcentage se transporte mieux qu'une température, mais le plateau se mesure pour chaque problème.

Le protocole complet

Une fonction par méthode, une boucle pour toutes

Un protocole refait à la main à chaque comparaison finit bâclé. Il s'écrit une fois : une fonction par méthode, qui reçoit un budget et une graine, et une boucle qui les lance toutes sur les mêmes budgets et les mêmes graines. Le programme suivant le fait sur un troisième problème de Valdrome : trente opérateurs sur trente postes, aux temps engendrés par une formule reproductible (graine 1). Le budget compte une évaluation par voisin examiné pour les descentes, une par itération pour le recuit, dont on retire les 200 évaluations qui ont réglé sa température ; variation évalue un échange de deux postes en quatre lectures.

Chaque méthode rend sa trace, le coût de la solution qu'elle tient après chacune de ses évaluations : le résultat d'un lancer en est le minimum. La référence est calculée, non cherchée : l'affectation se résout exactement, en un temps qui ne compte pas, par l'algorithme hongrois (linear_sum_assignment, de scipy).

À 500 évaluations, la médiane des redémarrages est à 104,5 % de l'optimum de 255 minutes, une descente depuis un ordre tiré au hasard demandant bien plus que ce budget ; le recuit est à 21,6 %. L'écart reste net à 2 000 évaluations (72,0 % contre 7,5 %) et se resserre à 10 000 (7,6 % contre 4,5 %). La suite lit les mêmes tirages autrement : deux lectures trompent, la troisième résume.

• Graine par graine, à 10 000 évaluations, le recuit gagne 8 fois sur 10 : sur une seule graine, une comparaison aurait pu annoncer le contraire, avec les mêmes programmes.
• Le meilleur tirage, 259 minutes contre 265, ne dit rien de l'ordinaire. La médiane, 266,5 contre 274,5, et le pire, 273 contre 289, en disent davantage.
• Le profil de performance donne la part des tirages à moins de $x$ % de l'optimum : pour les redémarrages, aucun à moins de 2 %, un sur dix à moins de 5 %, sept sur dix à moins de 10 % ; pour le recuit, un, six et dix sur dix. C'est la distribution entière, en trois seuils.

Le plan d'expérience se lit dans le code : les facteurs sont METHODES et BUDGETS, les répétitions GRAINES, et ce qui reste fixe (instance, voisinage, référence) est posé avant eux. Une méthode de plus s'ajoute en une ligne.

La courbe de convergence

Le tableau donne la qualité à trois budgets ; une courbe de convergence la donne à tous : en abscisse les évaluations dépensées, en ordonnée le meilleur coût vu jusque-là, la médiane des graines en trait et la bande du meilleur au pire tirage autour. Elle se construit à partir des traces.

Le programme du protocole fait ce calcul pour les dix lancers de 10 000 évaluations de chaque méthode (accumulate(t, min) donne d'un coup le meilleur coût vu après chaque évaluation), trace la médiane et la bande, et marque d'un point la médiane des lancers faits pour 500, 2 000 et 10 000 évaluations. Les deux méthodes ne se lisent pas de la même façon.

• Pour les redémarrages, un long lancer vaut des lancers courts. Leur hasard ne dépend pas du budget : jusqu'à sa 2 000e évaluation, un lancer de 10 000 fait exactement ce que fait un lancer de 2 000, et les points tombent sur la courbe (521,5 et 438,5 minutes à 500 et 2 000 évaluations). La courbe, plate pendant le premier balayage, descend ensuite d'une marche par balayage.
• Pour le recuit, non. Son refroidissement est réglé sur le budget : à la 2 000e évaluation d'un lancer de 10 000, il est encore chaud, quand un lancer de 2 000 a fini de refroidir. Lu en chemin, le long lancer tient 327 minutes en médiane à 2 000 évaluations, les lancers faits pour ce budget 274 ; à 500, 380,5 contre 310.

La courbe d'une méthode sans calendrier se lit donc sur un seul long lancer ; celle d'un recuit demande un lancer par budget.

Toutes les méthodes, et deux façons de compter le budget

Neuf méthodes sur la plaque P-600

La figure suivante oppose neuf méthodes sur P-600, celles des chapitres 6 à 11, chacune écrite et réglée comme dans son chapitre, avec le même décompte du budget ; seul le génétique a été réglé à nouveau. Là où un chapitre publie un résultat, les dix premières graines le redonnent exactement. Les vingt tirages par méthode et par budget ont été faits une fois par un script du dépôt. La figure demande de miser avant de voir ; rien des résultats n'apparaît avant la mise, ni la référence.

Le tableau suivant garde l'écart de la médiane à l'optimum. À lire après avoir joué.

Six constats, dans leur cadre : cette plaque, ces réglages, vingt graines.

• Une construction suivie d'une descente est un concurrent sérieux à petit budget : 5,57 %, sans réglage, pour 26 596 évaluations, mieux à 100 000 évaluations que les redémarrages, le tabou, le génétique et les fourmis Max-Min.
• Redémarrages et tabou ne se séparent qu'à 300 000 évaluations (4,23 % contre 2,71 %) : avant, aucune descente n'est finie, les deux méthodes sont la même descente interrompue au même endroit.
• GRASP fait mieux que les redémarrages à chaque budget (2,90 % contre 7,26 % à 100 000) : une construction gloutonne randomisée épargne à la descente la moitié de son chemin.
• Sans recherche locale, les méthodes à population traînent : les fourmis Max-Min de 17,2 % à 3,71 %, le génétique de 6,01 % à 1,39 %. Avec une descente, les fourmis passent de 3,25 % à 0,70 %, et le mémétique devance le génétique à chaque budget.
• Le recuit a la meilleure médiane à 100 000, un et trois millions d'évaluations, les fourmis avec 2-opt à 300 000 ; mais à un million comme à trois millions, la figure ne sépare du recuit ni GRASP ni les fourmis avec 2-opt.
• Le vainqueur dépend de ce qu'on regarde : au meilleur tirage, à 100 000 évaluations, c'est GRASP (0,31 % contre 0,40 % pour le recuit), et à 300 000 trois méthodes tombent sur l'optimum.

Un rang ne se lit pas sans les tirages. À 300 000 évaluations, quatre méthodes tiennent en quatre dixièmes de point (1,19 %, 1,31 %, 1,54 %, 1,56 %). La figure liste les méthodes dont la médiane tombe dans la boîte du premier, entre le premier et le troisième quartile de ses tirages : ici GRASP, que vingt graines ne départagent pas des fourmis avec 2-opt. Le hasard des graines fait bouger une médiane d'autant : celle du recuit est à 1,56 % à 300 000 évaluations, à 0,83 % à 210 000 (le budget d'une demi-seconde, plus bas).

Évaluations ou secondes

Le budget en évaluations ne dépend pas de la machine, mais une évaluation ne coûte pas la même chose selon la méthode : quatre lectures d'une matrice pour un voisin 2-opt, soixante et une pour une tournée de génétique, et pour le recuit, en plus des quatre lectures, un tirage de positions, un test d'acceptation, parfois un retournement de segment. Le tableau donne les débits des programmes qui ont produit les tirages, sur le poste qui les a faits.

Comparer à évaluations égales revient à donner au génétique 27 fois plus de temps qu'à une descente, au recuit 7 fois plus. La figure suivante refait la comparaison à temps de calcul égal : chaque méthode reçoit le même nombre de secondes, donc les évaluations que son débit permet.

Le classement se réordonne. Une demi-seconde donne plus d'un million d'évaluations à GRASP, aux redémarrages et au tabou, 210 000 au recuit, 52 000 au génétique. À 2 secondes, GRASP est en tête (0,41 %), et la figure ne le sépare pas des redémarrages (0,69 %) ni des fourmis avec 2-opt (0,70 %) ; à 8 secondes, GRASP et les redémarrages (0,10 % et 0,26 %) devancent le recuit (0,52 %). Les fourmis Max-Min, qui perdaient à un million d'évaluations, retrouvent 0,70 % avec 45 millions : il leur fallait du temps, pas une autre méthode.

Ce classement est celui de ces programmes, car le rapport des coûts dépend de l'écriture. Une itération de recuit coûte 6,6 évaluations de descente dans le script des figures ; de 3 à 5, selon l'ordinateur, dans le programme de la première comparaison, qui tire ses positions avec deux_positions et allège le balayage des descentes ; de 10 à 16 si ce recuit tire ses positions avec sample, pour exactement les mêmes tournées. Sur trente graines, hors du navigateur, le recuit de 300 000 évaluations a une médiane à 1,3 % de l'optimum, les redémarrages à 4,2 % (meilleur voisin) et 2,9 % (premier voisin) au même budget. À durée égale, ils reçoivent un million d'évaluations face à la première écriture et passent à 1,9 % et 1,5 % ; quatre millions face à la seconde, et passent à 0,9 % et 0,8 %. L'avance du recuit tombe de 1,6 à 2,9 points à quelques dixièmes (sur cent trente graines, de 0,3 à 0,4 point : établie, mais petite), puis s'inverse.

Trente postes : un autre problème, un autre classement

La figure suivante reprend les trente postes du protocole avec six méthodes (les fourmis et le mémétique, propres aux tournées, n'y jouent pas), sur quatre budgets ; l'optimum exact est 255 minutes. Les dix premières graines des redémarrages et du recuit sont celles du protocole : à 10 000 évaluations, leurs médianes passent de 7,6 % et 4,5 % sur dix graines à 7,45 % et 4,71 % sur vingt.

Le vainqueur n'est plus le même. GRASP a la meilleure médiane à chaque budget, à égalité avec la règle par case suivie d'une descente à 10 000 évaluations et avec le recuit à 500 000. Le tabou, dans le bas du classement de la plaque, est deuxième à 30 000 et 100 000 évaluations ; le recuit, premier de la plaque à 100 000, est ici troisième jusqu'à 100 000. La règle par case suivie d'une descente coûte 3 046 évaluations, sans hasard : à 10 000 évaluations, elle bat toutes les métaheuristiques sauf GRASP, son égal. Et l'algorithme hongrois rend 255 en un instant : sur ce problème, aucune de ces comparaisons n'avait d'enjeu pratique. Elles servent à s'exercer là où la réponse est connue, avant de juger une méthode là où elle ne l'est pas.

Le même soin pour chacun

Les graines qui jugent, dans les figures, sont 0 à 19 ; les réglages ont été cherchés sur d'autres, 100 à 104 pour la plaque et 100 à 109 pour les postes, par une grille par méthode.

Une grille est jugée sur la médiane de cinq graines (dix pour les postes) : un réglage retenu est un bon choix, pas le bon. Trois retenues ne sont d'ailleurs pas la meilleure médiane de leur grille, celles des chapitres ayant été gardées : le recuit à 5 % (10 % fait 1,3 % contre 1,8 %), GRASP à alpha 0,05 (0,5 fait 1,4 % contre 1,9 %, et 0,2 fait 4,2 % : cinq graines ne distinguent pas ces valeurs), le mémétique à six individus (dix font 1,5 % contre 2,0 %). Le réglage pèse parfois plus que la méthode : à 100 000 évaluations, sur les graines 0 à 9, la médiane du génétique seul est à 17,1 % de l'optimum avec le réglage de départ du chapitre 10 (cent individus, tournoi de trois, mutation à 30 %), à 7,8 % avec celui de la grille. La règle ne demande pas le même nombre d'essais à chaque méthode, mais une recherche honnête pour chacune.

Ce qui fausse une comparaison

Ce qu'on peut conclure

Une comparaison bien menée rend un classement dans un cadre : ce problème, ces budgets dans cette unité, ces réglages, ces programmes, ce nombre de graines. Ce chapitre a mesuré quatre cadres, et aucune méthode ne gagne dans tous : le recuit sur la grande plaque à évaluations égales, GRASP sur la même plaque à durée égale, les redémarrages sur huit postes, GRASP encore sur trente postes, où une règle constructive suivie d'une descente tient tête à toutes les métaheuristiques à petit budget. Ce qui se transporte d'un cadre à l'autre est la méthode de comparaison, pas son verdict. Un écart plus petit que ce que les graines font bouger ne se conclut pas, et un résultat dit sans son cadre ne se vérifie pas.

Exercices type

Sur la page Exercices, le thème de ce chapitre fait chiffrer un plan, résumer des tirages, construire la bande d'une courbe et juger une conclusion ; celui de l'ingénierie de la décision a deux exercices de comparaison, dont une comparaison qui range les graines avant de les confronter.

La méthode

1. Écrire le plan d'expérience avant de lancer : facteurs et niveaux, ce qui reste fixe, mesures, graines de réglage et graines de jugement, portée de la conclusion.
2. Régler chaque méthode avec le même soin sur ses graines de réglage, et l'écrire ; mettre dans la comparaison une règle constructive suivie d'une descente.
3. Lancer chaque méthode sur les mêmes graines, dix au moins, au même budget dans une unité dite, préparation comprise, et mesurer aussi l'autre unité.
4. Résumer chaque série par la meilleure, la médiane et la pire, en écart à une référence exacte ou à une borne.
5. Tracer la courbe de convergence et le profil : un seul long lancer suffit si le calendrier de la méthode ne dépend pas du budget, sinon un lancer par budget.
6. Conclure dans le cadre : un écart plus petit que la dispersion des médianes ne se lit pas.

Synthèse

• Une méthode aléatoire se juge par un plan d'expérience écrit avant de lancer : plusieurs graines, meilleure, médiane et pire, budget égal dans une unité dite, écart à une référence, réglages faits avec le même soin sur d'autres graines.
• Sur P-600, à 300 000 évaluations, la médiane du recuit est à 1,5 % de l'optimum, celles des redémarrages à 4,6 % et 2,5 % ; à durée égale, cette avance fond ou s'inverse selon l'écriture du programme. Le classement dépend de l'unité du budget.
• Une courbe de convergence donne le meilleur coût vu selon le budget, médiane et bande ; un profil de performance, la part des tirages à moins de $x$ % de la référence. Un long recuit ne se lit pas comme des recuits courts.
• Aucune méthode ne gagne partout, et un rang n'est pas une différence tant que la médiane de l'un tombe dans la boîte de l'autre.

Et ensuite

Comparer des méthodes entre elles ne dit pas encore s'il fallait en écrire une. Le chapitre suivant met les méthodes du parcours face aux solveurs, et suit une décision jusqu'à l'atelier : des données incertaines, des contraintes que personne n'a écrites, un plan qui doit rester stable d'un jour à l'autre.