Description

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

Ce projet a été réalisé dans un cadre pédagogique. A 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 : algorithme, heuristique, graphe
  • But : explorer diverses solutions algorithmiques pour résoudre un problème avancé à travers le problème de voyageur de commerce.
  • Apprentissages critiques :
    • AC 1  Analyser un problème avec méthode
    • AC 2 : Comparer des algorithmes pour des problèmes classiques
    • AC 3 : Expérimenter la notion de compilation et les représentations bas niveau des données
    • AC 4 : Formaliser et mettre en œuvre des outils mathématiques pour l’informatique 

Conditions de réalisation

  • Nombre d'étudiants : 3 (Morgane Viala, Félix Arnoux et moi-même)
  • Temps passé : 9h de formation et 12h de projet tutoré
  • Outils utilisés : Google Drive, Visual Studio 2019, GitHub, langage C#, framework créé par les professeurs 

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
  • R2.09 Méthodes numériques

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 TP de présentation du framework, du problème du voyageur de commerce, d’heuristiques
    et d’outils/notions qui vous seront utiles.
  • 2h de TP à mi-parcours pour faire un point sur votre avancement.

Résultat final

Pour ce projet, nous avons implémenté plusieurs heuristiques : heuristique de recherche locale, heuristique génétique, heuristique d'insertion au plus proche, heuristique d'insertion au plus loin, heuristique du plus proche voisin et tournée croissante.

Ces heuristiques ont ensuite été testés sur différents graphes que nous avons créés (dont graphe Eulérien, de Petersen, biparti, complet...)

Puis, nous avons comparé l'efficacité de ces heuristiques à travers le problème du voyageur de commerce.

Nous avons donc livré une documentation technique comprenant :

  • La présentation des heuristiques implémentées
  • Le choix des graphes de test
  • La comparaison d'efficacité sur chaque heuristique et chaque graphe.

Ainsi qu'un code source avec notre implémentation d'heuristique et des fichiers .gph contenant les graphes que nous avons utilisés.

Ajouter un commentaire Détails

Capture d'écran Plus proche voisin sur un Graphe Eulérien

Annotation: Analyser un problème avec méthode

Le problème de voyageur de commerce a été analysé avant tout pour savoir ce que l'on devrait mettre en place. J'ai donc appris à analyser un problème avec méthodes et à le découper en plusieurs éléments algorithmiques simples.

Annotation: Représentation bas niveau

J'ai dû compiler mon code pour pouvoir exécuter les différentes fonctions implémentées.

Annotation: Utiliser des outils maths.

Lors de cette SAé j'ai dû réfléchir à des graphes pertinents à mettre en place et les implémenter. J'ai donc appris à me servir d'outils mathématiques dans l'informatique.

Annotation: Comparer des algorithmes

Cette SAé m'a permis de mieux savoir comparer des algorithmes en termes de rapidité et d'efficacité. En effet, j'ai implémenté une heuristique qu'il a ensuite fallu comparer à d'autres heuristiques, le tout sur différents graphes et donc différentes situations.

Mis à jour le 15 juin 2022, 16:27