Harmony search

Harmony search (HS) is a metaheuristic algorithm (also known as soft computing algorithm or evolutionary algorithm) mimicking the improvisation process of musicians. In the process, each musician plays a note for finding a best harmony all together. Likewise, each decision variable in optimization process has a value for finding a best vector all together.

The algorithm

Harmony search tries to find a vector $x$ that minimizes some cost function.

The algorithm as given by [2] is:
# Initialize the harmony memory: pick $k$ random vectors $x^1\; ldots\; x^k$.
# Make a new vector $x\text{'}$. For each component $x\text{'}\_i$:
#* with probability $p\_\{hmcr\}$ pick the component from memory, $x\text{'}\_i\; =\; x^\{rand()\}\_i$
#* with probability $1-p\_\{hmcr\}$ pick a new random value in the allowed range.
# Pitch adjustment: For each component $x\text{'}\_i$:
#* with probability $p\_\{par\}$ change $x\text{'}\_i$ by a small amount, $x\text{'}\_i\; leftarrow\; x\text{'}\_i\; pm\; bwcdot\; rand()$.
#* with probability $1-p\_\{par\}$ do nothing.
# If $x\text{'}$ is better than the worst $x^i$ in the memory, then replace $x^i$ by $x\text{'}$.
# Repeat from step 2 until a maximum number of iterations has been performed.

The parameters of the search are
* $k$, the size of the memory. A typical value is in the order of 4 to 10.
* $p\_\{hmcr\}$, the rate of choosing from memory. A typical value is $0.95$.
* $p\_\{par\}$, the 'pitch adjustment rate'. Typical values range from $0.3$ to $0.99$.
* $bw$, the 'distance bandwidth', the amount of change for pitch adjustments.

It is possible to vary the parameters as the search progresses, this gives an effect similar to simulated annealing.

In improved harmony search, $p\_\{par\}$ is increased linearly, while $bw$ is decreased exponentially.

Harmony search applications

The HS algorithm had been successful in a wide variety of optimization problems in the following fields.

Bench-mark problems

* Bench-mark functions
* Traveling salesman problem
* Tour routing
* Music composition
* Sudoku puzzle solving

Real-world problems

* Structural design
* Vehicle routing
* Hydrologic parameter calibration
* Water distribution network design
* Multiple dam scheduling
* Aquifer parameters and zone structures
* Combined heat and power economic dispatch
* Offshore structure mooring
* QoS based multicast routing
* Satellite heat pipe design
* Heat exchanger design
* Face milling process

Harmony search features

HS has several advantages when compared with traditional gradient-based mathematical optimization techniques as follows:

