Opportunisme et ordonnancement en optimisation sans dérivées

Ce mémoire traite de comparaisons de stratégies algorithmiques applicables à certains algorithmes d'optimisation de boîtes noires. Une boîte noire est un problème typiquement lourd en temps de calcul, non différentiable, bruité et potentiellement propriétaire. Afin de résoudre ces problèmes, des techniques n'utilisant pas les informations sur les dérivées des expressions algébriques définissant les problèmes ont été conçues. Les méthodes ciblées pour y implémenter les stratégies algorithmiques sont celles figurant dans un cadre de travail spécifique. Les méthodes doivent contenir une étape nécessitant une séquence d'évaluations de la fonction objectif à des points figurant dans une liste prédéterminée. Les méthodes de recherche directe correspondent à ces critères ; elles sont des méthodes contenant une série d'évaluations de points, et basent la détermination de la prochaine liste de candidats sur les valeurs obtenues à ces points. Les méthodes d'optimisation par recherche directe identifiées sont la recherche par coordonnées (CS), la recherche par motifs généralisée(GPS), la recherche par ensembles générateurs (GSS), la recherche directe par treillis adaptatifs (MADS) et le filtrage implicite (IMFIL). La stratégie algorithmique étudiée est la stratégie opportuniste. Elle désigne l'arrêt de l'étape de l'algorithme comprenant une série d'évaluations séquentielles. L'arrêt peut-être fait après un ou plusieurs succès, c'est-à-dire l'évaluation d'un point pour lequel la valeur de la fonction objectif est inférieure à la minimale encourue précédemment dans la résolution. Plusieurs déclinaisons de la stratégie sont identifiées, implémentées et testées sur une batterie de problèmes tests, afin de déterminer numériquement leurs impacts. L'arrêt d'une série d'évaluations implique que l'ordre des points à évaluer impacte la performance de la stratégie opportuniste. On identifie les stratégies d'ordonnancements suivantes afin de les jumeler à la stratégie opportuniste et d'étudier leurs impacts : lexicographique, aléatoire, utilisant la direction du dernier succès et utilisant les modèles. Toutes ces stratégies sont implémentées et testées sur l'ensemble de problèmes tests. Les tests numériques sur un ensemble de problèmes incluant une boîte noire révèlent que l'opportunisme le plus rudimentaire, dont le critère d'arrêt est l'obtention d'un simple succès, est bénéfique à divers degrés pour toutes les méthodes de recherche directe identifiées sauf le filtrage implicite. Les stratégies d'ordonnancement utilisant les modèles, aléatoire et utilisant la direction du dernier succès, forment le classement des stratégies bénéfiques. L'ordonnancement lexicographique jumelé à l'opportunisme nuit aux algorithmes.