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.

Pour la résolution de problèmes d'ordonnancement d'ateliers de type flow-shop en industries pharmaceutiques et d'ateliers de type job-shop flexible, deux méthodes d'optimisation ont été développées : une méthode utilisant les algorithmes génétiques dotés d'un nouveau codage proposé et une méthode d'optimisation par essaim particulaire modifiée pour être exploitée dans le cas discret. Les critères retenus dans le cas de lignes de conditionnement considérées sont la minimisation des coûts de production ainsi que des coûts de non utilisation des machines pour les problèmes multi-objectifs relatifs aux industries pharmaceutiques et la minimisation du Makespan pour les problèmes mono-objectif des ateliers job-shop flexibles.Ces méthodes ont été appliquées à divers exemples d'ateliers de complexités distinctes pour illustrer leur mise en œuvre. L'étude comparative des résultats ainsi obtenus a montré que la méthode basée sur l'optimisation par essaim particulaire est plus efficace que celle des algorithmes génétiques, en termes de rapidité de la convergence et de l'approche de la solution optimale

Dans ce travail de thèse, nous présentons les travaux s'inspirant des fourmis réelles pour la résolution de problèmes en informatique. Nous proposons deux approches supplémentaires de ces nouvelles inspirations biomimétiques. La première reprend certains travaux en classification non supervisée et étend ces principes dans plusieurs directions. L'algorithme AntClass développé à cette occasion, est hybride dans le sens où la recherche du nombre de classes est effectué par des fourmis artificielles et qu'un algorithme classique en classification, les centres mobiles, est utilisé pour gommer les erreurs de classification inhérentes à une méthode stochastique telle que les fourmis artificielles. Après avoir souligné les ressemblances et différences entre les approches évolutionnaires et celles à base de population de fourmis et proposé un modèle commun, nous nous inspirons de la stratégie de recherche de nourriture d'une espèce de fourmis (Pachycondyla apicalis) pour résoudre des problèmes d'optimisation globale. L'apport de cette adaptation réside principalement dans sa simplicité. Nous appliquons l'algorithme qui en découle, appelé API, à des problèmes variés tels que l'optimisation de fonctions numériques, l'apprentissage de chaînes de Markov cachées ou des poids d'un réseau de neurones artificiels, ou encore à un problème d'optimisation combinatoire classique : le problème du voyageur de commerce.

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.

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée.

Un algorithme de simulation de l'interaction électrostatique est introduit, fondé sur un champ électrique fluctuant contraint par la loi de Gauss. Sa localité lui confère un coût linéaire en Monte Carlo.<br /><br />L'utilisation de conditions aux bords périodiques ne requiert pas de terme correctif, en contraste avec les méthodes usuelles. La simulation de systèmes quasi-bidimensionnels en est facilitée. Des surfaces quelconques à potentiel fixé peuvent être introduites.<br /><br />La loi de Gauss couple la dynamique des charges et du champ. La présence de charges libres accélère la relaxation du champ. La mobilité des charges est freinée par une « traînée de champ » qu'elles laissent en se déplaçant ; la modélisation quantitative de cet effet conduit à une méthode systématique pour le supprimer.

Dans cette thèse on a développé des algorithmes semi-implicites procédures partagées et monolithiques pour l'interaction entre un fluide gouverné par le modèle de Navier Stokes et une structure. Dans le premier chapitre, on présente un algorithme semi-implicite procédures partagées pour l'interaction entre un fluide et une structure gouvernée soit par les équations d'élasticité linéaire ou soit par le modèle de Saint-Venant Kirchhoff non linéaire. Dans le second chapitre, on propose un algorithme semi-implicite procédures partagées pour l'interaction entre un fluide et une structure de modèle linéaire et on montre un résultat de stabilité inconditionnelle en temps de l'algorithme. Un problème d'optimisation est résolu dans les deux algorithmes précédents, afin de satisfaire les conditions de continuité des vitesses et d'égalité des contraintes à l'interface. Durant les itérations de BFGS pour résoudre le problème d'optimisation, le maillage fluide reste fixe et la matrice fluide n'est factorisée qu'une seule fois, ce qui réduit l'effort de calcul. Dans le troisième chapitre, un algorithme semi-implicite monolithique pour l'interaction entre un fluide et une structure de modèle linéaire est proposé. L'algorithme utilise un maillage global pour le domaine fluide structure. La condition de continuité des vitesses à l'interface est automatiquement satisfaite et celle de l'égalité des contraintes n'apparaît pas explicitement dans la formulation faible. A chaque pas de temps on résout un système monolithique d'inconnues vitesse et pression définies sur le domaine global. Le temps CPU est réduit quand l'approche monolithique est utilisée à la place des procédures partagées.

