Optimisation Combinatoire : Méthodes Approchées
Optimisation Combinatoire : Méthodes Approchées
Programming, Mathematics · lab
Fiche de révisionGuide de TP
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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.
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.
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.
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.
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.
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.
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.
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 η.
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.
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.
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.
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.