Certains problèmes d'optimisation semblent faciles à énoncer et sont impossibles à résoudre exactement dès qu'ils grandissent. Plutôt que d'attendre la fin de l'univers, on se contente d'une bonne solution, trouvée vite. Encore faut-il savoir à quel point elle est bonne.
Le fil rouge de la page est le problème du voyageur de commerce : passer par n villes une fois chacune et revenir au départ par le plus court chemin. C'est l'exemple type du problème NP-difficile. Toutes les méthodes présentées ici, des plus naïves aux plus raffinées, s'y appliquent, et bien d'autres problèmes (tournées, ordonnancement, emplois du temps) se traitent de la même façon.
Un recuit simulé sur 70 villes : au début, la tournée accepte souvent des dégradations (température haute), puis elle se fige peu à peu dans une très bonne solution.
Les villes sont tirées au hasard. Tous les calculs et toutes les mesures de temps sont faits dans votre navigateur ; les temps dépendent donc de votre machine. La qualité des solutions est mesurée par rapport à l'optimum exact quand on peut le calculer, sinon par rapport à une borne inférieure certifiée. Cette page prolonge Programmation en nombres entiers et Transport, affectation et tournées.
Planche 1
Difficulté des problèmes : la notion de problème NP-difficile
On mesure la difficulté d'un problème par la façon dont le temps de calcul croît avec sa taille n. Un algorithme polynomial (n, n², n³ opérations) reste praticable quand n grandit. Un algorithme exponentiel (2ⁿ, n!) devient vite inutilisable : ajouter une seule donnée double le temps, ou pire.
Temps de calcul à un milliard d'opérations par seconde, en échelle logarithmique. Les lignes horizontales donnent des repères : une seconde, un jour, un siècle, l'âge de l'univers.
Mesuré dans votre navigateur : trouver un sous-ensemble de n nombres de somme donnée, en essayant tous les 2ⁿ sous-ensembles (points), et vérifier une solution proposée (en bas, presque à zéro).
Mesure : temps multiplié par, à chaque nombre en plus–
Extrapolation à n = 60–
Vérifier une solution trouvée–
Ce qu'il faut retenir. La classe P réunit les problèmes qu'on sait résoudre en temps polynomial (trier, plus court chemin, programmation linéaire). La classe NP réunit ceux dont on sait vérifier une solution en temps polynomial : c'est le cas de la somme de sous-ensemble, où le contrôle prend moins d'une microseconde alors que la recherche double à chaque nombre ajouté. Un problème est NP-difficile s'il est au moins aussi dur que tous les problèmes de NP : en résoudre un rapidement les résoudrait tous. Le voyageur de commerce, le sac à dos, l'ordonnancement d'atelier, les emplois du temps en font partie. Personne ne sait si P = NP ; la question est l'un des sept problèmes du millénaire, dotés d'un million de dollars.
Planche 2
Algorithmes exacts et méthodes approchées
Un algorithme exact garantit l'optimum, mais peut demander un temps exponentiel. L'énumération des (n − 1)!/2 tournées demande déjà près d'une minute à 15 villes et deux ans à 20 ; la programmation dynamique de Held et Karp (1962) ramène le travail à environ n² 2ⁿ, ce qui repousse le mur sans le supprimer. Une méthode approchée est rapide, mais sans certitude : certaines offrent une garantie écrite d'avance, d'autres aucune.
La tournée optimale (tirets rouges) et la tournée de la méthode choisie (trait plein).
Temps mesuré de l'algorithme exact de Held et Karp selon n (points), comparé à l'énumération de toutes les tournées à un milliard par seconde (courbe), et au plus proche voisin (en bas).
Optimum (Held et Karp) ; contrôle : borne du 1-arbre–
Énumération : nombre de tournées–
Sur 200 jeux de 10 villes : écart moyen et pire du plus proche voisin–
Ce qu'il faut retenir. Le plus proche voisin (aller toujours à la ville la plus proche non visitée) est immédiat, mais ne promet rien : en moyenne 10 % au-dessus de l'optimum sur 10 villes, jusqu'à 44 % dans le pire des 200 jeux. Le double arbre parcourt deux fois un arbre couvrant minimal ; comme cet arbre est plus court que toute tournée, il garantit d'être au plus deux fois l'optimum : c'est un algorithme d'approximation, avec un facteur 2. Ajouter une recherche locale (2-opt) rapproche presque toujours de l'optimum, souvent jusqu'à l'atteindre, sans aucune garantie. Sur de petites tailles, la méthode exacte reste la meilleure arme ; elle sert aussi à juger les autres.
Planche 3
Heuristiques gloutonnes et recherche locale
Une heuristique gloutonne construit la solution pas à pas, en prenant à chaque étape le choix qui semble le meilleur, sans jamais revenir en arrière. Une recherche locale part d'une solution complète et l'améliore par petites retouches, ici le 2-opt : on retire deux arêtes et on reconnecte autrement, tant que cela raccourcit. Elle s'arrête sur un optimum local, qu'aucune retouche n'améliore plus.
40 villes. D'abord la construction gloutonne, ville après ville ; puis chaque échange 2-opt : arêtes retirées en rouge, ajoutées en vert.
Longueur de la tournée au fil des améliorations (en haut). En bas : 200 recherches locales lancées depuis des tournées au hasard aboutissent à autant d'optimums locaux, de longueurs différentes. Tirets : la borne inférieure.
Borne inférieure certifiée (1-arbre de Held et Karp)–
Ce qu'il faut retenir. Le glouton est rapide mais myope : ses derniers choix sont forcés, et il laisse de longs retours et des croisements. Le 2-opt défait les croisements et divise l'écart par trois ou quatre. Mais un optimum local n'est pas l'optimum : des départs différents mènent à des optimums locaux différents, parfois éloignés de plusieurs pour cent. D'où les deux idées des métaheuristiques : s'échapper des optimums locaux, et diversifier les points de départ.
Planche 4
Recuit simulé, recherche tabou et algorithmes génétiques
Une métaheuristique est une stratégie générale pour guider une recherche locale au-delà des optimums locaux. Trois idées célèbres. Le recuit simulé (Kirkpatrick, 1983) imite le refroidissement d'un métal : il accepte parfois une dégradation, avec une probabilité e^(−Δ/T) qui diminue avec la température T. La recherche tabou (Glover, 1986) prend toujours le meilleur voisin, même moins bon, mais interdit pendant un temps de défaire les derniers mouvements, pour ne pas tourner en rond. L'algorithme génétique (Holland, 1975) fait évoluer une population de solutions par sélection, croisement et mutation.
–
–
–
Meilleure tournée ; écart à la borne–
Solutions évaluées ; temps–
Pour comparer : plus proche voisin + 2-opt–
––
Ce qu'il faut retenir. Chaque métaheuristique a ses réglages, et ils comptent : un recuit à température nulle n'est qu'une descente, et un recuit trop chaud erre au hasard. Une recherche tabou sans interdiction retombe dans le même optimum local, et un génétique sans mutation perd sa diversité. Les deux premiers partent ici d'une tournée au hasard, et tous voient le même jeu de 50 villes. Le génétique « pur », qui ne connaît pas la géométrie du problème, a besoin de beaucoup de générations (comparez 100 et 1 000) ; dès qu'on améliore chaque enfant par une recherche locale (algorithme mémétique), quelques générations suffisent. C'est la leçon générale : une métaheuristique vaut surtout par la recherche locale qu'elle pilote.
Planche 5
Évaluer la qualité d'une solution et le temps de calcul
Sans l'optimum, comment savoir si une solution est bonne ? On calcule une borne inférieure : une valeur dont on est sûr qu'aucune tournée ne fait mieux. Ici, celle du 1-arbre de Held et Karp. L'écart entre la solution et la borne est un écart garanti : l'optimum est quelque part entre les deux. On compare ensuite les méthodes honnêtement : plusieurs jeux de villes, plusieurs graines, le même effort, et des intervalles de confiance.
Chaque point est une exécution : temps de calcul (échelle logarithmique) et écart à la borne. Les croix donnent la moyenne de chaque méthode. Le meilleur compromis est en bas à gauche.
Écart moyen à la borne inférieure de chaque méthode, avec son intervalle de confiance à 95 %.
–
Banc d'essai–
Meilleure méthode en moyenne–
Optimum encadré, en moyenne sur les jeux : entre la borne et la meilleure solution–
Contrôle de la borne : jamais au-dessus d'une tournée trouvée–
Ce qu'il faut retenir. Une solution approchée ne vaut que si l'on sait la juger. La borne inférieure transforme « une bonne tournée » en « une tournée à moins de x % de l'optimum », et sur ces jeux l'optimum est encadré à environ 1 % près. Sur ces jeux, le mémétique est le meilleur à tous les budgets, suivi du tabou et du recuit, qui se départagent selon l'effort ; le génétique pur est très loin quand on lui donne peu de générations. Le temps compte aussi : le 2-opt à départs multiples donne environ 4 % d'écart en une ou deux millisecondes, vingt fois plus vite que le mémétique ; c'est souvent assez bon pour un premier plan. Une comparaison sérieuse fixe le budget, répète sur plusieurs instances et plusieurs graines, et donne des intervalles de confiance : une seule exécution chanceuse ne prouve rien.
Ce qu'il faut garder
La complexité
Polynomial, on attend ; exponentiel, on n'attend pas. Les problèmes NP-difficiles se vérifient vite, mais se résolvent lentement, sauf peut-être si P = NP.
Les méthodes
Exact pour les petites tailles, glouton pour démarrer, recherche locale pour améliorer, métaheuristique pour s'échapper des optimums locaux.
L'évaluation
Une borne inférieure garantit l'écart ; un banc d'essai équitable mesure qualité et temps ensemble, avec des intervalles de confiance.
Pour aller plus loin
Dans ce cahier.Le voyageur de commerce (heuristiques de construction, bornes, loi de Beardwood-Halton-Hammersley) ; Le problème du sac à dos ; Programmation en nombres entiers (séparation et évaluation) ; Simulation et Monte-Carlo (intervalles de confiance).
Sur les calculs. Somme de sous-ensemble : énumération complète par code de Gray, un seul élément change à chaque pas. Exact : programmation dynamique de Held et Karp sur les sous-ensembles. Double arbre : arbre couvrant minimal de Prim, parcouru en profondeur. 2-opt : amélioration au premier gain. Borne : 1-arbre avec poids de Lagrange ajustés par sous-gradient. Recuit : 2-opt aléatoire, refroidissement géométrique jusqu'au millième de la température initiale. Tabou : meilleur 2-opt non interdit, les arêtes retirées étant interdites pendant la durée choisie, sauf s'il bat le record (critère d'aspiration). Génétique : tournoi à trois, croisement OX, mutation par inversion, remplacement des moins bons. Les temps sont mesurés par l'horloge du navigateur.