Harmony search

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science and operations research, harmony search (HS) is a phenomenon-mimicking algorithm (also known as metaheuristic algorithm, soft computing algorithm or evolutionary algorithm) inspired by the improvisation process of musicians proposed by Zong Woo Geem in 2001. In the HS algorithm, each musician (= decision variable) plays (= generates) a note (= a value) for finding a best harmony (= global optimum) all together. Proponents claim the following merits:[citation needed]

  • HS does not require differential gradients, thus it can consider discontinuous functions as well as continuous functions.
  • HS can handle discrete variables as well as continuous variables.
  • HS does not require initial value setting for the variables.
  • HS is free from divergence.
  • HS may escape local optima.
  • HS may overcome the drawback of GA's building block theory which works well only if the relationship among variables in a chromosome is carefully considered. If neighbor variables in a chromosome have weaker relationship than remote variables, building block theory may not work well because of crossover operation. However, HS explicitly considers the relationship using ensemble operation.
  • HS has a novel stochastic derivative applied to discrete variables, which uses musician's experiences as a searching direction.
  • Certain HS variants do not require algorithm parameters such as HMCR and PAR, thus novice users can easily use the algorithm.

Basic harmony search algorithm[edit]

Harmony search tries to find a vector \mathbf{x} which optimizes (minimizes or maximizes) a certain objective function.

The algorithm has the following steps:

Step 1: Generate random vectors (\mathbf{x}^1, \ldots, \mathbf{x}^{hms}) as many as hms (harmony memory size), then store them in harmony memory (HM).


\mathbf{HM} =
\begin{bmatrix}
x^1_1 & \cdots & x^1_n & | & f(\mathbf{x}^1)\\
\vdots & \ddots & \vdots & | & \vdots\\
x^{hms}_1 & \cdots & x^{hms}_n & | & f(\mathbf{x}^{hms})\\
\end{bmatrix}.

Step 2: Generate a new vector \mathbf{x}'. For each component x^{'}_{i},

  • with probability hmcr (harmony memory considering rate; 0 ≤ hmcr ≤ 1), pick the stored value from HM: x^{'}_{i} \leftarrow x^{int(u(0, 1)*hms)+1}_i
  • with probability 1-hmcr, pick a random value within the allowed range.

Step 3: Perform additional work if the value in Step 2 came from HM.

  • with probability par (pitch adjusting rate; 0 ≤ par ≤ 1), change x^{'}_{i} by a small amount: x^{'}_{i} \leftarrow x^{'}_{i} + \delta or x^{'}_{i} \leftarrow x^{'}_{i} - \delta for discrete variable; or x^{'}_{i} \leftarrow x^{'}_{i} + fw \cdot u(-1, 1) for continuous variable.
  • with probability 1-par, do nothing.

Step 4: If \mathbf{x}^{'} is better than the worst vector \mathbf{x}^{Worst} in HM, replace \mathbf{x}^{Worst} with \mathbf{x}'.

Step 5: Repeat from Step 2 to Step 4 until termination criterion (e.g. maximum iterations) is satisfied.

The parameters of the algorithm are

  • hms = the size of the harmony memory. It generally varies from 1 to 100. (typical value = 30)
  • hmcr = the rate of choosing a value from the harmony memory. It generally varies from 0.7 to 0.99. (typical value = 0.9)
  • par = the rate of choosing a neighboring value. It generally varies from 0.1 to 0.5. (typical value = 0.3)
  • \delta = the amount between two neighboring values in discrete candidate set.
  • fw (fret width, formerly bandwidth) = the amount of maximum change in pitch adjustment. This can be (0.01 × allowed range) to (0.001 × allowed range).

It is possible to vary the parameter values as the search progresses, which gives an effect similar to simulated annealing.

Parameter-setting-free researches have been also performed. In the researches, algorithm users do not need tedious parameter setting process.

Other related algorithms[edit]

Harmony search lies in the fields of:

Other evolutionary computing methods include:

Other metaheuristic methods include:

Other stochastic methods include:

Criticism[edit]

In 2010, Dennis Weyland, a PhD student at the Dalle Molle Institute for Artificial Intelligence Research in Switzerland published an article titled "A Rigorous Analysis of the Harmony Search Algorithm: How the Research Community can be Misled by a “Novel” Methodology" in the International Journal of Applied Metaheuristic Computing (IJAMC),[1] stating that:

It turns out that Harmony Search is a special case of Evolution Strategies. We give compelling evidence for the thesis that research in Harmony Search, although undoubtedly conducted with the best of intentions, is fundamentally misguided, marred by a preoccupation with retracing paths already well traveled, and we conclude that future research effort could better be devoted to more promising areas.

A rebuttal was published by Geem in a later issue of the same journal,[2] (updated manuscript) but Kenneth Sörensen, professor of operations research at Antwerp University, called it "less than fully convincing".[3]

Independent of the work of Weyland, Miriam Padberg has shown in 2011 that for binary optimization problems the Harmony Search algorithm is equivalent to a certain evolutionary algorithm.[4] In fact, the reasoning is similar to that used in the work of Weyland, but this time explicitly stated in a rigorous mathematical way.

Notes[edit]

  1. ^ Weyland, Dennis (2010). "A Rigorous Analysis of the Harmony Search Algorithm: How the Research Community can be Misled by a "Novel" Methodology". International Journal of Applied Metaheuristic Computing 1 (2): 50–60. doi:10.4018/jamc.2010040104. 
  2. ^ Geem, Zong Woo (2010). "Research Commentary: Survival of the Fittest Algorithm or the Novelest Algorithm?". International Journal of Applied Metaheuristic Computing 1 (4): 75–79. doi:10.4018/jamc.2010100105. 
  3. ^ Sörensen, Kenneth. "Metaheuristics—the metaphor exposed". International Transactions in Operational Research. doi:10.1111/itor.12001. 
  4. ^ Padberg, Miriam (2012). "Harmony Search Algorithms for binary optimization problems". Operations Research Proceedings 2011: 343–348.

References[edit]

General information[edit]

Theory of harmony search[edit]

Applications in computer science[edit]

Applications in engineering[edit]

Applications in economics[edit]

Source codes[edit]

  • Improved Harmony Search (MATLAB) [2]
  • Hybrid HS-SQP (Visual C++) [3]
  • Multiobjective Harmony Search (C#) [4]
  • Other HS Variants [5]
  • Multiobjective Harmony Search Algorithm Proposals (C++) [6]
  • pyHarmonySearch (Python) [7]