Localisation optimale des concentrateurs d’un réseau coeur GSM

Formulation mathématique 

Cas où la position des MSC est supposée fixée : Le problème revient seulement à trouver les positions des sites d’installation des BSC. Le réseau comporte un MSC et n stations de base connectées à m contrôleurs de stations de base. Chaque station de base ne peut être connectée qu’à un BSC et le nombre de BTS connectées à un BSC est limité (limite imposée par le matériel) par MAX-BTS. Tous les BSC sont connectés à un seul MSC. Les emplacements des BTS et du MSC sont connus, le processus d’optimisation consiste à trouver le site optimal pour chaque BSC et à déterminer les BTS qui doivent lui être raccordées. On a plusieurs sites possibles d’implantation des BSC. Le but est donc de minimiser la somme des coûts d’implantation et la somme des coûts des liaisons. Ces liaisons comportent les liaisons entre les BTS et BSC et les liaisons entre les BSC et MSC. Soit donc : • Cij : le coût de raccordement du BTS i au site j. • Bj : le coût d’implantation d’un BSC sur le site j. • Mj : le coût de raccordement du MSC au site j.

Algorithme de résolution : Nous proposons dans cette section de donner une approche de résolution de la problématique de localisation des concentrateurs formulée dans 4.2 en utilisant les algorithmes génétiques en supposant que les positions des MSC ne sont pas fixées. 4.2.2.1 L’algorithme génétique Les algorithmes génétiques sont une abstraction de la théorie de l’évolution. Ils résolvent des problèmes n’ayant aucune méthode de résolution décrite précisément ou dont la solution exacte, si elle est connue, est trop complexe pour être calculée en un temps raisonnable. C’est notamment le cas quand des contraintes multiples, complexes doivent être satisfaites simultanément. Le but des AG est de déterminer les extrêmes d’une fonction f : X → R, où X est un ensemble quelconque appelé espace de recherche et f est appelée fonction d’adaptation ou fonction d’évaluation. Cette fonction agit comme une «boite noire» pour l’AG. Le premier pas dans l’implantation des algorithmes génétiques est de créer une population d’individus initiaux. En effet les algorithmes génétiques agissent sur une population d’individus, et non pas sur un individu isolé. Chaque individu de la population est codé par un chromosome. Une population est donc un ensemble de chromosomes. Chaque chromosome code un point de l’espace de recherche. L’efficacité de l’algorithme génétique va donc dépendre du choix du codage d’un chromosome. A chaque étape (appelée génération), ces chromosomes se combinent, mutent, et sont sélectionnés en fonction de leur qualité à répondre au problème