La problème de Voyageurs de Commerce Bi-Objectifs et la Métaheuristique

By 26 February 2014

“… problème du voyageur de commerce, l’une des méthodes exactes les plus classiques et les plus performantes reste la Procédure par Séparation et Evaluation (PSE). Cette méthode repose sur le parcours d’un arbre de recherche. Dans un chemin de cet arbre, le premier nœud représente la ville de départ, son successeur la deuxième ville visitée, puis la troisième ville visitée, etc. À chaque étape de l’algorithme, on crée autant de nœuds qu’il reste de villes…”

République Algérienne Démocratique et Populaire
Ministere de l’Enseignement Supérieur et de la Recherche Scientifique

Département de Mathématique et d’Informatique

Soutenance

Présenté pour l’obtention du diplôme de MASTER Option Réseaux et Multimédia

La Résolution du Problème de Voyageurs de Commerce Bi-Objectifs par La Métaheuristique d’Optimisation par Colonie de Fourmis Artificielles

Par

KOUCHI Mohamed & Mili Kamel

Promotion 2012 – 2013

Introduction générale

Les problèmes d’optimisation occupent actuellement une place importante dans la communauté scientifique, on peut voir de façon intuitive, un problème d’optimisation comme un problème de recherche qui consiste à explorer un espace contenant l’ensemble de toutes les solutions potentielles réalisables, dans le but de trouver la solution optimale, sinon la plus proche possible de l’optimum, permettant de minimiser ou maximiser une fonction dite objectif.

Il existe deux grandes catégories de méthodes de résolution des problèmes d’optimisation combinatoire, les méthodes exactes permettent d’obtenir une solution optimale exacte à chaque fois, mais le temps de calcul peut être long et les méthodes rapprochées appelées heuristiques (méta-heuristiques) permettent quant à elles d’obtenir rapidement une solution approchée, mais qui n’est donc pas toujours optimale.

Ces dernières années, la plupart des méta-heuristiques présentées pour résoudre des problèmes combinatoires sont d’inspiration biologique, Parmi ces métaheuristiques, nous pouvons citer les algorithmes génétiques, le recuit simulé, les réseaux de neurones, les algorithmes à estimation de distribution, et l’optimisation par colonie de fourmis qui représente le cœur de notre travail.

Le problème du voyageur de commerce (traveling salesman problem) se prête très bien à l’utilisation de méta-heuristiques comme les algorithmes génétiques ou les colonies de fourmis, ce dernier est problème classique d’optimisation combinatoire NP-complet connu pour sa grande difficulté il est l’un des problèmes NP-difficiles les plus étudiés, le TSP consiste à trouver un parcours de longueur minimum que doit emprunter un voyageur pour visiter une et une seule fois chaque ville s’il démarre de la ville de son domicile et y revient en fin de parcours. Ce problème est équivalent à la recherche d’un cycle hamiltonien minimal dans un graphe complet pondéré.

Parmi les algorithmes de résolution du TSP qui peuvent être répartis en deux classes (exactes et approchées) l’optimisation par colonies de fourmis qui consistent a une recherchent en parallèle d’une meilleure solution au TSP en coopérant indirectement à travers les phéromones qu’ils déposent sur le graphe.

Les algorithmes de colonies de fourmis sont nés à la suite d’une constatation fourmis en particulier, résolvent naturellement des problèmes relativement complexes. Les biologistes ont étudié comment les fourmis arrivent à résoudre collectivement des problèmes trop complexes pour un seul individu, notamment les problèmes de choix lors de l’exploitation de sources de nourriture.

Ce mémoire est organisé de la façon suivante.

