Search

International audience; The exploration and exploitation (E&E) of a search spaceare two fundamental processes in artificial intelligence. Theinfluence of E&E aims to improve these processes. The explainability of E&E is also an important issue. This articleintroduces an E&E independent influence process and indicators for the explainability of E&E. Our experiments ongenetic and reinforcement algorithms confirm that (1) theproposed influence process has a positive impact on E&E,(2) the proposed indicators represent E&E more clearly; L'exploration et l'exploitation (E&E) d'un espace de recherche sont deux processus fondamentaux en intelligence artificielle. L'influence de l'E&E vise à améliorer ces processus. L'explicabilité de l'E&E est aussi un enjeu important. Cet article introduit un processus indépendant d'influence de l'E&E et des indicateurs pour l'explicabilité de l'E&E. Nos expérimentations sur les algorithmes génétique et par renforcement confirment que (1) le processus d'influence proposé a un impact positif sur l'E&E, (2) les indicateurs proposés représentent l'E&E avec plus de clarté.

The exploration and exploitation (E&E) of a search space are two fundamental processes in artificial intelligence. The influence of E&E aims to improve these processes. The explainability of E&E is also an important issue. This article introduces an E&E independent influence process and indicators for the explainability of E&E. Our experiments on genetic and reinforcement algorithms confirm that (1) the proposed influence process has a positive impact on E&E, (2) the proposed indicators represent E&E more clearly., L'exploration et l'exploitation (E&E) d'un espace de recherche sont deux processus fondamentaux en intelligence artificielle. L'influence de l'E&E vise à améliorer ces processus. L'explicabilité de l'E&E est aussi un enjeu important. Cet article introduit un processus indépendant d'influence de l'E&E et des indicateurs pour l'explicabilité de l'E&E. Nos expérimentations sur les algorithmes génétique et par renforcement confirment que (1) le processus d'influence proposé a un impact positif sur l'E&E, (2) les indicateurs proposés représentent l'E&E avec plus de clarté.

In this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches.; Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectifs, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectifs dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectifs basées sur la décomposition.

Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectifs, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectifs dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectifs basées sur la décomposition. In this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches.

Les résultats économiques des élevages porcins dépendent des prix du porc et des matières premièresalimentaires, ainsi que des performances techniques des ateliers de production. Les coûts d'alimentation, ainsique le poids d'abattage et le taux de muscle des pièces de chaque porc interviennent dans la construction de lamarge brute. Les stratégies alimentaires et de gestion des abattages des porcs à l'engrais sont donc des facteurs clés des résultats économiques. Différents modèles et outils ont été précédemment développés pour prédire les effets des stratégies alimentaires sur les performances techniques et les résultats économiques (lnraPorc, MOGADOR ... ). Ils ont montré qu'il est nécessaire de prédire la trajectoire de croissance de chaque porc pour estimer correctement les résultats de l'atelier. Ils ne permettent cependant pas d'identifier la stratégied'alimentation optimale dans un contexte économique donné. L'objectif de ce travail était de développer un outilcapable de maximiser la rentabilité de l'atelier d'engraissement dans différents contextes économiques, enproposant le meilleur compromis entre coût d'alimentation et niveau de performance des animaux.L'outil associe un modèle bioéconomique de l'atelier d'engraissement et une procédure d'optimisation de lamarge brute moyenne par porc. Le modèle bioéconomique simule la croissance de chaque porc selon sonpotentiel d'ingestion et de croissance et selon la stratégie d'alimentation. Il calcule la marge brute moyenne parporc engraissé et les impacts environnementaux de la production (par Analyse de Cycle de Vie).La procédure d'optimisation maximise la marge brute moyenne par porc en trouvant le poids cible à l'abattage(PVa), la durée maximale d'engraissement (Dmax) et la meilleure stratégie d'alimentation biphase (BP) en termesde composition de la ration (pourcentages de deux aliments A et B formulés pour couvrir respectivement 110% et90% du besoin en lysine digestible du porc moyen à 30 kg et 120 kg de poids vif) et de poids vif moyen auchangement de phase. Cette procédure utilise un algorithme évolutionnaire adapté à la résolution de problèmesnon linéaires et discontinus (CMA-ES, Covariance Matrix Adaptation Evolution Strategy). Après une phase devalidation des conditions d'utilisation de l'outil, différents scénarios ont été explorés. Dans le contexte économique retenu pour les simulations, l'outil permet d'augmenter la marge brute de 1,33€/porc en cherchant la meilleure BP, en comparaison à un scénario de référence (SR) représenta nt les pratiques habituelles. En ajoutant PVa et Dmax aux variables de décision, l'outil propose une solution qui améliore la marge brute de 2,81 €/porc par rapport à SR. L'outil permet de maximiser le résultat économique de l'atelier d'engraissement en cherchant la meilleure séquence alimentaire biphase et la meilleure gestion des abattages. Les futurs travaux viseront à réaliser une optimisation économique et environnementale conjointe de l'atelier d'engraissement.

Recent technical advances have facilitated the massive acquisition of data described by a large number of measurable properties (high dimensional datasets).New technologies have also enabled the continuous acquisition of data over time, providing users with possibly infinite data streams.The analysis of both high dimensional and streaming data by means of traditional clustering algorithm turn out to be troublesome.In the context of high dimensional data, common similarity measures used by clustering techniques tend to be less meaningful, leading to a degradation of the clustering quality.Moreover, in the case of data streams, the large volume of data does not allow to run several passes on the dataset.In order to overcome these problems, a variety of new approaches has been proposed in the literature.An important task that has been investigated in the context of high dimensional data is subspace clustering.This data mining task is recognized as more general and complicated than standard clustering, since it aims to detect groups of similar objects called clusters, and at the same time to find the subspaces where these similarities appear.Furthermore, subspace clustering approaches as well as traditional clustering ones have recently been extended to deal with data streams by updating clustering models in an incremental way.The different algorithms that have been proposed in the literature, rely on very different algorithmic foundations.Among these approaches, evolutionary algorithms have been under-explored, even if these techniques have proven to be valuable addressing other NP-hard problems.The aim of this thesis was to take advantage of new knowledge from evolutionary biology in order to conceive evolutionary subspace clustering algorithms for static datasets and dynamic data streams.Chameleoclust, the first algorithm developed in this work, takes advantage of the large degree of freedomprovided by bio-like features such as a variable genome length, the existence of functional and non-functional elements and mutation operators including chromosomal rearrangements.KymeroClust, our second algorithm, is a k-medians based approach that relies on the duplication and the divergence of genes, a cornerstone evolutionary mechanism.SubMorphoStream, the last one, tackles the subspace clustering task over dynamic data streams. It relies on two important mechanisms that favor fast adaptation of bacteria to changing environments, namely gene amplification and foreign genetic material uptake.All these algorithms were compared to the main state-of-the-art techniques, obtaining competitive results. Results suggest that these algorithms are useful complementary tools in the analyst toolbox.In addition, two applications called EvoWave and EvoMove have been developed to assess the capacity of these algorithms to address real world problems.EvoWave is an application that handles the analysis of Wi-Fi signals to detect different contexts.EvoMove, the second one, is a musical companion that produces sounds based on the clustering of dancer moves captured using motion sensors.; Les récents progrès techniques ont facilité l'acquisition massive de données décrites par un grand nombre de propriétés mesurables (jeu de données à forte dimensionnalité).De plus, le développement de nouvelles technologies a permis l'acquisition continue des données, fournissant aux utilisateurs des flux de données potentiellement infinis.Dans ces deux cas, les algorithmes traditionnels de clustering s'avèrent souvent insuffisants.En effet, les mesures de similarité, couramment utilisées par les techniques de clustering, rencontrent des limites lorsqu'elles sont utilisées dans des espaces à forte dimensionnalité. Ce phénomène conduit à une dégradation de la qualité du modèle de clustering obtenu.D'autre part, les grands volumes des flux de données ne permettent pas d'utiliser des techniques qui nécessitent l'exécution de plusieurs passes sur le jeu de données.Pour surmonter ces problèmes, de nouvelles approches ont été proposées dans la littérature.Une tâche importante qui a été étudiée dans le contexte de données à forte dimensionnalité est la tâche connue sous le nom de subspace clustering.Le subspace clustering est généralement reconnu comme étant plus compliqué que le clustering standard, étant donné que cette tâche vise à détecter des groupes d'objets similaires entre eux (clusters), et qu'en même temps elle vise à trouver les sous-espaces où apparaissent ces similitudes.Le subspace clustering, ainsi que le clustering traditionnel ont été récemment étendus au traitement de flux de données en mettant à jour les modèles de clustering de façon incrémentale.Les différents algorithmes qui ont été proposés dans la littérature, reposent sur des bases algorithmiques très différentes.Parmi ces approches, les algorithmes évolutifs ont été sous-explorés, même si ces techniques se sont avérées très utiles pour traiter d'autres problèmes NP-difficiles.L'objectif de cette thèse a été de tirer parti des nouvelles connaissances issues de l'évolution afin de concevoir des algorithmes évolutifs qui traitent le problème du subspace clustering sur des jeux de données statiques ainsi que sur des flux de données dynamiques.Chameleoclust, le premier algorithme développé au cours de ce projet, tire partie du grand degré de liberté fourni par des éléments bio-inspirés tels qu'un génome de longueur variable, l'existence d'éléments fonctionnels et non fonctionnels et des opérateurs de mutation incluant des réarrangements chromosomiques.KymeroClust, le deuxième algorithme conçu dans cette thèse, est un algorithme de k-medianes qui repose sur un mécanisme évolutif important: la duplication et la divergence des gènes.SubMorphoStream, le dernier algorithme développé ici, aborde le problème du subspace clustering sur des flux de données dynamiques.Cet algorithme repose sur deux mécanismes qui jouent un rôle clef dans l'adaptation rapide des bactéries à des environnements changeants: l'amplification de gènes et l'absorption de matériel génétique externe.Ces algorithmes ont été comparés aux principales techniques de l'état de l'art, et ont obtenu des résultats compétitifs.En outre, deux applications appelées EvoWave et EvoMove ont été développés pour évaluer la capacité de ces algorithmes à résoudre des problèmes réels.EvoWave est une application d'analyse de signaux Wi-Fi pour détecter des contextes différents.EvoMove est un compagnon musical artificiel qui produit des sons basés sur le clustering des mouvements d'un danseur, décrits par des données provenant de capteurs de déplacements.

