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.