Optimisation Combinatoire : Méthodes Approchées

Ce laboratoire porte sur l'optimisation combinatoire à travers deux méthodes approchées : la recherche tabou et l'optimisation par colonies de fourmis. Il permet de comprendre et d'appliquer ces techniques sur des problèmes concrets, notamment la recherche locale sur un graphe binaire et la résolution d'un problème de voyageur de commerce (TSP). Pour réaliser ce TP, il est nécessaire d'avoir des connaissances de base en algorithmique, en représentation binaire, et en probabilités appliquées aux heuristiques.

Objectifs

• Comprendre et appliquer la méthode de recherche tabou sur un ensemble discret représenté par des entiers codés en binaire.
• Représenter un graphe dont les sommets sont des entiers binaires et les arêtes correspondent à une différence d’un seul bit.
• Mettre en œuvre la méthode Max-Min Ant System (MMAS) pour résoudre un problème de type TSP.
• Analyser l'impact des paramètres tels que la taille de la liste tabou et les coefficients de pondération dans MMAS.
• Interpréter les résultats obtenus et identifier les limites des méthodes approchées.

Prérequis et préparation

• Connaissance des nombres binaires sur 4 bits et des opérations élémentaires sur les bits.
• Notions de graphes, notamment la représentation des sommets et des arêtes.
• Compréhension de la méthode de recherche tabou et de ses paramètres (liste tabou, itérations).
• Notions d'optimisation par colonies de fourmis, en particulier la version Max-Min Ant System (MMAS).
• Matériel : ordinateur avec un environnement de programmation permettant d’implémenter les algorithmes.
• Les paramètres MMAS utilisés : coefficients de pondération α = 1, β = 1, coefficient d'évaporation p = 0.01, borne maximale de phéromone τmax = 6, borne minimale τmin = 0.1.

Recherche Tabou sur un ensemble binaire

On considère l'ensemble S des 16 premiers entiers naturels, de 0 à 15, codés sur 4 bits. La transformation élémentaire consiste à changer un bit en son complémentaire. La fonction f est définie sur S avec des valeurs données (voir tableau dans le document source). Le graphe est construit avec les sommets correspondant aux entiers 0 à 15, et deux sommets sont reliés par une arête si leurs représentations binaires diffèrent d’un seul bit. Chaque sommet porte la valeur de f associée à l’entier.

Les transformations tiro (mettre le i-ème bit à 1) et tior (mettre le i-ème bit à 0) sont définies pour 1 ≤ i ≤ 4.

Étape 1 : Application de la méthode Tabou avec liste de taille 1

Partir du sommet 1111 (binaire). Appliquer la recherche tabou avec une liste tabou de taille 1 et un nombre d’itérations suffisamment grand.

Départ : 1111
Liste tabou : taille 1
Nombre d'itérations : grand

Le but est d’explorer le voisinage en changeant un bit à la fois, en évitant les mouvements tabous pour ne pas revenir immédiatement en arrière. Un résultat correct montre une progression vers un minimum local de la fonction f, sans oscillations.

Étape 2 : Application avec liste tabou de taille 2

Recommencer la recherche tabou à partir de 1111 avec une liste tabou de taille 2.

Départ : 1111
Liste tabou : taille 2
Nombre d'itérations : grand

Une liste plus longue permet d’éviter des cycles plus longs et favorise une exploration plus large. Le résultat attendu est une meilleure convergence vers un optimum local plus profond.

Étape 3 : Application avec liste tabou de taille 3

Effectuer la recherche tabou à partir de 1111 avec une liste tabou de taille 3.

Départ : 1111
Liste tabou : taille 3
Nombre d'itérations : grand

Cette étape permet d’observer l’effet de la taille de la liste tabou sur la qualité et la stabilité des solutions obtenues.

Étape 4 : Application avec liste tabou de taille 4

Appliquer la méthode tabou avec une liste de taille 4 en partant de 1111.