La première partie est consacrée à la présentation des problèmes d’optimisation combinatoire et l’étude des méthodes de résolution existantes, nous introduisons dans le premier chapitre les problèmes d’optimisation combinatoire et les approches de résolution complètes, dans le second chapitre nous nous intéressons aux problématiques liées à la résolution de problèmes d’optimisation multiobjectif à l’aide de méta-heuristiques les plus connus dans le domaine de l’industrie, ainsi les principales approches non Pareto de résolution pour ces problèmes et quelques approches Pareto, dans la deuxième partie ou nous introduisons dans le troisième chapitre la présentation de problème de voyageurs de commerce ainsi les déférents algorithmes de résolution notamment colonie de fourmis puis dans Le quatrième chapitre qui introduit a la méta-heuristiques d’optimisation par colonies de fourmis pour la résolution de problème de voyageurs de commerce ou on parle sur le comportement des fourmis ainsi la similarité entre les fourmis réelles et artificielles et sa relation avec l’informatiques puis on parle sur quelque algorithmes bases sur la méta- heuristiques d’optimisation par colonies de fourmis.

Sommaire :

INTRODUCTION GENERALE
I. INTRODUCTION :
II. UN PROBLEME
III. PROBLEME D’OPTIMISATION COMBINATOIRE :
III.1. LE PROBLEME DU SAC A DOS (KNAPSACKPROBLEM) :
III.1.1. DESCRIPTION :
III.1.2. FORMULATION :
III.1.3. APPLICATIONS :
III.1.4. VARIANTES :
III.2. LE PROBLEME DU VOYAGEUR DE COMMERCE:
III.2.1. DESCRIPTION :
III.2.2. FORMULATION :
III.2.3. APPLICATIONS :
III.3. LE PROBLEME D’IMPLANTATION DE DEPOTS :
III.3.1. DESCRIPTION :
III.3.2. FORMULATION :
III.3.3. APPLICATIONS :
III.4. PROBLEMES DE COUVERTURE, DE PARTITION ET D’EMBALLAGE :
IV. LES METHODES DE RESOLUTION :
IV.1. LES METHODES EXACTES :
IV.2. METHODES APPROCHEES : [7]
V. CONCLUSION

I. Introduction :

La recherche opérationnelle est une discipline scientifique située au carrefour de l’informatique, des mathématiques appliquées et de l’économie. Elle s’adresse entre autres à la résolution de problèmes d’optimisation combinatoire et fait largement usage d’outils informatiques.

Si certains problèmes peuvent s’exprimer facilement à l’aide d’un formalisme issu de la programmation mathématique, par exemple, ils peuvent se révéler difficiles à résoudre en pratique. Cette difficulté apparait encore plus grande lorsque le problème véhicule plusieurs critères ou objectifs (problème d’optimisation multiobjectifs).

Il n’existe pas aujourd’hui de méthode générale efficace pour résoudre ces problèmes. Néanmoins, pour de nombreuses classes de problèmes, il existe des algorithmes spécifiques donnant de bons résultats. [1]

II. Un problème :

Un problème dans le point de vue informatique (Computational Problem) veut dire comment faire relier un ensemble de données par un ensemble de résultats, où les données ont subir un ensemble d’opérations dont on les appelle le traitement. Donc il est conçu comme une relation Π ⊆ l x S entre les entrées ou instances, et les sorties ou solutions.

Pour qu’une instance d’un problème soit compréhensible par un ordinateur numérique, elle doit être décrite comme une séquence finie de symboles d’un ensemble fini arbitraire appelé alphabet. De même, la solution d’une instance d’un tel problème est émise dans ce format. Généralement, l est infini alors que S peut être fini. [2]

III. Problème d’optimisation combinatoire :

On peut trouver de nombreuses définition de problème d’optimisation combinatoire, nous avons retenu de celle de collette et Siarry [3] qui propose la définition suivante : Définition 1.problème d’optimisation

Un problème d’optimisation se définit comme la recherche du minimum ou de maximum d’une fonction donnée, mathématiquement, dans le cas d’une minimisation, un problème d’optimisation se présentera sous la forme suivante :

