Les Algorithmes Évolutionnaires sont des algorithmes d'optimisation qui ont déjà montré leur efficacité dans plusieurs domaines; mais leur performance dépend du réglage de plusieurs paramètres. Cette thèse est consacrée au développement de techniques pour automatiser ce réglage par le biais de l'apprentissage automatique. Plus spécifiquement, nous avons travaillé sur un sous-problème: étant donné un ensemble d'opérateurs, cela consiste à choisir lequel doit être appliqué pour la génération de chaque nouvelle solution, basé sur la performance connue de chaque opérateur. Cette approche est utilisée en ligne, au cours de la résolution du problème, en utilisant exclusivement l'histoire du processus d'optimisation courant pour décider parmi les différents opérateurs; ce paradigme est couramment référencé comme Sélection Adaptative d'Opérateurs (SAO). Pour faire de la SAO, deux composants sont nécessaires. L'Affectation de Crédit définit comment récompenser les opérateurs selon l'impact de leur application sur le processus de recherche. La Sélection d'Opérateurs règle leur choix selon les récompenses reçues ultérieurement. En résumé, la contribution principale de cette thèse consiste dans la proposition et l'analyse de différentes approches pour la SAO, basées sur le paradigme de Bandit Manchot (BM); nous avons proposé plusieurs modifications pour transformer un algorithme BM en une technique à la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caractéristiques des problèmes diverses. La dernière méthode, appelé AUC-MAB, est capable de suivre efficacement le meilleur opérateur sans nécessiter d'un réglage spécifique pour chaque problème.

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

Les techniques de segmentation de graphe sont souvent utilisées en traitement d'images puisque ces dernières peuvent être vues comme des graphes valués. Dans cette thèse, nous montrons des liens existant entre plusieurs paradigmes de segmentation de graphes valués. Nous présentons tout d'abord différentes définitions de ligne de partage des eaux et sélectionnons celle dont le cadre permet la comparaison avec des forêts couvrantes particulières. Nous montrons qu'une telle ligne de partage des eaux relative à des marqueurs arbitraires est équivalente à une coupe induite par une forêt couvrante de chemins de moindre altitude. Ensuite, les coupes induites par des forêts couvrantes de poids minimum sont démontrées comme étant des cas particuliers ayant l'avantage d'éviter certaines segmentations non souhaitées. Enfin, nous montrons qu'une coupe minimale coïncide avec une coupe induite par une forêt couvrante de poids maximum pour certaines fonctions de poids particulières. Dans une seconde partie, nous présentons deux applications utilisant la segmentation de graphe : la renaissance d'images et le mélange de textures pour la reconstruction 3D

L'objectif de ce travail est le déploiement d'un système de segmentation d'images de résonance magnétiques (IRM) sur la plateforme de visualisation "BrainVISA". La segmentation vise à classifier le cerveau en trois régions : la matière blanche, la matière grise et le liquide céphalo-rachidien. Il existe plusieurs algorithmes de segmentation d'images, chacun possédant ses avantages et ses limites d'utilisation. Dans ce travail, nous utilisons deux types d'algorithmes : la FCM (Fuzzy C-Mean) qui étudie l'image dans sa globalité et permet de modéliser l'incertitude et l'imprécision et, la croissance de régions qui tient compte des relations de voisinage entre pixels ; le but étant de tirer partie des avantages de chacun. Les deux méthodes de segmentation sont utilisées de manière coopérative. Les prédicats de la croissance de régions sont adaptés à nos images afin d'améliorer la qualité de l'image segmentée. Une implémentation est alors mise en oeuvre autour d'un système multi-agents (SMA), qui permet d'utiliser l'algorithme de croissance de régions de manière plus efficace. La segmentation est réalisée sur des images réelles.

Dans les applications actuelles, le nombre de variables continue d'augmenter, ce qui rend difficile l'estimation de densité. En effet, le nombre de paramètres nécessaire pour l'estimation croit exponentiellement par rapport à la dimension du problème. Les modèles graphiques probabilistes fournissent une aide non négligeable pour lutter contre ce problème en fournissant une factorisation de la loi jointe mais souffrent d'un problème de passage à l'échelle. Le problème de grande dimension s'accentue du fait que le nombre d'observations avec lequel on effectue l'estimation de densité n'augmente pas dans les mêmes proportions, et reste même extrêmement faible dans certains domaines d'applications. La factorisation de la loi jointe s'avère non suffisante pour effectuer une estimation de densité de qualité lorsqu'il y a très peu de données. Le principe du Perturb & Combine, initialement appliqué en classification, permet de lutter contre ce genre de problèmes. Dans le cadre de cette thèse, nous proposons un algorithme générique d'estimation de densité en appliquant le principe du Perturb et Combine à une famille de modèles graphiques probabilistes "simples" , les structures arborescentes "manipulables" avec une complexité au pire quadratique. Plusieurs variantes de cet algorithme sont proposées en exploitant à deux niveaux le principe de perturbation: perturbation de la génération des modèles simples et perturbation des données d'apprentissage. Les expérimentations effectuées lors de ce travail montrent que nos premières approches sont concluantes en ce qui concerne la qualité d'approximation, pour une complexité algorithmique quadratique encore insuffisante en grande dimension. Notre seconde contribution concerne donc une nouvelle application du principe de perturbation, permettant d'arriver à une complexité algorithmique proche du quasi-linéaire pour une même qualité d'approximation.