This manuscript presents some of my research activities I have conducted as assistant researcher ("maitre de conférences") at the university Nice Sophia Antipolis and at the university Littoral Côte d'Opale since 2006. The synthesis of the presented works is in the field of single- and multi-objective combinatorial optimization using stochastic algorithms (metaheuristics such as evolutionary algorithms, local search algorithms, etc.). In particular, my research work focuses on the model of fitness landscapes, originally designed in the field of complex systems theory, which allows to study the dynamics of optimization algorithms. The main motivation of this work is to understand the relationship between an optimization algorithm and the problem to solve in order to explain and to predict the algorithms performance, and to design new more efficient algorithms based on this understanding.This document is divided in two main parts. The first one is on the local optima network which is a new model of fitness landscapes for the single-objective optimization. New properties of optimization problems are shown, as well as the prediction capacities of performance based on the estimation of these features. The second one is on the multi-objective optimization. The properties of such fitness landscapes are defined, and precisely analyzed with respect to algorithms performance. New multi-objective optimization methods are also proposed. Finally, this document concludes with broad perspectives for the research domain of fitness landscapes and more generally in the field of stochastic optimization.; Ce mémoire présente quelques-unes de mes activités de recherche que j'ai conduites depuis 2006 en tant que maître de conférences à l'Université Nice Sophia Antipolis puis à l'Université du Littoral Côte d'Opale. La synthèse des travaux présentés s'inscrit dans le domaine de l'optimisation mono-objective et multiobjective de problèmes combinatoires par des algorithmes stochastiques du type métaheuristique (algorithmes évolutionnaires, recherches locales, etc.). En particulier, mes travaux portent sur le modèle des paysages de fitness, modèle issu des sciences de la complexité, qui permet étudier la dynamique des algorithmes d'optimisation. La principale motivation de ces travaux est de comprendre la relation entre un algorithme d'optimisation et le problème à résoudre afin d'en expliquer et d'en prédire les performances et de concevoir de nouveaux algorithmes plus efficaces à partir de cette compréhension. Ce manuscrit se compose en deux parties principales. L'une porte sur le réseau des optima locaux qui est un nouveau modèle pour les paysages de fitness en optimisation mono-objective. De nouvelles propriétés des problèmes d'optimisation sont montrées, ainsi que les capacités de prédiction de performance à partir de l'estimation de ces propriétés. L'autre partie porte sur l'optimisation multiobjective. Les propriétés des paysages de fitness sont définies et précisément analysées en rapport avec les performances des algorithmes. De nouvelles méthodes d'optimisation multiobjective sont également proposées. Enfin, ce mémoire se termine par des perspectives pour le domaine des paysages de fitness et plus généralement en optimisation stochastique.

This manuscript presents some of my research activities I have conducted as assistant researcher ("maitre de conférences") at the university Nice Sophia Antipolis and at the university Littoral Côte d'Opale since 2006. The synthesis of the presented works is in the field of single- and multi-objective combinatorial optimization using stochastic algorithms (metaheuristics such as evolutionary algorithms, local search algorithms, etc.). In particular, my research work focuses on the model of fitness landscapes, originally designed in the field of complex systems theory, which allows to study the dynamics of optimization algorithms. The main motivation of this work is to understand the relationship between an optimization algorithm and the problem to solve in order to explain and to predict the algorithms performance, and to design new more efficient algorithms based on this understanding.This document is divided in two main parts. The first one is on the local optima network which is a new model of fitness landscapes for the single-objective optimization. New properties of optimization problems are shown, as well as the prediction capacities of performance based on the estimation of these features. The second one is on the multi-objective optimization. The properties of such fitness landscapes are defined, and precisely analyzed with respect to algorithms performance. New multi-objective optimization methods are also proposed. Finally, this document concludes with broad perspectives for the research domain of fitness landscapes and more generally in the field of stochastic optimization.; Ce mémoire présente quelques-unes de mes activités de recherche que j'ai conduites depuis 2006 en tant que maître de conférences à l'Université Nice Sophia Antipolis puis à l'Université du Littoral Côte d'Opale. La synthèse des travaux présentés s'inscrit dans le domaine de l'optimisation mono-objective et multiobjective de problèmes combinatoires par des algorithmes stochastiques du type métaheuristique (algorithmes évolutionnaires, recherches locales, etc.). En particulier, mes travaux portent sur le modèle des paysages de fitness, modèle issu des sciences de la complexité, qui permet étudier la dynamique des algorithmes d'optimisation. La principale motivation de ces travaux est de comprendre la relation entre un algorithme d'optimisation et le problème à résoudre afin d'en expliquer et d'en prédire les performances et de concevoir de nouveaux algorithmes plus efficaces à partir de cette compréhension. Ce manuscrit se compose en deux parties principales. L'une porte sur le réseau des optima locaux qui est un nouveau modèle pour les paysages de fitness en optimisation mono-objective. De nouvelles propriétés des problèmes d'optimisation sont montrées, ainsi que les capacités de prédiction de performance à partir de l'estimation de ces propriétés. L'autre partie porte sur l'optimisation multiobjective. Les propriétés des paysages de fitness sont définies et précisément analysées en rapport avec les performances des algorithmes. De nouvelles méthodes d'optimisation multiobjective sont également proposées. Enfin, ce mémoire se termine par des perspectives pour le domaine des paysages de fitness et plus généralement en optimisation stochastique.

This manuscript presents some of my research activities I have conducted as assistant researcher ("maitre de conférences") at the university Nice Sophia Antipolis and at the university Littoral Côte d'Opale since 2006. The synthesis of the presented works is in the field of single- and multi-objective combinatorial optimization using stochastic algorithms (metaheuristics such as evolutionary algorithms, local search algorithms, etc.). In particular, my research work focuses on the model of fitness landscapes, originally designed in the field of complex systems theory, which allows to study the dynamics of optimization algorithms. The main motivation of this work is to understand the relationship between an optimization algorithm and the problem to solve in order to explain and to predict the algorithms performance, and to design new more efficient algorithms based on this understanding.This document is divided in two main parts. The first one is on the local optima network which is a new model of fitness landscapes for the single-objective optimization. New properties of optimization problems are shown, as well as the prediction capacities of performance based on the estimation of these features. The second one is on the multi-objective optimization. The properties of such fitness landscapes are defined, and precisely analyzed with respect to algorithms performance. New multi-objective optimization methods are also proposed. Finally, this document concludes with broad perspectives for the research domain of fitness landscapes and more generally in the field of stochastic optimization., Ce mémoire présente quelques-unes de mes activités de recherche que j'ai conduites depuis 2006 en tant que maître de conférences à l'Université Nice Sophia Antipolis puis à l'Université du Littoral Côte d'Opale. La synthèse des travaux présentés s'inscrit dans le domaine de l'optimisation mono-objective et multiobjective de problèmes combinatoires par des algorithmes stochastiques du type métaheuristique (algorithmes évolutionnaires, recherches locales, etc.). En particulier, mes travaux portent sur le modèle des paysages de fitness, modèle issu des sciences de la complexité, qui permet étudier la dynamique des algorithmes d'optimisation. La principale motivation de ces travaux est de comprendre la relation entre un algorithme d'optimisation et le problème à résoudre afin d'en expliquer et d'en prédire les performances et de concevoir de nouveaux algorithmes plus efficaces à partir de cette compréhension. Ce manuscrit se compose en deux parties principales. L'une porte sur le réseau des optima locaux qui est un nouveau modèle pour les paysages de fitness en optimisation mono-objective. De nouvelles propriétés des problèmes d'optimisation sont montrées, ainsi que les capacités de prédiction de performance à partir de l'estimation de ces propriétés. L'autre partie porte sur l'optimisation multiobjective. Les propriétés des paysages de fitness sont définies et précisément analysées en rapport avec les performances des algorithmes. De nouvelles méthodes d'optimisation multiobjective sont également proposées. Enfin, ce mémoire se termine par des perspectives pour le domaine des paysages de fitness et plus généralement en optimisation stochastique.

