[PDF] Approches heuristiques pour lÕaffectation de cellules aux

Umts Les Rã Seaux Mobiles De Troisiã Me Gã Nã Ration By Harri

Umts Les Rã Seaux Mobiles De Troisiã Me Gã Nã Ration By Harri Holma Antti Toskala PDF Etude Et Conception D Algorithmes Pour Les Rseaux Smartphone Distributeur Informatique De Proximit En 22000 Gprs Edge Traduction Franaise Linguee Antennes Relais De Tlphonie Mobile Mobile Breitbandverbindung Linguee De Surface Approx Cm 694

Umts Les Rã Seaux Mobiles De Troisiã Me Gã Nã Ration By Harri

antennes gsm et gprs rs ponents un point sur les normes rseaux mobiles en france en galaxyprison co ttfone saturn tt900 t©l©phone portable d©bloqu surface approx cm 694 page 1 3 le secteur du transport publications fsr ac ma facult des sciences de rabat reseau d entreprise systme de noms de domaines fibre toute l actualit

Coopé ration dans lés Ré séaux d’Accé s 5G Multi Opé ratéurs

La cinquième génération de réseaux mobiles (5G) doit surmonter les nouveaux défis qui sont apparus avec la croissance explosive de la demande de trafic mobile En fait, le trafic mondial de données mobiles a augmenté de 69 en 2014, et il est prévu d'augmenter de près de dix fois entre 2014 et 2019 [1]

Umts Les Rã Seaux Mobiles De Troisiã Me Gã Nã Ration By Harri

Umts Les Rã Seaux Mobiles De Troisiã Me Gã Nã Ration By Harri Holma Antti Toskala reseau d entreprise systme de noms de domaines fibre un point sur les normes rseaux mobiles en france en galaxyprison co antennes relais de tlphonie mobile toute l actualit informatique du web 7 march 2013 nd

Coop eration dans les r eseaux d’acc es 5G multi-Op erateurs

l'opérateur Ainsi, les opérateurs de réseaux mobiles (ORM) cherchent à améliorer leurs réseaux afin d'élargir la couverture, augmenter la capacité, soutenir des débits plus élevés et améliorer la qualité de service d’une manière plus efficace concernant les coûts et la consommation d’énergie

Business opportunities through UMTS-WLAN networks

EN COOPI~RATION AVEC LES RI~SEAUX UMTS R6sum~ Cet article souligne l'attrait pour les opdrateurs mobiles que constitue la couverture des lieux publics fi forte

SAGEMCOM DEVOILE SES DERNIERES INNOVATION S DE SOLUTIONS

probl me de saturation des r seaux qui ne cesse de sÕintensifier avec les nouveaux usages des consommateurs Si la femtocell permet de soulager les r seaux mobiles, elle offre galement une meilleure couverture au domicile et apporte une solution aux zones non couvertes

Approches heuristiques pour lÕaffectation de cellules aux

dans les r”seaux mobiles Telecommunications / T”l”communications Le probl‘me de lÕaffectation des cellules aux commutateurs dans les r”seaux cellulaires consiste, ”tant donn” un ensemble de cellu-les et de commutateurs dont les emplacements sont connus, ‹ affecter les cellules aux commutateurs de fa“on ‹ minimiser une

AUTO-ORGANISATION DES RESEAUX SANS FIL MULTI-SAUTS A GRANDE

