🧭 Sur la Route de l’Optimum : Recuit Simulé pour le TSP

Recuit simulé avec pondération et opérations de voisinage multiples

Plongeons une fois de plus dans le monde fascinant des métaheuristiques, un domaine que j’explore avec un enthousiasme renouvelé à chaque nouvel article.

‘La Nuit étoilée’ de Vincent Van Gogh [source], qui capte l’essence même des métaheuristiques où l’ordre émerge du chaos

Dans cet esprit, je vous invite à découvrir notre dernier périple autour du Traveling Salesman Problem (TSP). Aussi appelé le problème du voyageur de commerce en français, c’est une énigme classique de l’optimisation combinatoire qui, malgré sa simplicité conceptuelle — trouver la route la plus courte pour visiter une série de villes et revenir à son point de départ (dans sa version symétrique) — , représente un défi complexe et multidimensionnel.

Résolution du Traveling Salesman Problem avec des villes des USA par une métaheuristique [source]

Il trouve des applications dans divers domaines, notamment la logistique, la planification de routes et l’intelligence artificielle.

Voilà pourquoi l’objectif principal de cet article sera de développer, implémenter et affiner une méthode de recuit simulé pour le TSP.

🔣 L’algorithme de recuit simulé

Le recuit simulé est une technique d’optimisation inspirée du processus de recuit en métallurgie. L’algorithme simule un processus où les solutions sont progressivement améliorées à travers des itérations, en permettant d’accepter occasionnellement les solutions de moins bonne qualité pour éviter les minimums locaux.

▶ Fonctionnement

Globalement le fonctionnement du recuit simulé est basé sur les principes suivant :

◼️ Initialisation : Commence par un état aléatoire du système avec une énergie (fitness) initiale et une température élevée.

◼️ Processus Itératif : A chaque itération, une petite modification est apportée à l’état actuel, générant un nouvel état.

• Si le nouvel état a une énergie inférieure (meilleure solution), il est accepté.
• Si l’énergie est supérieure (solution de moindre qualité), il peut être accepté avec une certaine probabilité qui dépend de la différence d’énergie et de la température actuelle.

◼️ Refroidissement : La température est progressivement diminuée selon une loi de décroissance (linéaire, exponentielle, etc.), réduisant la probabilité d’accepter des solutions de moins bonne qualité. C’est ce qui nous fait converger vers la meilleur solution.

◼️ Critère d’Acceptation : Si la nouvelle solution est meilleure, elle est systématiquement acceptée. Si elle est moins bonne, elle peut tout de même être acceptée avec une certaine probabilité, qui diminue au fur et à mesure du refroidissement. Cela permet d’éviter de rester bloqué dans un minimum local en acceptant temporairement des solutions de moindre qualité, favorisant ainsi l’exploration de l’espace des solutions de manière plus exhaustive.

Illustration des différentes étapes du recuit simulé [souce]

▶ Pseudo-code

Le pseudo-code suivant met en œuvre le recuit simulé :

i := i0 (* Solution initiale *) 
T := T0 (* Température initiale *)

Tant que la condition d'arrêt n'est pas vérifiée 
    Tant que la fin du pallier n'est pas atteinte 
        Générer nouvelle solution j
        Δ = e(j) - e(i)
        Si Δ < 0 alors
            i := j
        Sinon
            i := j avec une proba de exp(-Δ/T)
        Fin si
    Fin tant que
    Abaisser T
Fin tant que

👨🏿‍💻 Implémentation du Recuit Simulé pour le TSP

L’implémentation du recuit simulé pour résoudre le problème du voyageur de commerce (TSP) représente un défi fascinant en optimisation. Dans les sections suivantes, nous allons détailler les étapes clés de notre implémentation.

Nous commençons par lire un fichier TSP et extraire une liste des coordonnées des villes. Pour simplifier notre démonstration, nous nous concentrons sur les six premières villes, constituant ainsi un ensemble de données gérable pour illustrer clairement le fonctionnement de nos fonctions.

tsp_cities = read_tsp_data(tsp_data_filepath)[:6]
tsp_cities

'''
output:
[(1, 565.0, 575.0),
 (2, 25.0, 185.0),
 (3, 345.0, 750.0),
 (4, 945.0, 685.0),
 (5, 845.0, 655.0),
 (6, 880.0, 660.0)]
'''

▶ Création d’une solution initiale

