Aide à la décision et méthode de Branch and Bound

Radio logicielle (software radio)

La radio logicielle permet, idéalement, à des équipements de communiquer avec n’importe quel standard de radiocommunications par la seule modification du logiciel embarqué, et donc sans modification d’un quelconque élément matériel. Cependant, le caractère statique des protocoles actuels de communication pose les questions de l’optimisation de l’efficacité spectrale et de la flexibilité du domaine radio. De cette réflexion, concernant directement la pérennité des télécommunications modernes, est né le domaine de la radio intelligente ou cognitive radio. Cette évolution, aujourd’hui incontournable dans le monde des radiocommunications, donne la possibilité aux appareils de communication, devenus plus autonomes, de choisir les meilleures conditions de communication [2].

La radio cognitive :

L’idée de la radio cognitive a été présentée officiellement par Joseph Mitola III à un séminaire à KTH, l’Institut royal de technologie, en 1998, publié plus tard dans un article de Mitola et Gerald Q. Maguire, Jr en 1999. Mitola combine son expérience de la radio logicielle ainsi que sa passion pour l’apprentissage automatique et l’intelligence artificielle pour mettre en place la technologie de la radio cognitive. D’après lui : « Une radio cognitive peut connaître, percevoir et apprendre de son environnement puis agir pour simplifier la vie de l’utilisateur. » [3]

Le principe de la radio cognitive, repris dans la norme IEEE 802.22, nécessite une gestion alternative du spectre qui est la suivante : un mobile dit secondaire pourra à tout moment accéder à des bandes de fréquence qu’il juge libre, c’est-à-dire, non occupées par l’utilisateur dit primaire possédant une licence sur cette bande. L’utilisateur secondaire devra les céder une fois le service terminé ou une fois qu’un utilisateur primaire aura montré des velléités de connexion. L’une des principales caractéristiques de la radio cognitive est la capacité d’adaptation où les paramètres de la radio (fréquence porteuse, puissance, modulation, bande passante) peuvent être modifiés en fonction de : l’environnement radio, la situation, les besoins de l’utilisateur, la coopération des utilisateurs, l’état du réseau, la géolocalisation,…etc.

Le problème du sac à dos multidimensionnel

La variante multidimensionnelle du problème du sac à dos est une issue de la classe des problèmes du sac à dos. Elle est notée par MKP (de l’anglais, Multidimensional Knapsack Problem). Le MKP est un problème d’optimisation combinatoire qui appartient à la classe des problèmes NP-Difficiles [5]. Dans ce problème, on suppose qu’on a un sac à dos avec M dimensions. Chaque dimension a une capacité maximale Cj (j=1,…, M). D’autre part, on a un ensemble d’objets. Chaque objet a une valeur (profit) pi (i=1,…, N) et un poids wji dans la dimension j du sac à dos. Le problème qu’on cherche à résoudre consiste à trouver un sous ensemble d’objets de manière à maximiser la valeur totale du sac à dos sans dépasser les capacités de toutes ses dimensions. Le MKP peut être formulé comme suit:

Le problème du Sac à Dos Multidimensionnel peut être utilisé pour formuler une panoplie de problèmes industriels tels que les problèmes de budgets, d’allocation des ressources physiques et logiques dans un système informatique distribué, de la découpe du stocke, de la gestion des projets et du stockage des conteneurs [6]. Vu son importance et son appartenance à la classe des problèmes NP-Difficiles, le problème du sac à dos multidimensionnel a sollicité l’attention de plusieurs communautés de chercheurs. En effet, sa résolution à fait l’objectif principal de plusieurs travaux proposés par plusieurs chercheurs. Comme notre problème consiste à gérer l’allocation du spectre dans le contexte de la radio cognitive entre les utilisateurs primaires et secondaires nous avons introduit cette notion de Sac à dos Multidimensionnel, en considérant que les Pus représentent le Sac avec une capacité qui est le paramètre suivant (nombre de canaux libres) à remplir par des objets qui sont les Sus ayant un poids et un profit (nombre de canaux demandés, Prix unitaire).

Les méthodes exactes