Le développement du Web 2.0 a donné lieu à la production d'une grande quantité de discussions en ligne. La fouille et l'extraction de données de qualité de ces discussions en ligne sont importantes dans de nombreux domaines (industrie, marketing) et particulièrement pour toutes les applications de commerce électronique. Les discussions de ce type contiennent des opinions et des croyances de personnes et cela explique l'intérêt de développer des outils d'analyse efficaces pour ces discussions. L'objectif de cette thèse est de définir un modèle qui représente les discussions en ligne et facilite leur analyse. Nous proposons un modèle basé sur des graphes. Les sommets du graphe représentent les objets de type message. Chaque objet de type message contient des informations comme son contenu, son auteur, l'orientation de l'opinion qui y été exprimée et la date où il a été posté. Les liens parmi les objets message montrent une relation de type "répondre à". En d'autres termes, ils montrent quels objets répondent à quoi, conséquence directe de la structure de la discussion en ligne. Avec ce nouveau modèle, nous proposons un certain nombre de mesures qui guident la fouille au sein de la discussion et permettent d'extraire des informations pertinentes. Il existe des mesures centrées sur l'analyse de l'opinion qui traitent de l'évolution de l'opinion au sein de la discussion. Nous définissons également des mesures centrées sur le temps, qui exploitent la dimension temporelle du modèle, alors que les mesures centrées sur le sujet peuvent être utilisées pour mesurer la présence de sujets dans une discussion. La présence de l'utilisateur dans des discussions en ligne peut être exploitée soit par les techniques des réseaux sociaux, soit à travers notre nouveau modèle qui inclut la connaissance des auteurs de chaque objet message. De plus, une liste de messages clés est recommandée à l'utilisateur pour permettre une participation plus efficace au sein de la discussion.

Le sujet de cette thèse porte sur la reconstruction de formes à partir de coupes planaires. Dans de nombreux domaines d'application, il est nécessaire de reconstruire des formes à partir de sections. L'importance du sujet en imagerie médicale a conduit, depuis les années 1990, à des résultats importants qui sont cependant pour la plupart limités au cas de sections parallèles. Pourtant en échographie, les données obtenues au moyen d'une sonde guidée manuellement, forment une série d'images représentant des coupes de l'organe par des plans non parallèles. Cette application directe motivait le sujet de ma thèse. Dans cette thèse nous considérons le problème de la reconstruction d'une 3-variété à bord plongée dans R^3, à partir de ses intersections avec un ensemble de plans en positions arbitraires, appelées coupes. C'est pour la première fois que ce problème est étudié en toute généralité, dans le but de fournir des garanties théoriques satisfaisantes sur le résultat de la reconstruction. Aucune garantie théorique n'a été obtenue même pour le cas de coupes parallèles avant cette thèse. Dans le premier chapitre de ce manuscrit, nous étudions la méthode de reconstruction proposée par Liu et al. en 2008. Nous prouvons que si certaines conditions d'échantillonnage sont vérifiées, cette méthode permet de reconstruire la topologie de l'objet à partir des coupes données. Nous prouvons également que l'objet reconstruit est homéomorphe (et isotope) à l'objet. Le deuxième chapitre présente une nouvelle méthode de reconstruction en utilisant le diagramme de Voronoi des sections. Cette méthode permet d'établir plus de connections entre les sections par rapport à la première méthode. Favoriser les connections entre les sections est motivé par la reconstruction d'objets fins à partir de sections peu denses. Nous présentons des conditions d'échantillonnage qui sont adaptées aux objets fins et qui permettent de prouver l'équivalence homotopique entre l'objet reconstruit et l'objet de départ. En effet, nous prouvons que si les plans de coupe sont suffisamment transversales à l'objet, notre méthode de reconstruction est topologiquement valide et peut traiter des topologies complexes des sections avec plusieurs branchements. Dans le dernier chapitre de ce manuscrit, nous présentons une autre méthode de reconstruction qui permet d'établir encore plus de connections entre les sections en comparant avec les deux premières méthodes. Notre méthode est basée sur la triangulation de Delaunay et suit une approche duale en considérant le diagramme de Voronoi des sections. L'algorithme correspondant a été implémenté en C++, en utilisant la bibliothèque CGAL. Les résultats de la reconstruction obtenus par cet algorithme sont très satisfaisants pour les topologies complexes des sections. En se basant sur les études que nous avons développées durant cette thèse, nous espérons pouvoir fournir un fondement solide pour le processus d'acquisition et de reconstruction des données échographiques afin d'avoir un logiciel fiable pour les diagnostics.