This work focuses on the optimization of urban forms in relation to the solar potential. The goal is to improve our knowledge of best urban forms, firstly in order to derive guidelines for the urban planner, secondly to identify the relevant features of an urban development favorable to solar radiation. In this scope, an optimization tool based on an evolutionary algorithm has been implemented. It allows us to find the optimal positioning of volumes corresponding to buildings subjected to solar radiation. Different types of parameters are associated with buildings (height, orientation, location), while the urban context of the neighborhood can be seen in several ways: open, fixed (pre-existing neighborhood), or periodic. The latter representation considers the neighborhood as a set of identical cells repeated in each direction in order to build a continuum between the buildings subject to optimization and their environment. The optimization cases carried out seek to maximize sun exposure for latitudes between 40 and 60° N, different periods of time and built densities. An extension is further performed to investigate the neighborhoods minimizing energy requirements for heating. In all cases, the results show that there are many near-optimal configurations whose analysis can lead to the identification of general shapes taken by the district, depending on the optimization criterion.; Ce travail de thèse porte sur l'optimisation de formes urbaines par rapport au potentiel solaire. L’objectif est d’améliorer notre connaissance des meilleures formes urbaines, d’une part dans l’optique d’en tirer des règles ou des conseils pour l’aménageur, d’autre part pour identifier les composantes importantes d’un aménagement urbain favorable au rayonnement solaire. Pour cela, un outil d'optimisation reposant sur un algorithme évolutionnaire a été mis en place. Celui-ci permet de trouver le positionnement optimal de volumes correspondant à des bâtiments soumis au rayonnement solaire. Pour cela, différents types de paramètres sont associés aux bâtiments (hauteur, orientation, position), tandis que le contexte urbain du quartier peut être considéré de plusieurs manières : dégagé, fixe (quartier pré-existant), ou périodique. Cette dernière représentation considère le quartier comme un ensemble de cellules identiques qui se répètent dans chaque direction de manière à construire un ensemble homogène entre les bâtiments optimisés et leur environnement. Les essais d’optimisation effectués cherchent à maximiser l'exposition au soleil pour des latitudes comprises entre 40 et 60° N, différentes périodes de temps et densités bâties. Une extension est de plus réalisée pour étudier les quartiers minimisant les besoins en énergie pour le chauffage. Dans l’ensemble des cas, les résultats montrent qu’il existe de nombreuses configurations quasi-optimales dont l’analyse permet d’identifier des formes générales prises par le quartier en fonction du critère d’optimisation.

Object based image analysis is a rising research area in remote sensing. However, existing approaches heavily rely on the object construction process, mainly due to the lack of interaction between the two steps, i.e., Construction and identification.In this thesis, we focused on the study of the construction phase (i.e., segmentation) as a basis for the proposed approaches. The first proposed approach is based on a hierarchical semantic growth. This approach allows merging region-growing algorithms and Object Based Image Analysis approaches. Due to the dependency of the semantic growth on the seed class, we propose two adaptations of the approach on the most used class in the urban context, i.e., roadsand buildings. The second approach benefits of both multi-agent systems and genetic algorithms characteristics. It overcomes the threshold’s dependency of the proposed cooperative multi-agent system between an edge approach and a region approach. The genetic algorithm is used to automatically find building extraction parameters for each agent based on expert knowledge. The proposed approaches have been validated on a very high-resolution image of the urban area of Strasbourg., Avec l’avènement des images satellitaires à très haute résolution, les approches pixelliques ne donnant plus entière satisfaction ont été remplacées par les approches objets. Cependant, ces approches restent tributaires de la première étape qui permet le passage du pixel vers l’objet, à savoir l’étape de construction. L’architecture séquentielle de ces approches fait que les erreurs de l’étape de construction se répercutent sur l’étape d’identification. Il devient donc primordial de passer de cette architecture séquentielle vers une architecture itérative permettant la collaboration entre les étapes de construction et d’identification. Dans le cadre de cette thèse, nous nous sommes concentrés sur l’étude de l’étape de construction(i.e., la segmentation) comme base de départ pour les approches proposées. Nous avons proposé deux approches objets basées sur les techniques de segmentation les plus propices à la collaboration, à savoir les techniques régions et les techniques collaboratives région/contour. La première approche proposée se base sur une croissance sémantique hiérarchique. Elle permet de combiner les algorithmes de croissance de régions et les approches d’analyse d’images orientées objets. La croissance étant spécifique à la classe du germe de départ, nous avons proposé deux adaptations de l’approche sur les objets les plus rencontrés dans le contexte urbain, à savoir, les routes et les bâtiments. La deuxième approche utilise un algorithme évolutionnaire local permettant un paramétrage local des différents agents régions et contours évoluant au sein d’un système multi-agents.

National audience; Nous présentons une approche de smart fuzzing (frelatage intelligent) en boîte noire afin de détecter des vulnérabilités de type cross-site scripting (XSS) dans des applications web. L'intelligence est fournie par deux composants principaux : l'inférence de modèle et la génération automatique d'entrées malicieuses. Le premier est un "crawler" conscient du macro-état qui modèle l'application par une machine à états finis étendue, capturant la relation entre les paramètres d'entrée et les sorties (pages HTML). Le second, appelé fuzzing évolutionaire, est implémenté par algorithme génétique (AG). Afin de limiter le domaine de recherche de l'AG, nous introduisons un facteur additionnel, la grammaire d'entrées d'attaques afin de générer des entrées sous forme de chaînes de caractères qui sont malicieuses par nature, pour reproduire le comportement d'un attaquant. Un XSS est notamment caractérisé par une relation intrinsèque entre une entrée teintée et une sortie de l'application web. Comme nous faisons l'hypothèse de test en boîte noire, capturer précisément cette relation est une tâche difficile que nous résolvons en utilisant des techniques d'inférence de teinte. Grâce à ceci, nous pouvons - à la différence d'un fuzzing systématique - nous concentrer sur les transitions du modèle pour lesquelles cette relation semble vérifiée, en évitant intelligemment de fuzzer le système complet. L'AG automatise la génération des entrées en considérant les états de l'application et en évoluant intelligemment les entrées afin de révéler des vulnérabilités XSS, s'il y en a. Nous fournissons des preuves empiriques de l'intérêt de notre approche par des expérimentations avec des applications réelles et reportons des résultats encourageants.

We define and study a combinatorial optimization problem that models multi-path routing in a Network-on-Chip with guaranteed traffic. Based on time division multiplexing, the model allows to avoid collisions, deadlocks and livelocks in irregular network topologies, while minimizing latency. An extension of this multi-path problem is also presented that allows dynamic reconfigurable routing at execution time. In that case, independent sets of valid routes are pre-computed in such a way they can be interchanged during execution with no impact on the existing traffic, while reusing all the vacant time-slot resources. A time-expanded graph approach is retained for the solution process. First, we present a set of basic shortest paths computation operators. They can be a greedy parallel construction heuristic, neighborhood operators, or a modified Dijkstra algorithm for single path computation in pseudo-polynomial time. Then, operators are introduced and combined within two heuristic methods able to address both problems, that is, an iterated construction heuristic and a population based evolutionary algorithm. Experiments are done on a set of benchmarks representative of real life applications, they illustrate the accuracy of the method.; Nous définissons et étudions un problème d'optimisation combinatoire et un programme linéaire en nombres entiers, qui modélise le routage multi-chemin dans un réseau sur puce à garantie de trafic. Basé sur le multiplexage temporel et l'émission cyclique des messages, le modèle permet d'éviter les collisions, les blocages statiques et dynamiques dans des réseaux à topologie irrégulière, tout en minimisant les temps de latence. Une extension de ce problème de routage multi-chemin, qui permet une reconfiguration dynamique du routage au moment de l'exécution est également présentée. Dans ce cas, des ensembles indépendants de chemins valides sont pré-calculés de telle sorte qu'ils peuvent être inter-changés en cours d'exécution sans impact sur le trafic courant, tout en réutilisant tous les intervalles de temps dont les ressources sont vacantes ou libérées. L'approche du graphe spatio-temporel étendu est retenue dans les processus de résolution. Tout d'abord, nous présentons un ensemble d'opérateurs de base de calcul de plus courts chemins. Se sont une heuristique de construction parallèle gloutonne, un opérateur de voisinage, et un algorithme de Dijkstra modifié dans un graphe spatio-temporel étendu qui calcul un chemin unique dans un NoC occupé en temps pseudo-polynomial. Ensuite, pour résoudre l'ensemble des problèmes, les opérateurs sont introduits et combinés dans trois méthodes de recherche locale itérée capable de générer rapidement des solutions admissibles, un algorithme évolutionnaire à base de population solutions conférant une grande diversité à la recherche de solutions et un algorithme mémétique, tirant partie des avantages des deux précédents. Les expériences sont réalisées sur un ensemble d'instances d'applications réelles, et d'instances d'applications artificielles générées aléatoirement à partir des cas réels, pour illustrer les performances et la robustesse des méthodes de recherche.

