Harmony 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:

• 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.^[1]
• 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.^[2]
• HS has a novel stochastic derivative^[3] 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

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

Harmony search lies in the fields of:

• Evolutionary computing
  • Metaheuristics
    • Stochastic optimization
      • Optimization

Other evolutionary computing methods include:

• Evolutionary algorithms, including:
  • Genetic algorithms
  • Genetic programming
• Swarm algorithms, including:
  • Ant colony optimization
  • Particle swarm optimization
  • Intelligent Water Drops

Other metaheuristic methods include:

• Simulated annealing
• Tabu search

Other stochastic methods include:

• Cross-entropy method

Criticism

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),^[4] 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,^[5] (updated manuscript) but Kenneth Sörensen, professor of operations research at Antwerp University, called it "less than fully convincing".^[6]

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.^[7] 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

1. "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice". Computer Methods in Applied Mechanics and Engineering 194: 3902–3933. doi:10.1016/j.cma.2004.09.007.
2. "Improved Harmony Search from Ensemble of Music Players". Lecture Notes in Computer Science: 86–93. doi:10.1007/11892960_11.
3. "Novel derivative of harmony search algorithm for discrete design variables". Applied Mathematics and Computation 199: 223–230. doi:10.1016/j.amc.2007.09.049.
4. 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.
5. 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.
6. Sörensen, Kenneth. "Metaheuristics—the metaphor exposed". International Transactions in Operational Research 22: 3–18. doi:10.1111/itor.12001.
7. Padberg, Miriam (2012). "Harmony Search Algorithms for binary optimization problems". Operations Research Proceedings 2011: 343–348. doi:10.1007/978-3-642-29210-1_55.

References

General information

• Algorithm Website: Harmony Search Algorithm
• Book 1 Music-Inspired Harmony Search Algorithm, Springer 2009
• Book 2 Recent Advances in Harmony Search Algorithm, Springer 2010
• Book 3 Harmony Search Algorithms for Structural Design Optimization, Springer 2009
• Book 4 Optimal Design of Water Distribution Networks Using Harmony Search, LAP 2009
• Book 5 Engineering Optimization: An Introduction with Metaheuristic Applications, Wiley 2010
• Book 6 Clever Algorithms: Nature-Inspired Programming Recipes, Lulu.com 2011

Theory of harmony search

