Practical activity

Présentation & objectifs

Dans cette activité, vous allez développer un algorithme heuristique pour approximer une solution au problème du voyageur de commerce (TSP). Ici, nous choisissons de nous concentrer sur un algorithme glouton.

Dans les parties optionnelles, nous suggérons quelques heuristiques alternatives et améliorations. La partie sur le 2-OPT n’est pas très difficile, et intéressante à vérifier. N’hésitez pas à y jeter un œil !

Contenu de l’activité

1 — L’heuristique gloutonne

1.1 — Préparation

Avant de commencer, créons d’abord les fichiers dont nous avons besoin dans l’espace de travail :

• pyrat_workspace/players/Greedy.py – Dupliquez le fichier TemplatePlayer.py, et renommez-le en Greedy.py. Puis, comme dans la session précédente, renommez la classe en Greedy.

• pyrat_workspace/games/visualize_Greedy.ipynb – Créez un fichier qui lancera une partie avec un joueur Greedy, dans un labyrinthe avec de la boue (argument mud_percentage), et 20 morceaux de fromage (argument nb_cheese). Optionnellement, vous pouvez définir un random_seed et une trace_length. Vous devriez vous inspirer des autres fichiers dans le sous-répertoire games que vous avez rencontrés lors de la session précédente.

• pyrat_workspace/tests/tests_Greedy.ipynb – En vous inspirant des fichiers de tests unitaires rencontrés dans les sessions précédentes, créez un fichier test_Greedy.ipynb. Ce fichier contiendra les tests unitaires que vous développerez pour tester les méthodes de votre joueur Greedy.

1.2 — Programmer l’algorithme glouton

Nous voulons utiliser l’heuristique suivante : le chemin le plus court passant par tous les morceaux de fromage peut être approximé en allant séquentiellement vers le morceau de fromage le plus proche. Pour écrire un algorithme glouton avec cette heuristique, suivez les mêmes étapes que la dernière fois, c’est-à-dire :

• Identifier les fonctions – Vous devez d’abord identifier quelles fonctions vous aurez besoin. N’hésitez pas à revenir aux articles que vous avez dû étudier pour aujourd’hui. Une fois identifiées, écrivez leurs prototypes dans votre fichier Greedy.py.

• Identifier les tests – Déterminez quels tests vous devez effectuer pour garantir que ces fonctions fonctionnent comme prévu.

• Programmer les méthodes – Ensuite, écrivez du code (tests et joueur) pour vous assurer que vos fonctions fonctionnent comme prévu, et passent les tests que vous avez conçus.

La vidéo suivante vous montre un exemple de ce que vous devriez observer :

1.3 — Comparaison avec l’algorithme exhaustif

Comme vous l’avez vu dans les articles que vous avez dû étudier, un algorithme approximatif est un compromis entre précision, complexité, et parfois d’autres propriétés (mémoire requise, besoin de dispositifs particuliers…).

Vous devriez comparer le temps nécessaire pour récupérer tous les morceaux de fromage, pour le joueur Greedy que vous venez de créer, comparé aux joueurs Exhaustive de la session précédente. Veuillez créer un script dans le sous-répertoire games, qui créera un graphique du temps nécessaire, en fonction du nombre de morceaux de fromage dans le labyrinthe, pour les deux joueurs.

1.4 — Soyez réactif

Jusqu’à présent, vous avez probablement suivi le même raisonnement que dans les sessions précédentes. En d’autres termes, la façon la plus directe de programmer l’algorithme glouton est de calculer le chemin dans la phase de preprocessing, et de le dérouler à chaque appel de turn.

Maintenant, imaginons que vous avez un adversaire dans la partie. Si vous suivez un chemin prédéterminé sans considérer que votre adversaire peut manger certains morceaux de fromage entre-temps, vous allez définitivement perdre. En effet, vous allez essayer d’aller vers des morceaux de fromage qui ont disparu, tandis que l’adversaire se concentrera sur ceux qui restent.

1.4.1 — Une première amélioration

Reconsidérons comment fonctionne l’algorithme glouton :

• Considérez que vous êtes sur une cellule particulière dans le labyrinthe, et que vous lancez votre algorithme glouton.
• La sortie devrait être une liste de morceaux de fromage à manger, donnée dans l’ordre dans lequel les récupérer.
• Une fois que vous avez cette liste, vous effectuez une action dans la direction de ce morceau de fromage.

En effet, un algorithme glouton approxime un optimum global par une série d’optimums locaux. Avec la description ci-dessus, vous devriez observer que vous n’avez pas besoin de calculer tout le chemin d’un coup pour pouvoir prendre cette décision. En effet, déterminer le prochain morceau de fromage vers lequel aller suffit pour pouvoir déterminer la prochaine action.

