Différentes composantes des systèmes de traduction automatique statistique sont considérées comme des problèmes d'optimisations. En effet, l'apprentissage du modèle de traduction, le décodage et l'optimisation des poids de la fonction log-linéaire sont trois importants problèmes d'optimisation. Savoir définir les bons algorithmes pour les résoudre est l'une des tâches les plus importantes afin de mettre en place un système de traduction performant. Plusieurs algorithmes d'optimisation sont proposés pour traiter les problèmes d'optimisation du décodeur. Ils sont combinés pour résoudre, d'une part, le problème de décodage qui produit une traduction dans la langue cible d'une phrase source, d'autre part, le problème d'optimisation des poids des scores combinés dans la fonction log-linéaire pour d'évaluation des hypothèses de traduction au cours du décodage. Le système de traduction statistique de référence est basé sur un algorithme de recherche en faisceau pour le décodage, et un algorithme de recherche linéaire pour l'optimisation des poids associés aux scores. Nous proposons un nouveau système de traduction avec un décodeur entièrement basé sur les algorithmes génétiques. Les algorithmes génétiques sont des algorithmes d'optimisation bio-inspirés qui simulent le processus de l'évolution naturelle des espèces. Ils permettent de manipuler un ensemble de solutions à travers plusieurs itérations pour converger vers des solutions optimales. Ce travail, nous permet d'étudier l'efficacité des algorithmes génétiques pour la traduction automatique statistique. L'originalité de notre proposition est de proposer deux algorithmes : un algorithme génétique, appelé GAMaT, comme décodeur pour un système de traduction statistique à base de segments, et un algorithme génétique, appelé GAWO, pour l'optimisation des poids de la fonction log-linéaire afin de l'utiliser comme fonction fitness pour GAMaT. Nous proposons également, une approche neuronale pour définir une nouvelle fonction fitness pour GAMaT. Cette approche consiste à utiliser un réseau de neurones pour l'apprentissage d'une fonction qui combine plusieurs scores, évaluant différents aspects d'une hypothèse de traduction, combinés auparavant dans la fonction log-linéaire, et qui prédit le score BLEU de cette hypothèse de traduction. Ce travail, nous a permis de proposer un nouveau système de traduction automatique statistique ayant un décodeur entièrement basé sur des algorithmes génétiques / Different components of statistical machine translation systems are considered as optimization problems. Indeed, the learning of the translation model, the decoding and the optimization of the weights of the log-linear function are three important optimization problems. Knowing how to define the right algorithms to solve them is one of the most important tasks in order to build an efficient translation system. Several optimization algorithms are proposed to deal with decoder optimization problems. They are combined to solve, on the one hand, the decoding problem that produces a translation in the target language for each source sentence, on the other hand, to solve the problem of optimizing the weights of the combined scores in the log-linear function to fix the translation evaluation function during the decoding. The reference system in statistical translation is based on a beam-search algorithm for the decoding, and a line search algorithm for optimizing the weights associated to the scores. We propose a new statistical translation system with a decoder entirely based on genetic algorithms. Genetic algorithms are bio-inspired optimization algorithms that simulate the natural process of evolution of species. They allow to handle a set of solutions through several iterations to converge towards optimal solutions. This work allows us to study the efficiency of the genetic algorithms for machine translation. The originality of our work is the proposition of two algorithms: a genetic algorithm, called GAMaT, as a decoder for a phrase-based machine translation system, and a second genetic algorithm, called GAWO, for optimizing the weights of the log-linear function in order to use it as a fitness function for GAMaT. We propose also, a neuronal approach to define a new fitness function for GAMaT. This approach consists in using a neural network to learn a function that combines several scores, which evaluate different aspects of a translation hypothesis, previously combined in the log-linear function, and that predicts the BLEU score of this translation hypothesis. This work allowed us to propose a new machine translation system with a decoder entirely based on genetic algorithms

Les processeurs mono-coeurs traditionnels ne sont plus suffisants pour répondre aux besoins croissants en performance des fonctions avioniques. Les processeurs multi/many-coeurs ont emergé ces dernières années afin de pouvoir intégrer plusieurs fonctions et de bénéficier de la puissance par Watt disponible grâce aux partages de ressources. En revanche, tous les processeurs multi/many-coeurs ne répondent pas forcément aux besoins des fonctions avioniques. Nous préférons avoir plus de déterminisme que de puissance de calcul car la certification de ces processeurs passe par la maîtrise du déterminisme. L’objectif de cette thèse est d’évaluer le processeur many-coeur (MPPA-256) de Kalray dans un contexte industriel aéronautique. Nous avons choisi la fonction de maintenance HMS (Health Monitoring System) qui a un besoin important en bande passante et un besoin de temps de réponse borné.Par ailleurs, cette fonction est également dotée de propriétés de parallélisme car elle traite des données de vibration venant de capteurs qui sont fonctionnellement indépendants, et par conséquent leur traitement peut être parallélisé sur plusieurs coeurs. La particularité de cette étude est qu’elle s’intéresse au déploiement d’une fonction existante séquentielle sur une architecture many-coeurs en partant de l’acquisition des données jusqu’aux calculs des indicateurs de santé avec un fort accent sur le fluxd’entrées/sorties des données. Nos travaux de recherche ont conduit à 5 contributions:• Transformation des algorithmes existants en algorithmes incrémentaux capables de traiter les données au fur et mesure qu’elles arrivent des capteurs.• Gestion du flux d’entrées des échantillons de vibrations jusqu’aux calculs des indicateurs de santé,la disponibilité des données dans le cluster interne, le moment où elles sont consommées et enfinl’estimation de la charge de calcul.• Mesures de temps pas très intrusives directement sur le MPPA-256 en ajoutant des timestamps dans le flow de données.• Architecture logicielle qui respecte les contraintes temps-réel même dans les pires cas. Elle estbasée sur une pipeline à 3 étages.• Illustration des limites de la fonction existante: nos expériences ont montré que les paramètres contextuels de l’hélicoptère tels que la vitesse du rotor doivent être corrélés aux indicateurs de santé pour réduire les fausses alertes. / Traditional single-cores are no longer sufficient to meet the growing needs of performance in avionics domain. Multi-core and many-core processors have emerged in the recent years in order to integrate several functions thanks to the resource sharing. In contrast, all multi-core and many-core processorsdo not necessarily satisfy the avionic constraints. We prefer to have more determinism than computing power because the certification of such processors depends on mastering the determinism.The aim of this thesis is to evaluate the many-core processor (MPPA-256) from Kalray in avionic context. We choose the maintenance function HMS (Health Monitoring System) which requires an important bandwidth and a response time guarantee. In addition, this function has also parallelism properties. It computes data from sensors that are functionally independent and, therefore their processing can be parallelized in several cores. This study focuses on deploying the existing sequential HMS on a many-core processor from the data acquisition to the computation of the health indicators with a strongemphasis on the input flow.Our research led to five main contributions:• Transformation of the global existing algorithms into a real-time ones which can process data as soon as they are available.• Management of the input flow of vibration samples from the sensors to the computation of the health indicators, the availability of raw vibration data in the internal cluster, when they are consumed and finally the workload estimation.• Implementing a lightweight Timing measurements directly on the MPPA-256 by adding timestamps in the data flow.• Software architecture that respects real-time constraints even in the worst cases. The software architecture is based on three pipeline stages.• Illustration of the limits of the existing function: our experiments have shown that the contextual parameters of the helicopter such as the rotor speed must be correlated with the health indicators to reduce false alarms.

Cette thèse traite du développement d'algorithmes d'estimation en haute dimension. Ces algorithmes visent à résoudre des problèmes de discrimination et de classification, notamment, en incorporant un mécanisme de sélection des variables pertinentes. Les contributions de cette thèse se concrétisent par deux algorithmes, GLOSS pour la discrimination et Mix-GLOSS pour la classification. Tous les deux sont basés sur le résolution d'une régression régularisée de type "optimal scoring" avec une formulation quadratique de la pénalité group-Lasso qui encourage l'élimination des descripteurs non-significatifs. Les fondements théoriques montrant que la régression de type "optimal scoring" pénalisée avec un terme "group-Lasso" permet de résoudre un problème d'analyse discriminante linéaire ont été développés ici pour la première fois. L'adaptation de cette théorie pour la classification avec l'algorithme EM n'est pas nouvelle, mais elle n'a jamais été détaillée précisément pour les pénalités qui induisent la parcimonie. Cette thèse démontre solidement que l'utilisation d'une régression de type "optimal scoring" pénalisée avec un terme "group-Lasso" à l'intérieur d'une boucle EM est possible. Nos algorithmes ont été testés avec des bases de données réelles et artificielles en haute dimension avec des résultats probants en terme de parcimonie, et ce, sans compromettre la performance du classifieur. / This thesis deals with the development of estimation algorithms with embedded feature selection the context of high dimensional data, in the supervised and unsupervised frameworks. The contributions of this work are materialized by two algorithms, GLOSS for the supervised domain and Mix-GLOSS for unsupervised counterpart. Both algorithms are based on the resolution of optimal scoring regression regularized with a quadratic formulation of the group-Lasso penalty which encourages the removal of uninformative features. The theoretical foundations that prove that a group-Lasso penalized optimal scoring regression can be used to solve a linear discriminant analysis bave been firstly developed in this work. The theory that adapts this technique to the unsupervised domain by means of the EM algorithm is not new, but it has never been clearly exposed for a sparsity-inducing penalty. This thesis solidly demonstrates that the utilization of group-Lasso penalized optimal scoring regression inside an EM algorithm is possible. Our algorithms have been tested with real and artificial high dimensional databases with impressive resuits from the point of view of the parsimony without compromising prediction performances.

La segmentation des images est généralement l'étape la plus importante dans un système d'analyse d'images : dans l'aide au diagnostic en médecine, en navigation autonome des véhicules, etc. Toutes les tâches ultérieures de ces applications, comme l'extraction de primitives, la détection d'une position ou la reconnaissance d'un objet, dépendent fortement de la qualité de la segmentation. L'inconvénient majeur des algorithmes de segmentation actuels est leur incapacité à s'adapter aux différents types d'images. <br />L'apparition des "métaheuristiques" remonte aux années quatre-vingts. Ces algorithmes stochastiques d'optimisation globale peuvent être appliqués à tout problème, du moment qu'il est formulé sous la forme de l'optimisation de critère(s). Ces algorithmes sont inspirés par des analogies avec la physique (recuit simulé, recuit microcanonique), avec la biologie (algorithmes évolutionnaires) ou avec l'éthologie (colonies de fourmis, essaims particulaires). Ils se prêtent aussi à toutes sortes d'extensions, notamment en optimisation multiobjectif.<br />Afin de concevoir un système de segmentation qui permet d'avoir une meilleure qualité de la segmentation sur une grande variété d'images, nous formulons la segmentation comme un problème d'optimisation, mono-objectif dans un premier temps, puis multiobjectif. <br />Dans l'approche mono-objectif, nous adaptons plusieurs métaheuristiques au problème de la segmentation. Une application sur des images par résonance magnétique (IRM) cérébrales est ensuite réalisée. Cette adaptation des différentes métaheuristiques pour la segmentation nous permet de les comparer sur les plans suivants : la complexité, la vitesse de convergence, l'adaptabilité, et la reproductibilité des solutions. <br />Nous proposons ensuite une approche multiobjectif pour mieux résoudre le problème de la segmentation des images. Dans ce contexte, nous développons trois schémas de systèmes de segmentation adaptatifs : le premier est basé sur l'agrégation de critères, le second sur l'approche non-Pareto, et le troisième sur l'approche Pareto. Enfin, dans le cas particulier de la segmentation des espaces de ventricules cérébraux, nous appliquons différentes approches sur des IRM saines et d'autres pathologiques.