Dans mon implémentation, une solution initiale est représentée par une liste de tuples, chacun indiquant une ville avec ses coordonnées numériques. Cette solution initiale est générée en mélangeant aléatoirement les villes issues de notre ensemble de données, tout en gardant la ville de départ fixe. Dans le cadre du TSP symétrique, le chemin doit impérativement revenir au point de départ, donc la ville de départ rajouté à la fin.

La fonction pour générer cette solution initiale est structurée comme suit :

# Generate a random solution (starting point)
def initial_solution(tsp_cities):
    # Start with the first element
    start = tsp_cities[0]
    # Exclude the first element when shuffling the rest of the data
    rest_of_cities = tsp_cities[1:]
    random.shuffle(rest_of_cities)
    # Return the individual starting and ending with the first element
    individual = [start] + rest_of_cities + [start]
    return individual

sol = initial_solution(tsp_cities)
sol

'''
output:
[(1, 565.0, 575.0),
 (6, 880.0, 660.0),
 (4, 945.0, 685.0),
 (5, 845.0, 655.0),
 (2, 25.0, 185.0),
 (3, 345.0, 750.0),
 (1, 565.0, 575.0)]
'''

▶ Définition de la fonction objectif

La clé de toute optimisation réside dans la définition adéquate d’une fonction objectif, qui peut aussi servir de fonction d’évaluation. Pour le TSP, cette fonction (aussi appelée fonction coût) est la somme des distances entre les villes consécutives.

Pour optimiser les calculs, j’ai préconçu une matrice des distances entre toutes les paires de villes.

Voici l’implémentation de la matrice des distances :

# Compute the distance
def compute_distance(a, b):
    _, x1, y1 = a
    _, x2, y2 = b
    distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return distance

# Create a distance matrix for all cities
def create_distance_matrix(tsp_cities):
    num_cities = len(tsp_cities)
    distance_matrix = np.zeros((num_cities, num_cities))

    for i in range(num_cities):
        for j in range(i + 1, num_cities):
            distance = compute_distance(tsp_cities[i], tsp_cities[j])
            distance_matrix[i][j] = distance
            distance_matrix[j][i] = distance  # Mirror the distance as the matrix is symmetric

    return distance_matrix

distance_matrix = create_distance_matrix(tsp_cities)
print(distance_matrix.shape)
distance_matrix

'''
output:
(6, 6)
array([[   0.        ,  666.10809934,  281.11385594,  395.6008089 ,
         291.20439557,  326.26676202],
       [ 666.10809934,    0.        ,  649.32657423, 1047.09120902,
         945.14549145,  978.08486339],
       [ 281.11385594,  649.32657423,    0.        ,  603.51056329,
         508.9449872 ,  542.51728083],
       [ 395.6008089 , 1047.09120902,  603.51056329,    0.        ,
         104.40306509,   69.64194139],
       [ 291.20439557,  945.14549145,  508.9449872 ,  104.40306509,
           0.        ,   35.35533906],
       [ 326.26676202,  978.08486339,  542.51728083,   69.64194139,
          35.35533906,    0.        ]])
'''

Cette stratégie permet de récupérer les distances nécessaires sans recalculs inutiles et donc de gagner du temps [4].

En effet, le calcul de la distance totale du chemin permet d’évaluer chaque solution proposée par l’algorithme. Plus cette distance est courte, meilleure est la solution.

Voici l’implémentation de la fonction d’évaluation :

# Compute the sum of the distances between cities / the longer of the path
def fitness(solution, distance_matrix):
    total_distance = 0
    num_cities = len(solution)

    for i in range(num_cities - 1):
        city_from = solution[i][0]
        city_to = solution[i + 1][0]
        total_distance += distance_matrix[city_from-1][city_to-1]

    return total_distance

print('solution:', sol)
print('distance:', fitness(sol, distance_matrix))

'''
output:
solution: [(1, 565.0, 575.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
distance: 2375.8976901086
'''

En poursuivant cette démarche, l’objectif est de raffiner progressivement les solutions à travers les diverses itérations de l’algorithme de recuit simulé.

▶ Génération de solutions voisines

Pour générer des solutions voisines, je m’inspire grandement du travail de Francis ALLANAH [2]. En effet, différents opérateurs de voisinages comme l’échange (swap) de villes, l’insertion d’une ville, ainsi que l’insertion et l’inversion de sous-itinéraires sont utilisés. Ces opérations permettent de diversifier la recherche de nouvelles solutions potentiellement meilleures.