Mes travaux de recherche s'inscrivent dans le domaine de la recherche d'information (RI) dont l'objectif est de permettre à un utilisateur de trouver de l'information répondant à son besoin au sein d'un volume important d'informations. Les recherches en RI ont été tout d'abord orientées système. Elles sont restées très longtemps axées sur l'appariement pour évaluer la correspondance entre les requêtes et les documents ainsi que sur l'indexation des documents et de requêtes pour obtenir une représentation qui supporte leur mise en correspondance. Cela a conduit à la définition de modèles théoriques de RI comme le modèle vectoriel ou le modèle probabiliste. L'objectif initialement visé a été de proposer un modèle de RI qui possède un comportement global le plus efficace possible. La RI s'est longtemps basée sur des hypothèses simplificatrices notamment en considérant un type unique d'interrogation et en appliquant le même traitement à chaque interrogation. Le contexte dans lequel s'effectue la recherche a été ignoré. Le champ d'application de la RI n'a cessé de s'étendre notamment grâce à l'essor d'internet. Le volume d'information toujours plus important combiné à une utilisation de SRI qui s'est démocratisée ont conduit à une diversité des situations. Cet essor a rendu plus difficile l'identification des informations correspondant à chaque besoin exprimé par un utilisateur, marquant ainsi les limites des approches de RI existantes. Face à ce constat, des propositions ont émergé, visant à faire évoluer la RI en rapprochant l'utilisateur du système tels que les notions de réinjection de pertinence utilisateur ou de profil utilisateur. Dans le but de fédérer les travaux et proposer des SRI offrant plus de précision en réponse au besoin de l'utilisateur, le domaine de la RI contextuelle a récemment émergé. L'objectif est de différencier les recherches au niveau des modèles de RI en intégrant des éléments de contexte susceptibles d'avoir une influence sur les performances du SRI. La notion de contexte est vaste et se réfère à toute connaissance liée à la recherche de l'utilisateur interrogeant un SRI. Mes travaux de recherche se sont orientés vers la prise en compte des éléments de contexte que sont le domaine de l'information, la structure de l'information et l'utilisateur. Ils consistent, dans le cadre de trois premières orientations, à proposer des modèles qui intègrent chacun de ces éléments de contexte, et, dans une quatrième orientation, d'étudier comment adapter les processus à chaque recherche en fonction de son contexte. Différents projets européens et nationaux ont servi de cadre applicatifs à ces recherches et ainsi à valider nos propositions. Mes travaux de recherche ont également fait l'objet de développements dans différents prototypes et ont permis le déroulement de thèses de doctorat et stages de recherche.

Computational reflection is a fundamental mechanism in object oriented languages. Reflection has proved useful in many contexts, such as in the design of development environments, language extension, and the dynamic, unanticipated adaptation of running systems We identify three problems with the current approach to reflection in object oriented languages: partial behavioral reflection needs to be anticipated, structural reflection is limited to the granularity of a method, and behavioral reflection cannot be applied to the whole system. To address these problems, we extend structural reflection to cover sub-method elements and present how sub-method structural reflection supports unanticipated partial behavioral reflection. We add the concept of context to represent meta-level execution and show how this allows behavioral reflection to be applied even to system classes. We describe an implementation in Smalltalk. Benchmarks validate the practicability of our approach. In addition, we present an experimental evaluation in which we show how the system is used for dynamic analysis. We realize dynamic feature analysis by annotating the sub-method structure of the system directly to denote features instead of recording full execution traces.

Les réseaux des capteurs sans fil sont considérés comme une alternative aux réseaux câblés afin de permettre l'installation dans des zones peu accessibles. Par conséquent, de nouveaux protocoles ont été conçus pour supporter le manque des ressources qui est spécifique à ce type de réseau. La communication entre les nœuds est réalisée par des protocoles spécifiques pour la gestion efficace de l'énergie. La gestion des données collectées par ces nœuds doit être également prise en compte car la communication entre les nœuds engendre un coût non négligeable en termes d'énergie. De plus, l'installation de ce type de réseau dans des régions lointaines facilite les attaques sur la structure des réseaux ainsi que sur les données collectées. Les mesures de sécurité envisagées amènent des coûts d'énergie supplémentaires. Un aspect souvent négligé concerne le cas où un nœud ne peut pas communiquer avec la station de base (sink node) qui collectionne et traite les données. Cependant, les nœuds continuent à accumuler des informations en suivant les plans de collection. Si la situation continue, l'espace de mémoire (storage) diminue à un point où la collection de nouvelles données n'est plus possible.Nous proposons des mécanismes pour la réduction contrôlée de données en considérant leur priorité relative. Les données sont divisées dans des unités auxquelles un niveau d'importance est alloué, en fonction des considérations d'utilité et de missions qui les utilisent. Nous proposons un ensemble de primitives (opérations) qui permettent la réduction d'espace de stockage nécessaire, tout en préservant un niveau raisonnable de résolution des informations collectées. Pour les larges réseaux à multiple nœuds, nous proposons des mécanismes pour le partage de données (data load sharing) ainsi que la redondance. Des algorithmes ont été proposés pour évaluer l'efficacité de ces techniques de gestion de données vis-à-vis de l'énergie nécessaire pour transférer les données.A travers des simulations, nous avons validé le fait que les résultats sont très utiles dans les cas à mémoire limitée (wireless nades) et pour les communications intermittentes.