<  Back to the Polytechnique Montréal portal

Algorithme de recherche directe pour l’optimisation robuste de fonctions bruitées

Amina Ihaddadene

Masters thesis (2014)

[img]
Preview
Download (701kB)
Cite this document: Ihaddadene, A. (2014). Algorithme de recherche directe pour l’optimisation robuste de fonctions bruitées (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1635/
Show abstract Hide abstract

Abstract

RÉSUMÉ : Ce mémoire considère les problèmes d’optimisation de type boîte-noire, pour lesquels les fonctions définissant le problème sont complexes, difficiles à évaluer ou leur expression analytique est inconnue. Pour la plupart des problèmes industriels, il s’agit d’un programme informatique complexe et souvent inaccessible pour des raisons de confidentialité. L’exploitation de ces fonctions se fait par l’analyse des réponses à des entrées données, elles sont considérées comme des boîtes-noires sans aucune hypothèse sur les propriétés des fonctions. En optimisation de boîtes-noires, les méthodes mathématiques classiques ne sont pas applicables étant donné qu’elles reposent sur la différentiabilité, continuité, etc. C’est pourquoi plusieurs algorithmes sans dérivées conçus pour résoudre ce type de problèmes ont été développés et ne requièrent aucune hypothèse sur la fonction. La modélisation par les boîtes-noires ainsi que l’application des algorithmes sans dérivées ont permis de résoudre des problèmes d’optimisation des plus difficiles. Cependant, l’utilisation de ces algorithmes peut retourner des solutions affectées par le bruit. Les problèmes considérés ici sont ceux où le bruit est présent autant sur les entrées que sur la sortie de la boîte-noire. La solution obtenue par des algorithmes d’optimisation n’est pas désirable. En effet, lorsque les solutions peuvent varier dans un intervalle comme la tolérance de production, une légère modification de la solution optimale dans son intervalle de tolérance peut détériorer la performance de cette solution. Dans le contexte où la fonction objectif est à minimiser, la solution donnant une petite valeur de l’objectif n’est pas celle qu’on recherche, on s’intéresse plutôt à une solution robuste. La robustesse ici se traduit par une petite variation de la valeur de l’objectif dans un voisinage de la solution proposée. La contribution de ce mémoire est le développement d’un algorithme d’optimisation robuste, nommé RobustMads basé sur un algorithme de recherche directe, traitant les fonctions bruitées et retournant une solution robuste. Cet algorithme propose une façon judicieuse de lisser les valeurs de la fonction objectif pour corriger les valeurs bruitées. Dans le contexte où l’évaluation des fonctions est coûteuse, cette technique de lissage ne nécessite aucune évaluation supplémentaire. Une solution robuste est celle ayant un large voisinage dans lequel la valeur de la fonction varie peu. On introduit quatre mesures différentes pour mesurer la robustesse d’une solution. L’analyse des résultats de l’application de RobustMads sur une batterie de fonctions tests, dont deux types de bruits, ont été testés, a montré que l’algorithme est capable de retourner des solutions robustes. De plus, plus le niveau de bruit est élevé, plus RobustMads améliore la solution.----------ABSTRACT : This work considers blackbox optimization problems for which the objective function is complex, has no known analytical expression or may be costly to evaluate. In most industrial problems, the function may come from a complex software from which the code cannot be accessed for confidentiality purposes. The exploitation of such functions is done by analyzing its response to given inputs. They are considered blackbox functions on which no hypothesis is made about their properties. In blackbox optimization, classical mathematical methods cannot be applied because they rely on differentiability and continuity, just to name a few. For this reason, derivative-free optimization algorithms that do not require any assumption about the objective function are developed. Derivative-free algorithms and blackbox modeling have made it possible to solve some very hard optimization problems. Unfortunately, these algorithms may return a solution affected by the noise. These are problems that have a stochastic noise presence on the inputs as well as the outputs. The optimal solution obtained from classical algorithms may not be desirable. For example, when there exist a known uncertainty on some input variables, a slight variation of the solution may deteriorate the solution. In the case of a minimization problem, one would be looking not only to minimize the function, but also to obtain a robust solution. Here, a robust solution is one for which the objective function undergoes a slight deterioration within its neighborhood. The main contribution of this work is the development of a robust optimization algorithm named RobustMads, based on a direct search algorithm and designed for functions that include a stochastic noise and that returns a robust solution. In a context where evaluating the objective function may be costly, this algorithm proposes a judicious approach to smoothing the values of the objective function that does not require any additional evaluation. A robust solution possesses a large neighborhood for which the objective function varies slightly. Four means of measuring the robustness of a solution are introduced. The analysis of the results of the application of RobustMads on a series of test functions, including two different types of noise, shows that the algorithm is capable of finding robust solutions. Our numerical experiments suggest that the higher the noise, the more RobustMads improves the solution.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Charles Audet and Sébastien Le Digabel
Date Deposited: 01 Apr 2015 16:14
Last Modified: 24 Oct 2018 16:11
PolyPublie URL: https://publications.polymtl.ca/1635/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only