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.<br /><br />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).<br /><br />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.<br /><br />Nos algorithmes sont enfin appliqués dans le cadre de l'automatisation du suivi des lésions de l'oeil.

Cette thèse s'appuie sur le paradigme de l'énaction pour aborder la modélisation de l'autonomie d'entités artificielles. Dans un contexte d'interaction entre des humains et des entités autonomes en réalité virtuelle, les propriétés comportementales résultantes d'une autonomie constitutive pourraient favoriser la créativité et l'engagement en proposant à l'utilisateur un compromis entre surprise et régularité. La première partie de cette thèse est une proposition théorique qui mène à une définition d'agents virtuels situés dits énactifs, à travers des propriétés internes, liées au fonctionnement de l'agent, et des propriétés externes, liées au comportement de l'agent. Nous nous inscrivons dans une approche dynamique évolutionnaire, qui utilise conjointement des CTRNN et des méthodes évolutionnaires. Nous considérons, parmi les propriétés externes, la capacité à enrichir un comportement par l'interaction comme un point dur. Nous proposons une démarche pour obtenir un apprentissage à l'échelle ontogénétique qui reflète l'histoire particulière des interactions de l'agent avec l'environnement en utilisant un guidage. La deuxième partie est une tentative d'implémentation issue de cette réflexion à travers trois expériences. La conclusion de ce mémoire présente un bilan critique des résultats et de notre démarche, qui illustre la difficulté de la manipulation d'un système autonome. Nous avons montré des limites de l'approche évolutionnaire dans un tel contexte. Les perspectives tiennent compte de la nécessité à faire des compromis entre complexité comportementale et autonomie constitutive. Nous discutons également de l'exploitation potentielle de ce travail en réalité virtuelle.

Cette thèse porte sur la conception de contrôleurs pour robots explorateurs autonomes basée sur une approche en ligne (online) intégrée, ne nécessitant pas de vérité terrain ni d'intervention de l'expert humain au cours du processus d'entrainement.Le travail présenté se focalise sur le domaine de la robotique autonome et plus particulièrement la conception de controleurs robotiques pour les essaims de robots.Ce contexte présente deux difficultés spécifiques. Premièrement, les approches basées sur l'usage de simulateur sont d'efficacité limitée : d'une part, la précision du simulateur est limitée compte tenu de la variabilité des robots élémentaires; d'autre part, la complexité de la simulation est super-linéaire en fonction du nombre de robots de l'essaim. Deuxièmement, les approches guidées par le but se heurtent au fait que la fonction objectif n'est pas définie au niveau du robot individuel, mais au niveau de l'essaim.Une première étape vers la conception de contrôleur explorateur autonome est proposée dans cette thèse. L'approche proposée, appelée exploration robotique fondée sur l'évolution et l'information (Ev-ITER) se fonde sur l'hybridation de la robotique évolutionnaire et de l'apprentissage par renforcement utilisant l'entropie. Cette approche procède en deux phases: (i) dans une première phase l'évolution artificielle est utilisée pour générer des contrôleurs primaires (crawlers), dont les trajectoires sont d'entropie élevée dans l'espace sensori-moteur; (ii) dans une seconde phase, l'archive des trajectoires acquises par les controleurs primaires est exploitée pour définir les controleurs secondaires, inspirés de la motivation intrinsèque robuste et permettant l'exploration rigoureuse de l'environnement.Les contributions de cette thèse sont les suivantes. Premièrement, comme désiré Ev-ITER peut être lancé en ligne, et sans nécessiter de vérité terrain ou d'assistance. Deuxièmement, Ev-ITER surpasse les approches autonomes en robotique évolutionnaire en terme d'exploration de l'arène. Troisièmement, le contrôleur Ev-ITER est doté d'une certaine généralité, dans la mesure où il est capable d'explorer efficacement d'autres arènes que celle considérée pendant la première phase de l'évolution. Il est à souligner que la généralité du contrôleur appris vis-à-vis de l'environnement d'entrainement a rarement été considérée en apprentissage par renforcement ou en robotique évolutionnaire. / This thesis is concerned with building autonomous exploratory robotic controllers in an online, on-board approach, with no requirement for ground truth or human intervention in the experimental setting.This study is primarily motivated by autonomous robotics, specifically autonomous robot swarms. In this context, one faces two difficulties. Firstly, standard simulator-based approaches are hardly effective due to computational efficiency and accuracy reasons. On the one hand, the simulator accuracy is hindered by the variability of the hardware; on the other hand, this approach faces a super-linear computational complexity w.r.t. the number of robots in the swarm. Secondly, the standard goal-driven approach used for controller design does not apply as there is no explicit objective function at the individual level, since the objective is defined at the swarm level.A first step toward autonomous exploratory controllers is proposed in the thesis. The Evolution & Information Theory-based Exploratory Robotics (Ev-ITER) approach is based on the hybridization of two approaches stemming from Evolutionary Robotics and from Reinforcement Learning, with the goal of getting the best of both worlds: (i) primary controllers, or crawling controllers, are evolved in order to generate sensori-motor trajectories with high entropy; (ii) the data repository built from the crawling controllers is exploited, providing prior knowledge to secondary controllers, inspired from the intrinsic robust motivation setting and achieving the thorough exploration of the environment.The contributions of the thesis are threefold. Firstly, Ev-ITER fulfills the desired requirement: it runs online, on-board and without requiring any ground truth or support. Secondly, Ev-ITER outperforms both the evolutionary and the information theory-based approaches standalone, in terms of actual exploration of the arena. Thirdly and most importantly, the Ev-ITER controller features some generality property, being able to efficiently explore other arenas than the one considered during the first evolutionary phase. It must be emphasized that the generality of the learned controller with respect to the considered environment has rarely been considered, neither in the reinforcement learning, nor in evolutionary robotics.

