# The Pheromone-Based Harmony Search Algorithm for the Asymmetric Traveling Salesman Problem
## 2 A Classical Harmony Search Algorithm  
According to [19] we can assume that the aesthetic quality of a musical instrument is determined by its pitch (that in Musical Instrument Digital Interface is often represented as a numerical scale), timbre and amplitude. Timbre is determined by the harmonic content that depends on the pitch or frequency range of the particular instrument. When we adjust the pitch, we are trying to change the frequency. [PERSON] in [20] suggested a controversial metaheuristic that was based on the similarity of the process of jazz improvisation to looking for global optimum through the means of algorithmic methods. The technique assumes the existence of a structure \(HM\) (referred to as the Harmony Memory), which stores \(HMS\) harmonies that consist of a set number of pitches (representing the values of decision variables of a given result). The particular \(HM\) elements are interpreted as a complete solution of the problem, the value of the objective function of which is defined on the basis of its component parts. The initial content of the Harmony Memory is generated randomly, after which it is subjected to sorting on the basis of appropriate objective function values (in such a way as to make it possible that the result in the first position can be characterized by the best result). The realization of the described steps brings about the launch of an iterative creation of subsequent solutions. The procedure of creating a new solution applies the knowledge stored in \(HM\) and is based on an analogy to the process of harmony improvisation in music. The construction of such a solution consists in an iterative selection of the next pitch, according to two parameters--\(HMCR\) (Harmony Consideration Rate) and \(PAR\) (Pitch Adjustment Rate). On the basis of probability \(HMCR\) the pitch \(i\) is selected, using the values located in position \(i\) in harmonies that belong to \(HM\) (otherwise random generation of an acceptable value takes place). Creating a solution based on a component \(HM\) a modification of the pitch with the set probability \(PAR\) may occur (the change of value takes place on the basis of parameter \(bw\), the value of which depends on the representation of the problem). To sum up the random selection of the pitch value is done with probability \(1-HMCR\), using an unmodified value from \(HM\) may occur with probability \(HMCR\cdot PAR\), whereas modified value from \(HM\) is chosen with probability \(HMCR\cdot(1-PAR)\). After generating the subsequent solution, comparison of its objective function value with the appropriate parameter describing the component located in the last position in \(HM\) is held. In the situation of determining a better result, it replaces the worst result stored in the Harmony Memory and another sorting of the \(HM\) elements is conducted. The procedure of generating a new solution is conducted by \(IT\) iterations, after which the return of the best result occurs (located in the first position in the Harmony Memory). Pseudocode of the HS was presented in Algorithm 1. ```
1:\(iterations=0\)
2:for\(i=0;i<HMS;i++\)do
3:\(HM[i]\)=stochastically generate feasible solution
4:endfor
5: Sort \(HM\)
6:while\(iterations<IT\)do
7:for\(i=0;i<n;i++\)do
8: Choose random \(r\in(0,1)\)
9:if\(r<HMCR\)then
10:\(H[i]\)=choose randomly available pitch on position \(i\) in \(HM\)
11: Choose random \(k\in(0,1)\)
12:if\(k<PAR\)then
13:\(\alpha=bw\cdot random\in(-1,1)\)
14:\(H[i]\)=\(H[i]+\alpha\)
15:endif
16:else
17:\(H[i]\)=choose randomly available pitch
18:endif
19:endfor
20:if\(f(H)\) is better than \(f(HM[HMS-1])\)then
21:\(HM[HMS-1]=H\)
22: Sort \(HM\)
23:endif
24:\(iterations++\)
25:endwhile
26:return \(HM[0]\)
```  
**Algorithm 1** The Harmony Search pseudocode (based on [15]).