This work presents a methodological approach aiming at analyzing and processing mission profiles and more generally environmental variables (e.g. solar or wind energy potential, temperature, boundary conditions) in the context of system design. This process constitutes a key issue in order to ensure system effectiveness with regards to design constraints and objectives. In this thesis, we pay a particular attention on the use of compact profiles for environmental variables in the frame of system level integrated optimal design, which requires a wide number of system simulations. In a first part, we propose a clustering approach based on partition criteria with the aim of analyzing mission profiles. This phase can help designers to identify different system configurations in compliance with the corresponding clusters: it may guide suppliers towards "market segmentation" not only fulfilling economic constraints but also technical design objectives. The second stage of the study proposes a synthesis process of a compact profile which represents the corresponding data of the studied environmental variable. This compact profile is generated by combining parameters and number of elementary patterns (segment, sine or cardinal sine) with regards to design indicators. These latter are established with respect to the main objectives and constraints associated to the designed system. All pattern parameters are obtained by solving the corresponding inverse problem with evolutionary algorithms. Finally, this synthesis process is applied to two different case studies. The first consists in the simplification of wind data issued from measurements in two geographic sites of Guadeloupe and Tunisia. The second case deals with the reduction of a set of railway mission profiles relative to a hybrid locomotive devoted to shunting and switching missions. It is shown from those examples that our approach leads to a wide reduction of the profiles associated with environmental variables which allows a significant decrease of the computational time in the context of an integrated optimal design process.; Ce travail présente une démarche méthodologique visant le " traitement de profils " de " mission " et plus généralement de " variables environnementales " (mission, gisement, conditions aux limites), démarche constituant la phase amont essentielle d‟un processus de conception systémique. La " classification " et la " synthèse " des profils relatifs aux variables d‟environnement du système constituent en effet une première étape inévitable permettant de garantir, dans une large mesure, la qualité du dispositif conçu et ce à condition de se baser sur des " indicateurs " pertinents au sens des critères et contraintes de conception. Cette approche s‟inscrit donc comme un outil d‟aide à la décision dans un contexte de conception systémique. Nous mettons en particulier l‟accent dans cette thèse sur l‟apport de notre approche dans le contexte de la conception par optimisation qui, nécessitant un grand nombre d‟itérations (évaluation de solutions de conception), exige l‟utilisation de " profils compacts " au niveau informationnel (temps, fréquence,...). Nous proposons dans une première phase d‟étude, une démarche de " classification " et de " segmentation " des profils basée sur des critères de partitionnement. Cette étape permet de guider le concepteur vers le choix du nombre de dispositifs à concevoir pour sectionner les produits créés dans une gamme. Dans une deuxième phase d‟étude, nous proposons un processus de " synthèse de profil compact ", représentatif des données relatives aux variables environnementales étudiées et dont les indicateurs de caractérisation correspondent aux caractéristiques de référence des données réelles. Ce signal de durée réduite est obtenu par la résolution d‟un problème inverse à l‟aide d‟un algorithme évolutionnaire en agrégeant des motifs élémentaires paramétrés (sinusoïde, segments, sinus cardinaux). Ce processus de " synthèse compacte " est appliqué ensuite sur des exemples de profils de missions ferroviaires puis sur des gisements éoliens (vitesse du vent) associés à la conception de chaînes éoliennes. Nous prouvons enfin que la démarche de synthèse de profil représentatif et compact accroît notablement l'efficacité de l‟optimisation en minimisant le coût de calcul facilitant dès lors une approche de conception par optimisation.

Optimization takes place in many IFPEN applications: for instance estimation of parameters of numerical models from experimental data in geosciences or for engine calibration. These optimization problems consist in minimizing a complex function, expensive to estimate, and for which derivatives are often not available. Moreover, additional difficulties arise with the introduction of nonlinear constraints and even several objectives to be minimized. In this thesis, we developed the SQA method (Sequential Quadratic Approximation), an extension of a derivative-free optimization method proposed by M.J.D Powell for optimization with constraints with known or unknown derivatives. This method consists in solving optimization sub-problems based on local quadratic interpolation models of objective function and derivative-free constraints built with a limited number of function evaluations. If the solution of this sub-problem does not progress toward a solution of the original problem, new simulations are performed to try to improve the model quality. Numerical results on benchmarks show that SQA is an effective method for constrained derivative-free optimization. Finally, SQA has been tested with success on two industrial applications in reservoir engineering and in engine calibration. An other problem studied in this thesis is multi-objective minimization under constraints. The MO-CMA-ES method (Multi-Objective - Covariance Matrix Adaptation - Evolution Strategy) adapted to take into account constraints has been successful to determine different compromises for an engine calibration application.; 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.

Optimization takes place in many IFPEN applications: for instance estimation of parameters of numerical models from experimental data in geosciences or for engine calibration. These optimization problems consist in minimizing a complex function, expensive to estimate, and for which derivatives are often not available. Moreover, additional difficulties arise with the introduction of nonlinear constraints and even several objectives to be minimized. In this thesis, we developed the SQA method (Sequential Quadratic Approximation), an extension of a derivative-free optimization method proposed by M.J.D Powell for optimization with constraints with known or unknown derivatives. This method consists in solving optimization sub-problems based on local quadratic interpolation models of objective function and derivative-free constraints built with a limited number of function evaluations. If the solution of this sub-problem does not progress toward a solution of the original problem, new simulations are performed to try to improve the model quality. Numerical results on benchmarks show that SQA is an effective method for constrained derivative-free optimization. Finally, SQA has been tested with success on two industrial applications in reservoir engineering and in engine calibration. An other problem studied in this thesis is multi-objective minimization under constraints. The MO-CMA-ES method (Multi-Objective - Covariance Matrix Adaptation - Evolution Strategy) adapted to take into account constraints has been successful to determine different compromises for an engine calibration application.; 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.

National audience; Comme le recommande le programme SESAR, les systèmes ATC actuels doivent être améliorés afin d'absorber la croissance du trafic. Les contraintes de capacité des secteurs de contrôle constituent un obstacle à un système ATC efficace. Les précédentes études ont consisté à optimiser le procédé actuel d'allocation de créneaux de décollage pour satiafaire ces contraintes. Nous proposons de résoudre directement les conflits dans l'espace supérieur par une modification des heures de décollage. Nous comparons une méthode en PPC et un algorithme évolutionnaire pour la résolution de ce problème.

National audience

National audience

Cette étude se concentre sur la synthèse de lois de commande de servo-entraînements accouplés à une charge flexible à paramètres incertains avec l’unique mesure de la position du moteur. La loi de commande a pour but de minimiser les effets de ces variations tout en gardant la maîtrise d’un cahier des charges de type industriel (temps de réponse, dépassement, simplicité d’implantation et de synthèse). De ce fait, un contrôleur et un observateur sont implantés. Un contrôleur de type retour d’état avec une minimisation d’un critère linéaire quadratique assurant un placement du pôle dominant est associé à un observateur de type Kalman. Ces deux structures utilisent des méthodologies classiques de synthèse : placement de pôles et choix de pondération des matrices de Kalman. Pour ce dernier, deux stratégies sont abordées. La première utilise les matrices de pondération diagonale standard. De nombreux degrés de liberté sont disponibles et donnent de bons résultats. La seconde défini la matrice des bruits d’état avec la variation de la matrice dynamique du système. Le nombre de degrés de liberté est réduit, les résultats restent similaires à la stratégie précédente, mais la synthèse est simplifiée. Ceci permet d’obtenir une méthode n’exigeant que peu d’investissement théorique de la part d’un ingénieur mais non robuste. Pour ceci, la méthode de micro-analyse caractérisant la stabilité robuste est appliquée en parallèle à un algorithme évolutionnaire autorisant une synthèse, plus rapide et plus précise qu’un opérateur humain. Cette méthode complète permet de voir les avantages d’une synthèse croisée de l’observateur et du correcteur au lieu d’une synthèse séparée. En effet, le placement optimal des dynamiques de commande et d’observation dans le cadre des systèmes à paramètres variants ne suit plus une stratégie classique découplée. Ici, les dynamiques se retrouvent couplées voire meme inversées (dynamique de la commande inférieure à celle de l’observateur). Des résultats expérimentaux corroborent les simulations et permettent d’expliquer les effets des observateurs et régulateurs sur le comportement du système.

