Discussion # 5 (22 July 2009) : Common Paper

Article Reference
Zoong Woo Geem, Joong Hoon Kim, G V Loganathan, A New heuristic Optimization Algorithm : Harmony Search

Introduction
The paper tries to focus on the new heuristic algorithm called “Harmony Search” (HS) which is explained using three examples – TSP, academic optimization problem and a least cost pipe network design problem. Authors explain the drawbacks of using the normal optimization methods i.e LP, NLP and DP. In LP there are considerable losses associated as the real world non linear model is being expressed as a linear model; In DP increased variable increase the evaluation of the recursive functions; in NLP if the functions are not differentiable then finding optimum is not possible and attention is required to select the initial values in order to guarantee global optima instead of local optima. To overcome the above mentioned drawbacks, heuristic method of optimization is developed which results in near optimum solution within reasonable computation time and within reasonable use of memory. Since 1970 there have been many heuristic algorithms which have been developed combining rules and randomness mimicking the natural processes. The techniques are:
• Simulated annealing (SA) – It is based on the analogy of physical annealing process. In physical annealing as the materials temperature increases the molecules mobility increases and gradually these molecules form the crystalline structure i.e. the optimal solution.
• Tabu search (TS) – it explores the search space of feasible solutions by sequence of moves. To escape from the local optima and to prevent cycling some moves are classified as tabu.
• Evolutionary algorithms (EA) – it is based on the principle of evolution. Consists of four heuristic algorithms- genetic algorithm, evolutionary strategies, evolutionary programming and genetic programming.
• Genetic Algorithm – based on the natural selection and the mechanism of population genetics. It has three operators – reproduction, crossover and mutation. Main advantage of GA when compared to other optimization techniques or heuristic techniques is that GA evaluates different solutions simultaneously unlike the other methods which evaluate on solution at a time.
• Evolutionary strategies
• Evolutionary programming
• Genetic programming
These simulation based heuristic search techniques have powerful search abilities which overcome the drawbacks of the traditional optimization techniques. The paper proposes a new heuristic search technique which produces better solution in less number of iterations than the other techniques.

New Heuristic technique (Harmony Search)
The steps to be followed in this new technique are:
• Step 1 – Initialize a Harmony memory (HM)
• Step 2 – Improvise a new harmony from HM
• Step 3 – If the new harmony is better than the minimum harmony in HM then include the new harmony in the HM and exclude the minimum harmony from HM
• Step 4 – if the stopping criteria are not met then repeat the Step 2.

To improve the solutions and escaping from the local optima there two methods which are introduced, they are:
• Harmony memory considering rate (HMCR): indicates the probability of the algorithm which selects the variable from the harmony memory onto the next step
• Pitch adjusting rate (PAR): shifting the values to nearby neighboring values in the specified range which is called as PAR. PAR 10% means the new value is selected in the probability of 10% (5% of higher value or lower value with 5%)

Major difference between HS and GA is that HS makes a new vector from the existing vectors (i.e from all harmonies in the Harmony memory) where as GA makes new vector only from the two existing vectors (parent).

Examples
1. Travel Salesman Problem – Harmony memory consists of the existing tour lengths, if the new tour length is shorter than the existing HM tour lengths then the new tour length is replaced in the HM. Different HMCR and PAR parameters are considered and the iterations are performed to avoid the local optima solution. For faster convergence two new operators have been introduced – Neighboring city (i.e salesman visiting the closest neighboring city) and city inverting (i.e inverting the city if the former is shorter than the later city).
2. Simple constrained minimization problem – Initially decision variable x1 and x2 have been selected randomly based on the given range later the range has been narrowed to the values in the HM. This problem was solved using generalized reduced gradient (GRG), EP and GA, HS has evolved much better solutions than the other methods.
3. Design of pipe network for water supply – The problem has 32 nodes, 32 links and 3 loops, no pumping station is considered. Minimum pressure requirement at all the nodes is specified. This problem was solved using Nonlinear programming gradient and GA. HS gave a minimum least cost of the pipe network when compared to the other heuristic methods.

Conclusions and Discussion
HS is advantageous than the other methods
- as it makes a new set of vectors based on all existing vectors instead of just two vectors (parent),
- it does not require initial values of the decision variables
- It outperformed the other heuristic techniques (GA, EP etc)
- Faster convergence