# Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

This is the ad-supported version of the book. Buy it now if you like it.

# Harmony Search

Harmony Search, HS.

## Taxonomy

Harmony Search belongs to the fields of Computational Intelligence and Metaheuristics.

## Inspiration

Harmony Search was inspired by the improvisation of Jazz musicians. Specifically, the process by which the musicians (who may have never played together before) rapidly refine their individual improvisation through variation resulting in an aesthetic harmony.

## Metaphor

Each musician corresponds to an attribute in a candidate solution from a problem domain, and each instrument's pitch and range corresponds to the bounds and constraints on the decision variable. The harmony between the musicians is taken as a complete candidate solution at a given time, and the audiences aesthetic appreciation of the harmony represent the problem specific cost function. The musicians seek harmony over time through small variations and improvisations, which results in an improvement against the cost function.

## Strategy

The information processing objective of the technique is to use good candidate solutions already discovered to influence the creation of new candidate solutions toward locating the problems optima. This is achieved by stochastically creating candidate solutions in a step-wise manner, where each component is either drawn randomly from a memory of high-quality solutions, adjusted from the memory of high-quality solutions, or assigned randomly within the bounds of the problem. The memory of candidate solutions is initially random, and a greedy acceptance criteria is used to admit new candidate solutions only if they have an improved objective value, replacing an existing member.

## Procedure

Algorithm (below) provides a pseudocode listing of the Harmony Search algorithm for minimizing a cost function. The adjustment of a pitch selected from the harmony memory is typically linear, for example for continuous function optimization:

$x' \leftarrow x + range \times \epsilon$

where $range$ is a the user parameter (pitch bandwidth) to control the size of the changes, and $\epsilon$ is a uniformly random number $\in [-1,1]$.

Input: $Pitch_{num}$, $Pitch_{bounds}$, $Memory_{size}$, $Consolidation_{rate}$, $PitchAdjust_{rate}$, $Improvisation_{max}$
Output: $Harmony_{best}$
Harmonies $\leftarrow$ InitializeHarmonyMemory($Pitch_{num}$, $Pitch_{bounds}$, $Memory_{size}$)
EvaluateHarmonies(Harmonies)
For ($i$ To $Improvisation_{max}$)
$Harmony$ $\leftarrow$ $\emptyset$
For ($Pitch_{i}$ $\in$ $Pitch_{num}$)
If (Rand() $\leq$ $Consolidation_{rate}$)
$RandomHarmony_{pitch}^i$ $\leftarrow$ SelectRandomHarmonyPitch(Harmonies, $Pitch_{i}$)
If (Rand() $\leq$ $PitchAdjust_{rate}$)
$Harmony_{pitch}^i$ $\leftarrow$ AdjustPitch($RandomHarmony_{pitch}^i$)
Else
$Harmony_{pitch}^i$ $\leftarrow$ $RandomHarmony_{pitch}^i$
End
Else
$Harmony_{pitch}^i$ $\leftarrow$ RandomPitch($Pitch_{bounds}$)
End
End
EvaluateHarmonies($Harmony$)
If (Cost($Harmony$) $\leq$ Cost(Worst(Harmonies)))
Worst(Harmonies) $\leftarrow$ $Harmony$
End
End
Return ($Harmony_{best}$)
Pseudocode for Harmony Search.

## Heuristics

• Harmony Search was designed as a generalized optimization method for continuous, discrete, and constrained optimization and has been applied to numerous types of optimization problems.
• The harmony memory considering rate (HMCR) $\in [0,1]$ controls the use of information from the harmony memory or the generation of a random pitch. As such, it controls the rate of convergence of the algorithm and is typically configured $\in [0.7,0.95]$.
• The pitch adjustment rate (PAR) $\in [0,1]$ controls the frequency of adjustment of pitches selected from harmony memory, typically configured $\in [0.1,0.5]$. High values can result in the premature convergence of the search.
• The pitch adjustment rate and the adjustment method (amount of adjustment or fret width) are typically fixed, having a linear effect through time. Non-linear methods have been considered, for example refer to Geem [Geem2010a].
• When creating a new harmony, aggregations of pitches can be taken from across musicians in the harmony memory.
• The harmony memory update is typically a greedy process, although other considerations such as diversity may be used where the most similar harmony is replaced.

## Code Listing

Listing (below) provides an example of the Harmony Search algorithm implemented in the Ruby Programming Language. The demonstration problem is an instance of a continuous function optimization that seeks $min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=3$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$. The algorithm implementation and parameterization are based on the description by Yang [Yang2009], with refinement from Geem [Geem2010a].

def objective_function(vector)
return vector.inject(0.0) {|sum, x| sum +  (x ** 2.0)}
end

