Le contenu de cette thèse est divisé en deux parties. La première partie de cette thèse porte sur l'étude d'approches heuristiques pour approximer des fronts de Pareto. Nous proposons un nouvel algorithme de recherche locale pour résoudre des problèmes d'optimisation combinatoire. Cette technique est intégrée dans un modèle opérationnel générique où l'algorithme évolue vers de nouvelles solutions formées en combinant des solutions trouvées dans les étapes précédentes. Cette méthode améliore les algorithmes de recherche locale existants pour résoudre le problème d'assignation quadratique bi- et tri-objectifs.La seconde partie se focalise sur les algorithmes d'ordonnancement dans un contexte non-préemptif. Plus précisément, nous étudions le problème de la minimisation du stretch maximum sur une seule machine pour une exécution online. Nous présentons des résultats positifs et négatifs, puis nous donnons une solution optimale semi-online. Nous étudions ensuite le problème de minimisation du stretch sur une seule machinedans le modèle récent de la réjection. Nous montrons qu'il existe un rapport d'approximation en O(1) pour minimiser le stretch moyen. Nous montrons également qu'il existe un résultat identique pour la minimisation du flot moyen sur une machine. Enfin, nous étudions le problème de la minimisation du somme des flots pondérés dans un contexte online. / The content of this thesis is divided into two parts. The first part of the thesis deals with the study of heuristic based approaches for the approximation Pareto fronts. We propose a new Double Archive Pareto local search algorithm for solving multi-objective combinatorial optimization problems. We embed our technique into a genetic framework where our algorithm restarts with the set of new solutions formed by recombination and mutation of solutions found in the previous run. This method improves upon the existing Pareto local search algorithm for bi-objective and tri-objective quadratic assignment problem.In the second part of the thesis, we focus on non-preemptive scheduling algorithms. Here, we study the online problem of minimizing maximum stretch on a single machine. We present both positive and negative theoretical results. Then, we provide an optimally competitive semi-online algorithm. Furthermore, we study the problem of minimizing stretch on a single machine in a recently proposed rejection model. We show that there exists an O(1)-approximation ratio for minimizing average stretch. We also show that there exists an O(1)-approximation ratio for minimizing average flow time on a single machine. Lastly, we study the weighted average flow time minimization problem in online settings. We present a mathematical programming based framework that unifies multiple resource augmentation. Using the concept of duality, we show that there exists an O(1)-competitive algorithm for solving the weighted average flow time problem on unrelated machines. Furthermore, we proposed that this idea can be extended to minimizing l_k norms of weighted flow problem on unrelated machines.

Réglage Coordonné de Tension dans les Réseaux de Distribution à l'aide de la Production Décentralisée<br />Les réseaux électriques français et européen connaissent depuis quelques années de profondes mutations dues à des bouleversements à l'échelle internationale des politiques énergétiques. Celles-ci conduisent aujourd'hui à une accélération du phénomène d'insertion de production décentralisée d'électricité, généralement désignée sous le terme de "génération d'énergie dispersée", ou GED, dans les réseaux de distribution. Dans cette thèse, une analyse des méthodes de réglage de tension existantes au niveau du réseau de transport, ainsi que des moyens de réglage actuels dans les réseaux de distribution, est à l'origine du développement d'un nouveau système de réglage coordonné de tension pour les réseaux de distribution (D-RCT) utilisant les GED. Ce réglage, basé sur la mutualisation des capacités individuelles des GED, permet de réguler la tension de certains nœuds stratégiques du réseau dénommés "nœuds pilotes" par une gestion optimale de l'énergie réactive. Cette gestion, qui repose sur une optimisation multi objectifs des consignes de tension des GED à l'aide de matrices de sensibilité, présente l'avantage de soulager l'action de réglage de tension du réseau de transport en limitant les transits de puissance réactive entre le transport et la distribution. La validation du D-RCT par application sur un réseau test et par une série d'études paramétriques, ainsi qu'une comparaison avec un réglage local auto – adaptatif, laissent entrevoir la possibilité d'une nouvelle stratégie de réglage de tension hybride.

