Harmony search

Algorithm[edit]

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

The algorithm has the following steps:

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

${\displaystyle \mathbf {HM} ={\begin{bmatrix}x_{1}^{1}&\cdots &x_{n}^{1}&|&f(\mathbf {x} ^{1})\\\vdots &\ddots &\vdots &|&\vdots \\x_{1}^{hms}&\cdots &x_{n}^{hms}&|&f(\mathbf {x} ^{hms})\\\end{bmatrix}}.}$

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

• with probability ${\displaystyle hmcr}$ (harmony memory considering rate; 0 ≤ ${\displaystyle hmcr}$ ≤ 1), pick the stored value from HM: ${\displaystyle x_{i}^{'}\leftarrow x_{i}^{int(u(0,1)*hms)+1}}$
• with probability ${\displaystyle 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 ${\displaystyle par}$ (pitch adjusting rate; 0 ≤ ${\displaystyle par}$ ≤ 1), change ${\displaystyle x_{i}^{'}}$ by a small amount: ${\displaystyle x_{i}^{'}\leftarrow x_{i}^{'}+\delta }$ or ${\displaystyle x_{i}^{'}\leftarrow x_{i}^{'}-\delta }$ for discrete variable; or ${\displaystyle x_{i}^{'}\leftarrow x_{i}^{'}+fw\cdot u(-1,1)}$ for continuous variable.
• with probability ${\displaystyle 1-par}$, do nothing.

Step 4: If ${\displaystyle \mathbf {x} ^{'}}$ is better than the worst vector ${\displaystyle \mathbf {x} ^{Worst}}$ in HM, replace ${\displaystyle \mathbf {x} ^{Worst}}$ with ${\displaystyle \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

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