In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and operations research

Operations research

Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

, harmony search (HS) is a phenomenon-mimicking algorithm (also known as metaheuristic

Metaheuristic

In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...

 algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

, soft computing

Soft computing

Soft computing is a term applied to a field within computer science which is characterized by the use of inexact solutions to computationally-hard tasks such as the solution of NP-complete problems, for which an exact solution cannot be derived in polynomial time.-Introduction:Soft Computing became...

 algorithm or evolutionary algorithm

Evolutionary algorithm

In artificial intelligence, an evolutionary algorithm is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection...

) inspired by the improvisation process of musicians. In the HS algorithm, each musician (= decision variable) plays (= generates) a note (= a value) for finding a best harmony (= global optimum) all together.
The Harmony Search algorithm has 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.
• 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.
• HS has a novel stochastic derivative 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 which optimizes (minimizes or maximizes) a certain objective function.

The algorithm has the following steps:

Step 1: Generate random vectors () as many as (harmony memory size), then store them in harmony memory (HM).

Step 2: Generate a new vector . For each component ,

• with probability (harmony memory considering rate; 0 ≤ ≤ 1), pick the stored value from HM:
• with probability , pick a random value within the allowed range.

Step 3: Perform additional work if the value in Step 2 came from HM.

• with probability (pitch adjusting rate; 0 ≤ ≤ 1), change by a small amount: or for discrete variable; or for continuous variable.
• with probability , do nothing.

Step 4: If is better than the worst vector in HM, replace with .

Step 5: Repeat from Step 2 to Step 4 until termination criterion (e.g. maximum iterations) is satisfied.

The parameters of the algorithm are

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

Simulated annealing

Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...

.

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
  Evolutionary computation
  In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
  
  
  • Metaheuristic
    Metaheuristic
    In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
    
    s
    • Stochastic optimization
      Stochastic optimization
      Stochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...
      
      
      • Optimization
        Optimization (mathematics)
        In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
        
        

Other evolutionary computing methods include:

• Evolutionary algorithms, including:
  • Genetic algorithm
    Genetic algorithm
    A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
    
    s
• Swarm algorithms
  Swarm intelligence
  Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
  
  , including:
  • Ant colony optimization
    Ant colony optimization
    In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
    
    
  • Particle swarm optimization
    Particle swarm optimization
    In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
    
    
  • Intelligent Water Drops

Other metaheuristic methods include:

• Simulated annealing
  Simulated annealing
  Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
  
  
• Tabu search
  Tabu search
  Tabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
  
  

Other stochastic methods include:

• Cross-entropy method
  Cross-entropy method
  The cross-entropy method attributed to Reuven Rubinstein is a general Monte Carlo approach tocombinatorial and continuous multi-extremal optimization and importance sampling.The method originated from the field of rare event simulation, where...
  
  

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, Novel Derivative of Harmony Search Algorithm for Discrete Design Variables, Applied Mathematics and Computation, 2008.

• Ensembled Harmony Search: Geem ZW, Improved Harmony Search from Ensemble of Music Players, Lecture Notes in Artificial Intelligence, 2006.

• Continuous Harmony Search: Lee KS and Geem ZW, A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice, Computer Methods in Applied Mechanics and Engineering, 2005.

• 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), 2011.

• 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.

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.

• 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. 24rd 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

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.

• 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.

• 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

Source Codes

• Improved Harmony Search (MATLAB) https://sites.google.com/site/fesangharyweb/downloads
• Hybrid HS-SQP (Visual C++) https://sites.google.com/site/fesangharyweb/downloads
• Other HS Variants http://sites.google.com/a/hydroteq.com/www/