This document is devoted to artificial intelligence and optimization. This part will bedevoted to having fun with high level ideas and to introduce the subject. Thereafter,Part II will be devoted to Monte-Carlo Tree Search, a recent great tool for sequentialdecision making; we will only briefly discuss other tools for sequential decision making;the complexity of sequential decision making will be reviewed. Then, part IIIwill discuss optimization, with a particular focus on robust optimization and especiallyevolutionary optimization. Part IV will present some machine learning tools, useful ineveryday life, such as supervised learning and active learning. A conclusion (part V)will come back to fun and to high level ideas., On parlera ici de Monte-Carlo Tree Search, d'UCT, d'algorithmes évolutionnaires et d'autres trucs et astuces d'IA;l'accent sera mis sur la parallélisation.

National audience

This thesis deals with the search for innovative composite solutions for mass reduction of aeronautical structures. Composite materials offer new degrees of freedom for structural design and optimisation. The aim of this study is to propose a methodology for robust optimisation of the stacking sequence of composite sub-components. The proposed strategy consists of three interlinked elements : the optimisation algorithm, the calculation strategy and the method to account for design uncertainties. A multiobjective optimisation algorithm is developed, that yields a set of optimal trade-offs between conflicting objectives. It is an evolutionary algorithm, whose efficiency is greatly increased compared to generic algorithms, through the introduction of multiscale mechanical models specific to layered composite materials. The algorithm is particularly suited to take into account the industrial guidelines for stacking-sequence design. To reduce calculation costs, different strategies are implemented, that imply detailed simulations and model approximation. A robust optimisation method is proposed, to account for uncertainties, lack of knowledge or potential errors. The first application deals with the buckling and post-buckling behaviour of stiffened panels. The second application deals with strength optimisation of bolted joints in composite structures, whose calculation is still problematic. A model is developed for the prediction of bearing failure, based on a progressive approach of the laminate failure and the onset of delamination, with excellent results compared to experimental data. This model is applied to the maximisation of the strength of an elementary joint with one fastener. It is also integrated in a multilevel approach for the calculation of complex junctions involving hundreds of fasteners.; Ce travail de thèse s'inscrit dans le cadre de la recherche de solutions composites innovantes pour l'allègement des structures aéronautiques. Les matériaux composites stratifiés offrent, de par leur architecture interne, de nouveaux degrés de liberté pour la conception et l'optimisation des structures. L'objectif est ici de proposer une méthodologie pour l'optimisation robuste des empilements, à l'échelle de petits sous-ensembles structuraux composites. La démarche est décomposée en trois éléments imbriqués : algorithme d'optimisation, stratégie de calcul et prise en compte des incertitudes. L'algorithme multiobjectif développé retourne au concepteur un ensemble de compromis optimaux. Il s'agit d'un algorithme évolutionnaire, dont l'efficacité est considérablement accrue, par rapport aux outils génériques, par l'introduction de considérations mécaniques multiéchelles spécifiques aux composites stratifiés. Il est en particulier adapté à la prise en compte des recommandations industrielles pour le choix des séquences d'empilements. Afin de réduire les coûts de calcul, des stratégies de calcul sont mises en oeuvre, articulant modélisations fines et approximation des modèles. Une méthode d'optimisation robuste est proposée, pour la prise en compte des incertitudes, méconnaissances ou erreurs potentielles. La première application proposée traite du flambement et post-flambement de panneaux raidis. La seconde application traite de l'optimisation des assemblages boulonnés composites, dont le calcul reste aujourd'hui problématique. Un modèle de la rupture en matage est développé, basé sur une approche progressive de la rupture du stratifié et de l'amorce des délaminages, avec d'excellents résultats par rapport à l'expérience. Ce modèle est appliqué pour l'optimisation d'un assemblage élémentaire à une fixation, et intégré dans une approche multiniveau pour le calcul d'une jonction complexe à plusieurs centaines de fixations.

This thesis deals with the search for innovative composite solutions for mass reduction of aeronautical structures. Composite materials offer new degrees of freedom for structural design and optimisation. The aim of this study is to propose a methodology for robust optimisation of the stacking sequence of composite sub-components. The proposed strategy consists of three interlinked elements : the optimisation algorithm, the calculation strategy and the method to account for design uncertainties. A multiobjective optimisation algorithm is developed, that yields a set of optimal trade-offs between conflicting objectives. It is an evolutionary algorithm, whose efficiency is greatly increased compared to generic algorithms, through the introduction of multiscale mechanical models specific to layered composite materials. The algorithm is particularly suited to take into account the industrial guidelines for stacking-sequence design. To reduce calculation costs, different strategies are implemented, that imply detailed simulations and model approximation. A robust optimisation method is proposed, to account for uncertainties, lack of knowledge or potential errors. The first application deals with the buckling and post-buckling behaviour of stiffened panels. The second application deals with strength optimisation of bolted joints in composite structures, whose calculation is still problematic. A model is developed for the prediction of bearing failure, based on a progressive approach of the laminate failure and the onset of delamination, with excellent results compared to experimental data. This model is applied to the maximisation of the strength of an elementary joint with one fastener. It is also integrated in a multilevel approach for the calculation of complex junctions involving hundreds of fasteners., Ce travail de thèse s'inscrit dans le cadre de la recherche de solutions composites innovantes pour l'allègement des structures aéronautiques. Les matériaux composites stratifiés offrent, de par leur architecture interne, de nouveaux degrés de liberté pour la conception et l'optimisation des structures. L'objectif est ici de proposer une méthodologie pour l'optimisation robuste des empilements, à l'échelle de petits sous-ensembles structuraux composites. La démarche est décomposée en trois éléments imbriqués : algorithme d'optimisation, stratégie de calcul et prise en compte des incertitudes. L'algorithme multiobjectif développé retourne au concepteur un ensemble de compromis optimaux. Il s'agit d'un algorithme évolutionnaire, dont l'efficacité est considérablement accrue, par rapport aux outils génériques, par l'introduction de considérations mécaniques multiéchelles spécifiques aux composites stratifiés. Il est en particulier adapté à la prise en compte des recommandations industrielles pour le choix des séquences d'empilements. Afin de réduire les coûts de calcul, des stratégies de calcul sont mises en oeuvre, articulant modélisations fines et approximation des modèles. Une méthode d'optimisation robuste est proposée, pour la prise en compte des incertitudes, méconnaissances ou erreurs potentielles. La première application proposée traite du flambement et post-flambement de panneaux raidis. La seconde application traite de l'optimisation des assemblages boulonnés composites, dont le calcul reste aujourd'hui problématique. Un modèle de la rupture en matage est développé, basé sur une approche progressive de la rupture du stratifié et de l'amorce des délaminages, avec d'excellents résultats par rapport à l'expérience. Ce modèle est appliqué pour l'optimisation d'un assemblage élémentaire à une fixation, et intégré dans une approche multiniveau pour le calcul d'une jonction complexe à plusieurs centaines de fixations.

The solution to the inexact graph matching problem is the key for defining any type of graph distance. It is even more complex than the exact graph isomorphism problem. On the one hand, inexact graph matching is a combinatorial optimization problem in NP taking into account perturbations inherent in noisy real world environments. Exact graph matching, on the other hand, is a decision problem for which it has not yet been shown if its complexity class is P and which applies only to exactly identical graphs. In this thesis, we study an approach based on genetic algorithms addressing both exact and inexact isomorphisms. We introduce several new crossover operators, some more general for use with any kind of permutation encoding, some specialized which include a greedy heuristic specific to graph matching. We conduct an exhaustive study in order to compare these operators with the existing ones, underlining their respective characteristics, advantages and disadvantages. Furthermore, we examine several aspects for enhancing the algorithm, both theoretical and practical ones, leading to faster execution, better precision or even the assurance of finding the global optimum. We combine the genetic algorithm with generalized black-box heuristics, such as local search, specialized heuristics such as the A* algorithm or practical tools like parallelization techniques. Our final aim is to present a method addressing all different types of graph matching problems, i.e. exact and inexact, isomorphisms of graphs having the same size and sub-graph isomorphisms. We illustrate the generality of our approach with three applications with very distinct properties which cover the different problem types., L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.

National audience; Comment les algorithmes évolutionnaires trouvent-ils les meilleures solutions à un problème donné ? Marc Schoenauer, l’un des spécialistes du sujet, nous fournit quelques explications.

