Sondes locales intensives lors de l'exécution de l'algorithme MADS dans un environnement parallèle

L'optimisation de boîte noire consiste en la résolution d'un problème (P) : min{f(x) : x 2 } pour lequel les valeurs de la fonction objectif et les contraintes définissant Ω ⊑ Rn sont le résultat de l'exécution d'une simulation numérique parfois coûteuse en temps ou en ressources. Lors de son étape de sonde, l'algorithme MADS évalue la fonction objectif et les contraintes autour du meilleur point connu suivant des directions qui forment un ensemble générateur positif de l'espace des solutions. Dans un soucis de performance, le logiciel NOMAD 4 qui implémente MADS, utilise une base positive, i.e., un ensemble générateur positif de cardinalité minimale. Pour un problème de dimension n, cette base positive est constituée de 2n directions orthogonales, donc chaque étape de sonde conduit à 2n évaluations de l'objectif et des contraintes. L'accès aux infrastructures à fort degré de parallélisme est de plus en plus facile. Par exemple, le centre de recherche d'Hydro-Québec (IREQ) possède une grille de calcul (CASIR) à 152 noeuds, et 36 CPUs par nœud. Dans ce contexte, lors de l'étape de sonde locale, l'exécution de NOMAD 4 conduit à une sous-utilisation des ressources à disposition. En effet, le nombre d'évaluations à effectuer est beaucoup plus petit que le nombre de processeurs disponibles. Il semble alors pertinent d'évaluer l'objectif et les contraintes suivant un plus grand nombre de directions. Ce mémoire étudie l'influence de l'augmentation du nombre de directions de sonde, ainsi que celle de la géométrie donnée à ces directions. Un critère d'intensification est établi pour augmenter le nombre de directions uniquement lorsque cela semble nécessaire. Ce critère a pour but d'éviter de fournir un grand nombre d'évaluations aux processeurs lorsqu'il semble relativement facile d'améliorer l'objectif et les contraintes. Quatre variantes du type d'intensification dynamique sont formulées. Un cadre de travail est proposé pour répartir les évaluations fournies par les stratégies de sonde sur un ensemble de processeurs lorsque des fonctions oracles sont rendues disponibles pour connaître le temps ou le travail nécessaire à chaque évaluation. Enfin, des essais numériques sont menés sur plusieurs problèmes analytiques sans contraintes, et sur un problème réaliste issu de la littérature. Les résultats obtenus sont interprétés à l'aide de profils de données en évaluations et en itérations. Le premier type de profil permet de juger des performances des stratégies implémentées selon le nombre d'appels à la boîte noire. Le second type de profil permet d'estimer les performances des stratégies selon le nombre de cycles d'occupation de ressources parallèles. Les résultats obtenus montrent que la géométrie donnée aux directions de sonde importe peu, seul le nombre de directions influe sur les performances de la résolution de (P). L'intensification dynamique permet d'économiser des évaluations, et dans certains cas, d'obtenir des résultats semblables au cas où le nombre de points générés est constant d'une itération à l'autre.

Abstract

Blackbox optimization typically arises when the objective function and constraints of a prob-lem (P) : min{f(x) : x 2 } are obtained by executing a numerical simulation that may be time-consuming or expensive in terms of ressources needed to be completed. During the poll step of the MADS algorithm, the objective function f and constraint functions delimiting Ω ⊑ Rn are evaluated near the best incubent following directions of a positive spanning set in the search space. As a performance issue, the software NOMAD 4 that implements MADS, uses a positive basis, which is a positive spanning set of minimal cardinality. For a problem of dimension n, this positive basis is composed of 2n orthogonal directions and so the poll step leads to 2n evaluations of the objective and constraints. Nowadays, access to massively parallel ressources is easier. For instance, the research laboratory of Hydro-Québec (IREQ) owns a supercomputer made of 152 nodes and 36 CPUs per node. In this context, at the poll step, the execution of NOMAD 4 leads to an underuse of the available ressources. Indeed, the number of evaluations is far lower than the number of available processors. It seems relevant to evaluate the objective and constraints in a larger number of polling directions. This study focuses on the influence of increasing the number of polling directions and the geometry used to build them. A criterion on increasing the number of polling directions is set up in order to feed processors with more evaluations only when it seems to be relevant. Hence, one avoid generating too much evaluations when improving the objectif function seems to be easy. Four di˙erent kinds of dynamic intensification are formulated. A load balancing framework is described to order evaluations on a set of processors based on oracle functions providing information on the workload or time needed to evaluate the objective and the constraints on a point. Numerical results on several analytical problems without constraints, and one real world problem from the litterature are presented to draw the behaviour of the poll strategies. The results are post-processed with data profile in terms of evaluations and iterations. The first type of profil allows one to see the performance of each strategies in term of number of calls to the blackbox while the second type of profil gives the performance results in term of parallel ressources occupation cycles. Regarding the results obtained, the geometry given to the poll directions set seems to have neglictable effect on the performances of solving (P). The factor with the most noticablenfluence is the number of polling directions generated. In some cases, dynamic intensification of the number of polling directions provides nearly the same performance in improving f but with less evaluations than when a constant number of points is generated trough iterations.