L’intérêt des méthodes exactes réside dans le fait quelles assurent l’obtention de la solution optimale du problème traité. En fait, elles permettent de parcourir la totalité de l’ensemble de l’espace de recherche de manière à assurer l’obtention de toutes les solutions ayant le potentiel d’être meilleures que la solution optimale trouvée au cours de la recherche. Cependant, les méthodes exactes sont très connues par le fait qu’elles nécessitent un coût de recherche souvent prohibitif en termes de ressources requises. En effet, le temps de recherche et/ou l’espace mémoire nécessaire pour l’obtention de la solution optimale par une méthode exacte sont souvent trop grands, notamment avec des problèmes de grandes tailles. De ce fait, la complexité de ce type d’algorithme croit exponentiellement avec la taille de l’instance à traiter, elle devient très importante face à des problèmes comprenant plusieurs variables, fonctions objectifs et/ou critères. Il existe de nombreuses algorithmes exacts y compris l’algorithme du simplexe, la programmation dynamique, l’algorithme A*, les algorithmes de séparation et évaluation (Branch and Bound, Branch and Cut, Branch and Price et Branch and Cut and Price), les algorithmes de retour arrière (Backtracking),

La méthode Branch and Bound (B&B)

La méthode par séparation et évaluation (nommée Branch and Bound en anglais) est notée B&B. C’est une des méthodes qui permettent la résolution exacte de problèmes d’optimisation, notamment les problèmes d’optimisation combinatoires dont on cherche à minimiser le coût de la recherche. B&B propose un mécanisme de recherche très intelligent, grâce à lequel elle permet une bonne exploitation de l’espace de recherche et l’aboutissement à la solution optimale plus rapidement que d’autres méthodes exactes en combinant deux principes primordiaux: la séparation et l’évaluation. Le principe de base de la méthode B&B se base sur la technique «Diviser pour régner ». Elle consiste à dissocier le problème en sous problèmes de manière à représenter le problème sous forme d’une arborescence, où chaque noeud correspond à une solution partielle. Les solutions partielles se forment de manière incrémentale en s’enfonçant dans l’arbre. Chacune des solutions partielles potentielles possède une borne supérieure et une autre inférieure. Ces dernières sont utilisées pour couper quelques branches de l’arbre et ainsi éviter d’explorer tout l’arbre. En fait, si l’évaluation partielle d’un noeud xi a montré que sa qualité est supérieure à la borne supérieure, le sous arbre en question sera élagué; sinon, le noeud sera divisé en sous noeuds. Ce processus se répète tant qu’il reste des branches non parcourues et la recherche continue jusqu’à trouver la solution optimale si elle existe.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Liste des abréviations
Liste des Illustrations
Introduction Générale
Chapitre I : La Radio Cognitive
I.1 Introduction
I.2 Radio logicielle (software radio)
I.3 La radio cognitive
I.3.1 Historique :
I.3.2 Définitions
I.3.3 Architecture de la RC
I.3.4 Cycle de cognition
I.3.5 Fonctions de la radio cognitive
I.3.6 Composantes de la radio cognitive
I.4 Les domaines d’application de la radio cognitive
I.5 Conclusion
Chapitre II : Aide à la décision et méthode de Branch and Bound
II.1 Introduction
II.2 Définition
II.3 Problématique d’aide à la décision
II.4 Le problème du sac à dos
II.5 L’optimisation combinatoire
II.6 La théorie de la complexité
II.7 Les différentes classes de complexité
II.7.1 La classe P
II.7.2 La classe NP
II.7.3 La classe NP-complets
II.7.4 La classe NP-difficiles
II.8 Les méthodes exactes
II.8.1 La méthode Branch and Bound (B&B)
II.9 Méthode heuristique
II.9.1 Définitions
II.9.2 Les algorithmes gloutons
II.10 CONCLUSION
Chapitre III : Implémentation et comparaison des résultats
III.1 Introduction
III.2 Un système multi-agents
III.3 Propriétés clés des Agents
III.4 Domaines d’application des agents
III.5 Topologie du réseau utilisé
III.6 Présentation du scenario
III.7 Présentation des algorithmes utilisés
III.8 Outils utilisés pour l’implémentation de l’application
III.8.1 JADE
III.8.2 JFreechart
III.9 Présentation de l’application
III.10 Résultats après simulation
III.10.1 interactions entre les SUs et les PUs
III.10.2 Résultats 01 après simulation
III.10.3 Résultats 02 après simulation
III.11 Conclusion :
Conclusion Générale et perspectives
Reference Bibliographique