Harmony search

From Wikipedia, the free encyclopedia

Jump to: navigation, 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.

Contents

[edit] The algorithm

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

The algorithm as given by [2] is:

  1. Initialize the harmony memory: pick k random vectors x^1 \ldots x^k.
  2. Make a new vector x'. For each component x'i:
    • with probability phmcr pick the component from memory, x'_i = x^{rand()}_i
    • with probability 1 − phmcr pick a new random value in the allowed range.
  3. Pitch adjustment: For each component x'i:
    • with probability ppar change x'i by a small amount, x'_i \leftarrow x'_i \pm bw\cdot rand().
    • with probability 1 − ppar do nothing.
  4. If x' is better than the worst xi in the memory, then replace xi by x'.
  5. 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.
  • phmcr, the rate of choosing from memory. A typical value is 0.95.
  • ppar, 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, ppar is increased linearly, while bw 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
  • Heat exchanger design
  • Face milling process

[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

[edit] Theory of Harmony Search

  • Particle-Swarm Harmony Search: Omran, M.G.H. and Mahdavi, M. Global-Best Harmony Search, Applied Mathematics and Computation, In Press.

[edit] Applications in Artificial Intelligence

[edit] Applications in Engineering

  • 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.
  • 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.
Retrieved from "http://en.wikipedia.org/wiki/Harmony_search"
Personal tools