Harmony search

From Wikipedia, the free encyclopedia

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.

1 The algorithm
2 Harmony search applications
- 2.1 Bench-mark problems
- 2.2 Real-world problems
3 Harmony search features
4 Other Related Algorithms
5 References

[edit] 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'. For each component x'_i:
- with probability $p h m c r$ pick the component from memory, $x'_i = x^{rand()}_i$
- with probability $1 - p h m c r$ pick a new random value in the allowed range.
Pitch adjustment: For each component x'_i:
- with probability $p p a r$ change $x' i$ by a small amount, $x'_i \leftarrow x'_i \pm bw\cdot rand()$ .
- with probability $1 - p p a r$ do nothing.
If $x'$ is better than the worst $x i$ in the memory, then replace $x i$ by $x'$ .
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 h m c r$ , the rate of choosing from memory. A typical value is $0.95$ .
$p p a r$ , the 'pitch adjustment rate'. Typical values range from $0.3$ to $0.99$ .
$b w$ , 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 p a r$ is increased linearly, while $b w$ is decreased exponentially.

[edit] Harmony search applications

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

[edit] Bench-mark problems

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

[edit] 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

[edit] 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 discrete variables as well as 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 ensemble operation.

[edit] Other Related Algorithms

[edit] References

[edit] General Information

Algorithm Website: Harmony Search Algorithm

Book: Bhanu Prasad, Soft Computing Applications in Industry, 2008.

[edit] Theory of Harmony Search

Original Harmony Search: Geem, Z. W., Kim, J. H., and Loganathan, G. V. A New Heuristic Optimization Algorithm: Harmony Search, Simulation, 2001.

Stochastic Partial Derivative: Geem, Z. W. 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. 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. Improved Harmony Search from Ensemble of Music Players, Lecture Notes in Artificial Intelligence, 2006.

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, M.G.H. and Mahdavi, M. Global-Best Harmony Search, Applied Mathematics and Computation, In Press.

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, In Press.

[edit] Applications in Artificial Intelligence

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.

[edit] Applications in Engineering

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.

See also ebooksgratis.com: no banners, no cookies, totally FREE.