Minimiser Problème d’optimisation combinatoire

Avec g(s)<=0 (m contraintes d’inégalités) Et h(s) = 0 (p contraintes d’égalités) [4]

En d’autre termes, résoudre un problème d’optimisation P(S, f) revient à déterminer une solution s*ϵS minimisant ou maximisant la fonction f avec S l’ensemble des solutions ou l’espace de recherche et f : S →Y une application ou une fonction d’évaluation qui à chaque configuration s’associer une valeur f (S) ϵ Y

Il est possible de passer d’un problème de maximisation à un problème de minimisation grâce a la propriété suivante :

propriété [4]

Généralement, une solution s ϵ S est un vecteur d’un espace à N dimentions.

Définition 2.problème d’optimisation continue

Dans le cas de variables réelles, on a : problème d’optimisation continue

On parle alors de problème d’optimisation en variables continues.

Un problème d’optimisation continue (PO) peut être formulé de la façon suivante :

problème d’optimisation continue [4]

Définition 3.problème d’optimisation combinatoire Un problème d’optimisation combinatoire est un problème d’optimisation dans le quel le quel l’espace de recherche S est dénombrable.

Un problème d’optimisation combinatoire (POC) peut etre formulé ainsi :

problème d’optimisation combinatoire (POC)[4]

Ou une solution S est un vecteur composé de N valeurs entières, soit solution S est un vecteur composé de N valeurs

La principale différence entre problème d’optimisation continue et le problème d’optimisation combinatoire repose sur l’utilisation des variables discrètes, dans les deux catégories de problèmes, une solution s ϵ S est une instanciation des variables xi ϵ X, ou i est l’indice da la variable dans [1 ; N], et X est le vecteur de démentions N correspondant à la solution, et f(s) est son évaluation, résoudre ces problèmes revient à trouver une solution optimale appelées aussi optimum global.

Quelques exemples de problèmes d’optimisation combinatoire :

III.1. Le problème du sac à dos (Knapsackproblem) :

III.1.1. Description :

Le problème du sac à dos multidimensionnel (MKP) est un problème d’optimisation combinatoire sous contraintes NP-difficile [5]. Il modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

Pour justifier son nom, le problème se pose lorsqu’un randonneur au moment de préparer son périple est confronté au problème de la capacité limitée de son sac à dos. Il lui faut donc trancher pour prendre les choses dont il a le plus besoin (maximiser le coût) sans dépasser la capacité du sac à dos (15 kg).

problème du sac à dos Knapsackproblem

III.1.2. Formulation :

Etant donné un ensemble de n objets chacun ayant un certain poids aj et une certaine valeur (coût) cj, et soit b un réel qui représente la charge (poids, volume, capacité) maximale que l’on peut emporter dans un sac à dos. La formulation du problème conduit à un PLNE0-1 à une seule contrainte :

Formulation

xj = 1 signifiant que l’objet j est choisi.

III.1.3. Applications :

Ce problème est utilisé pour modéliser diverses situations, quelquefois en tant que sous problème :

* La sélection d’investissement « Capital BudgetingProblem » de manière à maximiser le rendement, sans bien sûr, dépasser la somme disponible.

* Dans le chargement de bateau ou d’avion « Cargo LoadingProblem » : tous les bagages à destination doivent être amenés, sans être en surcharge ;

* Dans la découpe de matériaux « Cutting Stock Problem » : pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer.

III.1.4. Variantes :

Le problème du sac à dos possède une multitude de variantes dont voici quelques unes :

** Knapsack entier

S’il existe plusieurs objets de chaque type ; soit Nj le nombre d’objets de type j, on obtient un PLNE avec xj {0, 1, …, Nj} (ou xj entier si Nj= ). Le problème ainsi obtenu est appelé Knapsack entier.

** Knapsackmulti-dimensionnel

