Harmony search

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'. For each component x'_i:
#* with probability p_{hmcr} pick the component from memory, x'_i = x^{rand()}_i
#* with probability 1-p_{hmcr} pick a new random value in the allowed range.
# Pitch adjustment: For each component x'_i:
#* with probability p_{par} change x'_i by a small amount, x'_i leftarrow x'_i pm bwcdot rand().
#* with probability 1-p_{par} 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_{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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Harmony (disambiguation) — Harmony is the art of using chords in music. More generally, it means agreement .Music* Harmony (Schenker), a book by Heinrich Schenker on music theory *Harmony (band), a melodic progressive metal band from Sweden *Harmony (dutch band), a dutch… …   Wikipedia

  • Harmony Grass — was a British pop group active briefly in the late 1960s.The group was formed in Essex by previous members of Tony Rivers the Castaways, including Tony Rivers himself. They signed to RCA Records about a year after they formed, and their single… …   Wikipedia

  • Harmony Township, New Jersey — Infobox Settlement official name = Harmony Township, New Jersey settlement type = Township nickname = motto = imagesize = image caption = image mapsize = 250x200px map caption = Map of Harmony Township in Warren County. Inset: Location of Warren… …   Wikipedia

  • Harmony Korine — Infobox Actor name = Harmony Korine birthdate = birth date and age|1973|01|4 location = Bolinas, California, U.S. birthname = Harmony KorineHarmony Korine (born January 4 1973)imdb name|0005101] is an American film director, producer,… …   Wikipedia

  • Harmony Kendall — Infobox Buffyverse Character Harmony Kendall Title=Harmony Kendall First= The Harvest (Buffy) Last= Not Fade Away (Angel) Creator=Joss Whedon Name=Harmony Kendall Status=Undead Kind=Vampire Affiliation=None, formerly Wolfram Hart, Angel… …   Wikipedia

  • Harmony, Pennsylvania — Geobox|Settlement name = Harmony native name = other name = other name1 = category = Borough etymology type = Named for etymology = official name = Borough of Harmony nickname = motto = image caption = Rapp s Seat overlooking Harmony, PA and… …   Wikipedia

  • Cuckoo search — (CS) is an optimization algorithm developed by Xin she Yang and Suash Deb in 2009.[1][2] It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (of other species). Some host… …   Wikipedia

  • Tabu search — is a mathematical optimization method, belonging to the class of local search techniques. Tabu search enhances the performance of a local search method by using memory structures: once a potential solution has been determined, it is marked as… …   Wikipedia

  • Diverse Harmony — Background information Birth name Diverse Harmony Origin Seattle, Washington, USA Genres …   Wikipedia

  • Quartal and quintal harmony — In music, quartal harmony is the building of chordal and melodic structures with a distinct preference for intervals of fourths . (.Use of the term arises from a contrast, compositional or perceptual, with traditional tertian harmonic… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”