def rand_in_bounds(min, max)
return min + ((max-min) * rand())
end

def random_vector(search_space)
return Array.new(search_space.size) do |i|
rand_in_bounds(search_space[i][0], search_space[i][1])
end
end

def create_random_harmony(search_space)
harmony = {}
harmony[:vector] = random_vector(search_space)
harmony[:fitness] = objective_function(harmony[:vector])
return harmony
end

def initialize_harmony_memory(search_space, mem_size, factor=3)
memory = Array.new(mem_size*factor){create_random_harmony(search_space)}
memory.sort!{|x,y| x[:fitness]<=>y[:fitness]}
return memory.first(mem_size)
end

def create_harmony(search_space, memory, consid_rate, adjust_rate, range)
vector = Array.new(search_space.size)
search_space.size.times do |i|
if rand() < consid_rate
value = memory[rand(memory.size)][:vector][i]
value = value + range*rand_in_bounds(-1.0, 1.0) if rand()<adjust_rate
value = search_space[i][0] if value < search_space[i][0]
value = search_space[i][1] if value > search_space[i][1]
vector[i] = value
else
vector[i] = rand_in_bounds(search_space[i][0], search_space[i][1])
end
end
return {:vector=>vector}
end

def search(bounds, max_iter, mem_size, consid_rate, adjust_rate, range)
memory = initialize_harmony_memory(bounds, mem_size)
best = memory.first
max_iter.times do |iter|
harm = create_harmony(bounds, memory, consid_rate, adjust_rate, range)
harm[:fitness] = objective_function(harm[:vector])
best = harm if harm[:fitness] < best[:fitness]
memory << harm
memory.sort!{|x,y| x[:fitness]<=>y[:fitness]}
memory.delete_at(memory.size-1)
puts " > iteration=#{iter}, fitness=#{best[:fitness]}"
end
return best
end

if __FILE__ == \$0
# problem configuration
problem_size = 3
bounds = Array.new(problem_size) {|i| [-5, 5]}
# algorithm configuration
mem_size = 20
consid_rate = 0.95
range = 0.05
max_iter = 500
# execute the algorithm
best = search(bounds, max_iter, mem_size, consid_rate, adjust_rate, range)
puts "done! Solution: f=#{best[:fitness]}, s=#{best[:vector].inspect}"
end

Harmony Search in Ruby

## References

### Primary Sources

Geem et al. proposed the Harmony Search algorithm in 2001, which was applied to a range of optimization problems including a constraint optimization, the Traveling Salesman problem, and the design of a water supply network [Geem2001].

A book on Harmony Search, edited by Geem provides a collection of papers on the technique and its applications [Geem2009], chapter 1 provides a useful summary of the method heuristics for its configuration [Yang2009]. Similarly a second edited volume by Geem focuses on studies that provide more advanced applications of the approach [Geem2010], and chapter 1 provides a detailed walkthrough of the technique itself [Geem2010a]. Geem also provides a treatment of Harmony Search applied to the optimal design of water distribution networks [Geem2009a] and edits yet a third volume on papers related to the application of the technique to structural design optimization problems [Geem2009b].

## Bibliography

 [Geem2001] Z. W. Geem and J. H. Kim and G. V. Loganathan, "A New Heuristic Optimization Algorithm: Harmony Search", Simulation, 2001. [Geem2009] Z. W. Geem (editors), "Music-Inspired Harmony Search Algorithm: Theory and Applications", Springer, 2009. [Geem2009a] Z. W. Geem, "Optimal Design of Water Distribution Networks Using Harmony Search", Lap Lambert Academic Publishing, 2009. [Geem2009b] Z. W. Geem (editors), "Harmony Search Algorithms for Structural Design Optimization", Springer, 2009. [Geem2010] Z. W. Geem (editors), "Recent Advances in Harmony Search Algorithms", Springer, 2010. [Geem2010a] Z. W. Geem, "State-of-the-Art in the Structure of Harmony Search Algorithm", in Recent Advances In Harmony Search Algorithms, pages 1–10, Springer, 2010. [Yang2009] X–S. Yang, "Harmony Search as a Metaheuristic", in Music-Inspired Harmony Search Algorithm: Theory and Applications, pages 1–14, Springer, 2009.

### Free Course

Get one algorithm per week...
• ...described in detail
Sign-up Now

### Own A Copy

This 438-page ebook has...
• ...45 algorithm descriptions
• ...best practice usage
• ...pseudo code
• ...Ruby code
• ...primary sources

Please Note: This content was automatically generated from the book content and may contain minor differences.

Do you like Clever Algorithms?