# The Pheromone-Based Harmony Search Algorithm for the Asymmetric Traveling Salesman Problem
## 5 Pheromone-Based Harmony Search for ATSP
### Pheromone-Based Harmony Search for ATSP  
In order to increase the effectiveness of the HS, suggested in [15], the process of constructing a new harmony was complemented with the knowledge accumulated by the means of a pheromone (performing the role of long-term memory). To preserve the idea describing the HS, activation of the described mechanism on the basis of \(H\)_MCR_ probability was assumed - when the list including successors of the recently visited cities is empty, a selection of the next city, on the basis of pheromone trail, takes place. The updating of the HS global memory is conducted according to Formula (7), after every iteration has been run. Based on the reference books it was assumed that \(Q_{3}=1\)[31] and \(\tau_{0}=1\)[32]. The probability of choosing a pitch in position \(s\) in harmony \(H\) is defined on the basis of a modified Formula (5) (based on the Simple-ACO approach, suggested in [32]), i.e.,  
\[p_{ij}(t)=\left\{\begin{array}{ll}\frac{\tau_{ij}(t)}{\sum_{j\in A}\tau_{ij}(t )}&\text{if }j\in A,\\ 0&\text{otherwise.}\end{array}\right., \tag{9}\]  
where: value \(i\) corresponds with the number of a city that is in harmony \(H\) in position \(s-1\), and \(A\) is a set of cities available for visiting.  
The introduction of pheromone memory is connected with the creation of a structure, the size of which is \(n^{2}\), and which can influence the problematic implementation of the suggested solution designed for large ATSP instances. In order to eliminate the indicated imperfection it is possible to apply selective pheromone memory, according to the approach suggested in [34]. Pseudocode of the PBHS for ATSP was presented in Algorithm 2.  
```
1:\(iterations=0\)
2:\(iterationsFromTheLastReplacement=0\)
3: Fill the pheromone memory \(\tau\) with the value \(1\)
4:for\(i=0;i<HMS;i++\)do
5:\(HM[i]\)=stochastically generate feasible solution
6:endfor
7: Sort \(HM\)
8:while\(iterations<IT\)do
9:\(H[0]\)=first city
10:for\(i=1;i<n;i++\)do\(\triangleright\)\(n\)--number of cities
11: Choose random \(r\in(0,1)\)
12:if\(r<HMCR\)then
13:\(list\)=create list containing vertices occurring after \(H[i-1]\) in \(HM\)
14:if\(list.length>0\)then
15:\(H[i]\)=choose element \(\in list\) according to the roulette wheel
16:else
17:\(H[i]\)=choose available city based on \(\tau\) and Formula (9)
18:endif
19: Choose random \(k\in(0,1)\)
20:if\(k<PAR\)then
21:\(H[i]\)=find nearest and available city from \(H[i-1]\)
22:endif
23:else
24:\(H[i]\)=choose randomly available city \(\
otin H\)
25:endif
26:endfor
27:if\(f(H)\) is better than \(f(HM[HMS-1])\)then
28:\(HM[HMS-1]=H\)
29: Sort \(HM\)
30:\(iterationsFromTheLastReplacement=0\)
31:else
32:\(iterationsFromTheLastReplacement++\)
33:endif
34:if\(iterationsFromTheLastReplacement=R\)then
35:for\(i=1;i<HMS;i++\)do
36:\(HM[i]\)=stochastically generate feasible solution
37:endfor
38: Sort \(HM\)
39:\(iterationsFromTheLastReplacement=0\)
40:endif
41: Update \(\tau\) based on Formula (7)
42:\(iterations++\)
43:endwhile
44:return \(HM[0]\)
```  
**Algorithm 2** The Pheromone-based Harmony Search for ATSP pseudocode.