Cette thèse se situe dans le contexte de l'optimisation. Deux grandes parties s'en dégagent ; la première concerne l'utilisation d'algorithmes évolutionnaires pour résoudre des problèmes d'optimisation continue et sans dérivées. La seconde partie concerne l'optimisation de séquences de décisions dans un environnement discret et à horizon fini en utilisant des méthodes de type Monte-Carlo Tree Search. Dans le cadre de l'optimisation évolutionnaire, nous nous intéressons particulièrement au cadre parallèle à grand nombre d'unités de calcul. Après avoir présenté les algorithmes de référence du domaine, nous montrons que ces algorithmes, sous leur forme classique, ne sont pas adaptés à ce cadre parallèle et sont loin d'atteindre les vitesses de convergence théoriques. Nous proposons donc ensuite différentes règles (comme la modification du taux de sélection des individus ainsi que la décroissance plus rapide du pas) afin de corriger et améliorer ces algorithmes. Nous faisons un comparatif empirique de ces règles appliquées à certains algorithmes. Dans le cadre de l'optimisation de séquences de décisions, nous présentons d'abord les algorithmes de référence dans ce domaine (Min-Max, Alpha-Beta, Monte-carlo Tree Search, Nested Monte-Carlo). Nous montrons ensuite la généricité de l'algorithme Monte-Carlo Tree Search en l'appliquant avec succès au jeu de Havannah. Cette application a été un réel succès puisqu'aujourd'hui les meilleurs joueurs artificiels au jeu de Havannah utilisent cet algorithme et non plus des algorithmes de type Min-Max ou Alpha-Beta. Ensuite, nous nous sommes particulièrement intéressés à l'amélioration de la politique Monte-Carlo de ces algorithmes. Nous proposons trois améliorations, chacune étant générique. Des expériences sont faites pour mesurer l'impact de ces améliorations, ainsi que la généricité de l'une d'entre elles. Nous montrons à travers ces expériences que les résultats sont positifs. / In this thesis we study two optimization fields. In a first part, we study the use of evolutionary algorithms for solving derivative-free optimization problems in continuous space. In a second part we are interested in multistage optimization. In that case, we have to make decisions in a discrete environment with finite horizon and a large number of states. In this part we use in particular Monte-Carlo Tree Search algorithms. In the first part, we work on evolutionary algorithms in a parallel context, when a large number of processors are available. We start by presenting some state of the art evolutionary algorithms, and then, show that these algorithms are not well designed for parallel optimization. Because these algorithms are population based, they should be we well suitable for parallelization, but the experiments show that the results are far from the theoretical bounds. In order to solve this discrepancy, we propose some rules (such as a new selection ratio or a faster decrease of the step-size) to improve the evolutionary algorithms. Experiments are done on some evolutionary algorithms and show that these algorithms reach the theoretical speedup with the help of these new rules.Concerning the work on multistage optimization, we start by presenting some of the state of the art algorithms (Min-Max, Alpha-Beta, Monte-Carlo Tree Search, Nested Monte-Carlo). After that, we show the generality of the Monte-Carlo Tree Search algorithm by successfully applying it to the game of Havannah. The application has been a real success, because today, every Havannah program uses Monte-Carlo Tree Search algorithms instead of the classical Alpha-Beta. Next, we study more precisely the Monte-Carlo part of the Monte-Carlo Tree Search algorithm. 3 generic rules are proposed in order to improve this Monte-Carlo policy. Experiments are done in order to show the efficiency of these rules.

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 thesis is performing a study on the law control synthesis for PMSM direct driving to a load having its mechanical parameters variant. Furthermore, only the motor position is sensored. The control law aim is to minimize the eects of these variations while keeping the performance inside industrial specifications (response time at 5%, overshoot, implementation and synthesis simplicity). As a result, an observer is programmed jointly with a controller. A state feedback controller deduced from a linear quadratic minimization is associated with a Kalman observer. These both structures employ standard method definitions : poles placement and arbitrary weight of Kalman matrices choice. Two definitions strategies are employed for the observer. The first is the classical arbitrary weights choice. A lot of degrees of freedom are accessible and allow this observer to impose a good behaviour to the system. The second defines the system dynamic matrix variation as the state space noise matrix. The number of degrees of freedom decreases dramatically. However the behaviour is kept as well as the previous case. This method is then easy to understand for an engineer, gives good result but non robust in an automatic sense. Consequently, an automatic study on robustness, the micro- analysis, is added to this control definition for theoretically checking. In parallel with the study robustness, an evolutionnary algorithm leads to a quicker and more accurate synthesis than a human operator. Indeed, in the case of systems having variant parameters, the optimal dynamics choice for the controller and the observer is not following the classical way. The dynamics are coupled or even mirrored ( the controller dynamic is slower than the observer one). At the end, experimental results allow to understand the way that observer or controller operate on the system.

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.

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.

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.

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.

