Comment ça marche · L'IA · module en construction
Les IA qui cherchent et optimisent
Mis à jour le .
Ton GPS trouve un trajet en une fraction de seconde parmi des millions possibles. Ces IA n'apprennent rien : elles cherchent. Elles explorent intelligemment les possibilités, et parfois s'inspirent des fourmis ou de l'évolution des espèces.
Choisis ton niveau et ta façon de lire : tu peux en changer à tout moment.
Étape 0 : Le plus court chemin
Pour aller de D à A dans une ville en grille, où l'avenue directe est embouteillée (5 minutes par pâté de maisons au lieu de 1), l'algorithme de Dijkstra explore les rues en onde, des plus proches aux plus lointaines : il examine 167 carrefours avant de trouver le meilleur trajet, 27 minutes, qui contourne le bouchon.
rue (1 min) bouchon (5 min) carrefour examiné trajet
🟢 Découverte
Pour aller de D à A, il y a des millions de trajets possibles. L'algorithme de Dijkstra ne les essaie pas tous : il avance en onde, en calculant le temps pour atteindre chaque carrefour, des plus proches aux plus lointains. L'avenue du milieu est embouteillée.
🟡 Curieux
La carte devient un « graphe » : des carrefours (les nœuds) reliés par des rues (les arêtes), chacune avec un coût, ici des minutes. Dijkstra garde toujours le meilleur temps connu pour chaque carrefour. Quand il atteint l'arrivée, il est sûr d'avoir le meilleur trajet. Ce n'est pas de l'apprentissage : c'est de la recherche, l'une des plus vieilles branches de l'IA.
🔴 Ingénieur
À chaque tour, on retire de la liste des carrefours « ouverts » celui qui a le plus petit temps depuis le départ, puis on met à jour ses voisins : si passer par lui est plus rapide, on retient ce nouveau temps et d'où l'on vient. Avec une file de priorité, le coût est de l'ordre de (A + N) log N pour N carrefours et A rues. Cela ne marche que si aucune rue n'a un coût négatif.
Un peu d'histoire
En 1956, Edsger Dijkstra, programmeur au Centre mathématique d'Amsterdam, cherche une démonstration compréhensible par tous pour un nouvel ordinateur, l'ARMAC : trouver le plus court trajet entre deux villes, sur une carte simplifiée de 64 villes des Pays-Bas. Il raconte avoir conçu la méthode « en une vingtaine de minutes », de tête, à la terrasse d'un café d'Amsterdam où il se reposait avec sa fiancée. Il ne la publie qu'en 1959, et découvre plus tard son nom dans un manuel allemand : « Das Dijkstra'sche Verfahren ».
Idées reçues
« Dijkstra a inventé le calcul du plus court chemin. » Sa description, courte et claire, s'est imposée. Mais d'autres équipes ont décrit la même méthode ou des méthodes proches à la même époque, comme Leyzorek et ses collègues en 1957, ou Edward Moore, aux Bell Labs, pour acheminer les appels téléphoniques.
Étape 1 : Chercher malin : A*
Pour aller de D à A dans une ville en grille, où l'avenue directe est embouteillée (5 minutes par pâté de maisons au lieu de 1), l'algorithme de Dijkstra explore les rues en onde, des plus proches aux plus lointaines : il examine 167 carrefours avant de trouver le meilleur trajet, 27 minutes, qui contourne le bouchon. A* ajoute à chaque carrefour une estimation de la distance qui reste : il trouve le même trajet de 27 minutes en n’examinant que 34 carrefours. Une recherche qui fonce vers l’arrivée n’examine que 22 carrefours, mais prend l’avenue embouteillée : 81 minutes.
rue (1 min) bouchon (5 min) carrefour examiné trajet
🟢 Découverte
Dijkstra explore même les rues qui partent à l'opposé de l'arrivée. A* (« A étoile ») ajoute une estimation : la distance à vol d'oiseau qui reste. Compare le nombre de carrefours examinés. Puis essaie de foncer vers l'arrivée sans réfléchir.
🟡 Curieux
L'estimation est une heuristiqueHeuristique — Règle approximative qui guide une recherche vers les solutions prometteuses, sans tout essayer : par exemple « privilégier les rues qui rapprochent de l'arrivée ». Elle accélère, mais ne garantit pas toujours la meilleure solution. : une règle approximative qui guide la recherche. Si elle ne surestime jamais le temps restant, A* trouve toujours le meilleur trajet. Si on lui fait trop confiance, on va plus vite… mais on peut se jeter dans le bouchon.
🔴 Ingénieur
A* classe les carrefours ouverts selon f = g + h : g est le temps depuis le départ, h l'estimation du temps restant (ici la distance de Manhattan, à 1 minute par pâté de maisons). Une heuristique « admissible » (h ≤ vrai coût) garantit l'optimalité. La troisième méthode prend f = g + 5h : beaucoup moins de carrefours examinés, mais plus de garantie. Les calculateurs d'itinéraires réels prétraitent en plus le réseau routier pour répondre en quelques millisecondes.
Un peu d'histoire
A* naît au Stanford Research Institute, en Californie, pour Shakey, un robot mobile étudié de 1966 à 1972. Selon le récit de Nils Nilsson, il propose d'estimer la distance restante « à vol d'oiseau » ; Bertram Raphael, qui dirige alors les travaux sur Shakey, propose d'y ajouter la distance déjà parcourue ; Peter Hart montre que si l'estimation ne dépasse jamais la vraie distance, on trouve toujours le plus court chemin. L'article paraît en 1968. « A » pour algorithme, « * » pour sa propriété de trouver le plus court chemin. Selon l'IEEE, des dérivés guident aujourd'hui les rovers martiens.
Idées reçues
« C'est le GPS qui calcule mon itinéraire. » Les satellites GPS ne donnent qu'une position. Le trajet est calculé par un logiciel, sur une carte. Sur le réseau routier d'Europe de l'Ouest (18 millions de carrefours), un Dijkstra simple met environ 2 secondes ; avec un précalcul qui ajoute des raccourcis au réseau (« hiérarchies de contraction »), une réponse prend environ un dixième de milliseconde. La synthèse de référence sur ces méthodes est cosignée notamment par Hannah Bast, Dorothea Wagner et Peter Sanders, en Allemagne.
Étape 2 : Trop de tournées
Un livreur doit passer par 8 villes et revenir à son point de départ. Il existe 2 520 tournées différentes : un ordinateur peut toutes les essayer. Mais ce nombre explose avec le nombre de villes :
| Villes | Tournées différentes |
|---|---|
| 5 | 12 |
| 8 | 2 520 |
| 10 | 181 440 |
| 15 | 43 589 145 600 |
| 20 | ≈ 6,1 × 10^16 |
| 30 | ≈ 4,4 × 10^30 |
🟢 Découverte
Un livreur doit passer par 8 hameaux et revenir au départ, par le chemin le plus court. Trace ta tournée, puis compare avec l'ordinateur. Pour 8 hameaux, il peut tout essayer. Pour 30, plus du tout.
🟡 Curieux
C'est le problème du voyageur de commerce. Le nombre de tournées explose avec le nombre de villes : on dit que le problème est « combinatoire ». Personne ne connaît de méthode rapide qui garantisse la meilleure tournée pour un grand nombre de villes. En pratique, on se contente de très bonnes tournées, trouvées par des méthodes approchées : les heuristiques.
🔴 Ingénieur
Pour n villes, il y a (n − 1)!/2 tournées. Le problème est NP-difficile. Les méthodes exactes (séparation et évaluation, plans de coupe) savent pourtant résoudre des instances de dizaines de milliers de villes, au prix d'énormes calculs. « Au plus proche » est glouton ; 2-opt est une recherche locale : on améliore une solution par petites modifications jusqu'à ne plus pouvoir.
Un peu d'histoire
Un manuel allemand pour voyageurs de commerce de 1832 pose déjà le problème : passer par le plus de lieux possible sans repasser deux fois au même endroit. En 1930, à Vienne, le mathématicien Karl Menger l'énonce comme le « problème du messager », celui que tout facteur doit résoudre, et remarque qu'aller au point le plus proche ne donne pas en général le plus court chemin. En 1949, Julia Robinson emploie le nom de « problème du voyageur de commerce » dans le titre d'un rapport de la RAND ; on ne sait pas qui l'a inventé.
En 1954, George Dantzig, Ray Fulkerson et Selmer Johnson prouvent la meilleure tournée pour 49 villes américaines. En 1960, à la London School of Economics, Ailsa Land et Alison Doig (aujourd'hui Alison Harcourt) publient la méthode de « séparation et évaluation », faite à l'époque sur des calculatrices de bureau ; en 1980, Ailsa Land devient la première femme titulaire d'une chaire de recherche opérationnelle au Royaume-Uni. En 1963, Caroline Karel cosigne l'article sur le voyageur de commerce qui donne son nom anglais à la méthode, branch and bound.
En 1972, Richard Karp range le problème parmi les « NP-difficiles ». Pourtant, le logiciel Concorde a résolu exactement un problème de 85 900 points en 2006, et l'équipe de William Cook a trouvé en 2025 la meilleure tournée de 81 998 bars de Corée du Sud, sur les vraies routes.
Idées reçues
« NP-difficile, ça veut dire impossible à résoudre. » Cela veut dire qu'on ne connaît pas de méthode rapide pour tous les cas. En pratique, on résout exactement des problèmes de dizaines de milliers de villes, et l'on trouve de très bonnes tournées pour bien plus.
Étape 3 : S'inspirer des fourmis
Douze fourmis virtuelles parcourent 20 villes. Chacune choisit sa route au hasard, avec une préférence pour les liaisons courtes et pour celles qui portent beaucoup de phéromone. À chaque génération, la phéromone s'évapore un peu, puis chaque fourmi en dépose sur son trajet, d'autant plus que sa tournée est courte. Au bout de quelques générations, les traces se concentrent sur une très bonne tournée. Aucune fourmi ne connaît la solution : elle émerge du groupe.
🟢 Découverte
Une fourmi seule ne sait pas trouver le plus court chemin. Une colonie, si : chaque fourmi laisse une trace chimique, la phéromone, et préfère suivre les traces les plus fortes. Des fourmis virtuelles font la même chose sur 20 villes.
🟡 Curieux
Les routes courtes sont parcourues plus vite, donc renforcées plus souvent ; la phéromone des autres s'évapore. La bonne solution émerge sans chef. On parle d'intelligence collective, ou « en essaim ». D'autres méthodes imitent les vols d'oiseaux ou les bancs de poissons.
🔴 Ingénieur
Ant System : la fourmi en i choisit j avec une probabilité proportionnelle à τᵢⱼ^α · (1/dᵢⱼ)^β (ici α = 1, β = 3) ; après chaque génération, τ ← (1 − ρ)·τ (évaporation, ρ = 0,3), puis chaque fourmi dépose une quantité inversement proportionnelle à la longueur de sa tournée. C'est une méthode « métaheuristique » : elle ne garantit pas l'optimum.
Un peu d'histoire
À l'Université libre de Bruxelles, Simon Goss, Serge Aron, Jean-Louis Deneubourg et Jacques Pasteels relient un nid de fourmis d'Argentine à de la nourriture par deux ponts (1989-1990). Si un pont est plus court, la colonie finit par le choisir : la phéromone s'y accumule plus vite. Ce type de communication indirecte, par l'environnement, avait été nommé « stigmergie » par l'entomologiste français Pierre-Paul Grassé, à propos des termites.
À l'École polytechnique de Milan, Marco Dorigo s'en inspire au début des années 1990, avec Vittorio Maniezzo et Alberto Colorni : c'est l'Ant System, publié en 1996 pour le voyageur de commerce. En 1995, James Kennedy, psychologue social, et Russell Eberhart, ingénieur, proposent l'optimisation par essaim particulaire, inspirée des simulations de vols d'oiseaux, comme les « boids » de Craig Reynolds (1986), qui suivent trois règles simples : se séparer, s'aligner, rester groupés.
Étape 4 : S'inspirer de l'évolution
Il faut choisir, parmi 15 objets, ce qu'on emporte en randonnée sans dépasser 9 kg, en étant le plus utile possible. Il y a 32 768 sacs possibles. L'algorithme génétique part de 24 sacs remplis au hasard. À chaque génération, les meilleurs sacs ont plus de chances d'être « parents » ; chaque nouveau sac prend le début de la liste d'un parent et la fin de l'autre (croisement), et quelques objets sont ajoutés ou retirés au hasard (mutation). En une douzaine de générations, il trouve ici le meilleur sac possible (75 points, 9 kg), sans les avoir tous essayés.
- ⛺ tente : 2,5 kg, utilité 15
- 🛌 sac de couchage : 1,5 kg, utilité 12
- 💧 eau (2 L) : 2 kg, utilité 16
- 🔥 réchaud : 1 kg, utilité 4
- 🥫 nourriture : 1,5 kg, utilité 9
- 🧥 pull : 0,8 kg, utilité 6
- 🔦 lampe : 0,3 kg, utilité 5
- 🩹 trousse de secours : 0,4 kg, utilité 7
- 🗺️ carte : 0,1 kg, utilité 6
- 📷 appareil photo : 0,9 kg, utilité 3
- 📖 livre : 0,6 kg, utilité 2
- 🔭 jumelles : 0,7 kg, utilité 2
- 🪑 chaise pliante : 2 kg, utilité 2
- 🎸 guitare : 3 kg, utilité 3
- 🧴 crème solaire : 0,2 kg, utilité 4
Le meilleur sac de la génération 0
🟢 Découverte
Quoi emporter en randonnée, sans dépasser 9 kg ? Un algorithme génétiqueAlgorithme génétique — Méthode d'optimisation inspirée de l'évolution des espèces : une population de solutions est notée, les meilleures se « reproduisent » (croisement) avec un peu de hasard (mutation), et l'on recommence sur de nombreuses générations. fait « évoluer » une population de sacs : les meilleurs se reproduisent, se mélangent, et mutent un peu.
🟡 Curieux
Chaque sac est une suite de 0 et de 1 (un objet emporté ou non), comme un petit « génome ». La sélection favorise les sacs utiles et pas trop lourds ; le croisement mélange deux bons sacs ; la mutation apporte de la nouveauté. Sur 32 768 sacs possibles, l'algorithme n'en examine que quelques centaines.
🔴 Ingénieur
Population de 24, sélection par tournoi entre deux individus, croisement en un point, mutation de chaque gène avec une probabilité de 5 %, élitisme (les deux meilleurs sont gardés). Un sac trop lourd est pénalisé de 50 points par kilo en trop. Ici, on peut vérifier le résultat en essayant les 2¹⁵ sacs ; pour 100 objets, ce serait impossible.
Un peu d'histoire
L'idée d'imiter l'évolution sur ordinateur naît dans plusieurs pays à la fois : Nils Aall Barricelli fait évoluer des « organismes » numériques à Princeton dès 1953 ; Alex Fraser simule la génétique en Australie en 1957 ; Ingo Rechenberg et Hans-Paul Schwefel inventent les « stratégies d'évolution » à Berlin dans les années 1960 ; Lawrence Fogel travaille aux États-Unis. En 1975, John Holland, à l'université du Michigan, donne le cadre des algorithmes génétiques.
Le 22 mars 2006, la NASA lance les trois microsatellites ST5. Une de leurs antennes a été dessinée par un algorithme génétique : une forme biscornue qu'un ingénieur n'aurait sans doute pas imaginée. Selon la NASA, ce sont les premiers objets « évolués » envoyés dans l'espace.
Une autre méthode imite la métallurgie : le recuit simulé (Kirkpatrick, Gelatt et Vecchi en 1983, publié aussi par Vlado Černý à Bratislava en 1985). Elle repose sur un calcul de physique de 1953, cosigné par Arianna Rosenbluth et Augusta Teller.
Idées reçues
« John Holland a inventé les algorithmes génétiques. » Il en a donné le cadre en 1975, mais le calcul évolutionnaire est né de plusieurs équipes indépendantes, aux États-Unis, en Allemagne et en Australie.
« Les IA qui imitent la nature sont plus intelligentes. » Fourmis et évolution sont des images utiles, pas des garanties. Sur beaucoup de problèmes, une méthode mathématique classique fait mieux. Elles servent surtout quand le problème est trop irrégulier pour les méthodes exactes.
Qui choisit ce qu'on optimise ?
Un algorithme d'optimisation trouve « le meilleur »… selon un critère choisi par des humains. Changer de critère, c'est changer de résultat.
| Problème | On peut optimiser… | … ou plutôt |
|---|---|---|
| Itinéraire | le temps de trajet | la distance, la consommation, la tranquillité des quartiers traversés |
| Tournée de livraison | les kilomètres | les horaires et les pauses des livreur·ses |
| Emploi du temps | le nombre de salles utilisées | les trous dans la journée des élèves |
| Planning d'hôpital | le coût | la fatigue des équipes, la continuité des soins |
Ces calculs sont partout. Selon UPS, son système ORION calcule chaque jour la tournée de ses 55 000 chauffeurs américains et économise des dizaines de millions de litres de carburant par an (chiffres de l'entreprise). En France, Parcoursup répartit les places dans l'enseignement supérieur avec une adaptation de l'algorithme de Gale et Shapley (1962), selon Claire Mathieu, qui a travaillé sur sa conception : ce n'est plus un chemin qu'on cherche, mais un appariement entre candidat·es et formations. La théorie de ces appariements a valu en 2012 le prix d'économie en mémoire d'Alfred Nobel à Lloyd Shapley et Alvin Roth.