Maximin Latin hypercubes for experimental design
Hypercubes Latins maximin pour l’echantillonage de systèmes complexes
Résumé
A maximin Latin Hypercube Design (LHD) is a set of point in a hypercube which do not share a coordinate on any dimension and such that the minimal distance between two points, is maximal. Maximin LHDs are widely used in metamodeling thanks to their good properties for sampling. As most work concerning LHDs focused on heuristic algorithms to produce them, we decided to make a detailed study of this problem, including its complexity, approximability, and the design of practical heuristic algorithms.We generalized the maximin LHD construction problem by defining the problem of completing a partial LHD while respecting the maximin constraint. The subproblem where the partial LHD is initially empty corresponds to the classical LHD construction problem. We studied the complexity of the completion problem and proved its NP-completeness for many cases. As we did not determine the complexity of the subproblem, we searched for performance guarantees of algorithms which may be designed for both problems. On the one hand, we found that the completion problem is inapproximable for all norms in dimensions k ≥ 3. We also gave a weaker inapproximation result for norm L1 in dimension k = 2. On the other hand, we designed an approximation algorithm for the construction problem which we proved using two new upper bounds we introduced.Besides the theoretical aspect of this study, we worked on heuristic algorithms adapted for these problems, focusing on the Simulated Annealing metaheuristic. We proposed a new evaluation function for the construction problem and new mutations for both the construction and completion problems, improving the results found in the literature.
Un hypercube latin (LHD) maximin est un ensemble de points contenus dans un hypercube tel que les points ne partagent de coordonnées sur aucune dimension et tel que la distance minimale entre deux points est maximale. Les LHDs maximin sont particuliè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.Nous avons généralisé le problème de construction d’un LHD maximin en définissant le problème de compléter un LHD entamé en respectant la contrainte maximin. 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 dans de nombreux cas. 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 L1 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.
Origine : Version validée par le jury (STAR)
Loading...