La thése poursuit les travaux de la théorie des Jeux évolutionnaires Cette théorie est un cadre de modehsation de la dynamique des populations dans lequel les interactions entre agents sont modélisées par des dilemmes classiques de la théorie des Jeux. Les agents interagissent avec leurs pairs et les meilleurs comportements se diffusent. les moins performants tendent à disparaître. Les modèles spécifiés mettent notamment en évidence des conditions sur les rapports inter-individuels qui permettent de faire émerger des équilibres coopératifs. En supposant que chaque agent a des relations non plus avec tous les agents de la population mais seulement avec un sous-ensemble des agents de la population et toujours avec les mêmes, on augmente considérablement le nombre des dynamiques possibles. Cette démarche fait apparaître un réseau des interactions,.soit un graphe. La contrainte spatiale s'avère une condition favorable au maintien des comportements coopératifs et de la biodiversité des comportements. L'analyse formelle de la convergence n'est généralement plus possible et les modèles sont étudiés par simulation. La these poursuit l'étude de l'impact de la répartition spatiale. Elle introduit un nouveau modèle de répartition spatiale où des communautés d'agents sont en réseau et non plus des agents. Ce modèle permet de mettre en évidence de nouvelles formes d'attracteurs coopératifs et de nouvelles conditions au maintien de la biodiversité. La thèse montre aussi la possibilité de convergence de marchés vers des équilibres non concurrentiels et de maintien de comportements coopératifs, des comportements de cartel.