La variété des concepts d'aéronef à voilure tournante n'a d'égal que l'étendue de leur hamp applicatif. Dès lors, se pose une question essentielle : quel concept est le plus adapté face à un certain nombre de missions ou de spécifications ? Une partie essentielle de la réponse réside dans l'étude des performances de vol et des impacts environnementaux de l'appareil. Le projet de recherche fédérateur C.R.E.A.T.I.O.N. pour " Concepts of Rotorcraft Enhanced Assessment Through Integrated Optimization Network " a pour but de mettre en place une plateforme numérique de calculs multidisciplinaires et multiniveaux capables d'évaluer de tels critères. La multidisciplinarité fait écho aux différentes disciplines associées à l'évaluation des giravions tandis que l'aspect multi-niveaux reflète la possibilité d'étudier un concept quelque soit l'état des connaissances sur ce dernier. La thèse s'inscrit dans ce projet. Une première implication est le développement de modèles de performances de vol et leur intégration dans des boucles de calcul multidisciplinaires. Au-delà de cet aspect de modélisation physique, la multidisciplinarité touche aussi le champ des mathématiques appliquées. Les méthodes d'optimisation multi objectifs multi paramètres, l'aide à la décision pour la sélection d'un optimum de meilleur compromis, l'exploration de bases de données, la création de modèles réduits sont autant de thématiques explorées dans cette thèse.

Les patients pharmaco-résistants sont des candidats pour la chirurgie de l'épilepsie. Le but de cette chirurgie est d'enlever les zones à l'origine de la crise (SOZ) sans créer de nouveaux déficits neurologiques. Pour localiser les SOZs, une des meilleures approches consiste à analyser des électroencéphalogrammes intracérébraux (iEEG). Toutefois, l'enregistrement des crises, qui sont des événements rares et critiques, est compliqué contrairement à l'enregistrement de décharges épileptiques intercritiques (IED), qui sont généralement très fréquentes et anodines. La prévision des SOZs, par estimation des régions à l'origine des IEDs, est donc une alternative très intéressante, et la question de savoir si l'estimation des régions IED peut être utile pour prédire les SOZs, a été au coeur de plusieurs études. Malgré des résultats intéressants, la question reste ouverte, notamment en raison du manque de fiabilité des résultats fournis par ces méthodes. L'objectif de cette thèse est de proposer une méthode robuste d'estimation des régions à l'origine des IEDs (notées LIED) par analyse d'enregistrements intracérébraux iEEG. Le point essentiel de cette nouvelle méthode repose sur la détermination d'un graphe de connectivité différentiel (DCG), qui ne conserve que les noeuds (électrodes) associées aux signaux iEEG qui changent de façon significative selon la présence ou l'absence d'IEDs. En fait, on construit plusieurs DCGs, chacun étant caractéristique d'une échelle obtenue après transformée en ondelettes. La fiabilitié statistiques des DCGs est obtenue à l'aide des tests de permutation. L'étape suivante consiste à mesurer les quantités d'information émise par chaque noeud, et d'associer à chaque connexion (arête) du graphe une orientation qui indique le transfert d'information du noeud source vers le noeud cible. Pour celà, nous avons introduit une nouvelle mesure nommée Local Information (LI), que nous avons comparée à des mesures classiques de graphes, et qui permet de définir de façon robuste les noeuds sources pour les graphes de chaque échelle. Les LIEDs sont finalement estimées selon une méthode d'optimisation multi-objectifs (de type Pareto, peu utilisée dans la communauté signal-image) construite à partir des valeurs des LI des DCG dans les différentes bandes de fréquences. La méthode proposée a été validée sur cinq patients épileptiques, qui ont subi une chirurgie d'exérèse et sont déclarés guéris. L'estimation des régions LIED a été comparée avec les SOZs détectées visuellement par l'épileptologue et celles détectées automatiquement par une méthode utilisant une stimulation destinée à provoquer des crises. La comparaison révèle des résultats congruents entre les SOZs et les régions LIED estimées. Ainsi, cette approche fournit des LIED qui devraient être des indications précieuses pour l'évaluation préopératoire en chirugie de l'épilepsie.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

