Les problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programmes linéaires mixtes sur des instances particulières.<br /><br />Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés.<br /><br />Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté.<br /><br />Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux.<br /><br />L'objet du quatrième chapitre est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau.

L'augmentation du nombre de génomes totalement séquencés rend de plus en plus efficace l'étude des mécanismes évolutifs à partir de la comparaison de génomes contemporains. L'un des principaux problèmes réside dans la reconstruction d'architectures de génomes ancestraux plausibles afin d'apporter des hypothèses à la fois sur l'histoire des génomes existants et sur les mécanismes de leur formation. Toutes les méthodes de reconstruction ancestrale ne convergent pas nécessairement vers les mêmes résultats mais sont toutes basées sur les trois mêmes étapes : l'identification de marqueurs commun dans les génomes contemporains, la construction de cartes comparatives des génomes, et la réconciliation de ces cartes en utilisant le critère de parcimonie maximum. La quantité importante des données à analyser nécessite l'automatisation des traitements et résoudre ces problèmes représente de formidables challenges computationnels. Affiner les modèles et outils mathématiques existants par l'ajout de contraintes biologiques fortes rend les hypothèses établies biologiquement plus réalistes. Dans cette thèse, nous proposons une nouvelle méthode permettant d'identifier des marqueurs communs pour des espèces évolutivement distantes. Ensuite, nous appliquons sur les cartes comparatives reconstituées une nouvelle méthode pour la reconstruction d'architectures ancestrales basée sur les adjacences entre les marqueurs calculés et les distances génomiques entre les génomes contemporains. Enfin, après avoir corrigé l'algorithme existant permettant de déterminer une séquence optimale de réarrangements qui se sont produits durant l'évolution des génomes existants depuis leur ancêtre commun, nous proposons un nouvel outil appelé VIRAGE qui permet la visualisation animée des scénarios de réarrangements entre les espèces.