Second order evolution (or indirect selection) corresponds to a situation where the individuals are not only selected on their fitness to an environment, but also on their ability to evolve « better ». Even if such a mechanism seems a priori very interesting in artificial evolution, it is not permitted by the structure of evolutionary algorithms because the evolutionary processes are fixed. Therefore, we propose a new evolutionary algorithm, RBFGene. It includes an intermediate level, the proteom (made of « proteins »), between the phenotype of an individual and its genotype, that allows for changes in the structure of the genome without changing the phenotype. These modifications can thereafter have an influence on later reproductions. We show the existence of an indirect selection in our algorithm, acting on genomes by changing the size of the non coding sequences or the order of the genes.; On parle d’évolution de second ordre (ou de sélection indirecte) lorsque les individus sont sélectionnés non pour leur seule adaptation à l’environnement mais aussi pour leur capacité à évoluer « mieux ». Bien qu’un tel mécanisme soit a priori très intéressant en évolution artificielle, la structure des algorithmes évolutionnaires interdit généralement celui-ci car les processus évolutifs sont figés. Nous avons ainsi proposé un nouvel algorithme évolutionnaire, RBF-Gene. Il possède un niveau intermédiaire, le protéome (composé de « protéines »), entre le phénotype d’un individu et son génotype lui permettant de faire varier la structure du génome sans modifier son phénotype sachant que ces variations auront une influence sur les reproductions futures. Nous montrons qu’une sélection de second ordre est bien à l’œuvre dans l’algorithme et qu’elle permet de façonner les génomes, en modifiant la taille des zones non codantes et l’ordre des gènes.

Thèse proposée pour un prix de thèse.; The pharmaceutical industry has been facing several challenges during the last years, and the optimization of their drug discovery pipeline is believed to be the only viable solution. High-throughput techniques, including computational approaches such as virtual screening or rational drug design, are now routinely used to guide drug discovery. Both rely on the prediction of the molecular interaction occurring between drug-like molecules and a therapeutically relevant target. A new docking software is introduced in this thesis : EADock. This hybrid evolutionary algorithm uses two fitness functions, and rely on CHARMM. Its docking efficiency was shown on 37 crystallized protein-ligand complexes. It has been used in a fragment-based rational drug design approach, leading to the successful design of new peptidic ligands for the a integrin and for the human PPARα. In both cases, the designed peptides presented activities comparable to that of well established ligands.; Les récentes difficultés de l'industrie pharmaceutique semblent ne pouvoir se résoudre que par l'optimisation de leur processus de développement de médicaments. Cette dernière implique de plus en plus de techniques dites “haut-débit”, dont des approches in silico telles que le criblage virtuel ou la conception rationnelle de nouvelles molécules. Toutes deux reposent sur la capacité à prédire l'interaction moléculaire entre un principe actif potentiel et une protéine cible ayant un intérêt thérapeutique. Cette thèse présente un nouveau logiciel réalisant cette prédiction : EADock. Cet algorithme évolutionnaire hybride utilise deux pressions de sélections et repose sur CHARMM. Son efficacité a été mise en évidence sur 37 complexes protéine-ligand cristallisés. Il a également permis la découverte de nouveaux ligands peptidiques de PPARα et de l'intégrine α5β1. Dans les deux cas, l'activité de ces nouveaux peptides est comparable à celles de ligands bien établis.

Second order evolution (or indirect selection) corresponds to a situation where the individuals are not only selected on their fitness to an environment, but also on their ability to evolve « better ». Even if such a mechanism seems a priori very interesting in artificial evolution, it is not permitted by the structure of evolutionary algorithms because the evolutionary processes are fixed. Therefore, we propose a new evolutionary algorithm, RBFGene. It includes an intermediate level, the proteom (made of « proteins »), between the phenotype of an individual and its genotype, that allows for changes in the structure of the genome without changing the phenotype. These modifications can thereafter have an influence on later reproductions. We show the existence of an indirect selection in our algorithm, acting on genomes by changing the size of the non coding sequences or the order of the genes., On parle d’évolution de second ordre (ou de sélection indirecte) lorsque les individus sont sélectionnés non pour leur seule adaptation à l’environnement mais aussi pour leur capacité à évoluer « mieux ». Bien qu’un tel mécanisme soit a priori très intéressant en évolution artificielle, la structure des algorithmes évolutionnaires interdit généralement celui-ci car les processus évolutifs sont figés. Nous avons ainsi proposé un nouvel algorithme évolutionnaire, RBF-Gene. Il possède un niveau intermédiaire, le protéome (composé de « protéines »), entre le phénotype d’un individu et son génotype lui permettant de faire varier la structure du génome sans modifier son phénotype sachant que ces variations auront une influence sur les reproductions futures. Nous montrons qu’une sélection de second ordre est bien à l’œuvre dans l’algorithme et qu’elle permet de façonner les génomes, en modifiant la taille des zones non codantes et l’ordre des gènes.

The concept of fitness landscape (or adaptive landscape) was introduce par S. Wright in the field of evolutionary biology in 1930's. It is one of the most relevant to explain the evolution of individuals. In the field of combinatorial optimization by metaheuristic, it is also used and allows to study the link between geometrical description of optimization problem and the dynamic of search algorithms. Two geometries of landscape which correspond to two dynamics of search have been studied. The multimodal geometry of landscape is related to the presence of local optima, where the search dynamic is a succession of adaptive walk toward better solutions and degradation of performance.The geometry of neutral fitness landscape, point out in molecular evolution by neutral theory of Motoo Kimura, is related to presence of plateaus ; the dynamic of search is characterized by random drift interrupted by the discover of rare better solution. This thesis propose to deeper study neutral fitness landscapes in the context of optimization and to design new metaheuristics according to those landscapes.This thesis is composed by four parts. In the first one, we present the main results about fitness landscapes and more particularly about neutral fitness landscapes. In the second part, we develop the concept of neutral set by introducing the notion of 'fitness cloud' which allows to study the correlation of performance between two neighbor solutions and we measure this correlation on 'embedded fitness landscapes' as an extension of NK landscapes and Max-SAT problems. In the third part, we summarize the set of measures on neutral networks and we propose the new measure.Experimental study is performed on three family of landscapes for which the neutrality is and two classical problems. Then, a new metaheuristic adapted of neutral fitness landscapes inspired by the new measure is proposed and evaluated on different landscapes. We studied the massively neutral fitness landscapes from the learning problem of a rule of cellular automata which perform the density task, in order to improve the best metaheuristics known.; Le concept de paysage adaptatif a été introduit par S. Wright dans le domaine de la biologie de l'évolution dans les années 1930. Il est l'un des concepts pertinents pour modéliser l'évolution d'une population d'organismes. Dans le domaine de l'optimisation combinatoire par métaheuristiques, il est également utilisé et permet de lier une description géométrique d'un problème d'optimisation avec la dynamique des algorithmes de recherche.Deux géométries de paysage correspondant à deux dynamiques d'algorithme ont été principalement étudiées. La géométrie de paysage multimodale est liée à la présence d'optima locaux,où la dynamique est une succession de marches adaptatives vers de meilleures solutions et de dégradations de performance. La géométrie des paysages adaptatifs neutres, mise en avant par la théorie de la neutralité en évolution moléculaire de Motoo Kimura,est liée à la présence de plateaux ; la dynamique se caractérise alors par une dérive aléatoire entrecoupée de rares découvertes de solutions plus performantes. Cette thèse se propose d'approfondir l'étude des paysages neutres dans le contexte de l'optimisation et de proposer de nouvelles métaheuristiques adaptées à ce type de paysages.La thèse se compose de quatre chapitres. Dans un premier chapitre,nous présentons les principaux résultats concernant les paysages adaptatifs et plus particulièrement les paysages adaptatifs neutres.Dans un deuxième chapitre, nous développons le concept d'ensemble de neutralité en introduisant la notion de 'nuage adaptatif' qui permet d'étudier la corrélation de performance entre solutions voisines et nous l'appliquons à la classe des paysages 'embarqués' qui regroupe les paysages NK et Max-SAT. Dans un troisième chapitre, nous résumons l'ensemble des mesures relatives aux réseaux de neutralité et nous proposons une nouvelle mesure. Une étude expérimentale est réalisée sur trois familles de paysages pour lesquelles la neutralité est ajustable et deux problèmes classiques de la littérature. Enfin, un nouvel algorithme de recherche adapté aux paysages neutres lié à la nouvelle mesure est proposé et évalué sur différents paysages neutres. Nous réalisons l'étude du paysage adaptatif massivement neutreissu du problème d'apprentissage de la règle d'un automate cellulaire réalisant la tâche de classification par la densité, afin d'en améliorer les métaheuristiques connues existantes.

