Harmony Search

Article Review

Geem, Z.W., Kim, J.H., Loganathan, G.V. (2001) “A New Heuristic Optimization Algorithm: Harmony Search”. 76(2): 60-68.

This paper presents the algorithm Harmony Search (HS), a new heuristic optimization algorithm inspired in the way musician improvise harmonies. The analogy with music is: musical performance seeks a harmony with maximum aesthetic estimation, as the optimization algorithm seeks the best solution. The aesthetic estimation represents the objective function and the pitches of instruments represent decision variables. The decision variables achieve better solution by a process of practice. After each iteration, the solution is evaluated. If the harmony is better than the previous ones, it is included in the Harmony Memory. The process is repeated until the stopping criteria is satisfied.

The harmony memory is initialized with random values. A new harmony is generated based on the solutions already present in the harmony search. If the new harmony is better than the ones in the harmony memory, it is included on it, and the worst harmony is excluded. In order to increase the decision space and find the global optimum, a parameter called Harmony Memory Considering Rate (HMCR), ranging from 0 to 1, is used to randomly generate new solutions. HMCR is uniformly generated. If it is above the current value of the HMCR, the algorithm selects a new variable with certain probability and introduces the new random value.
Another operator is used to escape local optima, similar to crossover in the genetic algorithm (GA). The Pitch Adjusting Rate (PAR) is used to select a variable with certain probability and shifts the value with its neighbors. The article uses the example of the solution {1,3,4,6,7,9}. The value {6} can be moved to neighboring {4} or {7}.

The article illustrates the harmony search with 3 problems found in the literature. The first one is the Traveling Salesman Problem (TSP), which tries to find the shortest path for a salesman that has to visit a certain number of cities once. The second problem is a 2 dimension constrained minimization problem. The performance of HS is compared with others methods like GA, Generalized Reduced Gradient (GRC) and Evolutionary Programming (EP). HS had better performance compared to the other methods. The last problem is the design of a pipeline network for water supply consisted of 32 nodes, 34 links and 3 loops. The results were compared with GA and Nonlinear Programming Gradient (NLPG). The HS produced the solution with the least cost related to the other methods.

Discussion

The HS algorithm is a very interesting methodology. Particularly for me that play the guitar, was very curious to see how real life phenomena can be invently used to develop new techniques to solve older and new problems. This paper was also interesting because I had the opportunity to attend the talk of one of the authors in the 2009 US-Korea Conference on Science, Technology and Entrepreneurship, last July 16-19, 2009 in Raleigh, North Carolina.

During our weekly discussion meeting, we tried to compared the differences and similarities between HS and GA. As a heuristic method, HS is similar to GA. One aspect that seems important is that HS creates a new solution based in all existing solutions presented in the harmony memory, while GA creates a new solution only with two previous solutions (parents).