• Swap Operator : Cet opérateur modifie une solution en échangeant les positions de deux villes choisies aléatoirement dans l’itinéraire, à l’exception des éléments de début et de fin.

# Swap Operator: This operator exchanges the positions of two cities in a route.
def swap_operator(solution):
    new_solution = solution.copy()
    # Randomly select two indexes, avoiding the first and last elements
    idx1, idx2 = np.random.choice(range(1, len(new_solution) - 1), 2, replace=False)
    # Perform the swap
    new_solution[idx1], new_solution[idx2] = new_solution[idx2], new_solution[idx1]
    return new_solution

print('solution:', sol)
print('swap_operator:', swap_operator(sol))

'''
output:
solution: [(1, 565.0, 575.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
swap_operator: [(1, 565.0, 575.0), (6, 880.0, 660.0), (5, 845.0, 655.0), (4, 945.0, 685.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
'''

• Insert Operator : Il déplace une ville d’une position aléatoire à une autre dans l’itinéraire, ce qui peut radicalement changer la configuration du parcours.

# Insert Operator: This operator moves a city from one random position to another.
def insert_operator(solution):
    new_solution = solution.copy()
    # Randomly select two indexes, avoiding the first and last elements
    idx1, idx2 = np.random.choice(range(1, len(new_solution) - 1), 2, replace=False)
    # Perform the insert operation
    city_to_move = new_solution.pop(idx1)
    new_solution.insert(idx2, city_to_move)
    return new_solution

print('solution:', sol)
print('insert_operator:', insert_operator(sol))

'''
output:
solution: [(1, 565.0, 575.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
insert_operator: [(1, 565.0, 575.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (6, 880.0, 660.0), (1, 565.0, 575.0)]
'''

• Inverse Subroutes Operator : Cette opération inverse l’ordre des villes dans un segment aléatoire de l’itinéraire, offrant une variation significative de la solution.

# Inverse Subroutes Operator: This operator reverses the order of the routes between two randomly selected nodes.
def inverse_subroutes_operator(solution):
    new_solution = solution.copy()
    # Select two random indexes and sort them
    idx1, idx2 = sorted(np.random.choice(range(1, len(new_solution) - 1), 2, replace=False))
    # Perform the inverse operation
    new_solution[idx1:idx2+1] = reversed(new_solution[idx1:idx2+1])
    return new_solution

print('solution:', sol)
print('inverse_operator:', inverse_subroutes_operator(sol))

'''
output:
solution: [(1, 565.0, 575.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
inverse_subroutes_operator: [(1, 565.0, 575.0), (6, 880.0, 660.0), (2, 25.0, 185.0), (5, 845.0, 655.0), (4, 945.0, 685.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
'''

• Insert Subroutes Operator : Cet opérateur sélectionne un sous-ensemble de l’itinéraire et l’insère à une position différente, permettant une restructuration plus complète de la solution.

# Insert Subroutes Operator: This operator selects a range of cities and inserts them at a random position.
def insert_subroutes_operator(solution):
    # Ensure there are enough cities for the operation
    if len(solution) <= 3: 
        return solution

    new_solution = solution.copy()
    # Select two random indexes and sort them
    idx1, idx2 = sorted(np.random.choice(range(1, len(new_solution) - 1), 2, replace=False))
    # Extract the subroute
    subroute = new_solution[idx1:idx2+1]
    # Remove the subroute from the original position
    new_solution = new_solution[:idx1] + new_solution[idx2+1:]

    # Insert the subroute at a new position
    if len(new_solution) > len(subroute):
        insert_idx = np.random.choice(range(1, len(new_solution) - len(subroute) + 1))
    else:
        insert_idx = 1  # or another backup logic if new_solution is too short

    new_solution = new_solution[:insert_idx] + subroute + new_solution[insert_idx:]
    return new_solution

print('solution:', sol)
print('insert_subroutes_operator:', insert_subroutes_operator(sol))

'''
output:
solution: [(1, 565.0, 575.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (1, 565.0, 575.0)]
insert_subroutes_operator: [(1, 565.0, 575.0), (2, 25.0, 185.0), (3, 345.0, 750.0), (6, 880.0, 660.0), (4, 945.0, 685.0), (5, 845.0, 655.0), (1, 565.0, 575.0)]
'''

Pour l’application de ces opérateurs à la solution, j’ai élaboré une méthode qui les applique de façon pondérée et répétitive, en tenant compte de la température de l’algorithme.

Par “pondéré” j’entends que, contrairement à une approche classique où toutes les opérations possèdent une probabilité égale d’être choisies, certaines opérations sont privilégiées par rapport à d’autres. Autrement dit, des probabilités différentes sont attribuées à chaque opérateur, reflétant leur “poids” dans le processus de sélection. .

Quant à l’aspect “répétitif”, cela signifie que la solution peut subir plusieurs modifications consécutives. En d’autres termes, les opérateurs de voisinage peuvent être appliqués de manière itérative sur une même solution, permettant ainsi de générer des solutions nouvelles et potentiellement plus optimales.

À noter que notre méthode ressemble à la sélection de la Roulette-Wheel, mais avec une différence : les probabilités associées à chaque option sont fixées manuellement au début lors de l’initialisation de la fonction. De plus, le processus peut être comparé à faire tourner la roulette plusieurs fois, bien que le nombre de tours diminue à mesure que la température baisse.

Avec la sélection de la Roulette-Wheel, un choix possédant une plus grande part sur la roue a une plus grande chance de se retrouver devant le point fixe lorsque la roue est tournée [source]

En effet, le nombre d’opérations effectuées est ajusté dynamiquement en fonction de la température mais aussi de la taille de la solution (le nombre de villes). Ainsi, il est proportionnel à la taille de la solution, tout en étant inversement proportionnel à la température. Cette relation est déterminée par la formule suivante, que j’ai élaborée :

# the dimension of the solution: number of cities
dim = len(new_solution)

# Determines a scaling factor
factor = ((temperature)/(max_temperature))**(1/dim*10)

# Determines the number of operations to perform
nbr_operations = 1 + int(round(0.2 * dim * factor))

Le nombre d’opérations de voisinage à appliquer est fixé à une base de 1, plus un nombre supplémentaire qui dépend de :

• factor un facteur d’échelle. Il calculé en prenant le rapport de la température actuelle sur la température maximale (normalisant ainsi le facteur entre 0 et 1), puis en élevant ce rapport à une puissance qui est inversément proportionnelle à la dimension de la solution. Cela signifie que pour des solutions plus grandes (avec plus de villes), le facteur diminue et converge plus lentement, permettant ainsi potentiellement plus d'opérations de voisinage à des températures plus élevées. Cependant, la diminution est assez lente, d’où la multiplication de dim par 10 dans le dénominateur pour accélérer la convergence.
• 0.2*dim un pourcentage de la dimension de la solution.

Cette approche garantit que :

• Davantage d’opérations sont effectuées à des températures plus élevées (exploration plus large) et moins à des températures plus basses (exploration plus fine)
• Davantage d’opérations sont effectuées sur des solutions de grande taille et moins sur des solutions de plus petite taille.

Voici l’implémentation final de la fonction pour la génération de solutions voisines :

# Neighbour Generation by Weighted Random Operator Choice
def neighbour(solution, temperature, max_temperature, weights=[50, 30, 10, 10]):
    list_operator_choice = []
    new_solution = solution.copy()

    # the dimension of the solution.
    dim = len(new_solution)

    # Determines a scaling factor based on the current temperature and the maximum temperature,
    factor = (temperature)**(1/dim*2) / (max_temperature)**(1/dim*2)

    # Determines the number of operations (neighbourhood changes) to perform.
    nbr_operations = 1 + int(round(0.2 * dim * factor))

    for _ in range(nbr_operations):

        operator_choice = random.choices([0,1,2,3], weights=weights)[0]
        if operator_choice == 0:
            new_solution = swap_operator(new_solution)
        elif operator_choice == 1:
            new_solution = insert_operator(new_solution)
        elif operator_choice == 2 :
            new_solution = inverse_subroutes_operator(new_solution)
        else:
            new_solution = insert_subroutes_operator(new_solution)

        list_operator_choice.append(operator_choice)

    return new_solution, list_operator_choice


print('solution:', sol)
new_solution, list_operator_choice = neighbour(sol, 500, 1000, weights=[50, 30, 10, 10])
print('new_solution:', new_solution)
print('nbr_operations:', len(list_operator_choice))
print('list_operator_choice:', list_operator_choice)

'''
output:
print('solution:', sol)
new_solution, list_operator_choice = neighbour(sol, 500, 1000, weights=[50, 30, 10, 10])
print('new_solution:', new_solution)
print('nbr_operations:', len(list_operator_choice))
print('list_operator_choice:', list_operator_choice)
'''

▶ Mécanisme de refroidissement

En effet, l’essence du recuit simulé repose sur un mécanisme de refroidissement [1] qui diminue progressivement la température. Cette baisse de température réduit la probabilité d’accepter des solutions de moins bonne qualité au fil du temps.

Pour gérer cette décroissance, j’ai opté pour une approche continue, en utilisant une loi exponentielle commune [1] :

Loi de décroissance exponentielle avec un facteur λ<1

▶ Critère d’acceptation des nouvelles solutions

Le critère d’acceptation des nouvelles solutions dans un algorithme de recuit simulé joue un rôle crucial pour l’équilibre entre l’exploration et l’exploitation dans la recherche de la meilleure solution.

Notre algorithme adopte l’approche probabiliste classique en recuit simulé pour décider d’accepter ou de rejeter les nouvelles solutions, en fonction de la différence de coût (la qualité de la solution) et de la température actuelle du système [4].

Voici l’implémentation de la fonction d’acceptance :

# Decision function to accept or reject the new point
def accept_probability(old_cost, new_cost, temperature):
    if new_cost < old_cost:
        return 1.0
    else:
        # The smaller the temperature, the smaller the probability of acceptance
        return np.exp((old_cost - new_cost) / temperature) # between 0 and 1

▶ Critères d’arrêt de l’algorithme

Passons maintenant aux critères d’arrêt de l’algorithme, qui représentent une autre dimension cruciale de notre approche. Le critère d’arrêt d’un algorithme de recuit simulé est essentiel pour déterminer quand l’algorithme doit cesser d’exécuter et renvoyer la meilleure solution trouvée.

Dans notre cas, plutôt que de simplement arrêter l’algorithme lorsque la température atteint zéro, nous allons nous arrêter lorsque la même solution candidate a été sélectionnée un certain nombre de fois [2].

Ce critère augmente les chances de trouver la meilleure solution possible. Cette méthode est particulièrement utile pour explorer de vastes espaces de recherche où la convergence vers un optimum global est difficile à atteindre rapidement.

▶ Implémentation final du recuit simulé

À présent, vous trouverez mon implémentation final du recuit simulé — s’appuyant sur les fonctions que nous avons soigneusement élaborées auparavant — en accédant au repository github du projet :

GitHub - PhDMlachahe/SimulatedAnnealing_TSP

📊 Tests, Résultats et Performance

Pour cette évaluer la performance de notre algorithme, nous avons choisi de nous appuyer sur des benchmarks disponibles sur le site TSPLIB : uni-heidelberg.de, à savoir :

• ulysses22.tsp : qui contient 22 villes
• berlin52.tsp : qui contient 52 villes
• st70.tsp : qui contient 70 villes
• ch130.tsp : qui contient 789 villes.. non 130 villes

Pour une analyse approfondie, nous enregistrons puis affichons le meilleur itinéraire trouvé, ainsi que l’historique des coûts, des températures, des probabilités d’acceptation et des choix d’opérateurs pour chaque itération.

▶ Affichage et Analyse des résultats

Nos résultats montrent comment le recuit simulé performe sur les benchmarks sélectionnés.

Voici quelques résultats avec différents paramètres en entrée :

Résultats avec les paramètres suivants : {‘initial temperature’: 10000, ‘gamma’: 0.99, ‘max solution selected’: 1500, ‘weights’: [100, 0, 0, 0]}

Résultats avec les paramètres suivants : {‘initial temperature’: 10000, ‘gamma’: 0.99, ‘max solution selected’: 1500, ‘weights’: [50, 15, 30, 5]}

Ces résultats soulignent l’importance de bien choisir les paramètres du recuit simulé et de la stratégie de voisinage. Ils démontrent que la diversification des opérations de voisinage peut conduire à des résultats nettement meilleurs, en évitant les pièges des optima locaux et en explorant plus efficacement l’espace des solutions.

▶ Analyse des paramètres de l’algorithme

Par ailleurs, en parlant de bonne ajustage des paramètres, suite à de multiples expérimentations pour optimiser les performances et la qualité des solutions, nous avons observé les points suivants :

• La valeur initiale de la température ‘initial temperature’ semble avoir un impact modéré sur la qualité finale de la solution.
• A contrario, le taux de décroissance de la température ‘gamma’ joue un rôle important. Un ‘gamma’ élevé ralentit la convergence de l’algorithme.
• Concernant la valeur 'max solution selected’, un nombre plus élevé offre des solutions de meilleure qualité, mais augmente également le nombre d’itérations.
• Le choix des poids d’opérations de voisinage ‘weights’ est crucial. De fait, les opérateurs d’échange apportent des modifications plus subtiles par rapport aux opérateurs d’insertion. Trouver un équilibre adéquat entre eux est essentiel pour générer des solutions à la fois nouvelles et optimales, évitant ainsi une trop grande similitude ou divergence des itinéraires proposés.

▶ Évaluation des performances de l’algorithme

Au final, nous avons compilé les performances de l’algorithme sur les différents benchmarks dans un tableau récapitulatif, avec comme paramètres d’entrée : {‘initial temperature’: 10000, ‘gamma’: 0.99, ‘max solution selected’: 1500} avec des valeurs de ‘weights’ différentes

Tableau récapitulatif des résultats avec les paramètres suivant : {‘initial temperature’: 10000, ‘gamma’: 0.99, ‘max solution selected’: 1500} et des valeurs de ‘weights’ différentes

On observe que les résultats sont meilleurs, c’est-à-dire possède le plus faible taux d’erreur, lorsque la balance “opérateurs d’échange & opérateurs d’insertion” est configuré de la sorte : [40, 30, 35, 5]

➕ Piste d’amélioration

Les résultats obtenus jusqu’ici sont encourageants et ouvrent la voie à de multiples ajustements et expérimentations susceptibles d’optimiser davantage notre approche. Après un plus gros travail bibliographique, les pistes suivantes peuvent être envisagées pour peaufiner notre algorithme et élargir le champ de nos recherches :

• Approfondissement significatif de la bibliographie, notamment autour du “Multi-Neighborhood simulated annealing” — car honnêtement, je n’ai pas eu le temps de me pencher longuement là-dessus — , pour renforcer la robustesse de notre approche et surtout l’aligner sur les dernières avancées sur notre sujet.
• Révision globale de l’implémentation du code en se concentrant sur la réduction de sa complexité, avec notamment dans changement dans le suivi détaillé de l’historique qui, bien que précieux pour l’analyse, pourrait être omis ou simplifié pour alléger les calculs et améliorer l’efficacité globale.
• Tests sur un spectre plus large de benchmarks, particulièrement avec des TSP de plus grandes dimensions pour évaluer l’efficacité de l’algorithme à plus grande échelle.
• Adoption de stratégies de refroidissement alternatives, comme des paliers de température fixes, pour une exploration plus méthodique de l’espace des solutions.
• Application d’optimisations d’hyperparamètres automatisées, telles que la recherche par grille ou bayésienne, pour identifier les configurations optimales de l’algorithme.

📝 Conclusion

En résumé, notre article a confirmé l’efficacité du recuit simulé dans la recherche de solutions approchées pour le problème du voyageur de commerce.

Par dessus tout, il est met en avant la bonne performance — bien qu’elle reste perfectible — de notre approche de recuit simulé avec pondération et opérations de voisinage multiples, celle-ci permettant une exploration encore plus agressive et diversifiée des solutions au début.

En dehors de tout cela, on peut remarquer que les opérateurs de voisinage utilisés suggèrent un potentiel intéressant s’ils étaient intégrés comme opérateurs de mutation dans un algorithme génétique. Cette hybridation pourrait potentiellement combiner les meilleures caractéristiques des deux approches, menant à des solutions encore plus performantes pour le TSP et au-delà. Peut-être que cette synergie prometteuse à déjà été abordé dans des papiers scientifiques, à voir encore une fois.

Mlachahe SAID SALIMO.

Article rédigé suite à un travail pratique du professeur Salim BITAM, de l’Université de Biskra.

Références

1. Recuit Simulé, la page Wikipédia.
2. Travelling Salesman Problem Using Simulated Annealing, l’article issu du blog Medium de Francis ALLANAH (2022).
3. List-Based Simulated Annealing Algorithm for Traveling Salesman Problem, un article scientifique de S. Zhan, J. Lin, Z. Zhang, et Y. Zhong.
4. Simulated annealing applied to the traveling salesman problem, l’article issu du blog Emmanuel GOOSAERT (2010).

Pour aller plus loin :

• Performance Comparison of Simulated Annealing, GA and ACO Applied to TSP, article scientifique de H. Mukhairez et A. Maghari (2015)
• Genetic Algorithms: Comparing Evolution With and Without a Simulated Annealing-inspired Selection, manuscript de Mats ANDERSSON & David MELLIN (2019)