Méthode de cross-entropie

Méthode de cross-entropie

Méthode de cross-entropie a été développé comme une technique d’estimation efficace pour les probabilités d’événements rares dans les systèmes de simulation d’événements discrets et a été adapté pour être utilisé dans l’optimisation. Le nom de la technique vient de la méthode de cross-entropie de Kullback-Leibler pour mesurer la quantité d’informations (bits) nécessaires pour identifier un événement à partir d’un ensemble de probabilités.

La stratégie de traitement de l’information de l’algorithme consiste à échantillonner l’espace du problème et à approximer la distribution des bonnes solutions. Ceci est réalisé en supposant une distribution de l’espace du problème (tel que gaussien), en échantillonnant le domaine du problème en générant des solutions candidates en utilisant la distribution et en mettant à jour la distribution en fonction des meilleures solutions candidates découvertes. Les échantillons sont construits par étapes (un composant à la fois) sur la base de la distribution résumée des bonnes solutions. Au fur et à mesure que l’algorithme progresse, la distribution devient plus raffinée jusqu’à ce qu’elle se concentre sur le domaine ou la portée des solutions optimales dans le domaine.

L’algorithme suivant décrit la méthode de cross-entropie pour minimiser une fonction de coût.

La méthode de cross-entropie a été adaptée aux problèmes d’optimisation combinatoire, bien qu’elle ait été appliquée à l’optimisation de fonction continue ainsi qu’aux problèmes de simulation contenant beaucoup de bruits.

Un paramètre alpha (a) ou un taux d’apprentissage dans [0; 1] est généralement réglé à un niveau élevé, tel que 0,7. Une fonction de lissage peut être utilisée pour contrôler davantage les mises à jour de la ou des distribution(s) des échantillons de l’espace de définition. Par exemple, dans l’optimisation d’une fonction continue, un paramètre peut remplacer (a) pour la mise à jour de l’écart-type, calculé au temps t comme B-B(1-1/t)^q, où B est initialement réglé dans [0,8; 0,99] et q est un petit entier dans [5; 10].