Stratégie de migration d'agents mobiles pour les applications du réseau de transport

31/08/2017
Publication REE REE 2006-5
OAI : oai:www.see.asso.fr:1301:2006-5:19718
DOI : You do not have permission to access embedded form.

Résumé

Stratégie de migration d'agents mobiles  pour les applications du réseau de transport

Métriques

14
4
3.29 Mo
 application/pdf
bitcache://2002bf0266a1459842c50fb5296597d6eacaf701

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2006-5/19718</identifier><creators><creator><creatorName>Hayfa Zgaya</creatorName></creator><creator><creatorName>Slim Hammadi</creatorName></creator></creators><titles>
            <title>Stratégie de migration d'agents mobiles  pour les applications du réseau de transport</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Thu 31 Aug 2017</date>
	    <date dateType="Updated">Thu 31 Aug 2017</date>
            <date dateType="Submitted">Sat 17 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2002bf0266a1459842c50fb5296597d6eacaf701</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33492</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

. Dossier) MÉTHODOEOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS Stratégie de migration d'agents mobiles m pour les applications du réseau de transport Hayfa ZGAYA, Slim HAMMADI LAGIS UMR 8146,-Ecole Centrale de Lille Mots clés Agentsmobiles, Algorithmes évolutionnistes, Systèmed'information multimodal, Réseaumultimodal 1. Introduction Un client du réseau de transport sollicite la disponibi- lité d'une information multimodale pertinente et interac- tive en temps réel au cours de son voyage. Un Système d'Information Multimodal (SIM) peut lui offrir un sup- port pour le guider et l'aider à prendre les bonnes déci- sions, avant et pendant son déplacement. Les données nécessaires pour aboutir à une telle assistance sont répar- ties sur différents noeuds d'un Réseau de Transport Multimodal (RTM). Ces noeuds représentent les diffé- rents exploitants du transport multimodal qui jouent le rôle de fournisseurs d'information. Dans un travail antérieur [1], nous avons proposé un SIM qui se base sur un type particulier d'agent logiciel : les Agents Mobiles (AMs). Un AM [2] est un programme composé de code, de données et d'un état d'exécution, pouvant se déplacer d'un noeud à un autre sur un réseau pour accomplir un certain nombre de tâches et enfin reve- nir à son noeud originaire appelé Hôte [4] [5] [6]. La tech- nologie des AMs peut réduire considérablement le trafic réseau [3] comme tel est le cas dans le domaine de l'ex- traction des données qui peut nécessiter l'accès à des sources de données volumineuses et géographiquement séparées [7]. En effet, au lieu de transférer les données à travers le réseau, un AM migre vers les sources d'infor- mation concernées. L'agent exécute alors son code sur les noeuds qu'il visite, utilisant leurs ressources et regagne en fin de parcours le noeud Hôte pour retourner un résultat. Dans cet article, nous présentons une stratégie de migration des AMs afin d'atteindre la satisfaction des utilisateurs en termes de coût et de temps de réponse. Nous proposons donc une solution d'optimisation qui opère sur deux étapes. La première vise à déterminer un ensemble d'AMs pour explorer l'ensemble des noeuds du RTM. Les plans de travail de ces agents sont alors provi- soires mais préconstruits pour une déduction rapide des parcours définitifs. Lorsqu'un ensemble de requêtes clients attend des réponses au même instant t, le SIM identifie instantané- ment les noeuds du RTM susceptibles de répondre aux services demandés. Grâce à une méthode évolutionniste, la deuxième étape doit discerner les sites qui vont répon- dre aux demandes des clients, à partir de l'ensemble des noeuds préalablement identifiés par le SIM. Le choix de ces sites se base sur le coût total des services demandés bESSENTIELM SYNOPSIS Cet article présente une stratégie de migration d'agents mobiles (AMs) pour satisfaire les requêtes clients des réseaux de trans- port, à travers un système d'information multimodal. Nous propo- sons pour ce problème une solution d'optimisation qui opère sur deux étapes. La premièrevise à déterminer un ensemble dAMs en construisant leurs plans initiaux de travail. A cette étape, les plansdoiventincorporertous les noeudsdu réseaumultimodalafin de l'explorer totalement. Grâceà une méthode évolutionniste, la deuxième étape doit optimiser le choix des noeudsfournisseurs d'information dansle but d'augmenter le nombre de clients satis- faits. Enfin,unemiseàjour des plansde travaildesAMs est indis- pensableaprès l'affectationdes serveurs d'information aux servi- ces demandés. Les plansde travaildéfinitifs sont donc déduits à partir des affectationsréalisées.Lastratégie adoptée réduit effec- tivement le temps de calculcar les plansde travailinitiaux ne sont recalculésque si le trafic réseauvarieconsidérablement. This paper presents a migration strategy of mobile agents (MAs) in order to satisfy transport networks users'requests, through a multimodal informationsystem. Forthis problematic,we propose an optimisation solution which operates on two stages.The first step of our proposedsolution aims to look for a set of MAs, buil- dingtheir initialWorkplans.Theseones must incorporateail nodes of the multimodalnetwork, in orderto explore it entirely.Thanksto an evolutionary method, the second step has to optimize the choiceof nodes,which representinformation providers,in orderto increasethe numberof satisfied users. Finally, Workplansof MAs has to be updatedafter the assignment of nodesto requiredser- vices. Consecutively,final Workplans are deduced from realised assignments. Adopted strategy decreases significantly time consuming becauseinitial Workplansare recomputed only if net- work traffic variousconsiderably REE NO 5 Mai2006 ainsi que sur le temps nécessaire pour répondre à l'en- semble des requêtes simultanées. Un client est satisfait s'il est servi dans les délais avec un coût raisonnable. L'article est organisé en six paragraphes. Après avoir présenté le problème dans la partie qui suit, nous détaille- rons la solution proposée à travers les paragraphes 4 et 5 qui représenteront respectivement la première et la deuxième étape de la démarche adoptée. Cette dernière sera préalablement abordée dans le paragraphe 3. Enfin, nous terminons l'article par une conclusion générale. 2. Description du problème Le déploiement de nouvelles applications distribuées repose de plus en plus sur les réseaux à grande échelle tel Internet. L'ampleur de tels réseaux justifie l'hétérogénéité des sources d'information existantes et l'intensité et la diversité des tâches informatiques exécutées (navigation, requêtes,stockage, mise à jour, etc.). Ces tâches peuventreque être lancées d'une manière simultanée et peuvent néces- siter l'accès à plusieurs sources d'information hétérogè- nes et distantes. Ainsi, une approche multi-agents semble être la plus appropriée au caractère complexe de tels systèmes dont le comportement résulte des interactions entre des entités individuelles [8]. Les applications distribuées à grande échelle sont dif- ficiles à mettre en oeuvre car la consommation excessive en bande passante remet en question la permanence de la connexion. Ainsi, pour atteindre un maximum d'effica- cité en termes de partage et d'accessibilité aux données, il faut gérer la disponibilité de l'information malgré les déconnexions. Dans ce contexte, la technologie mobile [9] peut être d'une grande complémentarité à l'intelligence artificielle car elle peut réduire considérablement le trafic réseau pour une meilleure latence [3]. Doter un agent logiciel de mobilité lui donne la possibilité de migrer vers n'importe quel noeud sur le réseau pouvant héberger des entités mobiles. L'idée est donc de concevoir un SIM pouvant recevoir et envoyer des AMs sur le RTM. Nous visons à étendre notre approche à la nouvelle génération d'applications distribuées (PDA, portable...) dont le déploiement repose sur les réseaux sans fil. Ces applications sont difficiles à mettre en oeuvre car de tels réseaux ont généralement une bande passante très réduite et très variable mettant en question la disponibilité de la connexion. Dans cet article, nous nous intéressons à la satisfac- tion des clients. Nous nous trouvons donc face à deux problèmes d'affectation : d'abord l'affectation des sites aux AMs pour construire leurs plans de travail que nous appelons tournées. Ensuite, l'affectation d'un sous- ensemble de ces mêmes sites aux tâches convoitant la satisfaction des clients. Les requêtes clients formulées simultanément seront tout d'abord décomposées en sous-requêtes appelées tâches. Ces dernières sont indépendantes et peuvent représenter des similarités entre les différentes requêtes clients (figure 1). Ensuite, les serveurs d'information pro- posant les services correspondant aux tâches sont identi- fiés (figure 2). Enfin, la bonne combinaison de serveurs doit être affectée aux tâches dans le but de satisfaire tous les clients connectés (figure 3). Un client satisfait est un utilisateur du système dont la réponse à une requête a été réalisée dans les délais avec un coût raisonnable. RULI 1 111, 1 2r l 1 LI, 1 11 " 1.14 1 111, (1, 1.114 1 -1i 1 t], Figtii-e 1. Décoiiipositioii de i-eclitëtes. 1\,U (I,lT 'I\ T. s- S.- S, s s,.s,.s,.s, Rcq; T T, T;ReLi, s, s ;.s,.s, n si i u E ;] -1 -''h T, T. T, T, ss. I.s : Fiaiii-e 2. Idenlifrcation des servenrs. E Ctll] Ti T T 1 1-1 1 ., 1. Reci, T, In 121 Tt T. i\ i, T. 1 Ti 1 11 " il 1 1 T l_ l ; i -n Fil1-1 1 Ti Figtire 3. Affectation des sei-veiii-.. REE Nc 5 Mai2006 m Dossier) MÉTHODOLOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS Le problème est défini par : . R requêtes, attendant des réponses au même instant t. L'ensemble de ces requêtes est noté RIO . chaque requête req,, E R, est décomposée en un ensemble de tâches indépendantes, noté 1,. ", . chaque requête req,, est caractérisée par une date de fin d'exécution au plus tard d par une date de fin d'exécution D et par un coût total C,,, . un ensemble de tâches indépendantes représentant tous les services proposés sur le RTM. Cet ensemble est noté L . la réalisation de chaque tâche Ti E Il demande une ressource ou encore un site sélectionné à partir d'un ensemble de J serveurs d'information disponibles sur le réseau, noté S avec S= (S "..., SJ,t j, . un ensemble de l'tâches indépendantes (1'< 1) com- posant R,, est noté l', (1,'C- 1,), . un ensemble de J'noeuds (J' J) sélectionné à par- tir de S pour exécuter I',, est noté S' (S'C S), . les temps d'exécution sont prédéfinis ; Pour un ser- veur S, et une tâche T, donnés, le temps d'exécution de T, par S, est connu et noté par ? . le coût d'un service est prédéfini : pour un serveur S, et une tâche T, donnés, le coût de l'information (cor- respondante au service référant T,), à collecter de S,, est connu et noté par C,,,,-- . la quantité de données à collecter pour répondre à un service est prédéfinie ; Pour un serveur S, et une tâche T, donnés, la taille de l'information est connue et notée par Qij, . nous avons à faire à une flexibilité partielle, la réali- sation d'une tâche T, se fait par un serveur sélectionné à partir d'un ensemble de serveurs proposant les ser- vices qui répondent à la tâche T, avec différents coûts, temps de réponse et tailles de l'information. Un même fournisseur d'information peut donc proposer différents services et un même service peut être proposé différemment par plusieurs fournisseurs d'information. Un service est donc décrit par : 1. Un temps de réponse Pi, correspondant à la tâche Ti sur le serveur S,.C'est le temps estimé pour exécu- ter la tâche Ti au moyen des ressources du serveur Sp 2. Le coût du service CI,,,correspondant à la tâche Ti sur le serveur S,, 3. La quantité de données Q,, qui correspond à la taille de l'information à collecter du serveur S, pour répondre à la tâche T. Une même tâche peut être exécutée différemment sur plu- sieurs serveurs, c'est-à-dire avec différents temps d'exé- cution, valant différents coûts et dont la réponse peut être de différentes tailles. Ces trois caractéristiques (PCQ,,) représentent successivement le premier, le second et le dernier termes de chaque élément de la table de service ci-dessous décrivant les services proposés : si S2 S3 S4 Ti (D'O,O) (2,5,3) (4,3,3) (2,5,3) T2 (2,4,5) (1,5,2) (4,5,1) (3,8,3) (1,7,3) (0,0,0) (2,5,3) (4,2,2) T4 (3,2,1(O'O'c (0,0,0) (0,0,0) T (2,3,1 (1, 1,3 (4,5,2) (4,5,3) Table 1. Exemple de services disponibles (Teiiips, coîit et taille de données). Lorsqu'un serveur n'offre pas de réponse pour une tâche (flexibilité partielle), le terme correspondant dans la table est (0,0,0). Sinon Pii#O, Coi, ; Oet Q,, ; 0. 3. Approche proposée Pour résoudre le problème décrit précédemment, nous proposons un système qui s'appuie sur la coordination de cinq types d'agents logiciels [8] [20] (figure 4) : 1). Agents Interface (AI) : Ces agents interagissent avec les utilisateurs du système, ce qui leur permet de choisir une forme de réponse convenable à leurs demandes. Ils gèrent également les requêtes et affichent les résultats. Lorsqu'un client du réseau de transport multimodal accède au SIM, un agent AI se charge de la formulation de sa requête et l'envoie à un agent identificateur qui peut recevoir, à un même instant t, plusieurs requê- tes formulées simultanément. Un agent identifica- teur est relatif à la même plate-forme à laquelle un ensemble d'utilisateurs sont connectés en même temps. Il doit identifier puis choisir les noeuds du RTM qui proposent les services correspondant aux demandes des clients. 2). Agents Identificateur (AId) : Ces agents décompo- sent les requêtes reçues en sous-requêtes, corres- pondant par exemple, à des portions de chemin ou REE N°S Mai2006 Stratégie de migration d'agents mobiles pour les applications du réseau de transport Utilisateur R, R ti R, {,- Rsllltats Resulta: For'faYion ;i Rtol, - - - -- - - Collecte 1 '; ForrUon Dedonnees ii x " Ii" \, ____'' " Conception&optimisation des tournéesdesagentsAC j RTM _' r RTM ] Figlit-e 4. Ai-chilectiii,e i7ililti-ageiit. à des zones géographiques bien déterminées. Les sous-requêtes sont des tâches élémentaires indé- pendantes dont l'exécution est assurée par l'en- semble des serveurs d'information existants sur le RTM. Chaque serveur doit s'inscrire au système en enregistrant tous les services qu'il propose. Un service correspond à la réponse à une tâche précise avec un temps de réponse, un coût et une taille, tous fixés. Ainsi, l'agent Ald décompose l'ensemble des requêtes disponibles simultanément en un ensemble de tâches indé- pendantes en reconnaissant les éventuelles similarités, dans le but d'empêcher une recherche redondante d'infor- mation. La décomposition se fait grâce à l'identification des serveurs d'information pouvant réaliser les tâches liées aux services demandés. Enfin, l'agent Ald transmet toute l'information générée à l'agent ordonnanceur qui se chargera de l'optimisation du choix des sites en respec- tant certaines contraintes. 3). Agents Ordoiinancezir (AO) : Plusieurs serveurs d'information peuvent proposer un même service, à des durées d'exécution, des prix et des formats différents. Le rôle de l'agent AO consiste à affec- ter les serveurs aux tâches en minimisant le coût et le temps total d'exécution afin de respecter la date de fin au plus tard d'une même requête (contrainte de données). L'ensemble des serveurs finalement choisis pour accomplir les tâches d'un ensemble de requêtes, constitue l'ensemble des noeuds qui forment les plans de travail (tournées) des agents collecteurs d'information. L'agent AO doit d'abord optimiser le nombre de ces agents ensuite l'affectation des noeuds aux différentes tâches. Ce comportement sera développé d'une manière plus détaillée dans la partie qui suit. 4). Agents Collecteiirs (AC) : Ce sont des agents logi- ciels dotés de mobilité pouvant se déplacer d'un serveur à un autre pour collecter l'information recherchée. Ces agents sont composés de données, de code et d'un état d'exécution [2]. Les données collectées ne doivent pas dépasser un seuil de capacité pour ne pas surcharger l'agent AC. Par conséquent, l'agent AO doit prendre en compte cet aspect lors de l'affectation des tâches. A leur retour au site Hôte, les agents AC doivent transmettre les données collectées à l'agent Fusion. 5). Agents Ftision (AF) : Ces agents se chargent de la fusion des données collectées pour construire les réponses conformes aux requêtes formulées simul- tanément. Cette construction se fait au fur et à mesure de la disponibilité des données collectées par les agents AC. Chaque nouveau composant de réponse doit être complémentaire aux composants déjà fusionnés. Le choix de la source d'information d'un service particulier a été fixé d'avance et les tâches sont supposées, pour l'instant, indépendan- tes. De ce fait, il n'y a pas de conflit possible entre les résultats des agents AC. Une réponse de requête peut être : . complète : la réponse est complètement construite car tous les composants sont disponibles ; . partielle : au moins une tâche composant la requête n'a pas été traitée, par exemple à cause d'un ser- vice indisponible ; . totalement vide : aucun composant n'est disponible. Si la réponse n'est pas complète, le résultat est quand même transmis à l'utilisateur via l'agent AI qui se charge de la reformulation de la requête, avec ou sans l'intervention de l'utilisateur. L'agent Ald se charge donc des différentes requêtes utilisateurs formulées simultanément. Il les décompose en un ensemble de tâches indépendantes. Le processus de décomposition comprend l'identification des similarités entre les requêtes pour formuler un ensemble de tâches distinctes et autonomes attendant des réponses au même instant t. Chaque tâche représente un service qui peut être proposé par divers noeuds du RTM, avec des temps de réponse, des coûts et des formats variés. Les données nécessaires pour répondre aux tâches sont disponibles dans le RTM, et leur collecte est à la charge des agents AC. Ensuite, l'agent AO doit optimiser l'affectation des serveurs aux tâches en minimisant le coût et le temps total d'exécution afin de respecter la date de fin au plus tard d'une même requête. Pour ce problème d'affectation nous proposons une solution d'optimisation qui opère sur deux étapes. La première vise à déterminer un nombre appro- prié d'agents AC et de construire leurs tournées pour explorer l'ensemble du RTM. La deuxième étape opti- mise le choix des noeuds fournisseurs d'information dans REE No 5 Mai2006 Dossier MÉTHODOEOGIES ET HEURISTIQUES POUR L'OPTIMISATION DES SYSTÈMES INDUSTRIELS le but d'augmenter le nombre de clients satisfaits. Ces deux étapes sont complémentaires, nous les avons détail- lées dans les deux paragraphes qui suivent en établissant les liens qui les assemblent. 4. Construction des tournées La latence est le temps nécessaire pour transférer un paquet de données d'un noeud à un autre à travers un réseau. Elle varie selon son état et peut ainsi affecter le transfert de données à travers les applications distribuées. Par conséquent, l'usage des agents AC peut réduire consi- dérablement le trafic car ils n'exigent pas la simultanéité de connexion entre les différents sites [3]. Dans cette par- tie, nous nous intéressons au problème de construction des tournées des agentsAC [10] [11] [12]. Dans un travail antérieur [13], nous avons proposé un schéma de tournée qui a pour but de trouver un ensemble d'agents AC mini- misant leurs temps de navigation afin d'explorer tous les noeuds du RTM, prenant en compte la latence réseau. A. Hypothèses Dans cette partie, nous nous basons sur les hypothèses suivantes : . la collecte des données sur un noeud visité nécessite un temps d'exécution. Nous supposons que la taille des données à collecter sur un noeud du réseau est égale à la taille moyenne des données qui s'y trouvent, . nous assumons qu'initialement, un agent AC n'est pas totalement vide car il transporte une quantité ini- tiale de données Qo, . nous supposons que la latence minimale entre cha- que paire de noeuds sur le réseau est disponible grâce à un service de gestion réseau, . l'information peut avoir un aspect multimédia, nous pouvons ainsi assumer que le temps de transmission d'une quantité de données entre deux noeuds du réseau dépend de la latence répandue. B. Description Le problème de construction des tournées peut être décrit de la manière suivante : Les agents AC sont créés et lancés à partir d'un noeud principal (noeud Hôte). Tous les autres noeuds du réseau représentent les fournisseurs d'information qu'un agent AC peut visiter pour réclamer des services. Ces derniers sont exprimés sous forme de tâches indépendantes. Un même service peut être proposé par différents serveurs avec des coûts et des temps de réponses distincts et sous différents formats. Sur le noeud Hôte, le temps de réponse est naturellement nul. Nous appelons temps de réponse d'un service donné sur un noeud, le temps d'exécution de la tâche correspondante à ce service sur le même noeud. Les temps de latence sont connus et peuvent affecter le temps de navigation des agents AC. Notre but est de mini- miser le nombre des agents AC et leurs temps de naviga- tion afin d'explorer l'ensemble du réseau, prenant en compte les temps de latence. C. Méthode de construction Dans cette partie, nous proposons une méthode lucrative de construction des plans de travail des agents AC. Nous supposons l'existence d'un module de gestion réseau fournissant les informations nécessaires sur son état (tra- fic, goulets d'étranglement, pannes...). Nous pouvons ainsi consulter le temps de latence entre chaque paire de noeuds sur le réseau. Ces temps de latence varient selon l'état du réseau, et ont un lien direct avec les temps de transmission des données qui y circulent. Nous assumons que les agents AC ne sont créés qu'au sein du noeud Hôte et ne sont pas clonés comme il a été le cas dans [12]. Il est clair que le fait d'envoyer un agent AC sur cha- que noeud du réseau nous donne le meilleur temps de cal- cul puisqu'ils sont fonctionnels simultanément. Notre but est donc de garder ce meilleur temps de calcul en minimi- sant le nombre d'agents. Pour la même problématique, J.W Baek propose un algorithme efficace de construction des tournées d'AMs [15]. Nous adoptons la même appro- che, mais en considérant les quantités de données trans- portées. L'objectif de cette partie est de trouver un ensemble d'agents AC minimisant leur temps de navigation dans le but d'explorer totalement le réseau multimodal, prenant en considération la latence réseau. Par conséquent, dans cette partie nous ne prenons pas en considération le coût des données collectées. Ainsi dans ce qui suit, la table de services présentée par la table 2 ci-dessous, exprime seu- lement le temps d'exécution et la taille de données col- lectées correspondant à un service (Pi,Q,,) : S, S2 Oj S, T, (0,0) (2,3) (4,3) (2,3) T2 2,5) (1,2 4,I) (3,3) T3 (1,3) 0,O) (2,3) (4,2) T4 (3,1) (0,0) (0,0 (0,0) T5 (2,1) (1,3 4,2) (4,3) Table 2. Exemple de services disponibles (Teiiips et taille de données). Description de l'algorithme Comme nous l'avons déjà mentionné, L,, (S,,Sj) repré- sentant la plus petite latence entre deux noeuds S, et S,, est connue. L'algorithme est alors décrit comme suit : Etape 1 : Trier les noeuds dans l'ordre décroissant de leur temps respectif de tournées T (tournée, = S,) VKJ. Calculer la borne supérieure ô qui représente le temps de tournée du premier noeud de la liste triée. Ô Max (1' (toitril, = S,)) REE No 5 Mai2006 Etape 2 : Rassembler les différents noeuds du réseau en parti- tions de façon à ce que le temps de tournée qui corres- pond à chaque partition ne dépasse pas la borne supé- rieure 6. Etape 3 : Appliquer un algorithme d'optimisation calculant le plus court chemin de tournée sur chaque partition [16]. Etape 4 : Attribuer chaque chemin de tournée ainsi construit à un agent AC pour explorer la partition correspondante du réseau. L'algorithme décrit ci-dessus est dynamique ; il tente de trouver la prochaine destination d'un agent AC à par- tir du noeud courant où il se trouve. En d'autres termes, cet algorithme cherche le prochain noeud à visiter calcu- lant à chaque fois le nouveau temps de tournée. Un noeud est sélectionné si le nouveau temps de tournée ne dépasse pas la borne supérieure 6. Sinon, un plan de travail est prêt et l'algorithme prend fin si chaque noeud du réseau fait partie d'une tournée. Cet algorithme permet de répar- tir l'ensemble des noeuds du RTM sur un ensemble d'agents AC dans le but de l'explorer intégralement. Cette étape permet de préparer les plans de travail initiaux des agents AC. Dans le prochain paragraphe, un sous-ensemble du RTM sera identifié grâce à une méthode évolutionniste, pour optimiser la gestion du flux informatique. Le but de la prochaine étape est donc d'optimiser le choix des noeuds du RTM, à partir d'un ensemble de serveurs d'in- formation proposant les services clients demandés. Les plans de travail définitifs des agents AC seront alors déduits à partir des plans initiaux afin de collecter les données nécessaires pour satisfaire les requêtes clients dans les plus brefs délais et avec des coûts raisonnables. 5. Optimisation du flux informatique Les algorithmes évolutionnistes (AE), inspirés des algorithmes génétiques, ont ajouté un nouvel aspect à l'intelligence artificielle. Ces algorithmes utilisent diffé- rents modèles de calcul évolutionniste afin de résoudre des problèmes informatiques. Ce sont des méthodes de recherche stochastique qui imitent la métaphore de l'évo- lution biologique naturelle ; ils opèrent sur une popula- tion de solutions potentielles appliquant le principe de survie des individus les plus viables dans le but de converger progressivement vers la solution optimale. A chaque génération, un AE produit un nouvel ensemble d'approximations grâce à une méthode de sélection qui choisit les individus selon un ou plusieurs critères, appe- lés niveaux de fitness par rapport à la population. Un pro- cessus de reproduction utilisant des opérateurs génétiques (tels le croisement et la mutation) est par la suite appliqué sur chaque nouvelle génération [17]. Par rapport aux méthodes traditionnelles d'optimisation comme celle de la descente de gradient, les AEs sont des techniques robustes de recherche globales dont le potentiel a été très rapidement reconnu. Dans cette partie [18], nous considérons les importantes caractéristiques des AEs et leurs pertinence à résoudre les problèmes traditionnels NP-complets. A. Représentation du chromosome Le choix d'une représentation convenable à une solution est fondamental pour le succès des applications des AEs. Ainsi, un codage adéquat à une solution de notre problé- matique et respectant ses contraintes est indispensable pour une meilleure résolution. Dans cette partie, nous proposons une représentation flexible du chromosome appelée Représentation Flexible d'Affectation des Tâches (FeTAR). Le chromosome est représenté par une matrice CH (FxJ') dont les lignes et les colonnes représentent respectivement les tâches et les serveurs d'information. Chaque élément de la matrice correspond à l'affectation de la tâche T, au serveur S, comme suit : CH [i,j] 1: Si S, est affecté à T, * : Si S, peut être affecté à T, X : Si S, ne peut pas être affecté à T, Nous notons que chaque tâche ne doit être affectée qu'une seule fois. Ainsi, parmi l'ensemble des serveurs d'information qui offrent le service correspondant à une tâche, un seul doit être sélectionné pour l'accomplir. Exemple : Soit 4 serveurs et 3 requêtes décomposées globalement en 5 tâches comme suit : Req, décomposée en T,, T., T et Ts, Req, décomposée en T, Req,, décomposée en T,, T,, et T " Une solution possible est un chromosome CH instance de FeTAR : CH S, S2 S3 S4i T, X 1 1 * T2 1 1 1 1z T3 1 x 1 T,TXXXTa 1 X X X , 1 REE N 5 Mai2006 DTtSB "')!tM '