Les métaheuristiques


pour traiter les problèmes NP-difficiles

Thibaut Lust

Problèmes NP-difficiles, explosion combinatoire, modélisation comprenant des millions de variables et un nombre d’inéquations exponentiel… Que faire quand aucune méthode d’optimisation ne fonctionne ? Quelle méthode utiliser lorsque l’on souhaite obtenir une solution rapidement à un problème ?

Sous l’hypothèse que P ≠ NP (voir article P est-il égal à NP ?), pour certains problèmes d’optimisation, il n’existe malheureusement pas d’algorithmes efficaces de résolution. Pourtant, comme souvent en mathématiques, leur formulation est parfois si simple que l’on n’imagine pas leur difficulté sous-jacente. Prenons par exemple le célèbre problème du voyageur de commerce : étant donné un ensemble de villes, quel trajet de distance minimale permet de visiter toutes les villes et de revenir au point de départ ? Malgré sa simplicité, il n’existe pourtant aucun algorithme permettant de résoudre efficacement ce problème : même le meilleur d’entre eux mettra un temps qui augmente exponentiellement avec le nombre de villes. Que faire lorsque l’on veut résoudre un problème « de grande taille » (de type de ceux rencontrés en pratique) en un temps « acceptable » (de l’ordre de quelques minutes) ?

 

 

85 900 villes : le record actuel !

 

La plus grande instance du problème du voyageur de commerce jamais résolue fait intervenir pas moins de quatre-vingt-cinq mille neuf cents villes. L’image ci-dessous représente un problème de voyageur de commerce comprenant ce nombre record (N = 85 900) de villes, provenant d’une situation rencontrée lors de la conception d’un circuit intégré. C’est le record à ce jour. Il a été résolu en ... Lire la suite


références

 Worst-case analysis of a new heuristic for the travelling salesman problem. Nicos Christofides, Technical Report 388, 1976.
 Optimization by simulated annealing. Scott Kirkpatrick, Daniel Gelatt et Mario Vecchi, Science 220, 1983
 Future paths for integer programming and links to artificial intelligence. Fred Glover, Computers and Operations Research 13, 1986.
 Adaptation in natural and artificial systems. John Holland, The University of Michigan Press, 1975.