Historique: PhD Theses
Aperçu de cette version: 24
Click on the + signs for more details on a PhD
Building processes optimization: Toward an artificial ontogeny based approach Alexandre Devert, June 2009
[+]- Defended on June 21. 2009 at LRI (Univ. Paris-Sud)
- Advisors: Nicolas Bredèche et Marc Schoenauer
- Dissertation in PDF
- Abstract:
Optimisation par Stratégies d'Evolution : Convergence et vitesses de convergence pour des fonctions bruitées - Résolution d'un problèmed'identification Mohamed Jebalia, Dec. 2008
[+]- Defended on December.19.2008 at LRI (at Univ. Paris Sud)
- Advisors: Anne Auger, Marc Schoenauer and Taïeb Hadhri
- Manuscript
- Abstract: Le cadre général de cette thèse est la résolution du problème d'optimisation non linéaire continu suivant : Etant donnée une fonction objectif f non-linéaire définie sur un ouvert de R^d, le but est de chercher le vecteur (donc d paramètres) qui minimise (ou maximise) la fonction f.
Dans cette thèse, on s'intéresse plus particulièrement à la résolution de ce problème par les Stratégies d'Evolution (SE). Les SE, algorithmes évolutionnaires opérant sur des espaces d'états continus, ont montré leur efficacité pratique pour la résolution de problèmes d'optimisation réels. Cependant les SE, comme l'ensemble des algorithmes évolutionnaires, ne sont pas basés sur une approche théorique, mais adaptés d'une imitation des principes de l'évolution naturelle, la survie des plus adaptés.
Dans une première partie de cette thèse, on étudie théoriquement et numériquement la convergence des SE. On étudie en particulier l'optimisation des fonctions objectifs bruitées. On montre en particulier que des niveaux assez élevés du bruit peuvent engendrer la non convergence de l'algorithme. Les expressions des vitesses de convergence sont établies théoriquement. Les cas de convergence et divergence sont distingués théoriquement et numériquement.
La seconde partie traite une application à un problème réel en génie chimique, l'identification de paramètres pour le système de la chromatographie analytique. L'approche évolutionnaire est comparée à une méthode déterministe basée sur le calcul du gradient numérique. L'approche évolutionnaire est plus robuste sur ce spécifique cas d'étude.
Evaluation d'algorithmes pour et par l'apprentissage Nicolas Baskiotis, Sept. 2008
[+]- Defended on June 22. Sept. 2008 at LRI (Univ. Paris-Sud)
- Advisor: Michèle sebag
- Dissertation in PDF
- Abstract: One of the main concerns involving machine learning applications is the a priori choice of an algorithm likely to yield the best classification performances. Our work is inspired by research in combinatorial optimisation on the phase transition problem. We suggest a dual approach to the standard view on this problem through metaleraning. Our goal is to build a competence map according to descriptors on the problem space which enables to identify the regimes where the system's performance are steady. We assess this approach on C4.5.
The second part of our work deals with machine learning problems in software testing. More precisely, we study a statistical structural method of software testing that uses the sampling of the so-called feasible paths in the control graph of the problems that is to be tested. In certain cases, the portion of feasible paths is very low, which hinders this method. Our goal is to design a learning and optimisation system that yields a random generator biaised towards the feasible paths and that warrantees a suitable sampling of the target concept. We designed the MLST system that implements active learning in a graph. We tested our work on both real and artificial problems and showed that our system achieves significantly improvement regarding the coverage of target concepts with respect to the initial data.
Une contribution à l'apprendissage par renforcement ; application au Computer GO Sylvain Gelly, Sept. 2007
[+]- Defended on Sept. 25. 2007 at Univ. Paris-Sud
- Advisors: Michèle Sebag and Nicolas Bredèche
- Manuscript (in English after the title
- Abstract : Reinforcement Learning (RL) is at the interface of control theory, supervised and unsupervised learning, optimization and cognitive sciences. While RL addresses many objectives with major economic impact, it raises deep theoretical and practical difficulties. This thesis brings some contributions to RL, mainly on three axis. The first axis corresponds to environment modeling, i.e. learning the transition function between two time steps. Factored approaches give an efficiently framework for the learning and use of this model. The Bayesian Networks are a tool to represent such a model, and this work brings new learning criterion, either in parametric learning (conditional probabilities) and non parametric (structure). The second axis is a study in continuous space and action RL, thanks to the dynamic programming algorithm. This analysis tackles three fundamental steps: optimization (action choice from the value function), supervised learning (regression) of the value function and choice of the learning examples (active learning). The third axis tackles the applicative domain of the game of Go, as a high dimensional discrete control problem, one of the greatest challenge in Machine Learning. The presented algorithms with their improvements made the resulting program, MoGo, win numerous international competitions, becoming for example the first go program playing at an amateur dan level on 9x9.
Evolutionary Algorithms for velocity model identification from seismic data Vijay Pratap Singh, Dec. 2006
[+]- Defended on Dec. 18. 2006 at École des Mines de Paris (GéoSciences)
- Advisor : Marc Schoenauer
- Manuscript
- Abstract :
Evolutionary Design of Geometric-based Fuzzy Systems Carlos Kavka, July 2006
[+]- Defended on July 6. 2006 at Université Paris-Sud (Computer Science)
- Advisor : Marc Schoenauer
- Manuscript
- Abstract : The main contribution of this thesis is the definition of a new model of fuzzy system where the exponential growth of the number of rules with respect to the number of input variables is reduced, with an efficient representation for the design, using evolutionary algorithms. In the proposed model, the partition of the input space is not defined as a regular structure built as the intersection of the linguistic labels of input variables, as usual in fuzzy systems, but in terms of multidimensional regions, each one associated with a single fuzzy rule.
The partition is defined based on well known concepts of computational geometry: the Voronoi diagrams and the Delaunay triangulations. The fuzzy system defined in terms of this partition has a clear and appealing structure. The representation of the individuals for evolutionary algorithms is simple, since each region in the multidimensional input space is represented with a single point. This geometric representation allows the use of geometric based operators for evolution. As an added advantage, the model allows an interesting approach for the inclusion of a priori knowledge about the solution of the problem in the individuals before and during the evolution.
Experimental results on evolutionary design of Voronoi based fuzzy systems are presented in two control problems: an inverted cart pole system and a typical robot control application. The approach is extended to the design of recurrent Voronoi-based fuzzy systems. This extension is evaluated in two other control problems: a system identification problem, where the outputs are defined in terms of past inputs and outputs, and a problem from evolutionary robotics, where the ability to introduce a priori knowledge in the form of recursive rules is demonstrated.
Étude de l'apprentissage actif. Application à la conduite d'expériences Jérémie Mary, Dec. 2005
[+]- Defended on December 12. 2005 at Université Paris-Sud (Computer Science)
- Advisor : Antoine Cornuéjols and Michèle Sebag
- Manuscript(in French)
- Abstract :
Approches évolutionnaires pour la robotique modulaire et anticipatoire Nicolas Godzik, Sep. 2005
[+]- Defended on September 29. 2005 at Université Paris-Sud (Computer Science)
- Advisor : Marc Schoenauer
- Manuscript(in French)
- Abstract : L'architecture de subsomption de Brooks basée sur la modularité et sur une hiérarchie de comportements s'avéra être un grand pas vers les applications réelles après l'échec relatif des méthodes classiques. Cependant, l'inconvénient de cette méthode réside dans le fait que tout est mis en place par un concepteur humain, et plus la tâche du robot est ardue, plus la conception des modules nécessaires l'est aussi.
D'autre part, la robotique évolutionnaire, qui optimise par évolution artificielle des contrôleurs neuronaux (poids et éventuellement architecture), est une approche boîte noire par rapport aux comportements, mais requiert la définition d'une (ou plusieurs) fonction objectif dont la complexité va elle aussi croître avec la difficulté de la tâche demandée au robot.
L'approche des ``contrôleurs symboliques et des ``superviseurs proposée dans cette thèse tente d'établir un compromis entre les deux précédentes. Les sorties ne sont plus des ordres moteurs élémentaires mais des comportements plus évolués (comme ``aller tout droit, ``tourner à gauche, ...). Le choix peut également être effectué avec une librairie de comportements de plus haut niveau (comme ``explorer, ``aller vers la lumière, ...). Cette approche a été validée expérimentalement dans une expérience d'exploration, ou bien encore de recharge d'énergie.
Le second axe de recherche de cette thèse s'intéresse à l'apprentissage dans le cadre de la robotique évolutionnaire. Le baldwinisme qui consiste à modifier le génotype pendant la vie du robot (pendant l'évaluation des individus), mais qui reste sans conséquence sur le génotype lui-même pour la suite de l'évolution artificielle, est étudié ici à travers diverses expériences.
Les réseaux dits "auto-teaching", qui permettent au robot de modifier son comportement durant sa vie en s'appuyant sur un réseau modèle lui aussi obtenu par évolution, sont étudiés ici avec attention. Des défauts patents de ses propriétés de généralisation ont été mis en évidence.
Une architecture baptisée Action, Anticipation, Adaptation (AAA) a été créée pour tenter de pallier ces défauts. Cette architecture neuronale a donc trois tâches à remplir: l'action (contrôler les moteurs du robot), l'anticipation (basée sur les perceptions du robot mais également sur ses actions moteurs) et l'adaptation (basée sur la différence entre les sensations prédites au temps t et les sensations réellement observées au temps t+1). Les erreurs sur la prédiction des futures sensations du robot sont utilisées pour modifier en ligne les poids du contrôleur.
L'analyse détaillée de cette architecture d'une part a montré des capacités de généralisation plus robustes que celles des réseaux auto-teaching, et d'autre part a mis en évidence quelques capacités d'adaptation.
Contributions théoriques et numériques à l'optimisation continue par Algorithmes Evolutionnaires Anne Auger, Dec. 2004
[+]- Defended on December 20. 2004 at Université Paris 6 (Applied Maths)
- Advisor : Marc Schoenauer
- Manuscript(in French)
- Abstract : Les Algorithmes Evolutionnaires sont des algorithmes d'optimisation stochastique inspirés de la théorie de l'évolution des espèces de Darwin. Nous les étudions ici dans le cadre de l'optimisation continue, c'est-à-dire pour la minimisation de fonctions à variables relles.
Le principe de ces algorithmes consiste à faire évoluer un ensemble de points en rajoutant typiquement un vecteur gaussien centré aux points existants (ceci constitue l'opération dite de mutation), puis à slectionner certains de ces points (ceux ayant les valeurs de fonction les plus basses) et recommencer. Un point crucial de ces algorithmes est l'adaptation des paramètres de l'algorithme aux différentes phases de la recherche d'un optimum : la phase d'exploration et la phase d'exploitation. En particulier, l'adaptation des paramtères du vecteur gaussien utilisé pour la mutation a constitué une part importante des développements effectués sur ces algorithmes ces dernières années. On distingue les méthodes adaptant seulement le pas de la mutation des méthodes adaptant également la matrice de covariance de la mutation.
Dans une première partie, nous proposons une méthode d'apprentissage de la matrice de covariance pour la mutation, basée sur une approximation locale de la fonction optimiser.
Dans une deuxième partie, nous étudions sur un plan théorique les méthodes d'adaptation du pas de la mutation et démontrons des conditions suffisantes reliant la taille de la population et les paramètres de la mutation garantissant la convergence linaire de certaines de ces méthodes sur certaines classes de fonctions. Ces études théoriques utilisent d'une part la théorie des martingales et d'autre part reposent sur l'étude du modèle markovien associé à l'algorithme évolutionnaire. Dans ce dernier cas, la convergence de l'algorithme précisment étudi repose sur l'étude de conditions de stabilité d'une chaîne de Markov sous-jacente à l'algorithme. Ces conditions de stabilité sont établies à l'aide de conditions de drift de Foster-Lyapunov.
Dans une troisième partie, nous présentons une application des algorithmes évolutionnaires à un problème de contrôle en physique quantique.
Intégration de la construction de la terminologie de domaines spécialisés dans un processus global de fouille de textes Mathieu Roche, Dec. 2004
[+]- Defended on December 13. 2004 at Université Paris-Sud
- Advisor : Yves Kodratoff
- Dissertation should be available soon.
- Abstract : L'extraction d'information à partir de textes spécialisés exige l'application d'un processus complet de fouille de textes. Une des étapes de ce processus consiste à extraire les termes dans les textes. Les termes sont définis comme des groupes de mots représentant des traces linguistiques de concepts. Le terme "data mining" évoque, par exemple, le concept de "technique informatique".
Enfin, une méthode fondée sur un processus d'apprentissage supervisé est proposée afin d'améliorer la qualité de la terminologie extraite.
Algorithmes évolutionnaires assistés par des méthodes d'apprentissage en grandes dimensions Kamal Abboud, Oct. 2004
[+]- Defended October 6. 2004 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- Manuscript (in French)
- Abstract : Les algorithmes évolutionnaires sont des algorithmes d'optimisation stochastique d'ordre zéro qui s'appliquent à des espaces de recherche non standard, pouvant par exemple combiner des variables continues et discrètes. Ces algorithmes sont utilisés pour résoudre des problèmes difficiles où ils permettent souvent de proposer de meilleures solutions que les algorithmes classiques d'optimisation lorsque ces derniers s'appliquent. Leur principal point faible est la nécessité d'évaluer la fonction objectif un grand nombre de fois. Ceci les rend inapplicables en pratique pour des problèmes où l'évaluation de cette fonction est coûteuse en temps de calcul (résultat d'un lourd calcul d'éléments finis par exemple). Le but de la thèse est de proposer une méthode permettant de diminuer le nombre de calculs de la fonction objectif dans le cas de fonctions coûteuses en temps de calcul et ainsi de diminuer le coût calcul. La méthode consiste à introduire un nouvel opérateur de mutation, nommé SDM (pour {\em Surrogate Deterministic Mutation}, basé sur une méthode d'approximation (nous étudierons en particulier comme méthodes d'approximation les Machines à Support Vecteur — SVM — et la méthode du Krigeage). L'opérateur SDM utilise des individus déjà évalués et se trouvant localement autour de l'individu devant être muté, pour définir une fonction modèle qui est facile à optimiser. Pour obtenir un bon modèle, non seulement le nombre de points d'exemples est important, mais aussi leur disposition autour de l'individu à muter. L'individu trouvé après optimisation du modèle est évalué avec la vraie fonction objectif et réinjecté dans la population. Nous avons démontré sur différentes fonctions-tests une nette amélioration de la convergence locale par rapport à un algorithme évolutionnaire classique, en l'occurrence les stratégies d'évolution (ES).
La thèse est formée de six chapitres :
- Le premier chapitre consiste en un survol de l'état de l'art des différentes techniques qui seront utilisées ensuite dans le reste de la thèse. En premier lieu, nous présentons les algorithmes d'optimisation déterministes d'ordre supérieur à un (optimisation différentiable). Ensuite, nous introduisons les algorithmes stochastiques allant des méthodes de Monte Carlo, passant par le recuit simulé, les algorithmes évolutionnaires (dont les stratégies d'évolutions (ES)) et pour finir la méthode de l'Adaptation de la Matrice de Covariance (CMA). Puis nous passons en revue les principales méthodes d'approximation disponibles : des représentations sous forme de maillage éléments finis aux méthodes spectrales (dont lapproximation de Legendre) et les méthodes à noyau (dont la méthode de Machines à Support Vecteur et la méthode de Krigeage). Finalement, nous faisons un état de l'art détaillé des méthodes hybrides précédemment proposées combinant une approche déterministe et/ou une approche stochastique et/ou une méthode d'approximation. Le chapitre se termine sur la présentation de l'ensemble des fonctions-tests qui seront ensuite utilisées pour valider notre approche.
- Le deuxième chapitre discute la possibilité de modéliser la fonction objectif à partir de points pré-évalués et d'utiliser les optimaux des modèles approchés comme des candidats-optima de la fonction objectif. Nous utilisons comme méthodes d'approximations les SVM et le Krigeage. Pour déterminer les optima du modèle nous utilisons comme algorithme déterministe la méthode L-BFGS-B. Ces méthodes d'approximation déterminent d'une manière unique un mo\-dè\-le à partir des points évalués et des paramètres représentant la régularité et l'erreur souhaitée sur les points (SVM). Le choix de ces paramètres offre la possibilité de contrôler les modèles de façon à trouver un modèle adapté à nos besoins. Nous testons différents critères pour le choix de ces paramètres. Notons que le but de l'approximation n'est pas ici d'interpoler le mieux possible la fonction objectif, mais de trouver un individu meilleur que les points d'apprentissage en un temps raisonnable. Les différents tests de ce chapitre seront faits sur la fonction sphère.
- Le troisième chapitre a pour but de définir un algorithme stochastique itératif simple, nommé AlgoAlea, basé sur une loi définie à travers des paramètres constants. Après une brève étude de la convergence de cet algorithme, nous l'hybridons respectivement avec une méthode déterministe (BFGS) pour définir un premier algorithme nommé AlgoDet, puis avec une méthode d'approximation (SVM ou Krigeage) et une méthode déterministe (BFGS), définissant l'algorithme AlgoApp. Dans le cadre itératif et dans le souci d'optimiser la recherche des paramètres de régularité et les autres paramètres définissant le modèle, nous proposons une approche dynamique dans la recherche des paramètres d'une itération à l'autre. Nous validons notre approche sur les fonctions-tests décrites au chapitre 2. Pour finir, nous définissons une variante de l'algorithme hybride, variante nommée AlgoAppBis. Au lieu d'utiliser un algorithme déterministe pour optimiser le modèle, nous utilisons un algorithme évolutionnaire, les stratégies d'évolution (ES). Nous comparons enfin les différents algorithmes sur les fonctions-tests, et nous montrons que les algorithmes itératifs AlgoApp et AlgoAppbis ont un comportement quasi-déterministe, et nous pointons des difficultés d'un algorithme déterministe comme BFGS sur certaines fonctions-tests.
- Le quatrième chapitre consiste à pallier les problèmes rencontrés dans le chapitre précédant en proposant une hybridation de l'algorithme AlgoApp avec un algorithme évolutionnaire global, ici les Stratégies d'évolution isotropes, l'algorithme AlgoApp se chargeant de la recherche locale, et ES de la recherche globale. Pour cela nous introduisons l'opérateur de mutation SDM ({\em Surrogate Determnistic Mutation}). Chaque mutation correspond de fait à une itération élémentaire de l'algorithme AlgoApp. L'interaction entre SDM et ES s'effectue à travers les paramètres des mutations gaussiennes. Nous définissons ainsi un paramètre de contrôle qui agit directement sur l'équilibre exploration-exploitation. Nous comparons notre approche avec une autre approche, inspirée de MAES introduite par Thomas Bäck (elle-même représentante de l'approche dynamique définie par Andy Keane), et nous la validons sur les fonctions-tests.
- Dans le cinquième chapitre, nous appliquons SDM-ES à un problème pratique provenant de la finance quantitative. Il s'agit d'un modèle de marché incomplet qui traite la problématique du {\em smile} tout en proposant une couverture dynamique optimale. La calibration d'un tel modèle conduit à la résolution d'un problème de minimisation mal posé. Nous montrons que les méthodes hybrides de type SDM-ES peuvent apporter un plus par rapport à des méthodes déterministes comme L-BFGS-B qui ne donnent pas toujours la bonne solution.
- Enfin, le sixième chapitre conclut la thèse par un bref rappel des principaux résultats obtenus. Prenant comme exemple le cas de la fonction Rosenbrock, réputée difficile, nous donnons quelques perspectives sur les adaptations possibles des hybridations proposées aux cas mal conditionnés. Nous montrons qu'un couplage de SDM avec la méthode plus récente de l'Adaptation de la Matrice de Covariance (CMA) semble une voie très prometteuse. Nous montrons également que le noyau sigmoïde, bien que beaucoup plus délicat à maîtriser que le noyau Gaussien le plus utilisé (et en particulier utilisé dans la thèse), est très intéressant et mérite une étude systématique.
Application des Algorithmes Evolutionnaires aux problèmes d'optimisation multi-critère avec contraintes Olga Roudenko, March 2004
[+]- Defended on March 5. 2004 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- PDF file or gzipped Postscript (in French)
- Abstract :
Extraction de connaissances à partir de données textuelles et numériques Jérôme Azé, Dec. 2003
[+]- Defended on December 16. 2003 at Université Paris-Sud (Computer Science)
- Advisor : Yves Kodratoff
- Manuscript (in French)
- Abstract : Le travail réalisé dans le cadre de cette thèse concerne l'extraction de connaissances dans des données transactionnelles. L'analyse de telles données est souvent contrainte par la définition d'un support minimal utilisé pour filtrer les connaissances non intéressantes. Les experts des données ont souvent des difficultés pour déterminer ce support.
Nous avons ainsi pu proposer un algorithme permettant d'extraire ces règles sans utiliser la contrainte du support minimal. Le comportement de notre algorithme a été étudié en présence de données bruitées et nous avons pu mettre en évidence la difficulté d'extraire automatiquement des connaissances fiables à partir de données bruitées. Une des solutions que nous avons proposée consiste à évaluer la résistance au bruit de chaque règle et d'en informer l'expert lors de l'analyse et de la validation des connaissances obtenues.
Enfin, une étude sur des données réelles a été effectuée dans le cadre d'un processus de fouille de textes. Les connaissances recherchées dans ces textes sont des règles d'association entre des concepts définis par l'expert et propres au domaine étudié. Nous avons proposé un outil permettant d'extraire les connaissances et d'assister l'expert lors de la validation de celles-ci. Les différents résultats obtenus montrent qu'il est possible d'obtenir des connaissances intéressantes à partir de données textuelles en minimisant la sollicitation de l'expert dans la phase d'extraction des règles d'association.
Old PhD Theses (prepared at CMAP - Ecole Polytechnique)
Optimisation de Formes multi-critères par algorithmes évolutionnaires H. Hamda, May 2003
[+]- Defended on May 6. 2003 at École Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer and Taieb Hadhri (École Polytechnique de Tunis)
- PDF file (2 Mo, in French)
- Abstract :
Algorithmes Evolutionnaires: Prise en Compte des Contraintes et Application Réelle Sana Ben Hamida, Mar. 2001
[+]- Defended on March 27. 2001 at Université Paris Sud (Computer Science)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Application de l'évolution artificielle à la décongestion du trafic aérien Sofiane Oussedik, Dec. 2000
[+]- Defended on december 14. 2000 at Université Paris-Sud (Computer Science)
- Advisor: Marc Schoenauer and Daniel Delahaye
- gzipped Postscript in French.
Analyse d'Algorithmes d'Évolution Artificielle appliqués au domaine pétrolier : Inversion sismique et approximation de fonctions Frédéric Mansanné
[+]- Defended on December 13. 2000 at Université de Pau (Applied Maths)
- Advisors: Mohamed Amara and Marc Schoenauer
- gzipped Postscript in French.
Algorithmes d'évolution stochastique : du cadre binaire aux représentations de longueur variable. - Etudes théoriques et heuristiques de la convergence, aspects spatiaux et temporels Leila Kallel, Feb. 1999
[+]- Defended on February 5. 1999 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in English, except the firts introductory 40 pages.
Méthodes d'optimisation pour l'évitement aérien : systèmes centralisés, systèmes embarqués Frédéric Medioni
[+]- Defended in December 1998 at Ecole Polytechnique (Computer Sciences)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Etude de problèmes inverses par algorithmes d'évolution et réseaux de neurones Alessandro Fadda, June 1998
[+]- Defended in June 1998 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer -
- gzipped Postscript in French.
Optimisation d'interféromètres par algorithmes génétiques Lionel Taieb, May 1997
[+]- Defended in May 1997 at Ecole Polytechnique (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.
Optimum Design et Algorithmes Génétiques Couro Kane, July 1996
[+]- Defended in July 1996 at Université Paris 6 (Applied Maths)
- Advisor : Marc Schoenauer
- gzipped Postscript in French.