Algorithme de recherche d'harmonie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L’Algorithme de recherche d’harmonie (RH) est une métaheuristique développée par [Geem et al., 2001].

Elle est basée sur le processus de performance musical qui consiste à trouver l’harmonie parfaite dans un orchestre musical où chaque musicien joue une note pour trouver une meilleure harmonie. D’une manière analogue, chaque variable de décision dans le processus d'optimisation a une valeur pour trouver la meilleure solution. L’algorithme RH a été appliqué avec succès sur plusieurs problèmes comme le problème du voyageur de commerce [Geem et al. 2001], le problème de tournée de véhicule [Geem et al. 2005a] et le problème de conception des structures [Geem et al. 2005b].

Étapes de l'algorithme[modifier | modifier le code]

Les principales étapes de l’algorithme RH sont présentées comme suit :

  • Étape 1. Initialisation des paramètres

Dans cette étape, les paramètres de l’algorithme sont initialisés : nombre HMS de solutions générées, taux de sélection HMCR, taux d’ajustement PAR et le critère d’arrêt.

  • Étape 2. Génération des solutions initiales (appelées mémoire de l’harmonie HM)

Dans cette étape, un ensemble de HMS solutions sont aléatoirement générées et pour chaque solution i (i=1,..,HMS), la fonction objectif fi est calculée. La figure 3 présente la structure générale de HM. Cette mémoire peut être considérée comme une matrice contenant un ensemble d’harmonies ou solutions.

  • Étape 3. ‘Improvisation’ d’une nouvelle harmonie (solution) à partir de la matrice HM.

Une nouvelle solution x=(x1,..,xn) est générée à partir de la matrice HM avec une probabilité HMCR. En utilisant le paramètre HMCR, chaque variable xi (i=1,..,n) est choisie aléatoirement du vecteur (y1i,..,yHMSi) de la matrice HM avec un taux HMCR.

  • Étape 4. Si la nouvelle solution est faisable et meilleure que la plus mauvaise solution dans la matrice HM, inclure la nouvelle solution dans HM et exclure la plus mauvaise.
  • Étape 5. Si le critère d’arrêt n’est pas satisfait, aller à l’étape 2.

Bibliographie[modifier | modifier le code]

  • Zong Woo Geem, Joong Hoon Kim et GV Loganathan, « A new heuristic optimization algorithm: harmony search », Simulation, SAGE Publications, vol. 76, no 2,‎ , p. 60-68
  • Geem ZW, Improved Harmony Search from Ensemble of Music Players

Lien externe[modifier | modifier le code]