# Les métaheuristiques pour traiter les problèmes NP-difficiles

Thibaut Lust

<figure><img src="image_1.png" /></figure>

## To cite this version:

Thibaut Lust. Les métaheuristiques pour traiter les problèmes NP-difficiles. Bibliothèque Tangente, 2020, Hors Série (75), pp.20-22. hal-03967898

HAL Id: hal-03967898

https://hal.science/hal-03967898

Submitted on 16 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# Les métaheuristiques : un outil puissant pour traiter les problèmes NP-difficiles

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 marche ? Quelle méthode utiliser lorsque l'on souhaite obtenir une solution rapidement à un problème ?

Sous l'hypothèse que P ≠ NP, pour certains problèmes d'optimisation, il n'existe malheureusement pas d'algorithmes efficaces de résolution (voir article « Escoffier P=NP ? »).

Pourtant, comment souvent en mathématiques, certains de ces problèmes ont des formulations si simples qu'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 tour de distance minimale permet de visiter toutes les villes et de revenir au point de départ ? De formulation simple, il n'existe pourtant aucun algorithme permettant de résoudre efficacement ce problème : même le meilleur algorithme connu pour résoudre ce problème mettra un temps qui augmente exponentiellement avec le nombre de villes.

## 85 900 villes : la plus grande instance du problème du voyageur de commerce jamais résolue

<figure><img src="image_3.png" /></figure>

Cette image représente un problème de voyageur de commerce comprenant 85 900 villes, provenant d'un problème rencontré lors de la conception d'un circuit intégré. C'est le problème comportant le plus grand nombre de villes qui a pu être résolu à ce jour. Il a été résolu en 2006 à l'aide du logiciel Concorde par une équipe de chercheurs américains [1]. Il a fallu l'équivalent de 136 années CPU pour résoudre ce problème, réduit à environ 1 année de calculs grâce à une grappe de processeurs permettant le calcul parallèle.

Que faire lorsque l'on veut résoudre un problème de grande taille en un temps acceptable (de l'ordre de quelques minutes) ?

## Heuristiques

La première solution est l'utilisation d'heuristiques (du grec « heuriskein » qui signifie trouver). Le but de l'heuristique est de trouver une solution respectant les contraintes du problème, et de bonne qualité selon le critère d'optimisation considéré. La solution ne sera pas forcément optimale, mais une heuristique efficace tente de trouver une solution de bonne qualité suivant le temps de résolution imparti.

Par exemple, pour le problème du voyageur de commerce, l'heuristique du plus prochain voisin est simple : on sélectionne la prochaine ville à visiter telle que la distance entre la ville courante et la prochaine ville soit minimale, et ce, jusqu'à avoir visité toutes les villes. On revient ensuite à la première ville visitée pour obtenir un tour. Cette heuristique est rapide, mais donne en pratique d'assez mauvais résultats : rien ne garantit en effet que la dernière ville visitée sera proche de la première ville, ce qui peut donner un trajet final long et pénalisant. Une heuristique bien plus efficace est l'heuristique de Christofides [2]. Cette heuristique est basée sur deux problèmes simples que l'on peut résoudre avec un
algorithme de complexité polynomiale : le problème de l'arbre couvrant de coût minimal (c'est-à-dire un arbre qui connecte toutes les villes) et le problème de couplage de coût minimal (association deux à deux des villes). Par conséquent, l'algorithme de Christofides est lui-même de complexité polynomiale - de complexité cubique plus exactement.