On considère ici que le sac à dos a d dimensions, avec d > 0 (d-KP). Par exemple, on peut imaginer une boîte. Chaque objet a trois dimensions, et il ne faut pas déborder sur aucune des dimensions.

La contrainte est alors remplacée par d contraintes :

Knapsackmulti-dimensionnel

III.2. Le problème du Voyageur de Commerce:

III.2.1. Description :

Etant donné n points (des villes) et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ. Voici un exemple simple :

problème du Voyageur de Commerce

Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ?

Ce problème est plus compliqué qu’il n’y paraît ; on ne connaît pas de méthode de résolution permettant d’obtenir des solutions exactes en un temps raisonnable (polynomiale) pour de grandes instances (grand nombre de villes) du problème. Pour ces grandes instances, on devra donc souvent se contenter de solutions approchées, car on se retrouve face à une exploration combinatoire. Le nombre de chemins hamiltoniens étant égal1 à (n–1)!/2.

III.2.2. Formulation :

Soit n villes et cij le coût (ou la distance) correspondant au trajet i – j. Le problème consiste à déterminer un tour ou circuit hamiltonien, c’est-à-dire ne passant qu’une et une seule fois par les n villes, et qui soit de coût minimum. Soit la variable xij qui vaut 1 si le tour contient le trajet i – j, et 0 autrement. Le problème s’écrit :

Formulation (PVC/TSP)

Où Q représente un sous-ensemble de {1,…,n} et Q son complémentaire. Les contraintes (3) expriment que la permutation des n villes doit être un tour, c’est-à-dire qu’il ne peut pas exister de sous tour.

III.2.3. Applications :

Le PVC fournit un exemple d’étude d’un problème NP-complet dont les méthodes de résolution peuvent s’appliquer à d’autres problèmes de mathématiques discrète. Néanmoins, il a aussi des applications directes, notamment dans les transports, les réseaux et la logistique. Par exemple, trouver le chemin le plus court pour les bus de ramassage scolaire ou, dans l’industrie, pour trouver la plus courte distance que devra parcourir le bras mécanique d’une machine pour percer les trous d’un circuit imprimé.

III.3. Le problème d’implantation de dépôts :

III.3.1. Description :

Le problème d’implantation de dépôts (ou équipement) se pose comme suit :

Etant donné un ensemble de sites potentiels pour l’implantation de dépôts, et un ensemble de clients devant être servis par les dépôts installés, le problème consiste à déterminer :

** Quels sites potentiels seront utilisés pour l’installation des dépôts (équipement) ?

** Comment affecter les clients aux dépôts installés ?

Le schéma suivant montre le problème posé (Facilities = Sites potentiels et Customers = Clients), ainsi qu’une solution possible au problème.

problème d’implantation de dépôts

III.3.2. Formulation :

Le problème d’implantation de dépôts existe en deux variantes suivant que les dépôts ont des capacités limitées ou non. Dans le premier cas, le dépôt ne peut satisfaire qu’un nombre limité de clients.

– Sans contraintes de capacité (Uncapacited FLP) Soit :

J un ensemble de sites potentiels ; fj, j J, représente le coût fixe d’ouverture d’un dépôt.

I un ensemble de clients ; cij, i I, j J, représente le coût de service du client i par le dépôt ouvert en j.

Le modèle correspondant utilise deux types de variables de décision :

xj = 1 ou 0 selon qu’un dépôt est installé en j ou non.

yij = 1 ou 0 selon que le client i est approvisionné (servi) par le dépôt installé en j ou non.

Le problème se formule comme suit :

problème se formule (UFLP)

Les contraintes (1) et (2) indiquent respectivement que tout client i doit être rattaché à un et un seul dépôt, et que tout approvisionnement d’un client i par le dépôt j ne peut se faire que si le dépôt est installé en j. (xj=1 yij =0 ou 1 i ; xj=0 yij=0 i)

– Avec contraintes de capacité (Capacited FLP)

