Harmony search

From HandWiki

In operations research, harmony search is a phenomenon-mimicking metaheuristic introduced in 2001 by Zong Woo Geem, Joong Hoon Kim, and G. V. Loganathan.[1] Harmony search is inspired by the improvisation process of jazz musicians.

Metaphor

In the harmony search algorithm, each musician, representing a decision variable, plays (generates) a note (value) for finding a best harmony corresponding a global optimum by synthesizing their sounds.

Algorithm

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

The algorithm has the following steps:

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

[math]\displaystyle{ \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}. }[/math]

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

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

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

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

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

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

The parameters of the algorithm are

  • [math]\displaystyle{ hms }[/math] = the size of the harmony memory. It generally varies from 1 to 100. (typical value = 30)
  • [math]\displaystyle{ hmcr }[/math] = the rate of choosing a value from the harmony memory. It generally varies from 0.7 to 0.99. (typical value = 0.9)
  • [math]\displaystyle{ par }[/math] = the rate of choosing a neighboring value. It generally varies from 0.1 to 0.5. (typical value = 0.3)
  • [math]\displaystyle{ \delta }[/math] = the amount between two neighboring values in discrete candidate set.
  • [math]\displaystyle{ fw }[/math] (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.

Criticism

Nature-inspired metaheuristics in general have started to attract criticism in the research community for hiding their lack of novelty behind an elaborate metaphor.[2][3][4][5][6] In response, Springer's Journal of Heuristics has updated their editorial policy to state that:[7]

Implementations should be explained by employing standard optimization terminology, where a solution is called a “solution” and not something else related to some obscure metaphor (e.g., harmony, flies, bats, countries, etc.).

Harmony search in particular has been strongly criticized for being a special case of the evolution strategies algorithm.[8]

References

  1. ↑ Geem, Zong Woo, Joong Hoon Kim, and G. V. Loganathan (2001). "A new heuristic optimization algorithm: harmony search." Simulation 76.2: pp. 60-68.
  2. ↑ 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. 
  3. ↑ Sörensen, Kenneth (2013). "Metaheuristics—the metaphor exposed". International Transactions in Operational Research 22: 3–18. doi:10.1111/itor.12001. "In recent years, the field of combinatorial optimization has witnessed a true tsunami of “novel” metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together – it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. In this paper, we will argue that this line of research is threatening to lead the area of metaheuristics away from scientific rigor.". 
  4. ↑ Fred Glover and Kenneth Sörensen, ed. "Metaheuristics". http://www.scholarpedia.org/article/Metaheuristics.  "A large (and increasing) number of publications focuses on the development of (supposedly) new metaheuristic frameworks based on metaphors. The list of natural or man-made processes that has been used as the basis for a metaheuristic framework now includes such diverse processes as bacterial foraging, river formation, biogeography, musicians playing together, electromagnetism, gravity, colonization by an empire, mine blasts, league championships, clouds, and so forth. An important subcategory is found in metaheuristics based on animal behavior. Ants, bees, bats, wolves, cats, fireflies, eagles, vultures, dolphins, frogs, salmon, vultures, termites, flies, and many others, have all been used to inspire a "novel" metaheuristic. [...] As a general rule, publication of papers on metaphor-based metaheuristics has been limited to second-tier journals and conferences, but some recent exceptions to this rule can be found. Sörensen (2013) states that research in this direction is fundamentally flawed. Most importantly, the author contends that the novelty of the underlying metaphor does not automatically render the resulting framework "novel". On the contrary, there is increasing evidence that very few of the metaphor-based methods are new in any interesting sense."
  5. ↑ Jerry Swan, Steven Adriaensen, Mohamed Bishr, Edmund K. Burke, John A. Clark, Patrick De Causmaecker, Juanjo Durillo, Kevin Hammond, Emma Hart, Colin G. Johnson, Zoltan A. Kocsis, Ben Kovitz, Krzysztof Krawiec, Simon Martin, J. J. Merelo, Leandro L. Minku, Ender Özcan, Gisele L. Pappa, Erwin Pesch, Pablo Garcáa-Sánchez, Andrea Schaerf, Kevin Sim, Jim E. Smith, Thomas Stützle, Stefan Voß, Stefan Wagner, Xin Yao. "A Research Agenda for Metaheuristic Standardization". "Metaphors often inspire new metaheuristics, but without mathematical rigor, it can be hard to tell if a new metaheuristic is really distinct from a familiar one. For example, mathematically, ‘Harmony search’ turned out to be a simple variant of ‘Evolution Strategies’ even though the metaphors that inspired them were quite different. Formally describing state, representation, and operators allows genuine novelty to be distinguished from minor variation."
  6. ↑ Alexander Brownlee and John R. Woodward (2015). "Why we fell out of love with algorithms inspired by nature". The Conversation.
  7. ↑ Journal of Heuristic Policies on Heuristic Search Research. Springer. "Proposing new paradigms is only acceptable if they contain innovative basic ideas, such as those that are embedded in classical frameworks like genetic algorithms, tabu search, and simulated annealing. The Journal of Heuristics avoids the publication of articles that repackage and embed old ideas in methods that are claimed to be based on metaphors of natural or manmade systems and processes. These so-called “novel” methods employ analogies that range from intelligent water drops, musicians playing jazz, imperialist societies, leapfrogs, kangaroos, all types of swarms and insects and even mine blast processes (Sörensen, 2013). If a researcher uses a metaphor to stimulate his or her own ideas about a new method, the method must nevertheless be translated into metaphor-free language, so that the strategies employed can be clearly understood, and their novelty is made clearly visible. (See items 2 and 3 below.) Metaphors are cheap and easy to come by. Their use to “window dress” a method is not acceptable."
  8. ↑ Dennis Weyland (2015). "A critical analysis of the harmony search algorithm—How not to solve sudoku". Operations Research Perspectives.

External links




Retrieved from "https://handwiki.org/wiki/index.php?title=Harmony_search&oldid=126823"