Optimisation aléatoire

L'optimisation aléatoire (OA) est une famille de méthodes d'optimisation numérique qui ne nécessite pas de connaître le gradient du problème pour être utilisée, comme dans le cas de fonctions non continues ou non différentiables. Ces méthodes sont aussi connues sous le nom de recherche directe, méthodes sans dérivation ou méthodes boîte noire.

Le nom d'optimisation aléatoire (random optimization) est attribué à Matyas[1], qui présenta une analyse mathématique de base des méthodes. L'optimisation aléatoire consiste en des déplacements itératifs vers de meilleures positions dans l'espace de recherche, positions déterminées selon une distribution normale autour de la position courante.

Algorithme

Soit la fonction devant être minimisée. Soit la position courante dans l'espace de recherche. L'algorithme d'optimisation aléatoire de base peut être décrit comme suit :

  • initialiser par une position au hasard dans l'espace ;
  • tant que la condition d'arrêt n'est pas vérifiée (c'est-à-dire jusqu'à être suffisamment proche de la solution recherchée), répéter :
    • créer une nouvelle position en ajoutant à un vecteur aléatoire distribué normalement,
    • si , se déplacer vers la nouvelle position : ,
  • fin de l'algorithme, est la solution recherchée.

Convergence et variantes

Matyas a montré que la forme basique de l'OA converge vers l'optimum d'une fonction unimodale simple en utilisant une preuve par limite : la convergence vers l'optimum est garantie après un nombre virtuellement infini d'itérations. Cependant, cette preuve n'est pas utile en pratique, où seul un nombre fini d'itérations peut être exécuté. En fait, une telle preuve par limite montre aussi qu'un échantillonnage aléatoire de l'espace de recherche mène inévitablement à un choix d'échantillon arbitrairement proche de l'optimum.

Des analyses mathématiques conduites par Baba[2] ainsi que Solis et Wets[3] ont établi que la convergence vers une région approchant l'optimum est inévitable sous certaines conditions faibles, pour des variantes de l'OA utilisant d'autres lois de probabilité pour l'échantillonnage. Une estimation du nombre d'itérations nécessaire pour approcher l'optimum est donnée par Dorea[4]. Ces analyses ont été critiquées par Sarma[5] via des tests empiriques, en utilisant les variantes de Baba et Dorea sur deux problèmes pratiques : l'optimum est atteint très lentement, et les méthodes se sont révélées incapables de trouver une solution convenable à moins de démarrer le processus d'un point déjà proche de l'optimum.

Voir aussi
  • Recherche aléatoire (en)
  • Luus-Jaakola (en)
  • Recherche par motif (en)
  • Optimisation stochastique (en)

Références
  1. (en) J. Matyas, « Random optimization », Automation and Remote Control, vol. 26, no 2,‎ , p. 246–253
  2. (en) N. Baba, « Convergence of a random optimization method for constrained optimization problems », Journal of Optimization Theory and Applications, vol. 33, no 4,‎ , p. 451–461
  3. (en) F.J. Solis et R.J-B. Wets, « Minimization by random search techniques », Mathematics of Operation Research, vol. 6, no 1,‎ , p. 19–30
  4. (en) C.C.Y. Dorea, « Expected number of steps of a random optimization method », Journal of Optimization Theory and Applications, vol. 39, no 3,‎ , p. 165–171
  5. (en) M.S. Sarma, « On the convergence of the Baba and Dorea random optimization methods », Journal of Optimization Theory and Applications, vol. 66, no 2,‎ , p. 337–343
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.