Les systèmes de stabilisation du roulis implantés à bord des navires utilisent souvent des ailerons, pilotés par une loi de commande. Celle-ci est paramétrée en vitesse, mais ne prend pas en compte les variations de l'environnement : la direction, la hauteur et la période des vagues. Intégrer ces informations doit permettre l'amélioration des performances des navires. La première partie est consacrée à la modélisation de la dynamique du navire en roulis. La deuxième partie, est consacrée à la synthèse des lois de commande : dans un premier temps, une méthodologie de réglage est proposée, basée sur l'interprétation naturelle du cahier des charges par un problème d'optimisation multi-objectifs. Ensuite, un régulateur à gains programmés est calculé, sous forme polytopique, par la résolution de LMI. Les paramètres variant sont la vitesse et un paramètre de qualité de stabilisation. Les lois de commande calculées sont testées en simulation.

L'optimisation intervient dans de nombreuses applications IFPEN, notamment dans l'estimation de paramètres de modèles numériques à partir de données en géosciences ou en calibration des moteurs. Dans ces applications, on cherche à minimiser une fonction complexe, coûteuse à estimer, et dont les dérivées ne sont pas toujours disponibles. A ces difficultés s'ajoutent la prise en compte de contraintes non linéaires et parfois l'aspect multi-objectifs. Au cours de cette thèse, nous avons développé la méthode SQA (Sequential Quadradic Approximation), une extension de la méthode d'optimisation sans dérivées de M.J.D. Powell pour la prise en compte de contraintes à dérivées connues ou non. Cette méthode est basée sur la résolution de problèmes d'optimisation simplifiés basés sur des modèles quadratiques interpolant la fonction et les contraintes sans dérivées, construits à partir d'un nombre limité d'évaluations de celles-ci. Si la résolution de ce sous-problème ne permet pas une progression pour l'optimisation originale, de nouvelles simulations sont réalisées pour tenter d'améliorer les modèles. Les résultats de SQA sur différents benchmarks montrent son efficacité pour l'optimisation sans dérivées sous contraintes. Enfin, SQA a été appliqué avec succès à deux applications industrielles en ingénierie de réservoir et en calibration des moteurs. Une autre problématique majeure en optimisation étudiée dans cette thèse est la minimisation multi-objectifs sous contraintes. La méthode évolutionnaire Multi-Objective Covariance Matrix Adaptation, adaptée à la prise en compte des contraintes, s'est révélée très performante dans l'obtention de compromis pour la calibration des moteurs.

Les travaux qui sont abordés dans cette habilitation sont à la confluence de plusieurs de ces domaines de recherche. Ils concernent deux aspects principaux. Le premier est relatif à la reconnaissance structurelle de formes, en proposant deux contributions liées respectivement à la classification supervisée de graphes et à la recherche d'isomorphismes de sous-graphes. Le second concerne la prise en compte d'objectifs multiples en analyse d'images de documents, tant pour l'évaluation des performances des systèmes que pour leur optimisation. Dans les deux cas, les travaux sont appliqués à des problèmes d'analyse de documents, pour la reconnaissance et la localisation de symboles et pour la reconnaissance de courriers manuscrits. Nous proposons dans ce mémoire de faire une synthèse de ces contributions et de nos perspectives dans ces domaines, en positionnant celles-ci par rapport à l'état de l'art des différentes problématiques abordées.