Par conséquent, sélectionner le prochain morceau de fromage uniquement lorsque vous atteignez votre cible vous permettra d’ignorer ceux qui ont été attrapés par l’adversaire entre-temps.

Vous devriez maintenant créer un nouveau joueur GreedyEachCheese.py, qui réalise cette amélioration. Créez également un script visualize_GreedyEachCheese.ipynb dans le sous-répertoire games pour lancer une partie avec ce joueur. N’oubliez pas d’ajouter des tests unitaires supplémentaires dans un fichier dédié si nécessaire.

1.4.2 — Encore mieux

Le joueur GreedyEachCheese a encore un inconvénient. En effet, si l’adversaire attrape le morceau de fromage que nous ciblons actuellement, alors que nous nous dirigeons vers lui, nous finirons quand même notre trajectoire.

Pour être encore plus réactif, repensons notre GreedyEachCheese :

• Considérez que vous êtes sur une cellule particulière dans le labyrinthe, et que vous lancez votre algorithme glouton.
• La sortie devrait être le prochain morceau de fromage à attraper (appelons-le c).
• Une fois que vous avez déterminé c, vous effectuez une action dans sa direction.

Eh bien, si nous faisons un pas dans la direction de c, nous pouvons distinguer les deux scénarios suivants :

• c est toujours là – Alors, c est toujours le morceau de fromage le plus proche, car nous avons réduit le nombre de tours nécessaires pour y aller de 1 (ou plus s’il y avait de la boue). Nous devrions continuer dans sa direction.
• c a été attrapé par un adversaire – Alors, nous devrions nous concentrer sur un autre morceau de fromage.

Notez que nous pouvons satisfaire les deux scénarios en lançant notre algorithme glouton à chaque tour pour déterminer la prochaine action (et non le prochain morceau de fromage comme dans GreedyEachCheese). En faisant cela, nous trouverions le même chemin à suivre si le fromage est toujours là, et nous nous déplacerions ailleurs si nécessaire.

Vous devriez maintenant créer un nouveau joueur GreedyEachTurn.py, qui réalise cette amélioration. Créez également un script GreedyEachTurn.ipynb dans le sous-répertoire games pour lancer une partie avec ce joueur. N’oubliez pas d’ajouter des tests unitaires supplémentaires dans un fichier dédié si nécessaire.

1.4.3 — Comparer les programmes

Vous avez maintenant trois algorithmes gloutons. D’abord, créez un script de partie à deux équipes match_Greedy_GreedyEachTurn.ipynb pour faire s’affronter Greedy et GreedyEachTurn. Pour cela, inspirez-vous des scripts sample_game.ipynb et tutorial.ipynb dans le sous-répertoire pyrat_workspace/games.

game.add_player(player_1, team="Team Ratz", location=StartingLocation.RANDOM)
game.add_player(player_2, team="Team Pythonz", location=StartingLocation.RANDOM)

Ensuite, répondez aux questions suivantes :

• En moyenne sur 100 parties, quel joueur gagne ?
• Par combien de parties ?
• Optionnel – Est-ce significatif ? Pour cela, vous pouvez utiliser un test T à un échantillon pour vérifier que la liste des différences de scores a (ou non) une moyenne de 0.

Créez également un autre script de partie match_GreedyEachCheese_GreedyEachTurn.ipynb pour faire s’affronter GreedyEachCheese et GreedyEachTurn, et répondez aux questions suivantes :

• Est-il intéressant de lancer l’algorithme glouton à chaque tour comparé à à chaque morceau de fromage (du point de vue des résultats) ?
• Optionnel – S’il y a une amélioration, est-elle significative ?

Pour aller plus loin

2 — 2-opt

Il existe beaucoup d’autres algorithmes approximatifs que vous pouvez utiliser pour approximer la solution au TSP. On peut distinguer deux catégories :

• Solution unique – Une solution unique au problème du TSP est trouvée, puis éventuellement améliorée pour obtenir une meilleure solution. L’algorithme glouton appartient à cette catégorie.
• Solutions multiples – Plusieurs solutions sont trouvées et mélangées pour produire de meilleures solutions. Les algorithmes génétiques appartiennent à cette catégorie.

L’algorithme glouton construit une solution unique puis l’utilise. Il ne réalise aucune amélioration de cette solution, bien que certaines améliorations simples pourraient être faites.

Une heuristique simple pour améliorer le résultat glouton est le 2-opt. L’algorithme commencera à partir d’une solution particulière au TSP (soit aléatoire, soit construite avec un algorithme glouton), et l’améliorera progressivement en supprimant les routes croisées.

