La recherche proposée est orientée vers l'étude de descriptions verbales d'itinéraires dans le but de géolocaliser des itinéraires décrits au sein de systèmes géo-référencés, avec une application à un contexte de course d'orientation dans un environnement naturel. Il s'agit explicitement de faire un lien conceptuel, structurel et logique entre une description verbale d'itinéraire et une représentation spatialisée. Une étude des descriptions verbales d'itinéraire produites lors d'expériences de course d'orientation a permis de définir une modélisation formelle par extraction des informations statiques et dynamiques d'un itinéraire décrit. La représentation logique dérivée s'appuie sur un modèle de graphe où les entités de référence sont les repères et les actions de déplacement. Elle permet en particulier une confrontation avec les démarches usuelles de qualification d'itinéraires en milieu urbain. Cette modélisation sert ensuite de support à une proposition d'algorithme de recherche et de géolocalisation d'itinéraire développée à partir des principes des algorithmes de colonies de fourmis. La démarche de recherche est validée par un prototype expérimental qui combine une modélisation d'itinéraire avec une recherche de parcours optimal. Ce prototype est illustré par une série de tests expérimentaux et des études de performance.

Cette thèse traite de deux sujets indépendants. La première partie est consacrée à l'étude des algorithmes stochastiques. Dans un premier chapitre introductif, je présente l'algorithme de [55] dans un parallèle avec l'algorithme de Newton pour l'optimisation déterministe. Ces quelques rappels permettent alors d'introduire les algorithmes stochastiques aléatoirement tronqués de [21] qui sont au cœur de cette thèse. La première étude de cet algorithme concerne sa convergence presque sûre qui est parfois établie sous des hypothèses assez changeantes. Ce premier chapitre est l'occasion de clarifier les hypothèses de la convergence presque sûre et d'en présenter une preuve simplifiée. Dans le second chapitre, nous poursuivons l'étude de cet algorithme en nous intéressant cette fois à sa vitesse de convergence. Plus exactement, nous considérons une version moyenne mobile de cet algorithme et démontrons un théorème centrale limite pour cette variante. Le troisième chapitre est consacré à deux applications de ces algorithmes à la finance : le premier exemple présente une méthode de calibration de la corrélation pour les modèles de marchés multidimensionnels alors que le second exemple poursuit les travaux de [7] en améliorant ses résultats. La seconde partie de cette thèse s'intéresse à l'évaluation des options parisiennes en s'appuyant sur les travaux de Chesney, Jeanblanc-Picqué, and Yor [23]. La méthode d'évaluation se base sur l'obtention de formules fermées pour les transformées de Laplace des prix par rapport à la maturité. Nous établissons ces formules pour les options parisiennes simple et double barrières. Nous étudions ensuite une méthode d'inversion numérique de ces transformées. Nous établissons un résultat sur la précision de cette méthode numérique tout à fait performante. A cette occasion, nous démontrons également des résultats liés à la régularité des prix et l'existence d'une densité par rapport à la mesure de Lebesgues pour les temps parisiens.