Départ : 1111
Liste tabou : taille 4
Nombre d'itérations : grand

On attend une exploration encore plus diversifiée, avec un risque plus faible de revenir sur des solutions déjà explorées.

Étape 5 : Discussion sur la taille de la liste tabou

Est-il utile d’envisager des tailles supérieures à 4 ? Cette question invite à réfléchir sur le compromis entre exploration et exploitation, ainsi que sur la complexité de gestion de la liste tabou.

Optimisation par colonies de fourmis (MMAS) pour le TSP

On reprend un problème de voyageur de commerce (TSP) avec une matrice de coûts donnée (voir tableau dans le document source). La méthode Max-Min Ant System (MMAS) est utilisée pour résoudre ce problème. Les traces de phéromone sont initialisées à une borne maximale τmax, bornées entre τmin et τmax, et seule la meilleure fourmi dépose la phéromone.

Étape 1 : Proposer une information heuristique

Il s’agit de définir une information heuristique pour guider les fourmis dans leur choix de chemin. Par exemple, l’inverse de la distance entre deux villes peut être utilisée comme information heuristique η.

Étape 2 : Signification des traces de phéromone

Les traces de phéromone déposées sur les chemins reflètent la qualité des solutions trouvées : plus un chemin est emprunté par les meilleures fourmis, plus sa trace est élevée, ce qui augmente la probabilité qu’il soit choisi à nouveau.

Étape 3 : Calcul de la probabilité de transition

En partant de la ville A, la probabilité de choisir la ville C est donnée par la formule :

p_{A,C} = (τ_{A,C}^α) * (η_{A,C}^β) / Σ_{j ∈ villes non visitées} (τ_{A,j}^α) * (η_{A,j}^β)

où τ est la trace de phéromone, η l’information heuristique, α et β les coefficients de pondération.

Étape 4 : Nombre de cycles pour atteindre τmin

Après un certain nombre de cycles, la trace de phéromone sur un chemin peut atteindre la borne minimale τmin. Le nombre minimal de cycles dépend du coefficient d'évaporation p et de la mise à jour des phéromones.

Étape 5 : Mise à jour de la matrice de phéromone

Supposons que la meilleure solution trouvée pendant un cycle est le chemin ABCDEF. La matrice de phéromone est mise à jour en augmentant les valeurs τ_{i,j} sur les arcs du chemin ABCDEF et en appliquant l'évaporation sur tous les arcs :

Pour chaque arc (i,j) :
  τ_{i,j} = (1 - p) * τ_{i,j} + Δτ_{i,j}
  
où Δτ_{i,j} = Q / longueur(ABCDEF) si (i,j) appartient au chemin ABCDEF, sinon 0.

Q est une constante liée à la quantité de phéromone déposée.

Résultats attendus

• Pour la recherche tabou, une convergence vers un minimum local de la fonction f sur le graphe binaire, avec une meilleure qualité de solution pour des listes tabou plus longues jusqu’à une certaine limite.
• Pour MMAS, une amélioration progressive des solutions TSP avec une matrice de phéromone qui se stabilise entre τmin et τmax.
• Probabilités de transition cohérentes avec les valeurs de phéromone et d’information heuristique.
• Nombre de cycles suffisant pour que les phéromones atteignent les bornes définies.

Erreurs courantes

• Ne pas respecter la taille de la liste tabou, ce qui peut entraîner des cycles ou un mauvais équilibre entre exploration et exploitation.
• Confondre les transformations tiro et tior lors de la modification des bits.
• Dans MMAS, ne pas appliquer correctement l’évaporation des phéromones, ou ne pas limiter les valeurs entre τmin et τmax.
• Calcul incorrect des probabilités de transition, notamment en oubliant la normalisation.
• Ne pas mettre à jour la matrice de phéromone uniquement avec la meilleure fourmi, ce qui fausse la dynamique de l’algorithme.