Vous pouvez essayer de coder cette heuristique en suivant les indications sur la page Wikipédia sur le 2-opt, ou d’autres ressources.

3 — Factoriser les codes

Si vous avez développé d’autres heuristiques, vous pouvez maintenant essayer de factoriser votre code, de sorte à avoir une classe abstraite GreedyHeuristic (dans le sous-répertoire utils), et des classes enfants qui codent les heuristiques. Enfin, créez un joueur GreedyPlayer.py qui exploite l’heuristique gloutonne que vous souhaitez.

Voici un petit diagramme UML qui représente une factorisation possible. Consultez la session 2 pour un guide sur la lecture.

4 — Une autre heuristique

Jusqu’à présent, votre heuristique favorisait le morceau de fromage le plus proche. Voici deux heuristiques possibles que vous pouvez implémenter :

• Meilleurs $k$ morceaux de fromage – Favoriser le morceau de fromage c tel que la série de $k$ morceaux de fromage commençant par c soit la plus courte. Pour cela, vous pouvez résoudre un TSP jusqu’à une profondeur $k$.

• Zones de forte densité – Favoriser les morceaux de fromage situés dans des zones où il y a beaucoup de fromage. Pour cela, vous devez calculer une mesure de densité pour chaque morceau de fromage.

5 — Réutiliser les parcours

Vous avez peut-être déjà remarqué que vous lancez plusieurs fois l’algorithme de Dijkstra pendant la partie. Parfois, vous utilisez même l’algorithme plusieurs fois depuis le même endroit. Cela peut arriver par exemple lorsque vous lancez l’algorithme depuis une position que vous avez déjà visitée plus tôt dans la partie, ou lorsque vous calculez une heuristique depuis un morceau de fromage.

Puisque c’est une opération coûteuse, il peut être judicieux de stocker les résultats dans un attribut pour éviter de recalculer les tables de routage si vous l’avez déjà fait. Une solution rapide est de créer un attribut et de vérifier d’abord son contenu avant de lancer le code coûteux. Voici un exemple de comment faire :

def __init__ (...):
    self.dijkstras = {}

def my_method (...):
    if source not in self.dijkstras:
        self.dijkstras[source] = ...
    make_some_computations(self.dijkstras[source])

Pour aller encore plus loin

6 — Recherche locale

La recherche locale est une méta-heuristique qui explore l’espace des solutions comme un parcours dans un graphe. L’idée est que nous allons créer un graphe de solutions dynamiquement, et l’explorer jusqu’à être bloqué dans un optimum local. Plus en détail, ce que vous pouvez faire pour implémenter une recherche locale est :

1. Partir d’une solution donnée $s$.
2. Identifier toutes les solutions voisines de $s$. Pour cela, vous devez définir une opération qui, appliquée à $s$, générera de nouvelles solutions. Par exemple, vous pourriez permuter deux sommets dans la solution. Cela générera une solution voisine pour chaque paire de sommets.
3. Évaluer les voisins, et votre nouveau $s$ devient la meilleure solution parmi les voisins.
4. Boucler jusqu’à ce qu’aucun voisin ne soit meilleur que $s$.

Essayez différentes stratégies pour générer les voisins. Vous pouvez aussi essayer différentes stratégies d’exploration des voisins, inspirées par des algorithmes tels que BFS ou DFS.

7 — Recuit simulé

Le recuit simulé est une méthode efficace pour approximer le TSP. Comme pour la recherche locale, vous avez besoin d’une méthode pour générer des voisins. Vous pouvez ensuite appliquer le recuit simulé comme suit :

1. Partir d’une solution initiale $s$.
2. Initialiser le recuit simulé :
   • Définir la température initiale $T$.
   • Choisir une stratégie de décroissance de la température, par exemple, décroissance exponentielle $T = T * \alpha$ où $\alpha$ est légèrement inférieur à 1 (ex. 0.99).
   • Fixer un critère d’arrêt, comme un nombre maximal d’itérations ou une température minimale.
3. Pour chaque itération :
   • Générer une nouvelle solution $s'$ en modifiant légèrement $s$.
   • Calculer la différence de qualité $\delta$ entre $s$ et $s'$.
   • Si $s'$ est meilleure, l’accepter.
   • Si $s'$ est pire, l’accepter avec une probabilité dépendant de la température actuelle et de la différence de coût. Cette probabilité est calculée comme $P = exp\left(-\frac{\delta}{T}\right)$.
   • Réduire la température selon la stratégie de décroissance.
4. S’arrêter lorsque la température est suffisamment basse ou après un nombre prédéfini d’itérations.