Avec la sévérisation des réglementations environnementales sur les émissions polluantes (normes Euro) des moteurs d'automobiles, la nécessité de maitriser les phénomènes de combustion a motivé le développement de la simulation numérique comme outil d'aide à la conception. Tenant compte de la complexité des phénomènes à modéliser, et de l'antagonisme des objectifs à optimiser, l'optimisation évolutionnaire multi-objectif semble être la mieux adaptée pour résoudre ce type de problèmes. Cependant, l'inconvénient principal de cette approche reste le coût très élevé en termes de nombre d'évaluations qui peut devenir très contraignant dans le contexte des optimisations réelles caractérisées par des évaluations très coûteuseL'objectif principal de ce travail de thèse est de réduire le coût global des optimisations du monde réel, en explorant la parallélisation des algorithmes évolutionnaires multi-objectifs, et en utilisant les techniques de réduction du nombre d'évaluations (méta-modèles).Motivés par le phénomène d'hétérogénéité des coûts des évaluations, nous nous proposons d'étudier les schémas d'évolution stationnaires asynchrones dans une configuration parallèle de type " maître-esclave ". Ces schémas permettent une utilisation plus efficace des processeurs sur la grille de calcul, et par conséquent de réduire le coût global de l'optimisation.Ce problème a été attaqué dans un premier temps d'un point de vue algorithmique, à travers une adaptation artificielle des algorithmes évolutionnaires multi-objectifs au contexte des optimisations réelles caractérisées par un coût d'évaluation hétérogène. Dans un deuxième temps, les approches développées et validées dans la première partie sur des problèmes analytiques, ont été appliquées sur la problématique de la combustion Diesel qui représente le contexte industriel de cette thèse. Dans ce cadre, deux types de modélisations ont été utilisés: la modélisation phénoménologique 0D et la modélisation multidimensionnelle 3D. La modélisation 0D a permis par son temps de retour raisonnable (quelques heures par évaluation) de comparer l'approche stationnaire asynchrone avec celle de l'état de l'art en réalisant deux optimisations distinctes. Un gain de l'ordre de 42 % a été réalisé avec l'approche stationnaire asynchrone. Compte tenu du temps de retour très coûteux de la modélisation complète 3D (quelques jours par évaluation), l'approche asynchrone stationnaire déjà validée a été directement appliquée. L'analyse physique des résultats a permis de dégager un concept intéressant de bol de combustion permettant de réaliser un gain en termes d'émissions polluantes.

Les Algorithmes Évolutionnaires (AEs) sont des méthodes de recherche inspirées par la théorie darwinienne de l'évolution, travaillant sur une population de solutions potentielles, par itération de phases de sélections et de variations aléatoires. La sélection d'une représentation, la définition des paramètres ou l'attribution de leurs propres valeurs ont une influence cruciale sur les performances de l'algorithme. Un choix qui ne s'accorde pas à la fonction de fitness peut rendre le problème plus difficile à résoudre. Trouver une configuration appropriée pour un AE est donc depuis longtemps un grand défi. Bien que les AEs soient reconnus comme des méthodes compétitives sur des problèmes de grande taille, ils sont sujets à un certain nombre de critiques tel celui du réglage/contrôle des paramètres. Par réglage, nous entendons l'approche qui consiste à trouver des valeurs satisfaisantes pour les paramètres avant l'exécution de l'algorithme. Dans cette thèse, nous fournissons des arguments qu'un jeu de paramètres constants durant l'exécution semble être inadéquat. Notre contribution au vaste domaine de l'optimisation concerne le réglage automatique des paramètres selon le problème traité. Dans la première partie, nous exposons la problématique du réglage/contrôle des paramètres ainsi que les principales heuristiques existantes. Dans la deuxième, nous proposons deux méthodes pour le contrôle dynamique des paramètres associés à la représentation des solutions. Dans la troisième, nous proposons l'algorithme évolutionnaire à états (SEA), une variante parallèle des AEs ; cette nouvelle approche gère simultanément plusieurs AEs afin de contrôler dynamiquement les paramètres au cours du processus d'optimisation. Dans la dernière partie, nous présentons une instanciation du SEA qui intègre différents taux de mutation afin d'adapter le meilleur taux à la recherche. Cette nouvelle instance est testée sur le problème du sac à dos multidimensionnel. Des résultats comparables ont été obtenus, ce qui prouve que le SEA est capable de contrôler dynamiquement le compromis exploration/exploitation.

