L’optimisation combinatoire /optimisation par essaims d’abeilles /Problème de l’arbre dominant /optimsation par essaims d’abeilles pour le problème d’arbre dominant /

Abstract

Le travail élaboré dans ce mémoire porte essentiellement sur le problème de l’arbre dominant DTP, qui permet la modélisation dans le domaine des réseaux de capteurs sans fil (WSN). L’objectif était d’appliquer l’algorithme d’optimisation par essaims pour résoudre le problème cité. Les trois premiers chapitres étaient consacrés aux études théoriques. Dans le premier chapitre, nous avons présentés des notions liées à l’optimisation combinatoire. Ensuite, nous avons introduit la notion des métaheuristiques en présentant des généralités sur ces derniers. Deux types de méthodes de résolution des problèmes NP-Difficile tel que le problème de l’arbre dominant DTP, ont été abordées dans ce chapitre : les méthodes exactes qui assurent l’optimalité de la solution mais pour des problèmes de petites instances (taille limitée), et les approches heuristiques et métaheuristiques qui fournissent des solutions appréciables en un temps raisonnable a des problèmes de n’importe quelle instance. Dans le chapitre 2 nous avons présenté en détails les étapes de l’algorithme d’optimisation par essaims d’abeilles pour l’optimisation des problèmes continus.Dans le chapitre 3, nous avons présenté quelques notions de bases sur les graphes. Ensuite, nous avons présenté le problème de l’arbre dominant et les problèmes connexes au problème DT. Ensuite, nous avons proposé notre approche de résolution du problème de l’arbre dominant DTP, cette approche était basée principalement sur l’algorithme BSO . Nous avons testé notre approche sur différents ensembles générés de manière aléatoire du problème de l’arbre dominant. Ces ensembles contiennent 33 instances de DTP, nous avons testé notre approche sur 32 instances (3 instances de 10 sommets et 15 arêtes, 3 instances de 15 sommets et 20 arêtes, 3 instances de 15 sommets et 30 arêtes, 3 instances de 20 sommets et 30 arêtes, 3 instances de 20 sommets et 50 arêtes, 3 instances de 100 sommets et 150 arêtes, 3 instances de 100 sommets et 200 arêtes, 3 instances de 200 sommets et 400 arêtes, 3 instances de 200 sommets et 600 arêtes, 2 instances de 300 sommets et 600 arêtes, 3 instances de 300 sommets et 1000 arêtes). Les résultats sont comparés avec les résultats optimaux pour les instances de petites tailles (10 et 20 sommets), pour les instances de grande taille (100, 200 et 300 sommets) nous avons comparés nos résultatsavec les meilleurs résultats trouvés dans la littérature. Les tests effectués sur ces instances ont montré que notre approche donne des résultats optimaux pour les instances de petite taille (10 et 20 sommets). Pour la plupart des instances de grande taille (100, 200 et 300 sommets), nous arrivons à des solutions plus performantes que celles des VNS et pour les instances qui restent nous arrivons à des solutions très proches. Les résultats obtenus dans l’expérimentation montrent l’efficacité de l’approche proposée.