L'heuristique de Christofides est bien plus efficace que l'heuristique du plus proche voisin. Elle possède même une propriété intéressante dans le cas métrique¹ : on peut garantir que le tour retourné par cette heuristique ne sera pas plus long de 50% du tour optimal. Malgré de nombreuses recherches (l'heuristique de Christofides date de 1976), aucun heuristique présentant de meilleur rapport de performance n'a été trouvée jusqu'à ce jour.

Même si ce résultat est encourageant pour le problème du voyageur de commerce, les heuristiques sont cependant spécifiques à chaque problème et rendent leur utilisation délicate. Pour chaque nouveau problème rencontré, il est nécessaire d'en définir une nouvelle.

## Métaheuristiques

Face à ce manque d'adaptabilité, les métaheuristiques ont été développées dans les années 60 (méta provenant du grec « meta », suffixe signifiant « au-delà, dans un niveau supérieur »). Les métaheuristiques sont un ensemble de concepts permettant de définir des heuristiques et qui peuvent être appliquées à de nombreux problèmes. Elles peuvent être vues comme une structure générale algorithmique, demandant relativement peu de modifications pour être adaptée à un problème spécifique. Les métaheuristiques peuvent être inspirées de systèmes physiques (recuit simulé) ou naturels (algorithmes génétiques, colonies de fourmis ou encore optimisation par essais particulaires).

On distingue deux grandes familles de métaheuristiques :

- les métaheuristiques dites à solution unique : une seule solution va subir des pertites modifications et évoluer dans l'espace de recherche.

- les métaheuristiques dites à population (parfois appelées méthodes évolutives) : une population de solutions évolue dans l'espace de recherche, en alternant des périodes d'adaptation individuelle et de coopération.

## Métaheuristiques à solution unique

Un autre nom donné aux métaheuristiques à solution unique est la recherche locale : une solution de départ est définie, ainsi qu'une fonction de voisinage permettant de générer plusieurs solutions proches (les solutions voisines) d'une solution (appelée la solution courante). Dans le cas de la méthode de descente, on va sélectionner parmi les solutions voisines la solution de coût minimal : si cette solution est meilleure que la solution courante, on relance la fonction de voisinage à partir de cette solution voisine, jusqu'à ce que plus aucune amélioration ne soit possible, c'est-à-dire jusqu'à ce que la meilleure solution voisine soit de moins bonne qualité que la solution courante. La solution finale obtenue par cette méthode de descente est ce qu'on appelle un « minimum local »: il n'est pas possible d'améliorer cette solution en considérant la fonction de voisinage considérée. Cependant, rien n'indique que cette solution est la solution optimale. Pour un problème d'optimisation, il peut exister plusieurs minimas locaux. La méthode de descente permet d'obtenir un de ces minimas locaux, qui n'est pas forcément le minimum global du problème. Cette métaheuristique, très simple, est facile à adapter pour n'importe quel problème d'optimisation. Uniquement deux éléments doivent être définis : une solution initiale et une fonction de voisinage. Si on revient au problème du voyageur de commerce, une solution initiale pourrait être un tour généré aléatoirement, et la fonction de voisinage, la fonction qui renvoie l'ensemble des tours obtenus en échangeant une paire de villes dans le tour.

1. Un problème du voyageur de commerce est dit métrique si l'inégalité triangulaire est respectée, c'est-à-dire pour tout triplet de villes (i,j,k) : $distance(i,k) <= distance(i,j) + distance(j,k)$.
Face au problème de minimum local de cette méthode, différentes techniques ont été développées pour s'en « échapper ». Nous allons en parcourir deux : le recuit simulé et la recherche tabou.

La méthode de recuit simulé s'inspire du processus physique de maintien en température et de refroidissement d'un métal afin de l'amener vers un état d'énergie minimale, dans le but de modifier ses caractéristiques [3]. La méthode de recuit simulé fonctionne analogiquement de la façon suivante : partant d'une solution initiale, on va générer une solution voisine : si cette solution améliore la solution courante, on accepte la solution voisine et on réitère le processus. En revanche, contrairement à la méthode de descente vue préalablement, si la solution voisine n'améliore pas la solution courante, elle sera tout de même sélectionnée avec une certaine probabilité. La probabilité dépend de deux facteurs : l'écart de valeur par rapport à la solution courante et un paramètre de contrôle, la température. Cette température permet de contrôler le processus de recherche du recuit simulé : en général, en début de méthode, une température élevée est considérée, ce qui permet d'accepter avec une grande probabilité des solutions dégradantes. La méthode ressemble donc à une recherche aléatoire : on explore l'espace de recherche afin de trouver une bonne solution de départ. Au fur et à mesure de l'état d'avancement de la méthode, on baisse la température, ce qui réduit l'exploration : on intensifie la recherche et les solutions dégradantes sont de moins en moins acceptées. Ce compromis exploration vs. intensification est un facteur clef des métaheuristiques. L'exploration permet de trouver une zone de l'espace de recherche prometteuse, tandis que l'intensification permet de trouver la meilleure solution dans cette zone de recherche de taille réduite.

Une autre métaheuristique à solution unique très populaire est la recherche tabou [4] : basée également sur la notion de voisinage, la meilleure solution voisine qui n'a pas encore été rencontrée auparavant est sélectionnée. Ici, une notion de mémoire est utilisée (plus précisément appelée la liste tabou) afin de sauvegarder les mouvements précédents. Cette technique permet de sortir des optima locaux, en évitant d'y retourner grâce à la liste tabou mémorisant les mouvements préalablement réalisés.

## Métaheuristiques à base de population

Parmi les métaheuristiques à base de population, les algorithmes génétiques sont ceux qui ont connu le plus de succès. Inventées en 1975, ces méthodes suivent le processus d'évolution darwinien : une population composée de différents individus évolue grâce à des opérateurs de croisement, de mutation, et de sélection [5]. L'opérateur de croisement permet de combiner plusieurs individus prometteurs afin d'en créer de nouveaux. L'opérateur de mutation fonctionne comme en génétique : une petite partie d'un individu est modifiée aléatoirement afin d'apporter de la diversité. Enfin le processus de sélection permet de sélectionner les meilleurs individus de la population, à travers une fonction d'adaptation, measuring la qualité des individus pour le problème que l'on cherche à résoudre.

## Une Mona Lisa dessinée en un seul trait !

<figure><img src="image_4.png" /></figure>

Cette image représente la Mona Lisa de Léonard de Vinci, dessinée à l'aide d'un seul coup de crayon ! Elle a été obtenue à l'aide de la disposition astucieuse de 100 000 points, et un tour passant par ses différents points. Cependant la solution optimale de ce problème n'est pas encore connue. La meilleure solution obtenue jusqu'à présent est de longueur égale à 5 757 191 et a été obtenue par un algorithme génétique. Un prix de 1000 $ est attribué à toute personne trouvant un tour de longueur inférieure [6].
## Conclusion

Les métaheuristiques sont des outils très puissants, permettant de fournir des solutions de bonne qualité pour des problèmes NP-difficiles de grande taille, en un temps réduit. Elles sont très utilisées en pratique, de par leur facilité d'utilisation et leur grande adaptabilité. Choisir une métaheuristique pour un problème donné n'est pas évident, chaque métaheuristique présente des avantages et inconvénients. L'hybridation est par conséquent couplement utilisée : les composants de plusieurs métaheuristiques sont combinés afin de tirer parti des avantages de chaque métaheuristique, ce qui conduit à encore plus de performances.

## Références

[1] http://www.math.uwaterloo.ca/tsp/pla85900/

[2] Christofides, N., Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976.

[3] Kirkpatrick, Scott & Gelatt, C. & Vecchi, M. (1983). Optimization by Simulated Annealing. Science (New York, N.Y.). 220 (4598) : 671-680.

[4] Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. 13 (5): 533-549.

[5] Holland, J.H. Adaptation in Natural and Artificial Systems. Ann Arbor, MI : University of Michigan Press, 1975.

[6] http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html