|
Contribution à l'optimisation complexe par des techniques de swarm intelligence( Télécharger le fichier original )par Lamia Benameur Université Mohamed V Agdal Rabat Maroc - Ingénieur spécialité : informatique et télécommunications 0000 |
2.3.2 Formulation du FS-FAPOn considère un système de n cellules représenté par n vecteurs X =x1, x2,. . . , xn. On suppose que les canaux disponibles sont numérotés de 1 à m. Une matrice de compatibilité de l'ordre m × m est utilisée pour représenter les différents types d'interférence. Soit R = r1, r2, . . . , rn un vecteur représentant la demande en fréquence pour chaque cellule. Chaque élément ri de R représente le nombre, minimal de canaux, qui doit être assigné à la cellule xi. Le problème FS-FAP est décrit par le triplet (X, R, C), oil X est le système cellulaire, R est le vecteur de demande et C la matrice de compatibilité. Supposons que N = 1, 2, ... ,m représente l'ensemble de canaux disponibles et Hi un sous ensemble de N assigné à la cellule xi. L'objectif principal de FS-FAP est d'identifier la meilleure affectation H = H1, H2, . . . , Hn satisfaisant les trois conditions suivantes :
Oil |Hi|désigne le nombre de canaux présents dans l'ensemble Hi. Par conséquent, la résolution de FS-FAP consiste à identifier la meilleure combinaison qui minimise le nombre total de violation de contraintes. De façon formelle nous avons l'équation (2.12) : Xn Min Xm Xn Xm oil : p(i, a)c(i, a, j, b)p(j, b) (2.12) { 0 si |a - b| = cij c(i, a, j, b) = (2.13) ( 1 si le canal a est assigné à la cellule p(i, a) = ,(2.14) 0 sinon c(i, a, j, b) est égal à 1 si l'assignation du canal a à la ième celule et le canal b à la jème cellule viole les contraintes de compatibilité électromagnétique. 2.3.3 Implémentation de l'algorithme d'optimisation par essaims particulaires à la résolution de FS-FAPLe FS-FAP [Benameur et al, 2010] opère uniquement sur des valeurs entières, la représentation d'une solution de FS-FAP se compose d'une séquence ordonnée de nombres entiers. De ce fait, il peut être considéré comme un problème de programmation discrète (Integer Programming IP) . Ce type de problèmes est souvent difficile à résoudre. Le but de cette étude consiste en l'application de l'algorithme d'optimisation discrète par essaims particulaires pour la résolution de FS-FAP. PSO a été à l'origine conçu pour traiter des problèmes dont l'espace de recherche est réel multidimensionnel. Pour pouvoir appliquer PSO à la résolution de FS-FAP, le modèle utilisé doit être adapté à ce type de représentation de solution ( c-à-d. la position d'une particule est maintenant une séquance ordonnée de nombres entiers). Le codage utilisé nécessite la redéfinition des éléments (position et vitesse) et des opérations (multiplication externe d'un coefficient par une vitesse, la somme de vitesses et la somme d'une vitesse et une position) des équations (1.1) et (1.2) du chapitre 1. En plus, il est nécessaire de déterminer comment la population initiale doit être choisie et de définir les critères d'arrêt les plus adéquats. - Position de la particule : Une position se compose d'une solution qui représente des affectations de fréquences. Chaque membre de l'essaim se compose de Dtot paramètres entiers, oil Dtot est le nombre total de fréquences demandées dans le système cellulaire. Par exemple, une position peut être une séquence (1, 6, 10, 2, 8, 3). - Vitesse de la particule : L' expression X2 - X1 oil X1 et X2 sont deux positions, représente la différence entre deux positions et la vitesse demandée pour aller de X1 à X2. Cette vitesse est une liste ordonnée de transformations (appelées mouvements) qui doivent être appliquées séquentiellement à la particule pour passer de sa position courante X1 en une autre X2. Un mouvement est une paire de valeurs a/j. Pour chaque position u dans la séquence X1, l'algorithme détermine si l'unité qui est en position u de la séquence X1 est la même unité qui est en position u de la séquence X2. Si les unités sont différentes, a est l'unité en position u de X2 et j est égal à la position u. Ainsi, ce mouvement dénote que pour aller de la séquence X1 à la séquence X2, l'unité en position j doit être échangée par l'unité a. Par exemple soient X1 = (A1, B1, C2, C1, B2, C4, A2, C3) et X2 = (A1, C1, B2, C2, A2, C4, B1, C3), donc la vitesse X2 - X1 est constituée par la liste de mouvement : {(C1/2), (B2/3), (C2/4), (A2/5), (B1/7)}
- Multiplication externe d'un coefficient par une vitesse : Les valeurs des coefficients des ô(t), u et u utilisés dans l'équation de la mise à jour du vecteur vitesse (équation (1.1) du chapitre 1) sont entre 0 et 1. Lorsqu'un coefficient est multiplié par une vitesse, il indique la probabilité de chaque mouvement à être appliquer. Par exemple, si on multiplie le coefficient 0.6 par la vitesse [(C1/2), (B2/3), (C2/4), (A2/5), (B1/7)], cinq nombres aléatoires entre 0 et 1 sont génerés pour la comparaison avec la valeur 0.6. Si le nombre aléatoire est inférieur à 0.6, le mouvement est appliqué. Par conséquent, si les valeurs des nombres aléatoires sont 0.8, 0.3, 0.7, 0.4 et 0.2, les mouvements (B2/3), (A2/5) et(B1/7) sont appliqués, tandis que les mouvements (C1/2) et (C2/4) ne sont pas appliqués. La vitesse résultante de la multiplication est donc [(B2/3), (A2/5), (B1/7)], qui, comme précédemment indiqué, représente une liste de mouvements qu'on va appliquer à un point. - Somme de vitesses : La somme de deux vitesses est simplement la concaténation de leur propre liste de mouvements. - Somme de vitesse et une position : La somme d'une vitesse et une position donne le résultat d'appliquer séquentiellement chaque mouvement de la vitesse à la position. - Population initiale : La population initiale est produite en plaçant une vitesse vide et une position aléatoire pour chaque particule. - Critère d'arrêt : L'algorithme s'arrête après avoir effectuer un nombre prédéfini d'itérations. |
|
