Description

Cette page va présenter les conditions de réalisation de la SAÉ 2.02, au cours du second semestre.

Ce projet a été réalisé dans un cadre pédagogique. À ce titre, il n'a pas vocation à être utilisé en dehors de ce cadre. Les différents éléments utilisés dans ce projet appartiennent à leurs propriétaires respectifs.

Présentation

  • Nom de la SAÉ : Exploration algorithmique d’un problème
  • Mots clés : Problème du voyageur, graphes, algorithmes, analyse
  • But : L’objectif de cette SAÉ est d’explorer diverses solutions algorithmiques pour résoudre un problème avancé.

Par groupes de 3, nous devions explorer différentes solutions possibles au problème du voyageur de commerce : un commerçant souhaite déposer des articles dans tous les magasins d'une carte donnée, nous devons donc chercher le plus court chemin sur un graphe partant d'un sommet de départ, passant par tous les sommets du graphe et revenant au point de départ.

La solution idéale serait de tester toutes les possibilités et de prendre la meilleure mais plus grand sera le graphe, plus longue sera cette démarche, ce pourquoi nous devons chercher une "Heuristique" : une solution adaptée à la résolution de ce problème.

 

Nous avons pu comparer 6 heuristiques durant cette SAÉ : Algorithme Croissant, Plus proche voisin, Insertion Proche, Insertion Au Plus Loin, Voisinage de Tournée et Algorithme Génétique.

Ressources mobilisées

Pour réaliser ce travail, j'ai dû mobiliser les enseignements des ressources suivantes :

  • R2.01 - Développement orienté objets
  • R2.02 - Développement d'applications avec IHM
  • R2.03 - Qualité de développement
  • R2.07 - Graphes

Contenu de la formation

Les heures de formation de cette SAÉ se sont reparties comme suit :

  • 1h de CM de présentation du sujet
  • 6h de TD de présentation de notions en termes de graphes.
  • 2h de TP de présentation du framework.
  • 2h de TP de mi-parcours
  • 16h de projet en autonomie

Résultat final

Notre objectif initial était de réaliser les heuristiques suivantes :

  • Algorithme Croissant, fait durant un cours à titre d'exemple
  • Plus Proche Voisin, réalisé par moi-même
  • Insertion Proche, réalisée par Matteo
  • Insertion Au Plus Loin, aussi gérée par Matteo étant donné qu'il s'agit de l'algorithme précédent à une égalité près.
  • Voisinage de Tournée, réalisée par Wassim.

L'algorithme génétique étant à faire en bonus, nous ne nous étions pas vraiment concentrés dessus pour commencer.

Nous avons donc pu réaliser l'ensemble de ces algorithmes, le mien était le plus simple et rapide à faire vu qu'il suffisait d'insérer en dernier indice un élément proche mais pour ce qui était de l'insertion, beaucoup de difficultés ont été rencontrées : on remarquait que rien ne se passait comme prévu et nous avons compris où était l'erreur après un certain temps (l'insertion en milieu de tournée qui se résumait à une ligne plutôt que ce que nous avions initialement fait).

Pour ce qui est du Voisinage de Tournée, très peu de difficultés ont été rencontrées, nous avons pu assez aisément la réaliser.

 

Ensuite, nous avons décidé pendant une bonne heure de "nettoyer" le code : les deux algorithmes d'insertion étant fondamentalement les mêmes à une ligne près, nous avons décidé de faire une classe globale rassemblant les méthodes utilisées qui serait héritée par les classes d'Insertion Proche, d'Insertion Au Plus Loin mais aussi de Voisinage de Tournée qui nécessitait une tournée dans un premier lieu.

 

Enfin, nous avions une marge de temps considérable avant le rendu du projet, nous avons donc décidé de commencer l'Algorithme Génétique : Matteo l'a en grande partie réalisé et j'ai surtout pu aider à le déboguer et à l'optimiser pendant plusieurs heures pour atteindre un résultat très optimisé.

 

Nous avons donc pu atteindre tous les objectifs que nous souhaitions réaliser en plus de réaliser un algorithme plus complexe et optimisé qui nous aura beaucoup appris en cours de route. Vous trouverez ci-contre le compte-rendu complet pour plus de détails.

Conditions de réalisation

  • Nombre d'étudiants : 3
  • Étudiants : Tristan DAL MOLIN, Matteo DE MARCO, Moulay-Wassim ALAOUI
  • Temps passé : 11h de formation et 16h de projet tutoré
  • Outils utilisés : Visual Studio 2022, Microsoft Word
Détails

Compte-Rendu du projet

Détails

Exemples du programme

Composantes essentielles

Composante Non prise en compte Prise en compte
a minima		 Bien prise en compte
En formalisant et modélisant des situations complexes      x
En recensant les algorithmes et les structures de données usuels      x
En s'appuyant sur des schémas de raisonnement      x
En justifiant les choix et validant les résultats      x

Annotation: Analyser un problème avec méthode

Durant ce projet, il était nécessaire de vraiment comprendre le problème du voyageur et comment les solutions données sont censées le résoudre, sans quoi il aurait été impossible de programmer les heuristiques.

 

Nous avons pu rencontrer différentes difficultés mais en analysant plus dans le détail les heuristiques qui posaient des problèmes, nous avons pu les surmonter.

Annotation: Utiliser des outils maths.

Afin de programmer les algorithmes, nous devions utiliser plusieurs outils mathématiques (modulo, génération aléatoire de tournées, comparaisons de longueurs de tournées,...) ce qui n'a pas posé problème, nous les maîtrisions plutôt bien au préalable.

Annotation: Comparer des algorithmes

Afin de résoudre ce problème du voyageur, nous devions comparer les différents algorithmes codés. Nous avons utilisé deux critères de comparaison : la durée d'exécution de l'algorithme et le résultat renvoyé par ce dernier.

Ainsi, selon les cas, on a pu trouver que le Plus Proche Voisin était l'algorithme le plus optimisé en durée et l'Algorithme Génétique en résultat, là où l'insertion était un juste milieu entre ces derniers. Un algorithme de Voisinage de Tournée n'ajoute que très peu de temps supplémentaire, pouvant donc la rendre utile pour optimiser le résultat d'un Plus Proche Voisin.

Mis à jour le 28 mai 2024, 10:47