Les re´seaux sans fil multi-sauts sont des re´seaux radio mobiles sans aucune infrastruc- ture, ce qui leur permet une implantation rapide Ils peuvent aussi eˆtre couple´s a` un

PCM Assemblée Générale - UnIPEF

les mobiles Alors, je formule un simple souhait : que l'on sache mieux apprécier le système des grandes écoles, et que l'on s'attache à le conserver et à le développer, dans un esprit de saine compétition et de complémentarité avec l'université Pour cela, il faut que l'on accepte d'y appliquer les principes d'efficacité qui sont

[PDF] evaluation evolution des observatoires arcep de qualite de service

[PDF] La couverture mobile et la qualité de service mobile - Telecom

[PDF] La fibre optique - Arcep

[PDF] SERVICES FIXES HAUT ET TRES HAUT DEBIT (SUIVI DES - Arcep

[PDF] MANUEL D 'UTILISATION et TUTORIEL

[PDF] L 'ARCHITECTE-RÉFÉRENT EN SÉCURITE DES SYSTÈMES D

[PDF] Vers une architecture n-tiers

[PDF] Evolution des Réseaux Mobiles

[PDF] Les architectures 3-tiers Partie I : les applications WEB

[PDF] Cours - Architecture N-tier - Cedric/CNAM

[PDF] Architecture Applicative - Deptinfo

[PDF] Histoire de l 'architecture occidentale

[PDF] Modèle client-serveur et architectures techniques n - Réseau Certa

[PDF] les quatre concepts fondamentaux de l´architecture contemporaine

[PDF] Réalisation d 'un Intranet : Cohérence d 'un - Tel Archives ouvertes

IEEE Canadian Review - Spring / Printemps 20049

revient, ˆ partir de n cellules et de m commutateurs, ˆ trouver un schŽma dÕaffectation des n cellules aux m commutateurs qui minimise le cožt total du rŽseau tout en respectant certaines contraintes. Si nous devions explorer de faon exhaustive tous les schŽmas dÕaffectation possibles (m n dans notre cas) pour en choisir le meilleur, nous dŽbou- mme les ordinateurs les plus performants mettraient un temps excessi- vement long ˆ rŽsoudre. ConsidŽrons maintenant lÕaspect de la capacitŽ des commutateurs. Il sÕagit alors de rŽaliser les affectations en tenant compte du fait quÕun commutateur a une capacitŽ limitŽe, cÕest-ˆ-dire que seul un nombre limitŽ de cellules peut lui tre raccordŽ. Cette capacitŽ sÕexprime enT

1.0 Introduction

ypiquement, un rŽseau cellulaire est constituŽ dÕun ensem- ble de stations de base desservant les cellules et de plusieurs commutateurs connus sous le nom de Mobile Switching entre les usagers prŽsents ˆ lÕintŽrieur dÕune mme couverture gŽogra- phique se fait gr‰ce aux liaisons c‰blŽes ou micro-ondes entre les rŽseau tŽlŽphonique commutŽ public. Les commutateurs ont la possibi- litŽ de se transfŽrer la prise en charge dÕun usager passant dÕune cellule ˆ une autre. Lorsque celui-ci passe dÕune cellule ˆ une autre, une mise ˆ jour est effectuŽe au niveau des commutateurs concernŽs. Cette opŽra- car les mises ˆ jour ˆ effectuer sont peu nombreuses. En revanche, si de ressources dans ce cas. LorsquÕun usager est en mouvement dans une cellule, le signal analogi- que Žmis est aussit™t pris en charge par la cellule la plus proche. Il existe un seuil de sensibilitŽ (ou seuil de filtrage) au-delˆ duquel le signal Žmis par lÕusager est suffisamment puissant pour tre pris en compte par la cellule. commutateur 1, alors que les cellules C et D dŽpendent du commuta- teur 2. Un utilisateur prŽsent en C pourrait Žmettre un signal suffisamment puissant pour tre peru simultanŽment par les cellules B faudrait se procurer un rŽseau de signalisation capable de juger quelle cellule reoit le signal avec le plus de clartŽ et de dŽterminer ainsi le commutateur qui sera responsable de la communication. Dans le cas o lÕusager quitte la cellule C et se retrouve dans la cellule D, on est en prŽ- de cette opŽration. En revanche, si lÕusager passe de la cellule C ˆ la cel- lÕinformation relative ˆ lÕusager et une mise ˆ jour de la base de don- LÕaffectation des cellules aux commutateurs consiste essentiellement ˆ trouver la configuration des liaisons commutateur-cellule qui minimise le cožt total du rŽseau, en tenant compte dÕun certain nombre de con- chaque commutateur. Parmi les facteurs qui doivent tre pris en compte, on trouve la configuration du rŽseau, la capacitŽ des commutateurs et le trafic acheminŽ par lÕintermŽdiaire du rŽseau.

MontrŽal, Montreal, QC.

Approches heuristiques pour lÕaffectation de cellules aux commutateurs dans les rŽseaux mobiles

Telecommunications / TŽlŽcommunications

les rŽseaux cellulaires consiste, Žtant donnŽ un ensemble de cellu- les et de commutateurs dont les emplacements sont connus, ˆ affecter les cellules aux commutateurs de faon ˆ minimiser une fonction de cožt qui comprend une composante de cožt de liaison affectation doit tenir compte de la contrainte de capacitŽ des com- mutateurs qui ne peuvent supporter quÕun nombre limitŽ dÕappels. cile, ce qui justifie le recours ˆ des mŽthodes heuristiques de rŽsolution pour conjurer le risque dÕexplosion combinatoire. Cet article examine lÕefficacitŽ de diffŽrentes interactions entre trois mŽta-heuristiques bien connus jusquÕici utilisŽs isolŽment pour recuit simulŽ et lÕalgorithme de recherche taboue. Les rŽsultats obtenus de ces interactions montrent que les algorithmes de recuit simulŽ et de recherche taboue permettent dÕamŽliorer les rŽsultats

obtenus par lÕalgorithme gŽnŽtique.For a set of cells and switches, the problem of cell assignment to

switches in cellular mobile networks consists of determining a cell assignment pattern, which minimizes a certain cost function, while respecting certain constraints, especially those related to limited switchÕs capacity. The cost function integrates a link and a han- doff cost component. Assigning cells to switches in cellular mobile networks being an NP-hard problem, enumerative search methods are practically inappropriate to solve large-sized instances of this problem. This paper presents the interaction between tabu search, simulated annealing and standard genetic algorithm to solve this problem. The implementation of these algorithms has been subject to extensive tests in order to measure the quality of solutions. The results obtained show that the simulated annealing and tabu search improve the individuals representing solutions provided by stan- dard genetic algorithm.Sommaire

Abstractcellule Acellule C

cellule D cellule B

Commutateur 1

Commutateur 2

10IEEE Canadian Review - Spring / Printemps 2004

volumes dÕappels par unitŽ de temps. ConsidŽrons enfin lÕaspect du trafic acheminŽ par lÕintermŽdiaire du rŽseau. Ce trafic peut varier considŽrablement ˆ deux moments de la journŽe. Ainsi, un schŽma dÕaffectation efficace ˆ un moment de la jour- nŽe peut sÕavŽrer inefficace ˆ un autre moment. Il sÕagit donc dÕimplanter deux affectations correspondant chacune ˆ un moment de la journŽe. Il peut alors arriver quÕune cellule soit reliŽe ˆ deux commuta- teurs diffŽrents, et cela doit tre pris en compte dans le calcul du cožt global du rŽseau. que de rŽsolution, ce que certains chercheurs ont dŽjˆ prŽconisŽ [4] [5]. Cet article examine lÕefficacitŽ de diffŽrentes interactions entre ces trois ment de ces heuristiques. La section 3 dŽfinit les interactions entre lÕalgorithme gŽnŽtique, le recuit simulŽ et la recherche taboue. La sec- tion 4 prŽsente et analyse les rŽsultats de simulation. La section 5, en guise de conclusion, rŽsume nos principales observations. ques utilisŽes: lÕalgorithme gŽnŽtique, la recherche taboue et le recuit simulŽ.

2.1 LÕalgorithme gŽnŽtique

Les algorithmes gŽnŽtiques (AG) introduits par John Holland [2] sont AG, les spŽcimens se reproduiront aussi; en particulier, ceux jugŽs les plus forts se reproduiront ˆ un rythme plus rapide. Des opŽrateurs gŽnŽ- tiques seront appliquŽs sur des candidats en espŽrant engendrer ainsi de nouveaux candidats plus performants [6] [7]. grande part de hasard. En effet, les candidats ˆ la reproduction sont choisis de faon probabiliste. Les chromosomes de la population sont some sont mutŽs selon une certaine probabilitŽ. En appliquant ainsi de gŽnŽration en gŽnŽration les opŽrateurs gŽnŽtiques sur des candidats jugŽs performants, on cherche ˆ obtenir une progŽniture plus perfor- mante que celle de la gŽnŽration prŽcŽdente, ce qui permet de sÕapprocher ainsi dÕune solution optimale.

2.1.1 Principe des algorithmes gŽnŽtiques

Les mŽcanismes de base usuels sur lesquels repose la mŽthode des algo- rithmes gŽnŽtiques sont principalement la reprŽsentation des tres de ces chromosomes assure la convergence vers une bonne solution. Dans un AG, les chromosomes ont souvent une reprŽsentation binaire. solutions sont transposables en binaire [6]. Les chromosomes sont alors reprŽsentŽs par une cha"ne de bits. Cette reprŽsentation est indŽpen- robuste. Les opŽrateurs gŽnŽtiques de base sont au nombre de trois: la sŽlection, le croisement et la mutation. La sŽlection est le processus selon lequel des cha"nes de la population sont choisies pour une nouvelle gŽnŽration objectif est ŽlevŽe, plus cette cha"ne a de chances dՐtre sŽlectionnŽe. Notons quÕune des techniques les plus utilisŽes pour rŽaliser la sŽlection est celle de la roulette de casino: dÕabord, on calcule la valeur dÕapti- tude de chaque chromosome, puis on calcule lÕaptitude totale en faisant la somme des valeurs dÕaptitude de chaque individu de la population; enfin, on calcule le pourcentage de chaque chromosome par rapport ˆ lÕaptitude totale. Le croisement est le processus selon lequel les bits de deux cha"nes

sŽlectionnŽes au hasard sont interchangŽs: dans le langage gŽnŽtique, ondira que ces cha"nes sont croisŽes. Chaque paire de longueur t subit le

ment entre 1 et (t-1). Deux nouvelles cha"nes sont crŽŽes en Žchangeant Les nouvelles cha"nes peuvent donc tre totalement diffŽrentes de leurs parents. Le croisement dŽcrit se produit en un lieu, mais on peut aussi retrouver des croisements avec plusieurs lieux dans certains AG. hasard dans un chromosome est rŽgŽnŽrŽe. Ce processus ne survient quÕoccasionnellement dans un algorithme gŽnŽtique. En modifiant alŽa- toirement la valeur dÕun bit dans une cha"ne, la mutation est utile pour ramener du matŽriel gŽnŽtique qui aurait ŽtŽ oubliŽ par les opŽrateurs de sŽlection et de croisement. De faon gŽnŽrale, un AG fonctionne de la faon suivante: permet de dŽduire sa valeur dÕaptitude. que nouvelle population remplaant la prŽcŽdente. Le nombre x de gŽnŽrations est dŽterminŽ au dŽpart. Dans chaque gŽnŽra- tion, on choisit n chromosomes auxquels on va appliquer les n nouveaux chromosomes crŽŽs remplacent la gŽnŽration prŽcŽdente. gŽnŽration, les chromosomes auront ŽvoluŽ de telle faon ceux des gŽnŽrations prŽcŽdentes.

2.1.2 LÕalgorithme gŽnŽtique dÕaffectation de cellules

dÕaffectation de cellules aux commutateurs vise ˆ trouver, ˆ partir dÕune population initiale de chromosomes, la meilleure affectation, cÕest-ˆ- dire celle qui minimise le cožt du rŽseau tout en respectant la contrainte sur la capacitŽ des commutateurs et celle dÕaffectation unique des cellu- les aux commutateurs. Dans un premier temps, il faut coder les forme la plus rŽpandue du codage est la reprŽsentation binaire o les un schŽma dÕaffectation spŽcifique. Les ŽlŽments de la cha"ne reprŽsen- tant un chromosome sont des entiers, qui reprŽsentent les diffŽrents commutateurs numŽrotŽs de 1 ˆ m. La Figure 2 donne un exemple dÕun chromosome reprŽsentant un schŽma dÕaffectation de 8 cellules ˆ trois commutateurs. La longueur des cha"nes est Žgale au nombre de cellules et reste inchan- gŽe, car toutes les cellules du rŽseau doivent tre affectŽes. De mme, la maximal de commutateurs du rŽseau. La lecture des chromosomes se fait de gauche ˆ droite; ainsi, le premier bit du chromosome contient le numŽro du commutateur auquel la cellule numŽro 1 est reliŽe. Le codage adoptŽ permet de satisfaire une contrainte: celle de lÕaffectation peut pas prendre simultanŽment plus dÕune valeur. La seule contrainte ˆ satisfaire reste alors celle sur la capacitŽ des commutateurs.

1223 1 323

Figure 2: ReprŽsentation non-binaire dÕun chromosome

IEEE Canadian Review - Spring / Printemps 200411

2.2 LÕalgorithme de recuit simulŽ

La mŽthode du recuit simulŽ (RS) a lÕoriginalitŽ de pouvoir sÕappliquer ˆ une grande variŽtŽ de domaines et en particulier aux tŽlŽcommunica- tions. Le recuit simulŽ est une heuristique dÕoptimisation qui consiste en une recherche locale par perturbations. Ce processus donne la possibi- litŽ de sՎloigner occasionnellement dÕun minimum local pour permettre ainsi un Žlargissement du champ de recherche de la solution idŽale [3].

2.2.1 Principe de la mŽthode

Le recuit simulŽ est une procŽdure de recherche selon laquelle la topolo- gie courante, retenue momentanŽment comme meilleure solution, est ches. Ces topologies voisines sont obtenues ˆ la suite de petites perturbations sur la topologie courante. LorsquÕune perturbation aboutit ˆ une topologie meilleure que la solution courante, elle est sauvegardŽe comme solution courante. Cependant, il peut arriver que, suite ˆ une perturbation, la topologie voisine obtenue soit conservŽe comme solu- tion courante, mme si elle nÕest pas meilleure que la solution courante, ˆ condition quÕelle respecte une certaine probabilitŽ dÕacceptation. Le fait dÕaccepter de temps ˆ autre une solution dŽgradŽe permet dՎviter de sÕenfermer trop t™t dans un minimum local. DÕautre part, la probabi- litŽ dÕacceptation doit tre suffisamment faible, de telle sorte que lÕalgorithme puisse sÕapprocher le plus possible de lÕoptimum global. satisfait. Ë cette Žtape, la recherche locale devrait avoir abouti ˆ un minimum local ou ˆ un optimum global. Il sÕensuit que la solution idŽale trouvŽe est, soit localement optimale vu le nombre ŽlevŽ de minima locaux, soit globalement optimale dans le meilleur des cas.

2.2.2 Affectation de cellules aux commutateurs avec lÕalgorithme de

recuit simulŽ tempŽrature q, et le facteur de recuit a. Cet algorithme commence par gŽnŽrer une topologie initiale, chaque cellule Žtant affectŽe ˆ un com- mutateur de faon alŽatoire, sans se soucier des contraintes de capacitŽ 0 relative- ment ŽlevŽe. On dŽbute alors la boucle des perturbations. Cette boucle dÕun maximum de rŽpŽtitions de la boucle. En outre, la valeur du fac- teur de recuit a doit tre choisie adŽquatement pour Žviter de dŽcrŽmenter q trop rapidement, ce qui rendrait moins poussŽe la recher- che de la meilleure solution.

2.3 LÕalgorithme de recherche taboue

La mŽthode de recherche taboue (RT) est une technique adaptative introduite dans les annŽes 70 en optimisation combinatoire pour rŽsou- heuristique, qui peut tre utilisŽe pour rŽsoudre diffŽrents types de pro-

2.3.1 Fondements de la mŽthode de recherche taboue

PrŽsentons dans un premier temps lÕalgorithme de descente simple. Il part dÕun N(s) de la solution courantes. Ensuite, il choisit dans cet ensemble V la meilleure solution, cÕest-ˆ-dire celle qui minimise la fonction objectif rithme continue jusquÕau moment o aucun ŽlŽment de V ne permet dÕavoir une meilleure valeur de la fonction objectif. La mŽthode de recherche taboue est une amŽlioration de lÕalgorithme minima locaux. Pour cela, il est nŽcessaire dÕac cepter de temps en temps des solutions qui nÕamŽliorent pas la fonction objectif, en espŽrant ainsi parvenir plus tard ˆ de meilleures solutions. Cependant, le fait de vou-

loir accepter des solutions non forcŽment meilleures introduit un risquede cycle, cÕest-ˆ-dire un retour vers des solutions dŽjˆ explorŽes. DÕo

lÕidŽe de conserver une liste taboue T (tabu list) des solutions dŽjˆ visi- tŽes. Ainsi, lors de la gŽnŽration de lÕensemble V des solutions voisines Notons tout de mme que, dÕune part, le stockage de toutes les solutions dŽjˆ visitŽes peut nŽcessiter beaucoup de mŽmoire et que, dÕautre part, il peut sÕavŽrer utile de revenir ˆ une solution dŽjˆ visitŽe pour continuer la recherche dans une autre solution. Un compromis a ŽtŽ adoptŽ en ne sÕarrte quand aucune amŽlioration nÕest intervenue depuis un certain nombre dÕitŽrations ou si toutes les solutions voisines candidates sont taboues.

2.3.2 Affectation de cellules aux commutateurs avec la recherche

taboue La dŽmarche adoptŽe consiste globalement ˆ modifier itŽrativement une solution initiale en espŽrant aboutir ˆ une solution finale respectant les vements pour passer dÕune solution ˆ une autre ˆ lÕintŽrieur dÕun espace de recherche prŽdŽfini. Dans lÕadaptation de la mŽthode RT, lÕespace de recherche choisi est libre des contraintes de capacitŽ sur les commuta- teurs, mais respecte la contrainte dÕaffectation u nique des cellules aux commutateurs. La faisabilitŽ de la solution finale nÕest donc pas garan- tie, mais le fait de pouvoir examiner un plus grand nombre de possibilitŽs augmente les chances dÕaboutir ˆ de bonnes solutions. RT est une Žvaluation de la solution prenant en compte le cožt et une sanc- tion, sous forme de pŽnalitŽ, pour le non-respect des contraintes de capacitŽ, sÕil y a lieu. Ë chaque Žtape, RT choisit la solution ayant la meilleure Žvaluation. Contrairement ˆ la mŽthode de descente, quand elle arrive ˆ un opti- mum local, la mŽthode RT choisit la solution voisine qui dŽgrade le moins la fonction objectif. Pour Žviter les cycles autour de cet opti- momentanŽment un retour vers ces solutions. Les solutions sont libŽ-

3.0 Interactions entre les heuristiques

Cette section expose les interactions des heuristiques que nous propo- commutateurs dans les rŽseaux cellulaires.

3.1 Interaction entre lÕalgorithme gŽnŽtique et le recuit simulŽ

LÕinconvŽnient principal de lÕalgorithme de recuit simulŽ (RS) est quÕil est appliquŽ ˆ une topologie gŽnŽrŽe de faon totalement alŽatoire. une solution qui ne respecte pas les contraintes de capacitŽ. Il serait donc prŽfŽrable dÕappliquer lÕalgorithme de recuit simulŽ ˆ une solu- tion que lÕon sait faisable et, dans le meilleur des cas, de faible cožt. Nous voulons optimiser lÕalgorithme gŽnŽtique en amŽliorant ˆ chaque gŽnŽration le meilleur chromosome de la population. Pour cela, ˆ cha- que gŽnŽration, nous prŽlevons le meilleur chromosome de la population, nous lui appliquons lÕalgorithme de recuit simulŽ et nous obtenons une solution qui sera au moins aussi bonne que la prŽcŽdente, puisque lÕalgorithme de recuit simulŽ ne peut produire quÕune solution de cožt infŽrieur ou Žgal ˆ celui de la topologie de dŽpart. Nous obte- nons ainsi un nouveau chromosome que nous insŽrons dans la population de lÕalgorithme gŽnŽtique, ˆ la place du chromosome de cožt maximal, cÕest-ˆ-dire le moins bon chromosome de la population. LÕalgorithme gŽnŽral de cette version est prŽsentŽ ˆ la Figure 3.

3.2 Interaction entre lÕalgorithme gŽnŽtique et la recherche taboue

Dans le cas de la recherche taboue, la solution de dŽpart est crŽŽe en attribuant chaque cellule au commutateur le plus proche, en terme de

12IEEE Canadian Review - Spring / Printemps 2004

Figure 3: Interaction entre lÕalgorithme gŽnŽtique et le recuit simulŽFigure 4: Interaction entre lÕalgorithme gŽnŽtique et larecherche taboue distance. Ë chaque test, cÕest donc la mme solution de dŽpart qui est fournie et la recherche taboue aboutira toujours ˆ la mme topologie finale. Donc, avec un mme fichier de donnŽes initial, on ne pourra aboutir quÕˆ une seule solution finale. LÕidŽe est donc de gŽnŽrer la solution initiale ˆ lÕaide de lÕalgorithme gŽnŽtique. Nous aurons ainsi ˆ notre disposition une variŽtŽ de solu- tions de dŽpart et on peut espŽrer que lÕalgorithme de recherche taboue permettra dÕatteindr e dÕautres minima locaux, voire le minimum global. Donc, lÕidŽe est dÕappliquer la recherche taboue ˆ chaque gŽnŽration de lÕalgorithme gŽnŽtique. LÕalgorithme gŽnŽral est prŽsentŽ ˆ la Figure 4. Nous voulons optimiser lÕalgorithme en amŽliorant ˆ chaque gŽnŽra- tion le meilleur chromosome de la population. Pour cela, ˆ chaque applique lÕalgorithme de recherche taboue et on obtient une solution qui sera au moins aussi bonne que la prŽcŽdente, puisque lÕalgorithme de recherche taboue ne peut produire quÕune solution de cožt infŽrieur ou Žgal ˆ celui de la topologie de dŽpart. Nous obtenons ainsi un nouveau chromosome que nous insŽrons dans la population de lÕalgorithme gŽnŽtique, ˆ la place du chromosome de cožt maximal, cÕest-ˆ-dire le moins bon chromosome de la population. recherche taboue, le processus gŽnŽtique se fait ˆ chaque gŽnŽration de lÕalgorithme gŽnŽtique. Une fois le processus gŽnŽtique accompli, on sÕintŽresse au meilleur chromosome de la population courante. Si ce chromosome constitue une topologie qui a dŽjˆ ŽtŽ sŽlectionnŽe pour tre solution initiale de la recherche taboue, on dŽplace notre choix sur le chromosome suivant, dans la population triŽe en ordre croissant des cožts des chromosomes, et ainsi de suite jusquÕˆ trouver le meilleur chromosome de la population qui nÕa jamais ŽtŽ choisi pour tre topolo- gie initiale de la recherche taboue.

4.0 ImplŽmentation et rŽsultats

Nous prŽsentons dans cette section les rŽsultats obtenus des interac- tions entre les algorithmes prŽsentŽes prŽcŽdemment.

4.1 Algorithmes seuls

Dans un premier temps, on effectue une simulation sur chacun des algo- rithmes pris sŽparŽment afin dÕavo ir des solutions de rŽfŽrence. Les tests ont ŽtŽ effectuŽs sur un ensemble de 900 topologies avec 3 rŽseaux dif-

fŽrents: 100 cellules et 5 commutateurs, 150 cellules et 6 commutateurs,et 200 cellules et 7 commutateurs. Pour chacun des algorithmes, nous

avons effectuŽ 20 tests pour chaque topologie diffŽrents et les valeurs prŽsentŽes correspondent ˆ une moyenne des 20 valeurs obtenues. Afin de dŽterminer le nombre de gŽnŽrations qui permet dÕobtenir le meilleur compromis cožt obtenu/temps nŽcessaire, nous avons effectuŽ des tests avec plusieurs nombres de gŽnŽrations. Les probabilitŽs de croisement et de mutation ont ŽtŽ fixŽes respectivement ˆ 0.9 et 0.08. La Figure 5 prŽsente lՎvolution du cožt du meilleur chromosome de la population en fonction du nombre de gŽnŽrations de lÕalgorithme gŽnŽ- tique pour un rŽseau de 100 cellules et 5 commutateurs. Cela illustre le fait que le nombre de 500 gŽnŽrations permet dÕaboutir ˆ de bons rŽsultats, en un temps acceptable. Avec 800 gŽnŽrations, on obtient des rŽsultats un peu meilleurs, mais le temps nŽcessaire est plus ŽlevŽ. Avec seulement 100 gŽnŽrations, les cožts de topologies obtenus sont ŽlevŽs; le seul point positif est le temps dÕexŽ cution qui est faible. Avec 500 gŽnŽrations, le compromis atteint est bon; on atteint des cožts comparables ˆ ceux atteints avec 800 gŽnŽrations, en un temps accepta- ble. Nous avons choisi donc dÕeffectuer les tests de rŽfŽrence avec un nombre de rŽfŽrences Žgal ˆ 500. Afin dÕavoir en notre possession des valeurs de rŽfŽrence, nous effectuons des tests avec chacun des trois algorithmes pris sŽparŽment. Les rŽsultats sont prŽsentŽs ˆ la Figure 6. Dans chacun des cas, la solution initiale est spŽcifique ˆ lÕalgorithme:

0500100015002000250030003500

1 44
87
130
173
216
259
302
345
388
431
474
517
560
603
646
689
732

775Cožt de la topologie

100 gŽnŽrations

500 gŽnŽrations

800 gŽnŽrations

Processus gŽnŽtique sur la

gŽnŽration courante

Le meilleur chromosome

a-t-il dŽjˆ ŽtŽ sŽlectionnŽ ?

Recherche du meilleur chromosome qui nÕa pas

quotesdbs_dbs7.pdfusesText_13