Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de

Doctorat
Equipe : Graphes, Algorithmes et Combinatoire

Hypercubes latins maximin pour l’échantillonnage de systèmes complexes

Début le 01/10/2014
Direction : TOMASIK, Joanna
[RIMMEL Arpad et WEISSER Marc-Antoine]

Ecole doctorale : ED STIC 580
Etablissement d'inscription : Centrale Supélec

Lieu de déroulement :

Soutenue le 24/01/2018 devant le jury composé de :
Directeur de thèse :
- Mme Joanna TOMASIK CentraleSupélec

Rapporteurs :
- M. Jarosław BYRKA University of Wrocław
- M. Tristan CAZENAVE Université Paris-Dauphine

Examinateurs :
- Mme Cristina BAZGAN Université Paris-Dauphine
- M. Yannis MANOUSSAKIS Université Paris-Sud
- M. Arpad RIMMEL CentraleSupélec
- M. Marc-Antoine WEISSER CentraleSupélec
- M. Bertrand LE CUN Google Inc.

Activités de recherche :

Résumé :
Un hypercube latin (LHD) est un ensemble de n points en dimension k, à coordonnées entières, contenus dans un hypercube de taille n k , et tel que les points ne partagent pas de coor- données sur aucune dimension. Un LHD maximin est un LHD tel que la distance de séparation, c’est-à-dire la distance minimale entre deux points, est maximale. Les LHDs maximin sont par- ticulièrement utilisés pour la construction de métamodèles en raison de leurs bonnes propriétés pour l’échantillonnage. Comme la plus grande partie des travaux concernant les LHD se sont concentrés sur leur construction par des algorithmes heuristiques, nous avons décidé de produire une étude détaillée du problème, et en particulier de sa complexité et de son approximabilité en plus des algorithmes heuristiques permettant de le résoudre en pratique. Pour conduire cette étude, nous avons généralisé le problème de construction d’un LHD maximin en définissant le problème de compléter un hypercube latin entamé en respectant la contrainte maximin: étant donné un LHD partiel (un LHD auquel il manque des points), lui ajouter des points de manière à obtenir un LHD avec une distance de séparation maximum. Le sous-problème dans lequel le LHD partiel est vide correspond au problème de construction de LHD classique. Nous avons étudié la complexité du problème de complétion et avons prouvé qu’il est NP-complet pour toutes les normes en dimension k ≥ 3, et pour les normes usuelles (i.e. les normes L p , avec p ∈ N et la norme L ∞ ) dans le plan. N’ayant pas déterminé la complexité du sous-problème, nous avons cherché des garanties de performances pour les algorithmes résolvant les deux problèmes. D’un côté, nous avons prouvé que le problème de complétion n’est approximable pour aucune norme en dimensions k ≥ 3. Nous avons également prouvé un résultat d’inapproximabilité plus faible pour la norme L ∞ en dimension k = 2. D’un autre côté, nous avons proposé un algorithme d’approximation pour le problème de construction, et avons calculé le rapport d’approximation grâce à deux bornes supérieures que nous avons établies. En plus de l’aspect théorique de cette étude, nous avons travaillé sur les algorithmes heuristiques, et en particulier sur la méta-heuristique du recuit simulé. Nous avons proposé une nouvelle fonction d’évaluation pour le problème de construction et de nouvelles mutations pour les deux problèmes, permettant d’améliorer les résultats rapportés dans la littérature. Nous avons observé que le comportement du problème de complétion change en fonction du nombre de points initiale- ment présent dans le LHD partiel, faisant varier la mutation la plus adaptée au problème. Nous avons pris ce fait en compte et amélioré le recuit simulé en utilisant une méthode de bandit pour choisir la mutation la plus appropriée pendant le déroulement de l’algorithme, dépassant chaque mutation individuelle lorsque le nombre de points présents initialement est intermédiaire.