Ce travail est une contribution au développement des Algorithmes Evolutionnaires Multi-objectif. La hausse remarquable d'intérêt pour ces méthodes récentes constatée depuis la dernière décénie s'explique notamment par leur capacité de trouver une (bonne) approximation de l'ensemble des compromis de Pareto en un seul essai de l'algorithme, à la différence des approches traditionnelles pour l'optimisation multi-critère, qui ne trouvent qu'une solution-compromis à la fois (d'autant que cette solution dépend fortement du choix subjectif de certains paramètres). En effet, lors de la résolution des problèmes réels d'optimisation multi-critère, et en particulier, des problèmes de conception, il est souvent préférable de prendre la décision finale à partir des informations les plus complètes possibles, même si cela nécessite un effort de calcul supplémentaire. Dans cette thèse, deux problèmes de l'industrie automobile sont étudiés. Le premier concerne l'optimisation paramétrique de la forme d'un pare-choc de voiture, un problème a 10 objectifs issus de 3 domaines mécaniques: crash, acoustique et statique. Le second problème qui se pose lors du calibrage du moteur diesel Common Rail (rampe commune) consiste à minimiser la consommation spécifique du carburant ainsi que le bruit de la combustion tout en respectant les normes européennes de fonctionnement en terme de nuisances à l'environnement. Une tendance remarquable des Algorithmes Evolutionnaires est que ces méthodes pénètrent" aujourd'hui dans de nombreux nouveaux domaines d'application malgré l'absence de bases théoriques (notamment, de preuves de convergence) aussi solides que celles qu'on peut trouver pour des approches alternatives. Inspirée par cette observation, la motivation principale de ce travail était de contribuer au développement des Algorithmes Evolutionnaires Multi-objectif de façon à rendre leur application aux problèmes réels la plus efficace possible. Ainsi, une contribution originale de cette thèse consiste à répondre à un manque criant dans ce domaine, le manque de critère d'arrêt plus fin qu'une simple borne sur le nombre d'itérations. Le critère d'arrêt proposé dans ce travail est destiné à optimiser le rapport entre la qualité des solutions et le coût de calcul: dans la pratique c'est ce compromis qui est le plus souvent recherché. De même, un nouvel opérateur de croisement basé sur la relation de la dominance de Pareto est proposé et nous montrons l'accélération de la progression vers la surface des compromis optimaux qu'il apporte.

Les circuits cryptographiques, parce qu'ils contiennent des informations confidentielles, font l'objet de manipulations frauduleuses, appelées communément attaques, de la part de personnes mal intentionnées. Plusieurs attaques ont été répertoriées et analysées. Parmi elles, les attaques DPA (Differential Power Analysis), DEMA (Differential Electromagnetic Analysis), DBA (Differential Behavior Analysis) et les attaques en probing forment la classe des attaques par corrélation et sont considérés comme les plus redoutables car elles permettent de retrouver, à moindre coût, les clefs de chiffrement des algorithmes cryptographiques. Les concepteurs de circuits sécurisés ont été donc amené à ajouter des parades, appelées contre-mesures, afin de protéger les circuits de ces attaques. Ces contremesures doivent impacter au minimum les performances et le coût du circuit. Dans cette thèse, nous nous intéressons dans un premier temps aux attaques par corrélation, le principe de ces attaques est décrit ainsi que les principales contre-mesures pour y parer. Un formalisme décrivant de manière unique ces attaques est aussi proposé. Dans un deuxième temps, nous étudions les outils d'évaluation sécuritaires qui permettent d'estimer la résistance des circuits intégrés face aux attaques par corrélation. Après un état de l'art sur les outils existants, nous décrivons notre outil basé sur une recherche de corrélations entre le modèle du concepteur et le modèle qui peut être prédit par un attaquant. L'analyse de corrélations permet de déterminer les bits les plus sensibles pour mener à bien une attaque. Cet outil est intégré dans le flot de conception permettant ainsi d'évaluer la résistance des algorithmes cryptographiques au niveau RTL (Register Transfer Level) et portes.

Internet ainsi que tous les moyens numériques modernes disponibles pour communiquer, s'informer ou se divertir génèrent des données en quantités de plus en plus importantes. Dans des domaines aussi variés que la recherche d'information, la bio-informatique, la linguistique computationnelle ou la sécurité numérique, des méthodes automatiques capables d'organiser, classifier, ou transformer des téraoctets de données apportent une aide précieuse. L'apprentissage artificiel traite de la conception d'algorithmes qui permettent d'entraîner de tels outils à l'aide d'exemples d'apprentissage. Utiliser certaines de ces méthodes pour automatiser le traitement de problèmes complexes, en particulier quand les quantités de données en jeu sont insurmontables pour des opérateurs humains, paraît inévitable. Malheureusement, la plupart des algorithmes d'apprentissage actuels, bien qu'efficaces sur de petites bases de données, présentent une complexité importante qui les rend inutilisables sur de trop grandes masses de données. Ainsi, il existe un besoin certain dans la communauté de l'apprentissage artificiel pour des méthodes capables d'être entraînées sur des ensembles d'apprentissage de grande échelle, et pouvant ainsi gérer les quantités colossales d'informations générées quotidiennement. Nous développons ces enjeux et défis dans le Chapitre 1. Dans ce manuscrit, nous proposons des solutions pour réduire le temps d'entraînement et les besoins en mémoire d'algorithmes d'apprentissage sans pour autant dégrader leur précision. Nous nous intéressons en particulier aux Machines à Vecteurs Supports (SVMs), des méthodes populaires utilisées en général pour des tâches de classification automatique mais qui peuvent être adaptées à d'autres applications. Nous décrivons les SVMs en détail dans le Chapitre 2. Ensuite, dans le Chapitre 3, nous étudions le processus d'apprentissage par descente de gradient stochastique pour les SVMs linéaires. Cela nous amène à définir et étudier le nouvel algorithme, SGD-QN. Après cela, nous introduisons une nouvelle procédure d'apprentissage : le principe du “Process/Reprocess”. Nous déclinons alors trois algorithmes qui l'utilisent. Le Huller et LaSVM sont présentés dans le Chapitre 4. Ils servent à apprendre des SVMs destinés à traiter des problèmes de classification binaire (décision entre deux classes). Pour la tˆache plus complexe de prédiction de sorties structurées, nous modifions par la suite en profondeur l'algorithme LaSVM, ce qui conduit à l'algorithme LaRank présenté dans le Chapitre 5. Notre dernière contribution concerne le problème récent de l'apprentissage avec une supervision ambigüe pour lequel nous proposons un nouveau cadre théorique (et un algorithme associé) dans le Chapitre 6. Nous l'appliquons alors au problème de l'étiquetage sémantique du langage naturel. Tous les algorithmes introduits dans cette thèse atteignent les performances de l'état-de-l'art, en particulier en ce qui concerne les vitesses d'entraînement. La plupart d'entre eux ont été publiés dans des journaux ou actes de conférences internationaux. Des implantations efficaces de chaque méthode ont également été rendues disponibles. Dans la mesure du possible, nous décrivons nos nouveaux algorithmes de la manière la plus générale possible afin de faciliter leur application à des tâches nouvelles. Nous esquissons certaines d'entre elles dans le Chapitre 7.

De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.

Cette thèse concerne le contrôle coopératif de systèmes multi-agents. Ce sujet a été largement étudié dans la littérature récente en raison de son grand nombre d'applications. Cette thèse propose des nouvelles conceptions de stratégies de contrôle collaboratif afin de réaliser une mission d'exploration sous-marine. En particulier, l'objectif final est de diriger une flotte de véhicules autonomes sous-marins, équipés de capteurs appropriés, jusqu'à l'emplacement d'une source de température, de polluants ou d'eau douce. Dans cette situation, il est pertinent de considérer les contraintes de communication entre véhicules qui sont décrites au moyen d'un graphe de communication. Les premières contributions traitent du développement des lois de commande d'une formation qui stabilisent la flotte vers des formations variant dans le temps, et qui, de plus, distribuent uniformément les véhicules le long de la formation. Enfin, le problème de recherche d'une source est abordé par l'interprétation de la flottille de véhicules comme un réseau de capteurs mobiles. En particulier, il est démontré que les mesures recueillies par la flotte de véhicules permettent d'estimer le gradient de concentration de la quantité d'intérêt. En suivant cette idée, un algorithme distribué basé sur des algorithmes de consensus est proposé pour estimer la direction du gradient d'une distribution de signal.

Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.

Nous nous intéressons dans ce mémoire à des méthodes de parallélisation par découplage du système dynamique. Plusieurs applications numériques de nos jours conduisent à des systèmes dynamiques de grande taille et nécessitent des méthodes de parallélisation en conséquence pour pouvoir être résolues sur les machines de calcul à plusieurs processeurs. Notre but est de trouver une méthode numérique à la fois consistante et stable pour réduire le temps de la résolution numérique. La première approche consiste à découpler le système dynamique en sous-systèmes contenant des sous-ensembles de variables indépendants et à remplacer les termes de couplage par l'extrapolation polynomiale. Une telle méthode a été introduite sous le nom de schéma C (p, q, j), nous améliorons ce schéma en introduisant la possibilité à utiliser des pas de temps adaptatifs. Cependant, notre étude montre que cette méthode de découplage ne peut satisfaire les propriétés numériques que sous des conditions très strictes et ne peut donc pas s'appliquer aux problèmes raides présentant des couplages forts entre les sous-systèmes. Afin de pouvoir répondre à cette problématique de découplage des systèmes fortement couplés, on introduit le deuxième axe de recherche, dont l'outil principal est la réduction d'ordre du modèle. L'idée est de remplacer le couplage entre les sous-ensembles de variables du système par leurs représentations sous forme réduite. Ces sous-systèmes peuvent être distribués sur une architecture de calcul parallèle. Notre analyse du schéma de découplage résultant nous conduit à définir un critère mathématique pour la mise à jour des bases réduites entre les sous-systèmes. La méthode de réduction d'ordre du modèle utilisée est fondée sur la décomposition orthogonale aux valeurs propres (POD). Cependant, ne disposant pas à priori des données requises pour la construction de la base réduite, nous proposons alors un algorithme de construction incrémentale de la base réduite permettant de représenter le maximum des dynamiques des solutions présentes dans l'intervalle de simulation. Nous avons appliqué la méthode proposée sur les différents systèmes dynamiques tels que l'exemple provenant d'une EDP et celui provenant de l'équation de Navier Stokes. La méthode proposée montre l'avantage de l'utilisation de l'algorithme de découplage basé sur la réduction d'ordre. Les solutions numériques sont obtenues avec une bonne précision comparées à celle obtenue par une méthode de résolution classique tout en restant très performante selon le nombre de sous-systèmes définis.

Cette thèse a pour but d'estimer la position et la puissance de sources sonores ponctuelles à l'aide d'une antenne acoustique. Nous nous intéressons d'abord à la directivité des antennes acoustiques pondérées. On montre qu'une telle antenne, appelée antenne conventionnelle, même si elle est à directivité optimale, est inutilisable pour localiser plusieurs sources sonores. Des traitements adaptatifs d'antenne sont donc exigés et les méthodes dites à haute résolution sont introduites. Elles sont basées sur l'estimation de la matrice de covariance des signaux issus des capteurs et présentent l'avantage de s'affranchir des limitations naturelles du traitement d'antenne conventionnel. Cependant, ces méthodes nécessitent l'emploi d'un modèle de propagation et sont donc par nature peu robustes aux erreurs de modèle, ce qui peut être parfois un handicap et dégrader leurs performances. Par la suite, nous présentons une nouvelle méthode de séparation des sources utilisant une représentation parcimonieuse des signaux. Nous montrons que ses performances sont meilleures que celles obtenues par les méthodes à haute résolution et notre algorithme parvient à une bonne résolution spatiale, même sous des conditions défavorables. Cette méthode est appliquée aux sources corrélées et décorrélées, à bande étroite et à large bande, en champ proche et en champ lointain. Pour finir, nous présentons des méthodes pour estimer la puissance des sources sonores. Des simulations numériques et des expérimentations en chambre anéchoïque sont effectuées afin de vérifier et de valider les analyses et les résultats théoriques