Les enjeux énergétiques et environnementaux liés au réchauffement climatique amènent à généraliser la sobriété énergétique des bâtiments neufs ainsi que la production locale d’énergie à l’horizon 2020. Ce travail de thèse se concentre sur le secteur de la maison individuelle qui représente près de la moitié des logements neufs construits en France pour un volume d’environ 200000 unités par an.Le contexte de la maison individuelle à énergie positive 100 % solaire consiste à rechercher les compromis entre le niveau de performance du bâti qui détermine les besoins en énergie et la capacité des équipements à valoriser l’énergie solaire pour d’une part subvenir aux besoins en chaleur pour assurer le chauffage et la production d’eau chaude sanitaire, et d’autre part produire l’électricité nécessaire à l’éclairage et aux autres usages spécifiques (matériels électroménager, vidéo, etc.). Après un examen des différents concepts de bâtiments à énergie positive, une analyse a été menée pour identifier les solutions techniques de systèmes solaires combinés capables de fournir le double service de production d’eau chaude et de chauffage. Un modèle détaillé a été développé dans l’environnement Dymola et vérifié par inter-comparaison de modèles à l’échelle des composants. Un algorithme de contrôle original a été mis au point pour maximiser la performance globale du système.Une première étude paramétrique a montré que ce système est capable dans certaines conditions de couvrir près de 80 % des besoins en chaleur de la maison étudiée. Néanmoins, son dimensionnement demeure complexe et la recherche de compromis entre la sobriété de la maison et le dimensionnement des systèmes solaires thermiques et photovoltaïques doit s’appuyer sur un algorithme d’optimisation multi-objectifs adapté.Un chapitre est donc consacré à l’élaboration d’un algorithme d’optimisation multi- objectifs qui s’appuie sur la méthode des colonies d’abeilles virtuelles. Cette approche s’est avérée particulièrement pertinente vis à vis du problème (paramètres discrets, continus et qualitatifs) à caractère multiobjectifs(maximiser la valorisation du solaire thermique pour le chauffage d’une part et pour la production d’eau chaude d’autre part, minimiser la consommation d’énergie conventionnelle) et sous contrainte car seules les solutions à bilan d’énergie positif sur l’année seront retenues. L’algorithme d’optimisation développé ici a été confronté à une série de problèmes classiques et a démontré sa capacité à construire l’ensemble des solutions avec un nombre relativement faible d’évaluations du modèle.Le dernier chapitre présente deux applications de conception de maisons à énergie positive. La première se situe en région bordelaise alors que la seconde est située à proximité de Strasbourg. Ces deux conditions climatiques permettent de mettre en évidence la capacité de l’algorithme d’optimisation à proposer un éventail de solutions optimales présentant des compromis différents en termes de performance du bâti et de dimensionnement des équipements solaires. Enfin, un outil d’aide à la décision permet d’explorer les fronts optimaux pour dégager les solutions à retenir. / With energy-related and environmental climate change challenges, energy sobriety and local energy production are yet to become a mainstream practice for new buildings construction by 2020. This works focuses on single-family houses which in France represent half of new buildings constructions with 200000 new units new units each year. Near zero energy single-family houses with 100 % solar energy consists on compromising between performance of building envelope which defines energy needs and the ability for equipments to value free solar energy. Hence solar energy must be able to cover space heating and domestic hot waterdemands but also provide enough energy for lightning and other specific uses such as domestic appliances.After a literature review of near zero energy house concepts, an analysis was undertaken to providea clear view of solar combi-systems technical solutions with the ability to provide enough energyfor both needs : space heating and domestic hot water. Using Dymola environment a detailed modelwas developed and its consistency was checked by inter-comparison at component scale. An innovative control algorithm has been worked out to maximize the solar system’s global performance. Afirst parametric study has shown that the system was able to cover close to 80 % of house heat requirement. However sizing of a solar combi-system is a complex task and requires to find compromises between building sobriety, solar thermal energy efficiency, and photovoltaics solar energy sizing. Because of the problem’s complexity, a decision aid tool with an appropriate multi-criteria optimizationalgorithm is required.To that end a chapter is dedicated to the development of a multi-criteria optimization algorithm based on artificial bee colony behavior. This approach has proved to be quite effective to solve the problem and to handle continuous, discrete and qualitative decision variables. Chosen solution was constrained to have a positive energy balance and must maximize solar space heating and domestic fraction in a view to reduce total energy consumption. A validation process has also been set up and the developed optimization algorithm has proved its ability to solve standard problems with a fairlyshort number of evaluations. Adopted methodology was illustrated by two applications of the design phase of a near zero energydetached house. First one is located at Bordeaux an second one in Strasbourg. Selected climate conditions emphasize the ability of the proposed approach to identify a wide range of optimal solutions showing differences within the building’s performance as well as the solar system sizing. Lastly a decision aid tool allows to explore optimal front in a convenient way to shape adapted solutions.

Les problèmes d’optimisation multi-objectifs mènent souvent à considérer des ensembles de points non-dominés très grands à mesure que la taille et le nombre d’objectifs du problème augmentent. Générer l’ensemble de ces points demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence, ce qui produit un nombre très limité de solutions avec des temps de calcul réduits. Cela nécessite la plupart du temps une élicitation précise de paramètres. Cette étape est souvent difficile pour un décideur et peut amener à délaisser certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d’informations partielles. Nous présentons dans cette thèse plusieurs modèles de relations partielles de préférences. En particulier, nous nous sommes intéressés à la génération de l’ensemble des points non-dominés selon ces relations. Les expérimentations démontrent la pertinence de notre approche en termes de temps de calcul et qualité des points générés. / Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models.In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets.