Ces dernières décennies, la spectroscopie moléculaire a bénéficié du progrès des spectromètres, notamment en terme de sélectivité et sensibilité, et de méthodes d'analyse et de calculs de chimie quantique toujours plus avancés. Désormais, la spectroscopie rotationnelle s'oriente vers l'analyse de systèmes moléculaires plus complexes caractérisés spectralement par une forte densité de raies. La congestion spectrale des espèces étudiées dans ma thèse s'explique non seulement par de faibles constantes rotationnelles mais aussi par la présence d'états vibrationnels excités à température ambiante, une forte richesse isotopique, un haut degré de splittings dus aux mouvements de grande amplitude ou encore par un paysage conformationnel complexe. Cette thèse illustre ainsi divers scénarii à travers les études du chlorure de thionyle, des nitrotoluènes et des méthoxyphénols. Les spectres rovibrationnels des bandes v2 et v5 des isotopologues du chlorure de thionyle ont été mesurés dans l'infrarouge lointain au synchroton SOLEIL et analysés en utilisant une approche semi-automatique basée sur des algorithmes évolutionnaires. Les isomères du nitrotoluène ont été ciblés pour leur intérêt défense comme traceurs d'explosif (TNT), les spectres de rotation pure ont été mesurés dans les régions micro-ondes en jet moléculaire et millimétrique à température ambiante. Le spectre millimétrique du 3-nitrotoluène était particulièrement faible et congestionné avec des splittings dus à la rotation interne très importants (jusqu'à plusieurs GHz) en raison d'une barrière de rotation très faible ( Vз=6.7659(24)cmˉ ¹). La limite de détection a été estimée et une liste de raies établie. Les spectres millimétriques des 2-nitrotoluène et 4-nitrotoluène ont également été partiellement analysés. Enfin, les méthoxyphénols émis lors de feux de biomasse ont également étudiés comme précurseurs d'aérosols organiques secondaires pour leur détection atmosphérique future. Associée à des calculs de chimie quantique, l'analyse du spectre millimétrique du 3-méthoxyphénol mesuré à température ambiante dans la région millimétrique a permis de déterminer la stabilité relative de quatre conformères. / In recent decades, molecular spectroscopy has benefited from the progress of spectrometers, particularly in terms of selectivity and sensitivity, and from the continuous advancement of the analysis methods and quantum chemistry calculations. Today, rational spectroscopy is moving towards the analysis of more complex molecular systems spectrally characterized by a high density of lines. The spectral congestion of the species studied in this thesis is not only explained by low rotational constants, but also by the presence of vibrational states excited at room temperature, a high isotopic richness, a high degree of line splitting due to large amplitude motions or by a complex conformational landscape. This thesis thus illustrates various scenarios through the studies of thionyl chloride, nitrotoluenes and methoxyphenols. The rovibrational spectra of the v2 and v5 bands of the isotopologues of thionyl chloride were measured in far-infrared at the SOLEIL synchroton and analyzed using a semi-automatic approach based on evolutionary algorithms. The isomers of nitrotoluene have been targeted for military application as explosive taggants (TNT), the pure rotation spectra were measured in the microwave region in molecular jet and in the millimeter-wave region at room temperature. The millimeter-wave spectrum of 3-nitrotoluene was especially weak and congested with very large internal rotation splittings (up to several GHz) due to a very weak rotational barrier (V3=6.7659(24)cmˉ ¹). The detection limit was estimated and a linelist established. The 2-nitrotoluene and 4-nitrotoluene millimeter-wave spectra have been also partially analyzed. Finally, methoxyphenols emitted during biomass fires have also been studied as they are secondary organic aerosol precursors for their future atmospheric detection. Combined with quantum chemistry calculations, the analysis of the millimeter-wave spectrum of the 3-methoxyphenol measured at room temperature permitted the relative stability of four conformers to be determined.

Le covoiturage se présente comme une solution de transport alternative qui vient soigner l’image environnementale, économique et sociétale de la voiture personnelle. Le problème du covoiturage dynamique consiste à élaborer en temps réel des tournées de véhicules optimisés, afin de répondre au mieux aux demandes instantanées de transport.C’est dans ce cadre que s’inscrivent nos travaux où l’optimisation et le temps réel sont les maître-mots. Étant donné la complexité exponentielle du problème, nous optons pour des méthodes approximatives pour le résoudre. Nous présentons notre première contribution en proposant une métaheuristique basée sur la recherche tabou. L'algorithme utilise un système de mémoire explicite et plusieurs stratégies de recherches développées pour éviter le piégeage par des optimums locaux. Ensuite, nous introduisons notre deuxième contribution qui se présente sous la forme d’une approche évolutionnaire supportée par un codage dynamique et basée sur des opérateurs génétiques contrôlés. La complexité exponentielle du problème nous amène à dévoiler notre troisième méthodologie, en proposant une approche évolutionnaire originale dans laquelle les chromosomes sont définis comme des agents autonomes et intelligents. Grâce à un protocole de négociation puissant, les Agents Chromosomes gèrent les opérateurs génétiques et orientent la recherche afin de trouver des solutions optimales dans un temps de calcul réduit. Dans la perspective d’une meilleure combinaison entre le covoiturage et les autres modes de transport, nous concevons un système baptisé DyCOS, intégrant nos approches et applications dédiées à la résolution du problème du covoiturage dynamique. / Carpooling is presented as an alternative transport solution that comes treat environmental image, economic and societal personal car. The dynamic carpooling problem is to develop real-time optimized touring vehicles to better respond to the instantaneous transport demands.Our work belongs within this context, where optimization and real time are the key words. Given the exponential complexity of the dynamic ridematching problem, we opt for the approximate methods to solve it. We present our first contribution by proposing a metaheuristic based on the multi-criteria tabu search. The proposed algorithm employs an explicit memory system and several searching strategies developed to avoid the entrapment by local solutions. Afterward, we introduce our second contribution which is in the form of an evolutionary approach supported by a dynamic coding and based on controlled genetic operators. However, the exponential complexity of the problem leads us to consider that a simple metaheuristics is not sufficient to solve effectively the problem of dynamic ridematching. It is with this in mind that we are unveiling our third solving methodology by developing an original evolutionary approach in which chromosomes are defined as autonomous and intelligent agents. Thanks to an accurate protocol negotiation, the Chromosomes Agents can control the genetic operators and guide search for finding optimal solutions within a reasonable period of time. With the prospect of a better combination between carpooling and other modes of transport, we design a system called DyCOS, integrating our approaches and applications dedicated to solving the problem of dynamic ridesharing.

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.

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.

L'optimisation multicritère de la cinématique de battement d'aile d'un mini-drône à ailes battantes est réalisée en vol de croisière. L'objectif est, pour différentes familles de cinématiques et pour différentes vitesses d'avancement, de trouver des solutions maximisant l'efficacité propulsive, minimisant l'écart à la portance cible et minimisant le moment aérodynamique. Nous avons choisi les algorithmes évolutionnaires pour résoudre ce problème multicritère pour leur simplicité d'implantation, leur flexibilité et leur bon rapport qualité des résultats/coût de calcul. En raison de la nature multicritère du problème, il existe un ensemble de solutions optimales et non pas une unique solution au problème, ce qui pose la question de la maniere de visualiser, d'analyser et d'extraire une solution satisfaisante parmi le groupe de solutions Pareto optimales. Nous avons identifié des methodes simples susceptibles d'aider a accomplir cette tâche, la "Scatter-Plot Matrix Method" pour visualiser les surfaces et ensembles de Pareto, l'utilisation d'une régression multivariée pour établir le lien entre paramètres cinématiques et critères optimisés, la méthode des normes Lp pour identifier une solution compromis au sein de la surface de Pareto, les arbres de décision pour trouver les paramètres de la cinématique auxquels le voisinage de la solution compromis est sensible et les cartes de Kohonen pour étudier la structure de ce voisinage. Ces différents outils nous ont permis, pour chaque famille de cinématiques (dièdre, dièdre et tangage, dièdre et tangage à deux panneaux), d'identifier une solution compromis et les paramètres cinématiques qui impactent le plus le voisinage du point compromis. Les caractéristiques de chaque solution compromis ont ete comparées à des mesures de puissance et de coefficients de traînée faites sur des oiseaux en vol de croisiere, et la légitimité d'appliquer un modèle linéarisé dans le cas de cette solution compromis est mise à l'épreuve en calculant des nombres adimensionés caractéristiques comme le nombre de Strouhal ou la fréquence réduite dont les petites valeurs attestent d'un cas favorable à une approche linéarisée. Puis, la comparaison de la fréquence de battement d'aile obtenue à celle d'un oiseau géométriquement similaire est faite, et elle montre que plus la cinématique est riche plus cette fréquence de battement se rapproche de celle de l'oiseau en question, ce qui constitue un résultat encourageant pour notre approche.

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.

Actuellement, la gestion des services de transport public change, passe d un niveau d échelle à un autre, se décentralise nationalement et s élargit localement. Ainsi, les Régions ont vu leurs compétences s élargir en termes d organisation des transports, créant ainsi de nouveaux problèmes de gestion. C est face à ces interrogations nouvelles que notre travail trouve sa place, en proposant une modélisation adaptée à la fois aux modifications permanentes de la mobilité quotidienne et aux nouvelles échelles d application de la gestion des transports. Nous nous sommes plus spécifiquement penché sur l étape de la génération de trafic, (ou modélisation du processus de choix à l origine du déplacement effectué par l individu), négligée jusqu ici dans son approche géographique. Traitée jusqu alors sous l angle de l économie des transports, la modélisation de la génération de trafic occultait un aspect géographique important de sa conception : le zonage de l aire d étude, dont dépend la quantification des déplacements. Nous nous proposons ici de réaliser dans sa totalité la modélisation de l étape de génération de trafic sur la Région de Franche-Comté. Il s agit tout d abord de comprendre et délimiter notre périmètre d étude ; puis d élaborer un zonage pertinent en fonction de notre problématique de gestion ; pour finalement quantifier les déplacements sur les zones créées.

Les travaux présentés dans cette thèse visent à proposer des méthodes permettant de résoudre un problème de Transport à la Demande multicritère. Le premier travail réalisé dans cette thèse est l'étude d'un problème de Dial-a-Ride (DARP) statique multicritère. Trois critères qui peuvent être conflictuels ont été définis : le premier consiste à minimiser le coût de transport, le deuxième critère consiste à minimiser l'insatisfaction des passagers et enfin le troisième critère consiste à minimiser la quantité de CO2 émise par l'ensemble des véhicules. Nous avons développé une méthode évolutionnaire NSGA-II pour chercher un ensemble approximatif d'optimas de Pareto. Le second travail réalisé est l'étude d'un problème d'Optimal Timing dans une tournée. Ce problème consiste à calculer les dates de début de service optimales des points d'arrêts d'une tournée afin de minimiser l'insatisfaction des passagers. Le dernier travail de cette thèse a porté sur l'étude d'un problème de Transport à la Demande dynamique dans lequel de nouvelles requêtes à traiter arrivent en cours de journée. Deux méthodes ont été proposées pour résoudre ce problème : la première est une heuristique d'insertion rapide et la seconde est une méthode arborescente tronquée connue sous le nom de Recovering Beam Search. / The work presented in this thesis aims to propose methods to solve a multicriteria dial-a-ride problem (DARP). Three objective functions that have to be optimized in order to measure the potential efficiency of the DARP solution on different aspects : the cost for the transportation operator, the quality of service for users and the impact on the environment. The first work in this thesis is the study of static DARP for which a NSGA-II algorithm is developped to identify a good approximation of the Pareto optimal set. The second work deals with an optimal timing algorithm which computes pickup and delivery dates when the requests are sequenced on the vehicles, the objective is to minimize the total customer' dissatisfaction. The last problem studied in this thesis aims to solve the dynamic version of DARP for which two methods are proposed. The first one is a fast insertion heuristic based on an attractive index. However, the second methode uses a recovering beam search heuristic which unlike the insertion heuristic allows to modify the structure of the routes previously scheduled in order to schedule the new requests.