The concept of fitness landscape (or adaptive landscape) was introduce par S. Wright in the field of evolutionary biology in 1930's. It is one of the most relevant to explain the evolution of individuals. In the field of combinatorial optimization by metaheuristic, it is also used and allows to study the link between geometrical description of optimization problem and the dynamic of search algorithms. Two geometries of landscape which correspond to two dynamics of search have been studied. The multimodal geometry of landscape is related to the presence of local optima, where the search dynamic is a succession of adaptive walk toward better solutions and degradation of performance.The geometry of neutral fitness landscape, point out in molecular evolution by neutral theory of Motoo Kimura, is related to presence of plateaus ; the dynamic of search is characterized by random drift interrupted by the discover of rare better solution. This thesis propose to deeper study neutral fitness landscapes in the context of optimization and to design new metaheuristics according to those landscapes.This thesis is composed by four parts. In the first one, we present the main results about fitness landscapes and more particularly about neutral fitness landscapes. In the second part, we develop the concept of neutral set by introducing the notion of 'fitness cloud' which allows to study the correlation of performance between two neighbor solutions and we measure this correlation on 'embedded fitness landscapes' as an extension of NK landscapes and Max-SAT problems. In the third part, we summarize the set of measures on neutral networks and we propose the new measure.Experimental study is performed on three family of landscapes for which the neutrality is and two classical problems. Then, a new metaheuristic adapted of neutral fitness landscapes inspired by the new measure is proposed and evaluated on different landscapes. We studied the massively neutral fitness landscapes from the learning problem of a rule of cellular automata which perform the density task, in order to improve the best metaheuristics known.; Le concept de paysage adaptatif a été introduit par S. Wright dans le domaine de la biologie de l'évolution dans les années 1930. Il est l'un des concepts pertinents pour modéliser l'évolution d'une population d'organismes. Dans le domaine de l'optimisation combinatoire par métaheuristiques, il est également utilisé et permet de lier une description géométrique d'un problème d'optimisation avec la dynamique des algorithmes de recherche.Deux géométries de paysage correspondant à deux dynamiques d'algorithme ont été principalement étudiées. La géométrie de paysage multimodale est liée à la présence d'optima locaux,où la dynamique est une succession de marches adaptatives vers de meilleures solutions et de dégradations de performance. La géométrie des paysages adaptatifs neutres, mise en avant par la théorie de la neutralité en évolution moléculaire de Motoo Kimura,est liée à la présence de plateaux ; la dynamique se caractérise alors par une dérive aléatoire entrecoupée de rares découvertes de solutions plus performantes. Cette thèse se propose d'approfondir l'étude des paysages neutres dans le contexte de l'optimisation et de proposer de nouvelles métaheuristiques adaptées à ce type de paysages.La thèse se compose de quatre chapitres. Dans un premier chapitre,nous présentons les principaux résultats concernant les paysages adaptatifs et plus particulièrement les paysages adaptatifs neutres.Dans un deuxième chapitre, nous développons le concept d'ensemble de neutralité en introduisant la notion de 'nuage adaptatif' qui permet d'étudier la corrélation de performance entre solutions voisines et nous l'appliquons à la classe des paysages 'embarqués' qui regroupe les paysages NK et Max-SAT. Dans un troisième chapitre, nous résumons l'ensemble des mesures relatives aux réseaux de neutralité et nous proposons une nouvelle mesure. Une étude expérimentale est réalisée sur trois familles de paysages pour lesquelles la neutralité est ajustable et deux problèmes classiques de la littérature. Enfin, un nouvel algorithme de recherche adapté aux paysages neutres lié à la nouvelle mesure est proposé et évalué sur différents paysages neutres. Nous réalisons l'étude du paysage adaptatif massivement neutreissu du problème d'apprentissage de la règle d'un automate cellulaire réalisant la tâche de classification par la densité, afin d'en améliorer les métaheuristiques connues existantes.

This thesis deals with the resolution of the satisfiability problems SAT and MAX-SAT. Our contributions are in three types. First, we have developed the memetic algorithm GASAT for the SAT and MAX-SAT problems which hybridies a tabu algorithm and a genetic algorithm. Some specific tools for the satisfiability problems have been included in it such as intensification mechanisms, diversification mechanisms and a new crossover operator. Next, we have proposed a new resolution framework which permits the exact and the approached methods to handle the same representation of the search space. To do this, we have added a third truth value “undetermined”. The results obtained by the tri-valued hybrid algorithms show the utility of this resolution framework. Finally, we are interested in the branching heuristics for the Branch and Bound algorithms in the MAX- SAT context. Our study shows that these heuristics react in different ways in function of the initial parameters, the structure of the studied instances and the improved mechanisms for Branch and Bound. The findings of this study may lead to the creation of new heuristics specifically dedicated to the MAX-SAT problem., Cette thèse est centrée sur la résolution des problèmes de satisfiabilité SAT et MAX-SAT. Les contributions apportées sont de trois types. Tout d’abord nous avons développé l’algorithme mémétique GASAT pour les problèmes SAT et MAX-SAT hybridant un algorithme tabou et un algorithme génétique. Des outils spécifiques aux problèmes de satisfiabilité y ont été intégrés tels que des mécanismes d’intensification, de diversification et un nouvel opérateur de croisement. Ensuite, nous avons proposé un nouveau cadre de résolution permettant aux méthodes exactes et aux méthodes approchées de manipuler la même représentation de l’espace de recherche. Pour cela, nous avons ajouté une troisième valeur de vérité indéterminé . Les résultats obtenus par les algorithmes hybrides trivalués montrent l’intérêt de ce cadre de résolution. Enfin, nous nous sommes penchés sur les heuristiques de branchement des algorithmes de Branch and Bound pour le problème MAX-SAT. L’étude que nous présentons montre que ces heuristiques réagissent très différemment en fonction des paramètres initiaux, de la structure de l’instance étudiée et des mécanismes d’amélioration du Branch and Bound. Elle permet d’envisager la création de nouvelles heuristiques spécifiquement dédiées au problème MAX-SAT.

Numerical technologies have generated for a few years, huge volumes of data, which can conceal useful information. This situation gave rise to knowledge discovery activities in data bases. This indicates the non obvious process of extracing implicit informations, previously unknown and potentially useful hidden into the data. A standard knowledge discovery process includes five steps. The main one is data mining. We are interested in a kind of information expressed as a dependency rule and in the interestingness of a rule. A dependency rule is a conditional implication between sets of attributes over the data set. The purpose of standard data mining algorithmes is generally to find the best model. In fact, behind these processes, there is an optimization problem which is not explicitly expressed. We consider interestingness of dependency rules as being an optimization problem in which rule interestingness is quantified by the mean of measures. Thus, it is necessary to study the search space induced by measures as well as seach algorithms associated with the analysis of these spaces. It arises that these measures have a different behavior according to the data set involved ; so, an analytical approach is not possible. It arises that some of these measures, when they are considered simultaneously, present antagonisms ; thus, obtaining "the" best rule is not possible ; it is necessary to consider a set of good tradeoffs. We bring solutions by the means of genetic approch.; Les technologies numériques ont engendré depuis peu, des volumes de données importants, qui peuvent receler des informations utiles. Ceci a donné naissance à l'extraction de connaissances à partir des données qui désigne le processus d'extraction d'informations implicites, précédemment inconnues et potentiellement utiles enfouies dans les données. La fouille de données comprend cinq phases dont la principale est l'extraction de modèles. Nous nous intéressons aux connaisances exprimées sous la forme de règles de dépendance et à la qualité de ces règles. Une règle de dépendance est une implication conditionnelle entre ensembles d'attributs. Les algorithmes standard ont pour but de rechercher les meilleurs modèles. Derrière ces processus se cache en fait une véritable problématique d'optimisation. Nous considérons la recherche des règles de dépendance les plus intéressantes comme étant un problème d'optimisation dans lequel la qualité d'une règle est quantifiée par des mesures. Ainsi, il convient d'étudier les espaces de recherche induits par les mesures ainsi que les algorithmes de recherche dans ces espaces. Il ressort que la plupart des mesures observées présentent des propriétés différentes suivant le jeu de données. Une approche analytique n'est donc pas envisageable dans fixer certains paramères. Nous observons les variations relatives de mesures évaluées simultanément ; certaines d'entre elles sont antagonistes ce qui ne permet pas d'obtenir "la" meilleure règle ; il faut alors considérer un ensemble de compromis satisfaisants. Nous apportons des solutions par le biais des algorithmes génétiques.

The ant colony algorithms are inspired by the collective behaviours observed in ant colonies and aim at solving difficult optimization problems.The first approach to conceive some metaheuristics for the continuous optimization using this metaphor concist in creating a multi-agent system. We thus propose an "interacting ant colony" algorithms (CIAC). The second approach describe these metaheuristics as some methods manipulating a sampling of a probability density. We thus propose an "estimation of distribution" algorithm (CHEDA).In line with the adaptive memory programming concept, our algorithms are hybridicized with a Nelder-Mead local search (HCIAC). We have afterward adapted this method to continuous dynamic problems (DHCIAC), and proposed a new coherent benchmark.Our algorithms are finally applied as part of the automatization of the follow-up of eye injury., Les métaheuristiques de colonies de fourmis s'inspirent des comportements collectifs observés chez les fourmis pour résoudre des problèmes d'optimisation difficile.La première approche pour concevoir des métaheuristiques d'optimisation continue en suivant cette métaphore consiste à créer un système multi-agent. Nous proposons ainsi un algorithme de "colonies de fourmis interagissantes" (CIAC). La deuxième approche décrit ces métaheuristiques comme des méthodes manipulant un échantillonnage d'une distribution de probabilité. Nous proposons ainsi un algorithme "à estimation de distribution" (CHEDA).En accord avec le concept de programmation à mémoire adaptative, nos algorithmes font l'objet d'une hybridation avec une recherche locale de Nelder-Mead (HCIAC). Nous avons ensuite adapté cette méthode à des problèmes continus dynamiques (DHCIAC), pour lesquels nous proposons également un nouveau jeu de test cohérent.Nos algorithmes sont enfin appliqués dans le cadre de l'automatisation du suivi des lésions de l'oeil.