Les Algorithmes Évolutionnaires (AE) sont des méthodes de recherche par itération de sélections et de variations aléatoires sur une population de solutions potentielles. <br />La Programmation Génétique (PG) est un AE qui permet la recherche automatique de programmes et qui manipule des représentations complexes : arbres (PGA) ou listes de longueur variables (PGL). <br />Les variations aléatoires permettant de créer de nouveaux programmes peuvent être des modifications locales (mutations) ou des recombinaisons de programmes (croisements). <br />L'opérateur de croisement recombine aléatoirement des sous-parties de programmes sans tenir compte du contexte : c'est une opération «brutale» qui est une des causes supposées de la croissance incontrôlée de la taille des programmes. <br />Inspirés par la recombinaison homologue de l'ADN, nous définissons, le Croisement par Maximum d'Homologie (CMH) pour la PGL. <br />A partir d'une mesure de similarité entre les expressions à recombiner, le CMH favorise les échanges qui respectent les structures communes préexistantes. <br />La capacité du CMH à effectuer une recherche moins brutale et à permettre un contrôle précis de la taille des programmes est mise en évidence sur des problèmes classiques de PG comme l'approximation de fonctions par régression symbolique. <br />En partant des différents résultats obtenus, nous appliquons notre méthode à la résolution d'un problème réel : l'inversion des composantes atmosphériques. De plus, nous montrons comment, à coût constant, il est possible de rechercher des combinaisons de modèles inverses dont les performances sont supérieures aux modèles standards.

La thèse de Monsieur Jeunechamps est intitulée "Simulation numérique, à l'aide d'algorithmes thermomécaniques implicites, de matériaux endommageables pouvant subir de grandes vitesses de déformation. Application aux structures aéronautiques soumises à impact". Elle comporte neuf chapitres et deux annexes. La bibliographie compte 285 références. Les développements informatiques ont été implémentés dans le code de calcul par éléments finis Metafor, développé au sein du département LTAS-MC&T et MN²L de l'Université de Liège. Le travail est divisé en trois parties principales. La première partie (chapitres 2 à 4) concerne la description et la modélisation thermomécanique des phénomènes à dynamique rapide sans dégradation irréversible des propriétés du matériau utilisé. La deuxième partie (chapitres 5 à 7) est consacrée à l'étude du comportement des matériaux dits endommageables éventuellement soumis à rupture, c'est-à-dire des matériaux dont les propriétés se dégradent de façon irréversible au cours de la déformation. La troisième partie (chapitre 8) est une application à l'échelle industrielle des méthodes proposées tout au long de cet ouvrage. Le chapitre 2 propose un inventaire des lois constitutives des matériaux, permettant de décrire le comportement de la structure lors de sollicitations rapides. L'accent est mis sur les principales lois d'évolution de la limite élastique implémentées dans les codes de calcul commerciaux, ainsi que sur les variantes de ces lois d'évolution. L'aspect numérique de l'intégration thermomécanique de ces lois est également abordé. Le deuxième aspect abordé dans cette première partie concerne les algorithmes d'intégration temporelle des équations de conservation de la quantité de mouvement. Le chapitre 3 décrit les algorithmes d'intégration utilisés dans ce travail, en mettant l'accent sur l'aspect dynamique et le couplage thermomécanique des phénomènes à dynamique rapide. Le chapitre 4 présente quelques applications illustrant les méthodes de calcul utilisées et permettant la validation de l'implémentation des modèles programmés dans Metafor. Les comparaisons sont effectuées dans la mesure du possible par rapport à des données expérimentales quand celles-ci sont disponibles et également par rapport à des résultats issus de codes de calcul commerciaux. Le chapitre 5 présente une modélisation de la dégradation du matériau au cours de la déformation. En effet, le matériau, sous l'effet des sollicitations et des efforts résultants, perd de ses propriétés de résistance à l'effort, et ce, de manière irréversible. Il est alors endommagé. Dans ce travail, nous avons choisi d'utiliser la théorie de l'endommagement continu pour décrire ces phénomènes. Le chapitre 5 rappelle les fondements de cette théorie ainsi que les principales lois d'endommagement continu. Une méthode générale et originale d'intégration de ces modèles d'endommagement est également proposée. Une fois que la structure est soumise à de trop fortes sollicitations, la rupture consécutive à l'endommagement du matériau apparaît. Le chapitre 6 décrit la méthode numérique développée pour modéliser le déchirement d'une structure ainsi que les différents critères de rupture utilisés. Encore une fois, nous nous limitons à une approche phénoménologique et pragmatique : il ne s'agit pas ici d'implémenter des critères complexes multi-échelles. Cependant, la structure du code de calcul est conçue pour permettre aisément de telles extensions. Le chapitre 7 présente une série d'applications permettant de valider l'implémentation des lois d'endommagement et de rupture ainsi que la formulation proposée de la théorie d'endommagement. Nous étudierons également le coût CPU engendré par la modélisation de l'endommagement et de la rupture du matériau. Enfin, le chapitre 8 présente une application industrielle proposée par la société Techspace Aero S.A. Il s'agit de l'étude du flambement d'une aube de compresseur basse pression d'un moteur d'avion lors du contact accidentel de celle-ci avec le carter du moteur. Tous les développements présentés dans les chapitres précédents sont alors utilisés pour simuler au mieux le phénomène. Les apports principaux du travail sont les suivants : utilisation d'algorithmes thermomécaniques de type étagé, dont l'intégration temporelle des équations de conservation du mouvement prend en compte les effets d'inertie ; amélioration de la technique d'intégration des lois constitutives avec endommagement, utilisant la théorie de l'endommagement continu, par l'utilisation d'un algorithme itératif ; méthode unifiée de calcul de la matrice de raideur tangente matérielle analytique pour un matériau hypoélastique avec endommagement, selon la théorie de l'endommagement continu, dans le cadre thermomécanique ; couplage thermomécanique général des modèles d'endommagement et des lois constitutives à grandes vitesses de déformation ; utilisation d'algorithmes implicites thermomécaniques dans la modélisation de la déchirure de structure par la méthode d'érosion ; établissement d'une plate-forme numérique d'accueil permettant l'implémentation future de lois matérielles, avec ou sans endommagement, ainsi que de techniques de modélisation de propagation de fissure ; processus complet de description d'un phénomène d'impact, par la modélisation du comportement thermomécanique du matériau par des lois de comportement avec endommagement adaptées au phénomène étudié et l'utilisation d'algorithmes implicites couplés à une méthode de déchirure de la structure.

L'objectif de cette thèse est de proposer des méthodes fiables, efficaces et rapides pour minimiser des critères convexes apparaissant dans la résolution de problèmes inverses en imagerie. Ainsi, nous nous intéresserons à des problèmes de restauration/reconstruction lorsque les données sont dégradées par un opérateur linéaire et un bruit qui peut être non additif. La fiabilité de la méthode sera assurée par l'utilisation d'algorithmes proximaux dont la convergence est garantie lorsqu'il s'agit de minimiser des critères convexes. La quête d'efficacité impliquera le choix d'un critère adapté aux caractéristiques du bruit, à l'opérateur linéaire et au type d'image à reconstruire. En particulier, nous utiliserons des termes de régularisation basés sur la variation totale et/ou favorisant la parcimonie des coefficients du signal recherché dans une trame. L'utilisation de trames nous amènera à considérer deux approches : une formulation du critère à l'analyse et une formulation du critère à la synthèse. De plus, nous étendrons les algorithmes proximaux et leurs preuves de convergence aux cas de problèmes inverses multicomposantes. La recherche de la rapidité de traitement se traduira par l'utilisation d'algorithmes proximaux parallélisables. Les résultats théoriques obtenus seront illustrés sur différents types de problèmes inverses de grandes tailles comme la restauration d'images mais aussi la stéréoscopie, l'imagerie multispectrale, la décomposition en composantes de texture et de géométrie. Une application attirera plus particulièrement notre attention ; il s'agit de la reconstruction de l'activité dynamique en Tomographie par Emission de Positrons (TEP) qui constitue un problème inverse difficile mettant en jeu un opérateur de projection et un bruit de Poisson dégradant fortement les données observées. Pour optimiser la qualité de reconstruction, nous exploiterons les caractéristiques spatio-temporelles de l'activité dans les tissus.