Enjeux :<br />Le pétrole ne se manifeste à distance par aucune propriété physique permettant sa découverte. C'est pourquoi<br />l'exploration pétrolière consiste à imager par la méthode sismique les pièges susceptibles d'en contenir. Le but de la<br />migration, ou rétropropagation numérique des enregistrements sismiques, est de former une image des structures<br />géologiques en replaçant en profondeur les réflecteurs qui ont causé les échos enregistrés. Les variations de la<br />vitesse de propagation des ondes, de 1500 m/s dans l'eau à 6000 m/s et plus dans les roches sédimentaires<br />compactes, rendent cette tâche critique car un modèle de vitesse erroné donne une image très distordue. Le coût<br />énorme des forages effectués sur des structures fausses impose l'obtention d'images précises du sous-sol et donc la<br />détermination du champ des vitesses sismiques, surtout en contexte de piémonts lorsque les images sont peu<br />lisibles.<br />Positionnement du sujet :<br />Toutes les méthodes de détermination des vitesses exploitent la redondance des données sismiques : chaque portion<br />de réflecteur renvoie plusieurs échos correspondant à des couples source-récepteur dont le déport, la distance de la<br />source au récepteur, diffère. Certaines méthodes telles que la tomographie fonctionnent bien lorsque les structures<br />géologiques sont assez simples pour que les réflexions soient bien reconnaissables sur l'ensemble des<br />enregistrements, mais ce n'est pas le cas dans les piémonts. Nous avons donc choisi la migration itérative, dont le<br />principe est que, la Terre étant unique, les images obtenues avec les différents déports doivent être superposables.<br />Ce critère ne suffisant généralement pas à déterminer les vitesses correctes, il est nécessaire d'introduire des<br />informations géologiques. Pour l'optimisation du champ des vitesses, les méthodes de gradient étant<br />d'implémentation fort lourde, nous avons choisi un algorithme évolutionnaire pour sa simplicité, son adaptabilité, et<br />surtout son automaticité. De plus, la diversité de la population optimale donne une idée de l'incertitude qui entache<br />le résultat.<br />Résultats :<br />Parmi tous les champs de vitesses possibles, bien peu ont une géométrie géologiquement acceptables, d'où l'idée de<br />ne manipuler que des modèles satisfaisant au critère de coupe équilibrée. Une coupe est équilibrée lorsqu'elle est<br />compatible avec les hypothèses de conservation des épaisseurs et des longueurs mesurées le long des couches.<br />Dans une première partie, nous avons montré que l'on pouvait non seulement générer des modèles<br />géométriquement plausibles, mais aussi les optimiser relativement à des données de pendage de couches ou de<br />position de chevauchements disponibles à l'affleurement ou dans des puits. La seconde partie concernant<br />l'optimisation des vitesses n'a pu être reliée à la première. Dans cette seconde partie, nous avons représenté le<br />champ de vitesses par des grilles. Par le choix d'un algorithme évolutionnaire multi objectif, nous avons pu faire<br />coopérer efficacement les critères de semblance et de semblance différentielle qui, tous deux, mesurent l'invariance<br />de l'image migrée quant au déport. Nous avons amélioré le réalisme des solutions en les lissant dans la direction du<br />pendage. Enfin, nous avons extrait, des écarts à cette invariance, des corrections des grilles de vitesse qui<br />accélèrent notablement la convergence. Les résultats obtenus sur les données Marmousi, un cas synthétique<br />réaliste, sont satisfaisants. Sur les données réelles de Mer du Nord, le dôme de sel reste un problème non résolu par<br />les méthodes automatiques, mais ses environs sont bien imagés.<br />Transfert des résultats vers l'industrie :<br />Le principal intérêt de la méthode développée est son automaticité et sa souplesse. Son créneau est le dégrossisage<br />rapide de problèmes difficiles, avant qu'un interprétateur ne reprenne la main avec des méthodes interactives plus<br />poussées, mais aussi plus exigeantes en expérience et plus consommatrices de temps humain.

Thèse de doctorat--Informatique et réseaux--Paris--ENST, 2005. / Bibliogr. p. 165-177. Résumé.

Il est de plus en plus fréquent de faire appel à des opérateurs spécifiques en conception de circuits. Les opérateurs spécifiques peuvent être mis en oeuvre par des unités matérielles dédiées, en vue de réduire la taille du code, d'améliorer les performances et de réduire la surface du circuit. Dans cette thèse, nous proposons un flot de conception basé sur l'identification d'opérateurs spécifiques pour la synthèse de haut niveau. Les points clés de ce flot de conception sont l'énumération automatique et la sélection des opérateurs spécifiques à partir d'un code de l'application de haut niveau et la re-génération du code source intégrant les opérateurs spécifiques sélectionnés. Contrairement aux approches proposées précédemment, notre flot de conception est adaptable et est indépendant des outils de synthèse de haut niveau (il ne nécessite pas d'intervenir sur les algorithmes d'ordonnancement et de projection des outils de synthèse de haut niveau). Les résultats expérimentaux montrent que notre approche permet de réduire la surface du circuit de 19% en moyenne, et jusqu'à 37% dans certains cas, par rapport à une synthèse de haut niveau traditionnelle. La latence du circuit est réduite en moyenne de 22%, et atteint jusqu'à 59%. De plus, la taille du code est réduite de 74% en moyenne.

Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.