The ant colony algorithms are inspired by the collective behaviours observed in ant colonies and aim at solving difficult optimization problems.The first approach to conceive some metaheuristics for the continuous optimization using this metaphor concist in creating a multi-agent system. We thus propose an "interacting ant colony" algorithms (CIAC). The second approach describe these metaheuristics as some methods manipulating a sampling of a probability density. We thus propose an "estimation of distribution" algorithm (CHEDA).In line with the adaptive memory programming concept, our algorithms are hybridicized with a Nelder-Mead local search (HCIAC). We have afterward adapted this method to continuous dynamic problems (DHCIAC), and proposed a new coherent benchmark.Our algorithms are finally applied as part of the automatization of the follow-up of eye injury., Les métaheuristiques de colonies de fourmis s'inspirent des comportements collectifs observés chez les fourmis pour résoudre des problèmes d'optimisation difficile.La première approche pour concevoir des métaheuristiques d'optimisation continue en suivant cette métaphore consiste à créer un système multi-agent. Nous proposons ainsi un algorithme de "colonies de fourmis interagissantes" (CIAC). La deuxième approche décrit ces métaheuristiques comme des méthodes manipulant un échantillonnage d'une distribution de probabilité. Nous proposons ainsi un algorithme "à estimation de distribution" (CHEDA).En accord avec le concept de programmation à mémoire adaptative, nos algorithmes font l'objet d'une hybridation avec une recherche locale de Nelder-Mead (HCIAC). Nous avons ensuite adapté cette méthode à des problèmes continus dynamiques (DHCIAC), pour lesquels nous proposons également un nouveau jeu de test cohérent.Nos algorithmes sont enfin appliqués dans le cadre de l'automatisation du suivi des lésions de l'oeil.

Predatory fishes, such as tunas, billfishes, and sharks, coexist in pelagic regions of the tropical oceans. In situ experiments have revealed horizontal and vertical movement patterns for different pelagic species, but the influence of the biotic environment on movement behaviour has not been studied. In this paper, we propose a simple model in which the movement behaviour of these fishes is driven entirely by the biotic environment, without implementing physiological constraints. We explore this concept via computer simulations based on the Latent Energy Environments model (Menczer, F., Belew, R.K., 1966a. From complex environments to complex behaviors. Adapt. Behav. 4(3/4), 317-63). In our model, multiple behaviours for artificial fishes evolve in a three-dimensional environment where spatial and temporal distributions of prey are patterned after hydroacoustic data taken during ultrasonic telemetry experiments on tunas in the open ocean in French Polynesia. Interactions among indiviudals are modeled through their shared prey resources. Movement patterns of the adapted individuals are analyzed to : (i) compare artificial individuals with real fishes (three species of tuna, three species of billfishes, and one species of shark) observed by ultrasonic telemetry ; and (ii) examine how the artificial fishes exploit their environment. Most of the individuals evolved vertical patterns virtually identical to those exhibited by fishes in the wild. The agreement between our simple model and the ethological data validates the use of computational models for studies of the characteristics of multiple species inhabiting a common ecosystem. (Résumé d'auteur)

National audience; On propose un nouvel algorithme mémétique (algorithme évolutionnaire dont la mutation est remplacée par une recherche locale) pour le problème de coloration de sommets d'un graphe. Il s'agit d'un problème théorique classique déjà longuement étudié. L'objectif est de colorier les sommets d'un graphe avec le moins de couleurs possible tout en assurant que deux sommets reliés par une arête n'aient pas la même couleur. La population de l'algorithme proposé est réduite à deux solutions candidates seulement. Contrairement aux approches à base de population classiques, ici il n'y a donc pas d'opérateur de sélection des parents (qui sont à tous les coups les deux individus de la population), ni d'opérateur permettant de choisir les individus de la population à remplacer. De ce fait, le contrôle de la balance intensification/diversification en est simplifié. L'algorithme proposé est appliqué sur les instances de graphes DIMACS, benchmark le plus étudié depuis les années 1990. Il s'est révélé très performant, trouvant les meilleures colorations connues à ce sur plusieurs instances et dans des temps très courts. Pour plus de détails sur ce problème : http://www.laas.fr/files/MOGISA/Gondran-20120404.pdf

Minimizing environmental impacts of human activity represent a major objective of sustainable development considering resources depletion and the limited capabilities of the environment to adapt. Devices with better environmental performance require a specific design approach integrating credible environmental criteria. It is indeed by acting at the early phase of design that it is likely to provide the maximum flexibility to minimize environmental impacts of a product (or service). This method is called eco-design. In the field of eco-design, these works are conduct on applications of electrical engineering and more specifically of electromagnetic energy converters. These components have the distinction of consuming energy during use. This particularity implies a strong connection between the operating mode of the device and its life cycle design. This thesis propose in a first part an introduction to life cycle assessment and to the basic principles of eco-design. The methodological perspectives that these considerations open in the specific field of Electrical Engineering are then described. In a second part, three Electrical Engineering cases of increasing complexity are studied : a simplified single-phase transformer, a permanent capacitor single-phase induction machine with very short operating times (real commercial product) and finally a three-phase induction machine with optimized power supply. These applications are used to emphasize the principles of eco-design and are optimized regarding three environmental criteria : the gross energy requirement, the resources depletion and the global warming potential. In fact, taking into account other environmental impacts is identical in terms of methodology. In these studies, we show that it is interesting to optimize the design of these electromagnetic converters on life cycle, when their cumulative operating time is small compared to the total time of use. The amount of operating losses is also a parameter having a significant action on the results of eco-design. The setting of these applications is also subject to various sensitivity studies in order to determine more precisely the influence of the elementary energy costs, the choice of raw materials, etc.. Finally, we introduce the definition of an energy efficiency on life cycle more appropriate to an eco-design methodology.; Dans un contexte de raréfaction des ressources et de limitation des capacités d'adaptation de l'environnement, la minimisation des impacts environnementaux de l'activité humaine représente un des objectifs majeurs du développement durable. Proposer des dispositifs présentant de meilleures performances environnementales nécessite une démarche de conception spécifique intégrant des critères environnementaux crédibles. Il s'agit en effet d'agir dès la conception d'un produit (ou d'un service) afin de bénéficier du maximum de latitude pour minimiser ses impacts environnementaux. Cette démarche se nomme l'éco-conception. Rejoignant cette thématique, ces travaux ciblent des applications du domaine du Génie Electrique et plus particulièrement celui des convertisseurs électromagnétiques d'énergie. Ces composants présentent la particularité d'être fondamentalement, à l'usage, consommateurs d'énergie. Cet aspect implique un fort couplage entre le mode de fonctionnement du dispositif et son dimensionnement sur son cycle de vie. Ce travail de thèse aborde dans une première partie l'analyse sur cycle de vie ainsi que les principes fondamentaux de la démarche d'éco-conception. Les perspectives méthodologiques que ces considérations ouvrent dans le domaine plus spécifique du Génie Electrique sont ensuite décrites. Dans une seconde partie, trois cas d'étude en Génie Electrique de complexité croissante, font l'objet d'applications des principes d'éco-conception : un transformateur monophasé simplifié à alimentation fixe, une machine asynchrone monophasée à condensateur permanent réelle (produit commercial) et présentant des durées de fonctionnement très brèves, et enfin une machine asynchrone triphasée alimentée à fréquence variable. Les critères environnementaux retenus pour les optimisations sont l'énergie globale sur cycle de vie et les émissions de gaz à effet de serre. En effet, la prise en compte d'autres impacts environnementaux est identique du point de vue méthodologique. Lors de ces études, nous montrons qu'il est intéressant d'optimiser la conception de ces convertisseurs électromagnétiques sur cycle de vie, lorsque leur durée cumulée de fonctionnement est faible devant leur durée d'usage. Le niveau de puissance de fonctionnement des convertisseurs est aussi un paramètre ayant une action significative sur les résultats d'éco-conception. Le paramétrage des trois cas d'études fait par ailleurs l'objet de différentes analyses de sensibilité permettant de cerner plus précisément, sur les résultats d'optimisation, l'influence des coûts énergétiques élémentaires, des choix des matériaux constituant le dispositif, etc. Enfin, pour les convertisseurs d'énergie, nous introduisons la notion de rendement énergétique sur cycle de vie prenant en compte leur efficacité globale.