Le problème du voyageur de commerce à Java

1. Introduction

Dans ce didacticiel, nous allons découvrir l'algorithme de recuit simulé et nous montrerons l'exemple d'implémentation basé sur le problème du voyageur de commerce (TSP).

2. Recuit simulé

L'algorithme de recuit simulé est une heuristique pour résoudre les problèmes avec un grand espace de recherche.

L'Inspiration et le nom sont issus du recuit en métallurgie; c'est une technique qui implique le chauffage et le refroidissement contrôlé d'un matériau.

En général, le recuit simulé diminue la probabilité d'accepter les pires solutions en explorant l'espace des solutions et en abaissant la température du système. L'animation suivante montre le mécanisme de recherche de la meilleure solution avec l'algorithme de recuit simulé:

Comme nous pouvons l'observer, l'algorithme utilise une gamme de solutions plus large avec une température élevée du système, à la recherche d'un optimum global. En abaissant la température, la plage de recherche devient plus petite, jusqu'à ce qu'elle trouve l'optimum global.

L'algorithme a quelques paramètres avec lesquels travailler:

  • nombre d'itérations - condition d'arrêt des simulations
  • température initiale - l'énergie de démarrage du système
  • paramètre de vitesse de refroidissement - le pourcentage par lequel nous réduisons la température du système
  • température minimale - condition d'arrêt optionnelle
  • temps de simulation - condition d'arrêt facultative

Les valeurs de ces paramètres doivent être soigneusement sélectionnées - car elles peuvent avoir une influence significative sur les performances du processus.

3. Problème de vendeur itinérant

Le problème du voyageur de commerce (TSP) est le problème d'optimisation informatique le plus connu dans un monde moderne.

En termes simples, il s'agit de trouver un itinéraire optimal entre les nœuds du graphe. La distance totale parcourue peut être l'un des critères d'optimisation. Pour plus de détails sur TSP, veuillez consulter ici.

4. Modèle Java

Afin de résoudre le problème du TSP, nous aurons besoin de deux classes de modèle, à savoir City et Travel . Dans le premier, nous allons stocker les coordonnées des nœuds dans le graphique:

@Data public class City { private int x; private int y; public City() { this.x = (int) (Math.random() * 500); this.y = (int) (Math.random() * 500); } public double distanceToCity(City city) { int x = Math.abs(getX() - city.getX()); int y = Math.abs(getY() - city.getY()); return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2)); } }

Le constructeur de la classe City nous permet de créer des emplacements aléatoires des villes. La logique distanceToCity (..) est responsable des calculs concernant la distance entre les villes.

Le code suivant est responsable de la modélisation d'une visite de vendeur itinérant. Commençons par générer l'ordre initial des villes en voyage:

public void generateInitialTravel() { if (travel.isEmpty()) new Travel(10); Collections.shuffle(travel); }

En plus de générer l'ordre initial, nous avons besoin des méthodes pour permuter les deux villes au hasard dans l'ordre de déplacement. Nous l'utiliserons pour rechercher les meilleures solutions dans l'algorithme de recuit simulé:

public void swapCities() { int a = generateRandomIndex(); int b = generateRandomIndex(); previousTravel = travel; City x = travel.get(a); City y = travel.get(b); travel.set(a, y); travel.set(b, x); }

De plus, nous avons besoin d'une méthode pour annuler la génération de swap à l'étape précédente, si la nouvelle solution ne sera pas acceptée par notre algorithme:

public void revertSwap() { travel = previousTravel; }

La dernière méthode que nous voulons couvrir est le calcul de la distance totale parcourue, qui sera utilisée comme critère d'optimisation:

public int getDistance() { int distance = 0; for (int index = 0; index < travel.size(); index++) { City starting = getCity(index); City destination; if (index + 1 < travel.size()) { destination = getCity(index + 1); } else { destination = getCity(0); } distance += starting.distanceToCity(destination); } return distance; }

Maintenant, concentrons-nous sur la partie principale, l'implémentation de l'algorithme de recuit simulé.

5. Mise en œuvre du recuit simulé

Dans l'implémentation de recuit simulé suivante, nous allons résoudre le problème du TSP. Juste un petit rappel, l'objectif est de trouver la distance la plus courte pour parcourir toutes les villes.

In order to start process, we need to provide three main parameters, namely startingTemperature, numberOfIterations and coolingRate:

public double simulateAnnealing(double startingTemperature, int numberOfIterations, double coolingRate) { double t = startingTemperature; travel.generateInitialTravel(); double bestDistance = travel.getDistance(); Travel currentSolution = travel; // ... }

Before the start of the simulation, we generate initial (random) order of cities and calculate the total distance for travel. As this is the first calculated distance, we save it inside the bestDistance variable, alongside with the currentSolution.

In the next step we start a main simulations loop:

for (int i = 0; i  0.1) { //... } else { continue; } }

The loop will last the number of iterations that we specified. Moreover, we added a condition to stop the simulation if the temperature will be lower or equal to 0.1. It will allow us to save the time of simulations, as with low temperatures the optimization differences are almost not visible.

Let's look at the main logic of the Simulated Annealing algorithm:

currentSolution.swapCities(); double currentDistance = currentSolution.getDistance(); if (currentDistance < bestDistance) { bestDistance = currentDistance; } else if (Math.exp((bestDistance - currentDistance) / t) < Math.random()) { currentSolution.revertSwap(); }

In each step of simulation we randomly swap two cities in the traveling order.

Furthermore, we calculate the currentDistance. If the newly calculated currentDistance is lower than bestDistance, we save it as the best.

Otherwise, we check if Boltzmann function of probability distribution is lower than randomly picked value in a range from 0-1. If yes, we revert the swap of the cities. If not, we keep the new order of the cities, as it can help us to avoid the local minima.

Finally, in each step of the simulation we reduce the temperature by provided coolingRate:

t *= coolingRate;

After the simulation we return the best solution that we found using Simulated Annealing.

Please note the few tips on how to choose the best simulation parameters:

  • for small solution spaces it's better to lower the starting temperature and increase the cooling rate, as it will reduce the simulation time, without lose of quality
  • for bigger solution spaces please choose the higher starting temperature and small cooling rate, as there will be more local minima
  • always provide enough time to simulate from the high to low temperature of the system

Don't forget to spend some time on the algorithm tuning with the smaller problem instance, before you start the main simulations, as it will improve final results. The tuning of the Simulated Annealing algorithm was shown for example in this article.

6. Conclusion

Dans ce tutoriel rapide, nous avons pu en apprendre davantage sur l'algorithme de recuit simulé et nous avons résolu le problème du voyageur de commerce . J'espère que cela montre à quel point cet algorithme simple est pratique, lorsqu'il est appliqué à certains types de problèmes d'optimisation.

La mise en œuvre complète de cet article est disponible à l'adresse over sur GitHub.