Métaheuristiques : trouver vite sans solution parfaite

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Aujourd'hui, on vous a préparé un programme hyper dynamique. Préparez-vous parce qu'on s'attaque à une exploration franchement absolument fascinante au cœur de l'optimisation mathématique.

Intervenant 20:14

Ouais, un sujet vaste et souvent mal compris en fait.

Intervenant 10:18

Totalement. Alors pour cette session, on a rassemblé une pile de sources assez imposantes. On a des articles d'informatique théorique hyper pointus, des papiers de recherche sur les algorithmes contemporains et bien sûr des notes de synthèse passionnantes de la rédaction. Et le but de notre mission aujourd'hui, c'est de comprendre ce qui se passe quand les mathématiques littéralement se cassent les dents sur un problème.

Intervenant 20:40

C'est une super façon de le formuler parce que, tu vois, on a souvent l'image des mathématiques comme une espèce de science toute puissante. Genre, il suffit de donner un problème à un ordi assez costaud et paf, on a la solution. Ben

Intervenant 10:52

ouais, c'est ce qu'on se dit tous.

Intervenant 20:54

Sauf que la réalité est bien plus nuancée et parfois beaucoup plus frustrante.

Intervenant 10:59

C'est clair. Imaginons un instant le pire cauchemar d'un logisticien, tu vois. On a un modèle mathématique à résoudre, c'est pas juste une petite équation de lycée, c'est un système avec des millions de variables, des inéquations dans tous les sens, et très vite on fait face à ce fameux mur, l'explosion combinatoire.

Intervenant 21:17

Ah oui, le moment où tout s'effondre.

Intervenant 11:19

Voilà. On lance le calcul, les ventilos du serveur se mettent à hurler, l'écran fige, et le temps de calcul estimé affiche un truc du genre 3 milliards d'années.

Intervenant 21:28

Ouais, c'est le mur absolu. Et face à ça, la question n'est pas juste théorique, elle est brutale. Qu'est-ce qu'on fait quand un problème est si monstrueux qu'absolument aucune de nos méthodes classiques marche ?

Intervenant 11:39

Surtout quand on a besoin d'une décision dans les dix prochaines minutes en fait.

Intervenant 21:42

Exactement.

Intervenant 11:44

Bon, du coup, c'est tout l'enjeu de notre plongée d'aujourd'hui. Comment forcer le destin quand l'ordinateur refuse de coopérer ? Mais avant de parler des solutions de secours, j'aimerais bien qu'on comprenne pourquoi ça bloque. Pourquoi un supercalculateur moderne s'étouffe ?

Intervenant 22:00

Alors, pour piger ce blocage, il faut évoquer un des plus grands mystères de l'informatique théorique. Le fameux problème du millénaire. L'hypothèse de savoir si P est égal à NP.

Intervenant 12:11

Oula ! D'accord, posons les bases directes, parce que ça c'est un concept qui peut vite donner des maux de tête. Ça veut dire quoi concrètement P et NP ?

Intervenant 22:19

On va simplifier au maximum. L'ensemble P, ça regroupe les problèmes qu'un ordi peut résoudre facilement, dans un temps raisonnable.

Intervenant 12:28

Genre, un exemple ?

Intervenant 22:29

Tu penses à trier une liste de noms par ordre alphabétique. Même avec un million de noms, la machine, elle te fait ça en une fraction de seconde.

Intervenant 12:36

Ouais, c'est instantané.

Intervenant 22:37

Voilà. L'ensemble NP, par contre, ça regroupe des problèmes où c'est hyper facile de vérifier si une solution qu'on te propose est bonne, mais c'est potentiellement impossible de trouver cette solution depuis zéro de manière efficace.

Intervenant 12:50

Ah d'accord. Donc si je saisis bien, sous l'hypothèse que P est différent de NP, ce que tout le monde admet en gros, ça signifie qu'il y a une frontière infranchissable. C'est pas un souci de processeur trop vieux ou d'un codeur qui a mal fait son boulot.

Intervenant 23:04

Non pas du tout.

Intervenant 13:05

C'est carrément la nature de l'univers mathématique qui dit bah non, trouver la solution parfaite ici, ça prendra toujours un temps délirant.

Intervenant 23:12

C'est exactement ça pour ces problèmes d'optimisation qu'on appelle NP difficile. Chercher la perfection, c'est mathématiquement hors de portée si t'es pressé.

Intervenant 13:22

Bon, passons à un exemple concret qu'on a dans nos recherches là. Le piège, je trouve, c'est que ces monstres mathématiques, ils ont souvent l'air super simples. Ils se cachent derrière des formulations d'une innocence redoutable.

Intervenant 23:35

Prenons le célébrissime problème du voyageur de commerce.

Intervenant 13:38

Ah, le classique.

Intervenant 23:39

C'est vraiment l'archétype du problème NP difficile. La formulation tient en une phrase. Tu as un ensemble de villes sur une carte. Quel est le trajet le plus court possible pour visiter chaque ville exactement une fois et revenir à ton point de départ ?

Intervenant 13:54

En apparence, c'est enfantin. Tu prends un stylo, tu relis des points. Mais l'article qu'on a épluché montre que les enjeux derrière sont colossaux. Imaginons une immense boîte de logistique, genre Amazon ou FedEx. S'ils optimisent mal la tournée de leurs milliers de camions, c'est pas juste pour faire joli sur une carte. C'est du carburant gaspillé, de l'usure, des heures sup. On part d'un manque à gagner qui chiffre en centaines de millions de dollars.

Intervenant 24:21

Ouais, c'est colossal. Et c'est là que le piège du voyageur de commerce se referme. S'il y a, disons, 5 villes, l'ordi teste toutes les combinaisons en un éclair. S'il y a 10 villes, on grimpe à environ 3 millions de trajets possibles.

Intervenant 14:34

Ça va 3 millions, un ordi gère.

Intervenant 24:36

Un ordi gère très bien. Mais attention, avec seulement 50 villes, 50, c'est rien. Le nombre de trajets possibles dépasse le nombre d'atomes dans l'univers observable.

Intervenant 14:45

Attends, vraiment ?

Intervenant 24:47

Juste avec 50 villes ? Ouais, juste 50. Et c'est ça, la fameuse explosion combinatoire. Malgré la simplicité du truc, il n'y a aucun algorithme au monde capable de résoudre ça parfaitement pour un grand nombre de villes. Le temps de calcul, il augmente de façon exponentielle. Chaque ville que tu rajoutes, paf, ça multiplie le temps astronomiquement.

Intervenant 15:05

Bon, du coup, on est au pied du mur. La boîte de logistique, elle doit lancer ses camions dans 15 minutes. L'ordi lui dit qu'il lui faut 15 milliards d'années pour trouver le trajet parfait. On fait quoi là ? On débranche tout et on y va au pif ?

Intervenant 25:16

Sûrement pas. C'est là qu'on a un changement de paradigme crucial en fait. On abandonne l'idée de la perfection et on passe à ce qu'on appelle les heuristiques.

Intervenant 15:25

D'accord.

Intervenant 25:25

Le terme, il vient du grec « Euriskein », ça veut dire « trouver ». Le but d'une heuristique, c'est plus de trouver LA solution absolue, puisqu'on sait que c'est mort. Le but, c'est de trouver une solution de bonne qualité.