Dans ce cas, chaque client i possède une certaine demande di à satisfaire, et chaque dépôt (éventuel) j possède une capacité maximale qj. La formulation se fait avec les mêmes variables xj que précédemment mais avec des variables yij 0 (réelles) représentant la quantité fournie au client i à partir du dépôt j (cij est alors un coût unitaire) :

contraintes de capacité (Capacited FLP(CFLP)

III.3.3. Applications :

Ce problème possède une multitude d’applications dans divers domaines tels que :

– Les Réseaux : Implantation de concentrateurs (Relais),…

Logistique : Gestion des aéroports (bagages par exemple), Installations de points de vente,…

Urbanisme : Choix des emplacements d’écoles, de mosquées…

III.4. Problèmes de Couverture, de Partition et d’emballage :

(SET COVERING PROBLEM / SET PARTITIONING PROBLEM / SET PACKING PROBLEM)

– Problème de couverture

Soit m objets, i I, n sous-ensembles Pj de I. Une couverture de I est une collection de Pj vérifiant la condition :

U Pj I

Soit cj le coût associé à Pj. Le problème de la recherche d’une couverture de coût minimal consiste à sélectionner des sous-ensemblesPj de façon à ce que chaque objet apparaisse au moins une fois, et cela avec le coût global le plus petit. Si on pose xj = 1 si Pj appartient à la couverture, 0 sinon, On obtient le modèle suivant :

Problème de couverture (Set Covering Problem)

Où aij = 1 sii Pj, 0 sinon.

– L’exemple d’application classique du problème de couverture est celui de l’ouverture d’un nombre minimum de magasins dans une région pour couvrir l’ensemble de la zone. Par ailleurs, des problèmes de routages, de livraisons, d’ordonnancements et d’implantation d’équipements ou d’infrastructures sont aussi des problèmes qui peuvent se modéliser en problème de couverture.

– Problème de partition

Une partition est une couverture qui vérifie les conditions supplémentaires
Une partition est une couverture qui vérifie les conditions supplémentaires

Le problème de la recherche d’une partition de coût minimal se formule comme suit :

Set PartitioningProblem(Set PartitioningProblem)

– Le problème de partition se pose lorsque chaque client doit être servi par exactement un serveur, chaque citoyen doit être assigné à un seul district (organisation des votes par exemple).

– Problème d’emballage

Dans ce problème, les partitions Pj ont une valeur (ou bénéfice) plutôt qu’un coût ; il consiste à sélectionner des sous-ensembles disjoints de façon à maximiser la valeur totale :

Set PackingProblem(Set PackingProblem)

– Le problème d’emballage se pose généralement lorsqu’on veut mettre en œuvre une production de valeur maximale dans un contexte de ressources limitées. D’autres applications incluant des problèmes d’ordonnancements où on cherche à satisfaire le plus de demandes possibles sans créer de conflits, correspondent aussi au modèle du problème d’emballage.

IV. Les méthodes de résolution :

Il existe deux grandes catégories de méthodes de résolution : les méthodes exactes et les méthodes approchées. Les méthodes exactes permettent d’obtenir une solution optimale à chaque fois, mais le temps de calcul peut être long si le problème est compliqué à résoudre. Les méthodes approchées, encore appelées heuristiques, permettent quant à elles d’obtenir rapidement une solution approchée, mais qui n’est donc pas toujours optimale.[6]

IV.1. Les méthodes exactes :

Pour le problème du voyageur de commerce, l’une des méthodes exactes les plus classiques et les plus performantes reste la Procédure par Séparation et Evaluation (PSE). Cette méthode repose sur le parcours d’un arbre de recherche. Dans un chemin de cet arbre, le premier nœud représente la ville de départ, son successeur la deuxième ville visitée, puis la troisième ville visitée, etc. À chaque étape de l’algorithme, on crée autant de nœuds qu’il reste de villes à visiter. À chaque nœud, le choix consiste à sélectionner la prochaine ville à visiter parmi les villes restantes. Ainsi, voici l’arbre de recherche pour l’exemple présenté ci-dessus :

méthodes exactes

Dans le cas du problème du voyageur de commerce, la fonction objectif à minimiser est la longueur du cycle. La réduction de l’espace de recherche repose sur l’utilisation de bornes inférieures et supérieures. Rappelons que :

Une borne inférieure est une estimation par défaut de la fonction objectif. Autrement dit, c’est une valeur qui est nécessairement inférieure à la valeur de la meilleure solution possible. Dans notre cas, s’il y a un graphe avec N sommets à traverser, le cycle hamiltonien passera obligatoirement par N arêtes. Ainsi, pour avoir une borne inférieure assez intuitive, il suffit d’additionner le poids des N arêtes possédant les plus petits poids. Même si cette solution a de forts risques de ne pas être réalisable, la valeur de la fonction objective ne pourra pas être plus petite.

Une borne supérieure est une estimation par excès de la fonction objectif. Autrement dit, la meilleure solution a nécessairement une valeur plus petite. Dans notre cas, un cycle hamiltonien quelconque dans le graphe fournit une borne supérieure.

Le principe de réduction de l’arbre de recherche consiste à couper l’exploration de l’arbre à la hauteur de certains nœuds. Où faut-il couper l’arbre de recherche ? Supposons que la borne supérieure soit fournie par un algorithme approché – que nous détaillerons plus loin. On examine les nœuds sur les différentes branches, en partant du sommet, pour déterminer une borne inférieure correspondant à chacun des nœuds visités. Pour un nœud donné, on calcule cette borne inférieure en additionnant la somme des poids des arêtes déjà sélectionnées dans le cycle avec la somme des x plus petits poids parmi les arêtes restantes, x étant le nombre d’arêtes manquantes dans le cycle en cours de construction. À partir d’un nœud et de sa borne inférieure, les solutions descendantes de ce nœud ne pourront pas avoir une valeur plus petite que cette borne inférieure. Si jamais, à un nœud donné, la valeur de la borne inférieure excède la valeur de la borne supérieure, alors il est inutile d’explorer les nœuds en dessous de celui-ci. Enfin, la valeur de la borne supérieure peut être actualisée lorsqu’est trouvée une solution réalisable qui possède une valeur plus petite. Ce système de calcul de bornes demande un faible coût en temps de calcul et permet d’augmenter la rapidité de la PSE, puisqu’elle coupe les branches inutiles à explorer.

Les chercheurs ont mis au point différentes techniques pour diminuer la taille de l’arbre et augmenter la rapidité de la PSE. Certaines sont basées sur le choix de l’ordre de visite des villes. Ainsi, une stratégie de recherche qui fonctionne bien pour fixer l’ordre de visite des villes est la règle du plus proche voisin : au nœud correspondant à une ville donnée, la recherche du prochain nœud, c’est-à-dire de la prochaine ville à visiter, commencera par le nœud le plus proche de celui considéré. Elles peuvent aussi reposer sur une évaluation à chaque nœud, ou encore sur des propriétés du problème qui permettent de tirer des conclusions au sujet de certaines villes ou sur des sous-ensembles de villes. C’est une telle démarche qui a été utilisée pour le niveau expert de l’applet.

IV.2. Méthodes approchées : [7]

Dans le cas d’un nombre de villes si grand que même les meilleures méthodes exactes nécessitent un temps beaucoup trop long de résolution, des méthodes approchées, ou algorithmes d’approximation, sont utilisées. Elles permettent d’obtenir en un temps très rapide de bonnes solutions, pas nécessairement optimales, mais d’une qualité suffisante.

Étant donné que le problème du voyageur de commerce a été, et continue à être largement étudié du fait de sa complexité et du nombre important de problèmes dérivés, il existe de nombreux algorithmes d’approximation. Chacun a ses avantages et ses inconvénients. La méthode retenue ne sera pas le même selon que l’on privilégie le temps de calcul, la qualité de la solution, ou encore le choix entre plusieurs solutions.

Une famille de méthodes est celle des algorithmes gloutons, dont l’un des plus connus est la méthode par insertion. L’idée est la suivante : le parcours du voyageur de commerce est construit pas à pas en y insérant de nouvelles villes. À un instant donné de l’algorithme, un certain cycle de villes a été construit. L’étape suivante consiste à insérer une ville supplémentaire dans le cycle de manière optimale, c’est-à-dire qu’elle augmente au minimum la longueur totale du cycle. À l’étape initiale de l’algorithme, le parcours de voyageur est composé de deux villes, la ville de départ et celle qui en est la plus proche. L’algorithme se termine lorsque toutes les villes à visiter ont été insérées. Cependant, même si l’insertion d’une ville dans le cycle est optimale et rapide à calculer, la solution finale n’est pas nécessairement optimale, mais elle est obtenue rapidement.

L’algorithme du plus proche voisin : qui peut lui aussi être considéré comme un algorithme glouton, est également simple. La première étape repose sur le choix aléatoire d’une première ville, et les étapes suivantes consistent à se déplacer de ville en ville en appliquant la règle du plus proche voisin, c’est-à-dire en sélectionnant la prochaine ville telle que le poids entre la ville courante et la prochaine ville soit minimal, et ce, jusqu’à avoir visité toutes les villes. Il faut enfin revenir à la première ville choisie, pour obtenir un cycle.

La méthode de l’élastique : n’est pas facile à mettre en œuvre, mais l’idée reste simple. Comme son nom l’indique, elle repose sur un élastique dont la propriété est de s’étirer tout en gardant une force l’empêchant de se détendre. Pour comprendre le principe, il suffit d’imaginer que les villes sont des points fixes distants les uns des autres en fonction des poids. Il s’agit de placer un élastique au milieu des villes et d’étirer celui-ci jusqu’à ce qu’il passe par tous ces points fixes, tout en essayant de le détendre le moins possible.

L’algorithme de descente locale : donne aussi rapidement de bons résultats. Son principe est le suivant : après la construction d’une solution initiale par l’utilisation d’un algorithme glouton, un opérateur de voisinage est appliqué à cette solution pour obtenir plusieurs nouvelles solutions voisines. Cet opérateur de voisinage consiste à modifier une solution selon une règle bien définie. Parmi cet ensemble de nouvelles solutions, l’algorithme va choisir la meilleure, celle qui a le cycle de plus petite longueur. Enfin, soit cette solution sélectionnée est meilleure que la précédente, et l’algorithme recommence à appliquer l’opérateur de voisinage sur cette nouvelle solution sélectionnée, soit la solution est moins bonne que la précédente et l’algorithme se termine. Il existe de nombreux opérateurs de voisinage d’efficacités variées. Un exemple simple est l’échange de deux villes dans le cycle. Pour obtenir l’ensemble de nouvelles solutions à partir d’une solution, il suffit de tester l’échange de chaque ville avec toutes les autres dans le cycle. Par exemple, avec une solution 1-2-3-4, en appliquant cet opérateur de voisinage, les solutions testées seraient : 2-1-3-4 (permuter 1 et 2), 3-2-1-4 (permuter 1 et 3), 4-2-3-1 (permuter 1 et 4), 1-3-2-4 (permuter 2 et 3), 1-4-3-2 (permuter 2 et 4), et 1-2-4-3 (permuter 3 et 4).

L’algorithme du recuit simulé : inspiré du processus de refroidissement et réchauffement d’un métal pour minimiser son énergie, peut être utilisé pour améliorer l’algorithme de descente locale. En effet, ce dernier algorithme se termine assez rapidement, puisqu’il n’autorise à explorer que les solutions améliorant les précédentes. Dans l’algorithme du recuit simulé, l’exploration de solutions autorise à explorer les solutions de moins bonne qualité. Au lieu de s’arrêter dès que la solution ne peut plus être améliorée par l’opérateur de voisinage, le recuit simulé continue l’exploration en prenant la meilleure solution parmi l’ensemble calculé, même si celle-ci est moins bonne que la solution précédente. Le critère d’arrêt est donc différent, il va dépendre du temps et de la dégradation de la solution, évaluée comme la différence de la longueur du cycle de la solution précédente et de la nouvelle solution sélectionnée. À chaque dégradation, l’algorithme s’arrête avec une probabilité dépendant de cette dégradation — plus la dégradation est grande, plus la probabilité de continuer diminue — et du temps ou du nombre d’itérations de l’algorithme — plus ce nombre est grand, plus la probabilité de continuer diminue elle aussi.

La recherche Tabou : très utilisée pour de nombreux problèmes, est encore une amélioration de la descente locale. Elle converge vite vers une bonne solution. Le principe est similaire : à partir d’une solution, appelée solution courante, l’algorithme explore d’autres solutions en appliquant un opérateur de voisinage. La sélection d’une solution à partir de la solution courante doit être la meilleure parmi son voisinage. À chaque choix d’une solution parmi un voisinage, la solution choisie est stockée dans une liste Tabou. Cette liste contient donc un certain nombre de solutions choisies précédemment. Le temps que la solution reste dans la liste dépend de la longueur maximale de cette liste, que l’on aura fixée au préalable. À chaque sélection, la nouvelle solution choisie ne doit pas appartenir à cette liste Tabou. Contrairement à une simple descente locale, la solution sélectionnée peut être de moins bonne qualité que la solution courante, ce qui permet d’éviter d’être rapidement bloqué sur une solution et de continuer à en explorer d’autres. Après un certain nombre d’itérations, la meilleure solution trouvée, parmi toutes celles qui ont été explorées, est retournée par l’algorithme. Le nombre d’itérations maximal doit lui aussi être défini préalablement.

Il existe encore de nombreuses améliorations des algorithmes présentés ici, ainsi que des hybridations (mélanges d’algorithmes) proposées dans le but de rendre leur résolution plus performante.

Enfin, il existe d’autres méthodes approchées, fondées sur des principes totalement différents. Nous évoquerons deux d’entre elles, assez innovantes et intéressantes puisqu’elles s’inspirent de phénomènes naturels : les algorithmes génétiques et les algorithmes de colonies de fourmis.

V. Conclusion :

Les métaheuristiques constituent une classe de méthodes approchées adaptables à un très grand nombre de problèmes combinatoires et de problèmes d’affectation sous contraintes. Elles ont révélé leur grande efficacité pour fournir des solutions approchées de bonne qualité pour un grand nombre de problèmes d’optimisation classiques et d’applications réelles de grande taille. C’est pourquoi l’étude de ces méthodes est actuellement en plein développement.

Si on peut constater la grande efficacité des métaheuristiques pour de nombreuses classes de problèmes, il existe en revanche très peu de résultats permettant de comprendre la raison de cette efficacité. Cette question constitue sans doute un défi important qu’il revient à la recherche de relever. Nous possédons bien des comparaisons entre métaheuristiques sur différentes classes de problèmes mais nous ne savons généralement ni expliquer le fonctionnement d’une métaheuristique, ni prévoir son efficacité sur une instance donnée. Pour améliorer cette situation, une tendance se dessine qui consiste à privilégier les tests descriptifs : ceux-ci consistent à identifier les facteurs supposés influencer les performances et à effectuer des comparaisons en faisant varier ces facteurs. Certains auteurs proposent d’aller plus loin et réclament une véritable science empirique des algorithmes devant aboutir à des modèles descriptifs de leur comportement.