LOTOS (Language Of Temporal Ordering Specification) est un langage <br />de description de systemes paralleles communicants, normalise par l'ISO et le <br />CCITT afin de permettre la definition formelle des protocoles et des services<br />de telecommunications. Le langage utilise des types abstraits algebriques pour<br />specifier les donnees et un calcul de processus proche de CSP et CCS pour<br />exprimer le controle. <br /><br /> Cette these propose une technique de compilation permettant de traduire <br />un sous-ensemble significatif de LOTOS vers un modele reseau de Petri<br />interprete (pouvant servir a produire du code executable) puis vers un<br />modele automate d'etats finis (permettant la verification formelle de programmes<br />LOTOS soit par reduction ou comparaison modulo des relations d'equivalence, soit<br />par evaluation de formules de logiques temporelles).<br /><br /> La methode employee differe des approches usuelles basees sur la<br />reecriture de termes, qui construisent directement le graphe d'etats<br />correspondant a un programme LOTOS. <br /> Ici au contraire la traduction est effectuee en trois etapes successives<br />(expansion, generation et simulation) s'appuyant sur des modeles semantiques<br />intermediaires (le langage SUBLOTOS et le modele reseau). Elle met en oeuvre<br />une analyse statique globale du comportement des programmes.<br /> Elle prend en compte les donnees, celles-ci devant etre compilees<br />au moyen dalgorithmes deja existants.<br /><br /> Ces principes de compilation ont ete entierement implementes dans<br />le logiciel CAESAR. Les performances obtenues confirment l'interet de la methode.

Un des challenges actuels de la planification est la résolution de problèmes pour lesquels on cherche à optimiser la qualité d'une solution telle que le coût d'un plan-solution. Dans cette thèse, nous développons une méthode originale pour la planification de coût optimal dans un cadre classique non temporel et avec des actions valuées.<br /><br />Pour cela, nous utilisons une structure de longueur fixée appelée graphe de planification. L'extraction d'une solution optimale, à partir de ce graphe, est codée comme un problème de satisfaction de contraintes pondérées (WCSP). La structure spécifique des WCSP obtenus permet aux solveurs actuels de trouver, pour une longueur donnée, une solution optimale dans un graphe de planification contenant plusieurs centaines de nœuds. <br /><br />Nous présentons ensuite plusieurs méthodes pour déterminer la longueur maximale des graphes de planification nécessaire pour garantir l'obtention d'une solution de coût optimal. Ces méthodes incluent plusieurs notions universelles comme par exemple la notion d'ensembles d'actions indispensables pour lesquels toutes les solutions contiennent au moins une action de l'ensemble. <br /><br />Les résultats expérimentaux effectués montrent que l'utilisation de ces méthodes permet une diminution de 60% en moyenne de la longueur requise pour garantir l'obtention d'une solution de coût optimal. La comparaison expérimentale avec d'autres planificateurs montre que l'utilisation du graphe de planification et des CSP pondérés pour la planification optimale est possible en pratique même si elle n'est pas compétitive, en terme de temps de calcul, avec les planificateurs optimaux récents.

L'influence de la diversité lors de la construction d'ensembles de classifieurs a soulevé de nombreuses discussions au sein de la communauté de l'Apprentissage Automatique ces dernières années. <br> Une manière particulière de construire un ensemble de classifieurs consiste à sélectionner individuellement les membres de l'ensemble à partir d'un pool de classifieurs en se basant sur des critères prédéfinis. <br> La littérature fait référence à cette méthode sous le terme de paradigme Surproduction et Sélection, également appelé élagage d'ensemble de classifieurs.<br> <br> Les travaux présentés dans cette thèse ont pour objectif d'étudier le compromis entre la précision et la diversité existant dans les ensembles de classifieurs. Nous apportons également certains éléments de réponse sur le comportement insaisissable de la diversité lorsqu'elle est utilisée de manière explicite lors de la construction d'un ensemble de classifieurs.<br> <br> Nous commençons par étudier différents algorithmes d'apprentissage de la littérature. Nous présentons également les algorithmes ensemblistes les plus fréquemment utilisés. Nous définissons ensuite le concept de diversité dans les ensembles de classifieurs ainsi que les différentes méthodes permettant de l'utiliser directement lors de la création de l'ensemble.<br> <br> Nous proposons un algorithme génétique permettant de construire un ensemble de classifieurs en contrôlant le compromis entre précision et diversité lors de la sélection des membres de l'ensemble. Nous comparons notre algorithme avec différentes heuristiques de sélection proposées dans la littérature pour construire un ensemble de classifieurs selon le paradigme Surproduction et Sélection.<br> <br> Les différentes conclusions que nous tirons des résultats obtenus pour différents jeux de données de l'UCI Repository nous conduisent à la proposition de conditions spécifiques pour lesquelles l'utilisation de la diversité peut amener à une amélioration des performances de l'ensemble de classifieurs. Nous montrons également que l'efficacité de l'approche Surproduction et Sélection repose en grande partie sur la stabilité inhérente au problème posé.<br> <br> Nous appliquons finalement nos travaux de recherche au développement d'un système de classification supervisée pour le contrôle de la pollution atmosphérique survenant sur des sites industriels. Ce système est basé sur l'analyse par traitement d'image de scènes à risque enregistrées à l'aide de caméras. Son principal objectif principal est de détecter les rejets de fumées dangereux émis par des usines sidérurgiques et pétro-chimiques.

Un objectif de cette thèse est de fournir des outils d'analyse, de conception et d'implantation des approches métaheuristiques pour l'optimisation combinatoire en les formulant dans le cadre des systèmes multi-agents. L'accent est mis sur la potentialité de mise en œuvre distribuée des approches et sur l'utilisation de techniques d'apprentissage permettant d'adapter dynamiquement des méthodes de recherche.<br /><br />Dans le cadre de cette thèse nous proposons tout d'abord, un framework organisationnel et multi-agent pour la modélisation et l'implantation de métaheuristiques. Ce framework nommé AMF (Agent Metaheuristic Framework), introduit un modèle organisationnel de métaheuristiques qui décrit le système sous la forme d'une organisation composée de rôles en interaction. Le premier objectif de ce modèle est de donner un cadre d'analyse et de comparaison des différentes métaheuristiques existantes. Ensuite, il doit faciliter la conception de nouveaux algorithmes en encourageant une approche multi-agent. L'intérêt de l'approche organisationnelle, actuellement utilisée dans les systèmes multi-agents, est de pouvoir décrire un système aussi bien comme un tout, le système multi-agent, que comme un assemblage de composants, les agents. De plus, cette approche permet de distinguer l'analyse des fonctions du système, de l'analyse de son architecture. Enfin, l'approche organisationnelle encourage la modularité et la réutilisation des modèles. Nous proposons en complément de ce modèle un guide méthodologique. Il définit un ensemble d'étapes permettant de passer du modèle organisationnel à une méthode d'optimisation exprimée en termes d'agent.<br /><br />Ensuite, nous présentons une métaheuristique fondée sur la métaphore de la coalition, CBM (Coalition Based Metaheuristic), mettant en avant l'intérêt d'utiliser les systèmes multi-agents pour la conception de métaheuristiques. Dans cette métaheuristique, la recherche de solution est effectuée par un ensemble d'agents regroupés dans une coalition. Chaque agent est capable d'effectuer indépendamment des autres une recherche dans l'espace des solutions à l'aide d'opérateurs de déplacement dans un voisinage de la solution courante et d'adapter sa stratégie par apprentissage par renforcement. Des mécanismes de coopération entre agents permettent d'améliorer l'efficacité de la recherche. La structure de coalition permet d'intégrer naturellement au système de résolution des aspects de distribution et de décentralisation du contrôle, de même que des procédés d'apprentissage individuels et collectifs. L'efficacité de notre approche est évaluée expérimentalement en traitant deux problèmes d'optimisation combinatoire : un problème de tournées de véhicules et un problème de positionnement.

Aujourd'hui, les plates-formes hétérogènes et partagées que sont les grilles de calcul sont omniprésentes. De plus, le besoin d'exécuter des applications parallèles complexes est croissant. Cette thèse vise à ordonnancer des applications représentées par des graphes de tâches modelables (dont le nombre de processeurs est fixé par l'ordonnanceur) sur des grilles de calcul en exploitant le maximum de parallélisme, utilisant efficacement les ressources, gérant l'hétérogénéité et le partage des ressources. Nous avons pour cela opté pour des heuristiques pragmatiques car, bien qu'elles n'offrent pas de garantie de performance, elles peuvent néanmoins conduire à de bonnes performances moyennes tout en construisant des ordonnancements en des temps relativement courts. La plupart des heuristiques existantes n'ordonnancent les applications parallèles mixtes qu'en milieu homogène et utilisent parfois inefficacement les ressources. Nous avons donc tout d'abord étudié différentes heuristiques dans le cas de plates-formes homogènes et proposé des améliorations visant à améliorer le compromis entre réduction du temps de complétion et efficacité. Nous avons ensuite introduit la gestion de l'hétérogénéité dans l'heuristique proposée et comparé ses performances à celles d'un algorithme garanti. Enfin, nous avons tenu compte du caractère partagé des grilles en gérant la concurrence entre applications. L'approche retenue consiste à limiter la quantité de ressources que chaque application peut utiliser pour construire son ordonnancement. Nous avons également proposé plusieurs stratégies de détermination de cette contrainte de ressources.

- Recherche en traitement d'images sur la mesure du mouvenment d'objets déformables<br>-enseignement à distance collaboratif (Campus virtuel EDEN3)<br>-formation à distance et travail distant collaboratif : quels apports des EIAH pour les remote labs, ...

La problématique est l'étude de la modélisation pour la simulation de systèmes complexes. Les processus de modélisation et de simulation étant complexes, il faut rationaliser la modélisation et gagner en maîtrise sur elle. Nous proposons de concevoir le modèle complexe comme une société de modèles en interaction. Nous appliquons l'approche orientée pattern pour rationaliser la modélisation en la centrant sur les données. Nous utilisons l'approche agent pour distribuer l'observation et le contrôle dans le modèle global. La société de modèles permet alors l'émergence des patterns par l'activité des agents. Les artefacts, appliqués à la modélisation, sont le support des données, des patterns et des interactions entre agents. Le couplage des agents se fait ainsi via les \artefacts, à la différence d'une approche par événements.<br />Nous identifions trois types d'agents : <br />1° les agentmodeles, qui exécutent le modèle d'un phénomène ; <br />2° les agents-observateurs, qui construisent des observables ; <br />3° les agents-contrôleurs, qui contrôlent localement le modèle global.<br />Les agents peuvent également s'adapter à leur environnement avec des opérations pour modifier leurs perceptions et actions. Le modèle complexe peut alors être construit incrémentalement, les comportements des agents peuvent être modifiés facilement, et un agent peut être ajouté ou enlevé du modèle global sans impact sur la structure des autres agents.<br />Enfin, nous identifions quatre types de comportements pour un agent-modèle : 1° basé sur des équations différentielles (intensionnel) ; 2° centré individu (émergent) ; 3° pré-calculé (extensionnel) ; 4° joué par un expert (participatif). Pour aller plus loin dans la rationalisation de la modélisation, nous exhibons les biais computationnels induits par la traduction de modèles conceptuels en modèles computationnels dans le cas de modèles de peuplements d'agents. Nous montrons que nos modèles sont très sensibles aux différents biais étudiés. Il est nécessaire que les thématiciens connaissent les sources de biais et que l'outil de simulation soit spécialisé afin de permettre : 1° d'expliciter le modèle, 2° de garantir les propriétés identifiées et 3° de permettre des analyses systématiques. C'est ce que nous faisons dans notre simulateur. Enfin, ce travail entre dans le cadre du projet ANR Chaloupe. L'enjeu est d'envisager la co-viabilité de peuplements écologiques et de leur exploitation par des groupes sociaux (e.g. pêcheries). Nous présentons les résultats de simulation obtenus validant la société de modèles qui permet une modélisation souple et rigoureuse.

Classiquement la réalité augmentée consiste en l'annotation d'objets fixes pour un utilisateur en mouvement au sein d'un environnement réel. Le travail présenté dans cette thèse porte sur l'utilisation de la réalité augmentée dans le but de décrire des objets dynamiques dont le comportement n'est que peu prévisible. Nous nous intéressons tout particulièrement aux problèmes posés par la nature dynamique de l'environnement en ce qui concerne: 1°/ la description du réel (adapter les explications fournies par le guide virtuel à l'évolution de l'environnement) ; 2°/ la perception du réel (percevoir l'environnement à expliquer en temps réel à l'aide de caméras).<br>La description du réel consiste en la génération d'un exposé par le guide virtuel. Cette génération repose sur deux points: des connaissances a priori sous la forme d'explications et un comportement décrit par un automate hiérarchique. Nous considérons la visite guidée comme l'évolution conjointe du comportement du guide virtuel et des explications qu'il fournit aux visiteurs. Une explication permet de décrire l'enchaînement d'éléments de discours sur un sujet donné à l'aide d'un graphe. Chacun de ces éléments décrit une unité de discours indivisible décrivant l'utilisation des différentes modalités (parole, gestes, expression, ...) sous la forme d'un script. L'exécution d'un graphe d'explication est effectuée par le comportement qui intègre la notion d'interruption. Lorsqu'un processus d'explication est interrompu, il est suspendu et le sujet courant de la visite guidée est réévalué. Cette réévaluation repose sur l'utilisation d'un ensemble d'experts votant pour les différentes explications disponibles selon un point de vue particulier. Ce vote se base sur le contexte courant de la visite guidée (historique, temps écoulé/restant, ...) et l'état de l'environnement réel. <br>La perception consiste en la construction et la mise à jour d'une représentation de l'environnement. Ceci est effectué en temps réel par la coopération de différentes routines de perception. La complexité de l'environnement observé (quantité d'informations et variations des conditions d'éclairage) empêchent une analyse complète du flux vidéo. Nous proposons de surmonter ce problème par l'utilisation de stratégies de prise d'information adaptées. Ces stratégies de perception sont mises en oeuvre par certaines routines au travers du choix et du paramétrage des traitements qu'elles effectuent. Nous présentons un ensemble minimal de routines nécessaires à la construction d'une représentation de l'environnement exploitable dans le cadre de la description de cet environnement. Ce système repose sur la mise en oeuvre de trois stratégies de perception: la vigilance qui coordonne des traitements de détection dans le temps et dans l'espace; le suivi qui se charge de mettre à jour les propriétés spatiales des entités existantes dans la représentation; la reconnaissance dont le rôle est d'identifier ces entités. L'efficacité des stratégies de perception suppose une interaction entre la prise de décision (génération de l'exposé) et la perception (construction d'une représentation de l'environnement) de notre acteur virtuel autonome. Nous proposons de mettre en oeuvre cette interaction au travers de la représentation de l'environnement et des requêtes effectuées par le processus de prise de décision sur cette représentation.<br>Nous avons mené des expérimentations afin mettre en évidence le fonctionnement des différents aspects de notre proposition et de la valider des conditions contrôlées. Ces travaux sont appliqués à un cas concret d'environnement réel dynamique complexe au sein du projet ANR SIRENE. Cette application met en évidence les questions liées à notre problématique et montre la pertinence de notre approche dans le cadre de la présentation d'un aquarium marin d'Océanopolis.