• Original Harmony Search: Geem ZW, Kim JH, and Loganathan GV, A New Heuristic Optimization Algorithm: Harmony Search, Simulation, 2001.
• Stochastic Partial Derivative: Geem, ZW (2008). "Novel Derivative of Harmony Search Algorithm for Discrete Design Variables". Applied Mathematics and Computation 199: 223–230. doi:10.1016/j.amc.2007.09.049.
• Ensembled Harmony Search: Geem ZW, Improved Harmony Search from Ensemble of Music Players, Lecture Notes in Artificial Intelligence, 2006.
• Continuous Harmony Search: Lee, KS; Geem, ZW (2005). "A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice". Computer Methods in Applied Mechanics and Engineering 194: 3902–3933. doi:10.1016/j.cma.2004.09.007.
• Exploratory Power of Harmony Search: Das, S; Mukhopadhyay, A; Roy, A; Abraham, A; Panigrahi, BK. "Exploratory Power of the Harmony Search Algorithm: Analysis and Improvements for Global Numerical Optimization". IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 41 (1): 89–106. doi:10.1109/TSMCB.2010.2046035.
• Improved Harmony Search: Mahdavi M, Fesanghary M, and Damangir E, An Improved Harmony Search Algorithm for Solving Optimization Problems, Applied Mathematics and Computation, 2007.
• Particle-Swarm Harmony Search: Omran MGH and Mahdavi M, Global-Best Harmony Search, Applied Mathematics and Computation, 2008.
• Hybrid Harmony Search: Fesanghary M, Mahdavi M, Minary-Jolandan M, and Alizadeh Y, Hybridizing Harmony Search Algorithm with Sequential Quadratic Programming for Engineering Optimization Problems, Computer Methods in Applied Mechanics and Engineering, 2008.
• Parameter-Setting-Free Harmony Search: Geem ZW and Sim K-B, Parameter-Setting-Free Harmony Search Algorithm, Applied Mathematics and Computation, 2010.
• Multiobjective Harmony Search Algorithm Proposals: Juan Ricart, Germán Hüttemann, Joaquín Lima, Benjamín Barán. Multiobjective Harmony Search Algorithm Proposals, Electronic Notes in Theoretical Computer Science, 2011.
• Hybrid Harmony Search: HS-BFGS algorithm : Karahan H, Gurarslan G and Geem ZW, [doi:http://dx.doi.org/10.1061/(ASCE)HE.1943-5584.0000608 "Parameter Estimation of the nonlinear Muskingum flood routing model using a hybrid harmony search algorithm", Journal of Hydrologic Engineering, doi:10.1061/(ASCE)HE.1943-5584.0000608, 2012.
• Generalised Adaptive Harmony Search: Jaco Fourie, Richard Green, and Zong Woo Geem, Generalised Adaptive Harmony Search: A Comparative Analysis of Modern Harmony Search, Journal of Applied Mathematics, vol. 2013, Article ID 380985, 13 pages, 2013. doi:10.1155/2013/380985
• A harmony search algorithm for high-dimensional multimodal optimization problems:Shouheng Tuo, Junying Zhang, Longquan Yong, Xiguo Yuan, Baobao Liu, Xiaoyang Xu, Fang'an Deng,

Digital Signal Processing, Volume 46, November 2015, Pages 151-163 doi:10.1016/j.dsp.2015.08.008

Applications in computer science

• Music Composition: Geem, Z. W. and Choi, J. Y. Music Composition Using Harmony Search Algorithm, Lecture Notes in Computer Science, 2007.
• Tetris Agent Optimization: Romero, V., Tomes, L., Yusiong, J., Harmonetris: Tetris Agent Optimization Using Harmony Search Algorithm, International Journal of Computer Science Issues, 2011.
• Sudoku Puzzle: Geem, Z. W. Harmony Search Algorithm for Solving Sudoku, Lecture Notes in Artificial Intelligence, 2007.
• Tour Planning: Geem, Z. W., Tseng, C. -L., and Park, Y. Harmony Search for Generalized Orienteering Problem: Best Touring in China, Lecture Notes in Computer Science, 2005.
• Visual Tracking: J. Fourie, S. Mills and R. Green Visual tracking using the harmony search algorithm, Image and Vision Computing New Zealand, 2008. 23rd International Conference
• Visual Tracking: Jaco Fourie, Steven Mills, Richard Green, Harmony Filter: A Robust Visual Tracking System Using the Improved Harmony Search Algorithm, Image and Vision Computing (2010), doi:10.1016/j.imavis.2010.05.006
• Visual Correspondence: J. Fourie, S. Mills and R. Green Directed correspondence search: Finding feature correspondences in images using the Harmony Search algorithm, Image and Vision Computing New Zealand, 23-25 Nov. 2009. 24th International Conference
• Image Deconvolution: J. Fourie, S. Mills and R. Green Counterpoint Harmony Search: An accurate algorithm for the blind deconvolution of binary images, Audio Language and Image Processing (ICALIP), 2010 International Conference on, Shanghai, China
• Capacitated clustering 1: I. Landa-Torres, S. Gil-Lopez, S. Salcedo-Sanz, J. Del Ser, J. A. Portilla-Figueras, A Novel Grouping Harmony Search Algorithm for the Multiple-Type Access Node Location Problem, Expert Systems with Applications, vol. 39, no. 5, pp. 5262–5270, April 2012.
• Capacitated clustering 2: I. Landa-Torres, J. Del Ser, S. Salcedo-Sanz, S. Gil-Lopez, J.A. Portilla-Figueras, O. Alonso-Garrido, A comparative study of two hybrid grouping evolutionary techniques for the capacitated P-median problem, Computers and Operations Research, vol. 39, no. 9, pp. 2214–2222, September 2012.
• Design of radar codes: S. Gil-Lopez, J. Del Ser, S. Salcedo-Sanz, A. M. Perez-Bellido, J. M. Cabero and J. A. Portilla-Figueras, A Hybrid Harmony Search Algorithm for the Spread Spectrum Radar Polyphase Codes Design Problem, Expert Systems with Applications, Volume 39, Issue 12, pp. 11089–-11093, September 2012.
• Dynamic Spectrum Allocation: J. Del Ser, M. Matinmikko, S. Gil-Lopez and M. Mustonen, Centralized and Distributed Spectrum Channel Assignment in Cognitive Wireless Networks: A Harmony Search Approach, Applied Soft Computing, vol. 12, no. 2, pp. 921–930, February 2012.
• Power and subcarrier allocation in OFDMA systems: J. Del Ser, M. N. Bilbao, S. Gil-Lopez, M. Matinmikko, S. Salcedo-Sanz, Iterative Power and Subcarrier Allocation in Rate-Constrained OFDMA Downlink Systems based on Harmony Search Heuristics, Elsevier Engineering Applications of Artificial Intelligence, Vol. 24, N. 5, pp. 748–756, August 2011.
• Efficient design of open Wifi networks: I. Landa-Torres, S. Gil-Lopez, J. Del Ser, S. Salcedo-Sanz, D. Manjarres, J. A. Portilla-Figueras, Efficient Citywide Planning of Open WiFi Access Networks using Novel Grouping Harmony Search Heuristics, accepted for its publication in Engineering Applications of Artificial Intelligence, May 2012.
• Single-objective localization: D. Manjarres, J. Del Ser, S. Gil-Lopez, M. Vecchio, I. Landa-Torres, R. Lopez-Valcarce, A Novel Heuristic Approach for Distance- and Connectivity-based Multihop Node Localization in Wireless Sensor Networks, Springer Soft Computing, accepted, June 2012.
• Bi-objective localization: D. Manjarres, J. Del Ser, S. Gil-Lopez, M. Vecchio, I. Landa-Torres, S. Salcedo-Sanz, R. Lopez-Valcarce,On the Design of a Novel Two-Objective Harmony Search Approach for Distance- and Connectivity-based Node Localization in Wireless Sensor Networks, Engineering Applications of Artificial Intelligence, in press, June 2012.

Applications in engineering

• Fuzzy Data Clustering: Malaki, M.,Pourbaghery, JA, A Abolhassani, H. A combinatory approach to fuzzy clustering with harmony search and its applications to space shuttle data, Proceedings of the SCIS & ISIS,17–21,2008.
• Structural Design: Lee, K. S. and Geem, Z. W. A New Structural Optimization Method Based on the Harmony Search Algorithm, Computers & Structures, 2004.
• Structural Design: Saka, M. P. Optimum Geometry Design of Geodesic Domes Using Harmony Search Algorithm, Advances in Structural Engineering, 2007.
• Water Network Design: Geem, Z. W. Optimal Cost Design of Water Distribution Networks using Harmony Search, Engineering Optimization, 2006.
• Vehicle Routing: Geem, Z. W., Lee, K. S., and Park, Y. Application of Harmony Search to Vehicle Routing, American Journal of Applied Sciences, 2005.
• Ground Water Modeling: Ayvaz, M. T. Simultaneous Determination of Aquifer Parameters and Zone Structures with Fuzzy C-Means Clustering and Meta-Heuristic Harmony Search Algorithm, Advances in Water Resources, 2007.
• Soil Stability Analysis: Cheng, Y. M., Li, L., Lansivaara, T., Chi, S. C. and Sun, Y. J. An Improved Harmony Search Minimization Algorithm Using Different Slip Surface Generation Methods for Slope Stability Analysis, Engineering Optimization, 2008.
• Energy System Dispatch: Vasebi, A., Fesanghary, M., and Bathaeea, S.M.T. Combined Heat and Power Economic Dispatch by Harmony Search Algorithm, International Journal of Electrical Power & Energy Systems, 2007.
• Construction Management: Gholizadeh, R. , Amiri, G.G., Mohebi, B. An alternative approach to a harmony search algorithm for a construction site layout problem, Canadian Journal of Civil Engineering, 2010.
• Offshore Structure Mooring: Ryu, S., Duggal, A.S., Heyl, C. N., and Geem, Z. W. Mooring Cost Optimization via Harmony Search, Proceedings of the 26th International Conference on Offshore Mechanics and Arctic Engineering (OMAE 2007), ASME, San Diego, CA, USA, June 10–15, 2007.
• Hydrologic Parameter Calibration: Kim, J. H., Geem, Z. W., and Kim, E. S. Parameter Estimation of the Nonlinear Muskingum Model using Harmony Search, Journal of the American Water Resources Association, 2001.
• Hydrologic Parameter Calibration: Karahan, H, Gurarslan, G. and Geem, Z.W.[doi:http://dx.doi.org/10.1061/(ASCE)HE.1943-5584.0000608 "Parameter Estimation of the nonlinear Muskingum flood routing model using a hybrid harmony search algorithm", Journal of Hydrologic Engineering, doi:10.1061/(ASCE)HE.1943-5584.0000608, 2012.
• Satellite Heat Pipe Design: Geem, Z. W. and Hwangbo, H. Application of Harmony Search to Multi-Objective Optimization for Satellite Heat Pipe Design, Proceedings of US-Korea Conference on Science, Technology, & Entrepreneurship (UKC 2006), CD-ROM, Teaneck, NJ, USA, Aug. 10-13 2006.
• Dam Scheduling: Geem, Z. W. Optimal Scheduling of Multiple Dam System Using Harmony Search Algorithm, Lecture Notes in Computer Science, 2007.
• Ecological Conservation: Geem, Z. W. and Williams, J. C. Ecological Optimization Using Harmony Search, Proceedings of American Conference on Applied Mathematics, Harvard University, Cambridge, MA, USA, March 24–26, 2008.
• Heat exchanger design: Fesanghary, M., Damangir, E. and Soleimani, I. Design optimization of shell and tube heat exchangers using global sensitivity analysis and harmony search, Applied Thermal Engineering, In press.
• Heat exchanger design: Doodman, A., Fesanghary, M. and Hosseini, R. A robust stochastic approach for design optimization of air cooled heat exchangers, Applied Energy, In press.
• Heat exchanger network design: Khorasani, R.M., Fesanghary, M. A novel approach for synthesis of cost-optimal heat exchanger networks, Computers and Chemical Engineering, In press.
• Face milling: Zarei, O., Fesanghary, M., Farshi, B., Jalili Saffar, R. and Razfar, M.R. Optimization of multi-pass face-milling via harmony search algorithm, Journal of Materials Processing Technology, In press.
• Document Clustering:, Mahdavi., M., Chehreghania, H., Abolhassania, H., Forsati, R. Novel meta-heuristic algorithms for document clustering, AMC Journal
• Multicast Routing: Forsat, R., Haghighat, M., Mahdavi, M.,Harmony search based algorithms for bandwidth-delay-constrained least-cost multicast routing, Computer Communications, Elsevier
• AYVAZ, M.T. and GENÇ, Ö., Optimal estimation of Manning’s roughness in open channel flows using a linked simulation-optimization model, BALWOIS 2012, International Conference on Water, Climate and Environment, May 28 - June 2, 2012, Ohrid, Madeconia.
• Poursalehi, N.; Zolfaghari, A.; Minuchehr, A. (2013). "PWR loading pattern optimization using Harmony Search algorithm". Ann. Nucl. Energy 53: 288–298. doi:10.1016/j.anucene.2012.06.037.

Applications in economics

• I. Landa-Torres, E. G. Ortiz-Garcia, S. Salcedo-Sanz, M. J. Segovia, S. Gil-Lopez, M. Miranda, J. M. Leiva-Murillo, J. Del Ser, Evaluating the Internationalization Success of Companies using a Hybrid Grouping Harmony Search - Extreme Learning Machine Approach, IEEE Journal on Selected Topics in Signal Processing, Vol. PP., N. 99 (early access), May 2012.

Source codes

• Improved Harmony Search (MATLAB)
• Hybrid HS-SQP (Visual C++)
• Multiobjective Harmony Search (C#)
• Other HS Variants
• Multiobjective Harmony Search Algorithm Proposals (C++)
• pyHarmonySearch (Python)