Optimisation aléatoire - Random optimization

L'optimisation aléatoire (RO) est une famille de méthodes d' optimisation numérique qui ne nécessitent pas l' optimisation du gradient du problème et la RO peut donc être utilisée sur des fonctions qui ne sont pas continues ou différentiables . Ces méthodes d'optimisation sont également appelées méthodes de recherche directe, sans dérivé ou boîte noire.

Le nom d'optimisation aléatoire est attribué à Matyas qui a fait une première présentation de RO avec une analyse mathématique de base. RO fonctionne en se déplaçant itérativement vers de meilleures positions dans l'espace de recherche qui sont échantillonnées en utilisant par exemple une distribution normale entourant la position actuelle.

Algorithme

Soit f : ℝ n  → ℝ la fonction d'aptitude ou de coût qui doit être minimisée. Soit x  ∈ ℝ n une position ou une solution candidate dans l'espace de recherche. L'algorithme RO de base peut alors être décrit comme:

  • Initialisez x avec une position aléatoire dans l'espace de recherche.
  • Jusqu'à ce qu'un critère de terminaison soit satisfait (par exemple, nombre d'itérations effectuées ou adéquation adéquate atteinte), répétez ce qui suit:
    • Échantillonner une nouvelle position y en ajoutant un vecteur aléatoire normalement distribué à la position courante x
    • Si ( f ( y ) <  f ( x )) alors passez à la nouvelle position en définissant x  =  y
  • Maintenant, x occupe la position la mieux trouvée.

Cet algorithme correspond à une stratégie d'évolution (1 + 1) à pas constant.

Convergence et variantes

Matyas a montré que la forme de base de RO converge vers l'optimum d'une simple fonction unimodale en utilisant une limite-preuve qui montre que la convergence vers l'optimum est certaine de se produire si un nombre potentiellement infini d'itérations est effectué. Cependant, cette preuve n'est pas utile en pratique car un nombre fini d'itérations ne peut être exécuté. En fait, une telle preuve limite théorique montrera également qu'un échantillonnage purement aléatoire de l'espace de recherche donnera inévitablement un échantillon arbitrairement proche de l'optimum.

Des analyses mathématiques sont également menées par Baba et Solis et Wets pour établir que la convergence vers une région entourant l'optimum est inévitable dans certaines conditions douces pour les variantes RO en utilisant d'autres distributions de probabilité pour l'échantillonnage. Une estimation du nombre d'itérations nécessaires pour s'approcher de l'optimum est dérivée par Dorea. Ces analyses sont critiquées à travers des expériences empiriques par Sarma qui a utilisé les variantes d'optimisation de Baba et Dorea sur deux problèmes du monde réel, montrant l'optimum à approcher très lentement et de plus que les méthodes étaient en fait incapables de localiser une solution d'aptitude adéquate, à moins que le processus a commencé suffisamment près de l'optimum pour commencer.

Voir également

Les références