Les métaheuristiques

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) ?