* HS does not require complex calculus, thus it is free from divergence.
* HS does not require initial value settings for the decision variables, thus it may escape local optima.
* HS can handle [http://sim.sagepub.com/cgi/content/abstract/76/2/60 discrete variables] as well as [http://dx.doi.org/10.1016/j.cma.2004.09.007 continuous variables] , while gradient-based techniques handle continuous variables only.

Also, the HS algorithm could overcome the drawback of genetic algorithm's building block theory by considering the relationship among decision variables using its [http://dx.doi.org/10.1007/11892960_11 ensemble operation] .

Other Related Algorithms

* Genetic algorithms
* Simulated annealing
* Tabu search
* Ant colony optimization

References

General Information

*Algorithm Website: [http://www.hydroteq.com Harmony Search Algorithm]

*Book: Bhanu Prasad, [http://www.springer.com/engineering/book/978-3-540-77464-8 Soft Computing Applications in Industry] , 2008.

Theory of Harmony Search

*Original Harmony Search: Geem, Z. W., Kim, J. H., and Loganathan, G. V. [http://sim.sagepub.com/cgi/content/abstract/76/2/60 A New Heuristic Optimization Algorithm: Harmony Search] , Simulation, 2001.

*Stochastic Partial Derivative: Geem, Z. W. [http://dx.doi.org/10.1016/j.amc.2007.09.049 Novel Derivative of Harmony Search Algorithm for Discrete Design Variables] , Applied Mathematics and Computation, In Press.

*Continuous Harmony Search: Lee, K. S. and Geem, Z. W. [http://dx.doi.org/10.1016/j.cma.2004.09.007 A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice] , Computer Methods in Applied Mechanics and Engineering, 2005.

*Ensembled Harmony Search: Geem, Z. W. [http://www.springerlink.com/content/b382536117777v22/ Improved Harmony Search from Ensemble of Music Players] , Lecture Notes in Artificial Intelligence, 2006.

*Improved Harmony Search: Mahdavi, M., Fesanghary, M., and Damangir, E. [http://dx.doi.org/10.1016/j.amc.2006.11.033 An Improved Harmony Search Algorithm for Solving Optimization Problems] , Applied Mathematics and Computation, 2007.

*Particle-Swarm Harmony Search: Omran, M.G.H. and Mahdavi, M. [http://dx.doi.org/10.1016/j.amc.2007.09.004 Global-Best Harmony Search] , Applied Mathematics and Computation, In Press.

*Hybrid Harmony Search: Fesanghary, M., Mahdavi, M., Minary-Jolandan M., and Alizadeh, Y. [http://dx.doi.org/10.1016/j.cma.2008.02.006 Hybridizing Harmony Search Algorithm with Sequential Quadratic Programming for Engineering Optimization Problems] , Computer Methods in Applied Mechanics and Engineering, 2008.

Applications in Artificial Intelligence

*Music Composition: Geem, Z. W. and Choi, J. Y. [http://www.springerlink.com/content/8395xp88473826p0/?p=9a58d87e926f47fc9782388b495670a8&pi=3 Music Composition Using Harmony Search Algorithm] , Lecture Notes in Computer Science, 2007.

*Sudoku Puzzle: Geem, Z. W. [http://www.springerlink.com/content/488571w6036764v0/?p=336060128e684defa2d88b3522bdbe27&pi=0 Harmony Search Algorithm for Solving Sudoku] , Lecture Notes in Artificial Intelligence, 2007.

*Tour Planning: Geem, Z. W., Tseng, C. -L., and Park, Y. [http://www.springerlink.com/content/6jadggrn5v7bvtye/ Harmony Search for Generalized Orienteering Problem: Best Touring in China] , Lecture Notes in Computer Science, 2005.

Applications in Engineering

*Structural Design: Lee, K. S. and Geem, Z. W. [http://dx.doi.org/10.1016/j.compstruc.2004.01.002 A New Structural Optimization Method Based on the Harmony Search Algorithm] , Computers & Structures, 2004.

*Structural Design: Saka, M. P. [http://dx.doi.org/10.1260/136943307783571445 Optimum Geometry Design of Geodesic Domes Using Harmony Search Algorithm] , Advances in Structural Engineering, 2007.

*Water Network Design: Geem, Z. W. [http://dx.doi.org/10.1080/03052150500467430 Optimal Cost Design of Water Distribution Networks using Harmony Search] , Engineering Optimization, 2006.

*Vehicle Routing: Geem, Z. W., Lee, K. S., and Park, Y. [http://www.doaj.org/doaj?func=abstract&id=175458&toc=y Application of Harmony Search to Vehicle Routing] , American Journal of Applied Sciences, 2005.

*Ground Water Modeling: Ayvaz, M. T. [http://dx.doi.org/10.1016/j.advwatres.2007.05.009 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. [http://dx.doi.org/10.1080/03052150701618153 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. [http://dx.doi.org/10.1016/j.ijepes.2007.06.006 Combined Heat and Power Economic Dispatch by Harmony Search Algorithm] , International Journal of Electrical Power & Energy Systems, 2007.

*Offshore Structure Mooring: Ryu, S., Duggal, A.S., Heyl, C. N., and Geem, Z. W. [http://www.hydroteq.com/c_2007_OMAE.pdf 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. [http://www.blackwell-synergy.com/doi/abs/10.1111/j.1752-1688.2001.tb03627.x Parameter Estimation of the Nonlinear Muskingum Model using Harmony Search] , Journal of the American Water Resources Association, 2001.

*Satellite Heat Pipe Design: Geem, Z. W. and Hwangbo, H. [http://www.hydroteq.com/c_2006_ukc_ast.pdf 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. [http://www.springerlink.com/content/x1q6618054866162/?p=3fb93efd6f4a460ea92a62a59fce6c3e&pi=38 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. [http://www.hydroteq.com-a.googlepages.com/c_2008_wseas.pdf 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. [http://dx.doi.org/10.1016/j.applthermaleng.2008.05.018 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. [http://dx.doi.org/10.1016/j.apenergy.2008.08.021 A robust stochastic approach for design optimization of air cooled heat exchangers] , Applied Energy, In press.

*Face milling: Zarei, O., Fesanghary, M., Farshi, B., Jalili Saffar, R. and Razfar, M.R. [http://dx.doi.org/10.1016/j.jmatprotec.2008.05.029 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. [http://dx.doi.org/10.1016/j.amc.2007.12.058 Novel meta-heuristic algorithms for document clustering] , AMC Journal

*Multicast Routing: Forsat, R., Haghighat, M., Mahdavi, M., [http://dx.doi.org/10.1016/j.comcom.2008.03.019 Harmony search based algorithms for bandwidth-delay-constrained least-cost multicast routing] , Computer Communications, Elsevier