# Rank-Based Ant System via the Relative Position in a Local Hierarchy

Authors: Tomoko Sakiyama; Kotaro Uneme; Ikuo Arizono
Journal: Complexity
 (2021)

---

## Abstract

ASrank has been proposed as an improved version of the ant colony optimisation (ACO) model. However, ASrank includes behaviours that do not exist in the actual biological system and fall into a local solution. To address this issue, we developed ASmulti, a new type of ASrank, in which each agent contributes to pheromone depositions by estimating its rank by interacting with the encountered agents. In this paper, we attempt further improvements in the performance of ASmulti by allowing agents to consider their position in a local hierarchy. Agents in the proposed model (AShierarchy) contribute to pheromone depositions by estimating the consistency between a local hierarchy and global (system) hierarchy. We show that, by using several TSP datasets, the proposed model can find a better solution than ASmulti.


---

## Body

## 1. Introduction

Ant colony optimisation (ACO) is a well-known strategy for determining short tours in the travelling salesman problem (TSP) [1]. Many ACO models have been developed by extending the ant system (AS) proposed by Dorigo [2–6]. Rank-based ant system (ASrank) is one of the representative models that extend the original AS [7]. Using the pheromone procedure update for exploring simulations, this model finds a solution to the TSP. In ASrank, ant agents are ranked in the order of shorter tour lengths at the end of each tour. Only the top-ranking agents are allowed to deposit pheromones. This function improves the convergence of the system by adding pheromones on only the edges toured by top-ranked agents. Thus, the system converges faster by concentrating pheromones on specific edges. However, because pheromones tend to concentrate solely on specific edges, the system frequently falls into local solutions. Furthermore, while ASrank is inspired by the behaviour of real ants, the viewpoint of a third party is introduced outside the system to classify agents in a single hierarchy, i.e., to place agents in the order of tour lengths. Agents that can complete tours in less time are rewarded with higher positions in the hierarchy.To eliminate the viewpoint of the third party from the system, we recently proposed a new type ofASrank named ASmulti in which an individual agent constructs a subjective hierarchy based on the interaction with encounters [8]. In ASmulti, agents decide whether to deposit pheromones based on a unique hierarchy for each agent, i.e., deposit pheromones when they encounter other agents that have worse solutions than theirs. Furthermore, if two agents meet one other during a tour, a subjective/unique hierarchy is used to rank them and other agents according to the tour lengths. To this end, individuals have a unique list of ranked agents based not on the viewpoint of the third party but on the first-person view. We found that such a contrivance allows the ASmulti system to find better solutions than ASrank. However, agents in ASmulti sometimes fall into a local solution caused by the mismatch between their subjective hierarchies and the system hierarchy, i.e., the actual single rank of the agents’ tours. Therefore, there is room for further improvement in ASmulti.In this study, we propose an improved version ofASmulti. We name this as AShierarchy. AShierarchy follows ASmulti; however, agents in AShierarchy sometimes deposit pheromones even when they encounter other agents with better solutions than themselves. This occurs because agents consider the mismatch between their local hierarchies and the global (system) hierarchy as individual agents cannot know the absolute rank in the system hierarchy. From the viewpoint of a specific agent, the greater the number of agents offering better solutions than the agent who encounters them, the fewer the opportunities for the agent to get away from a local solution. Therefore, the agents are allowed to deposit pheromones to some extent in cases where they encounter other agents having better solutions. Thus, individual agents in living systems seem to adapt as they consider the local information [9]. Through numerical simulations using several TSP datasets, we show that the proposed model outperforms ASmulti.Eliminating the viewpoint of the third party from the system is related to the subpopulations. Several studies have employed this approach for some optimisation problems [10–13]. For example, Cai et al. used the cooperative coevolution strategy to improve the global search capability for airport gate allocation optimisation [10]. Deng et al. used a similar mechanism, i.e., the CC framework, to deal with large-scale problems [11]. Multipopulations or population diversity contribute toward finding the global optimal solution. In our method, individual agents independently modulate their pheromone depositions based on their experiences during each tour.


## 2. Materials and Methods

### 2.1. Multirank-BasedAS (ASmulti)

We propose a multirank-based ant system (ASmulti) [8] as an improved version of ASrank [7]. In ASmulti, the probability of the next destination selection determined in the same manner as in ASrank, but a new approach is used for regulating agents who contribute to pheromone deposition. The new method of pheromone update in ASmulti is explained here. First, we define the parameters as follows:s: step count in one tourθstep: threshold for tour step in agent competitionratio: the value calculated in agent competitionφratio: threshold for ratio in agent competitionCk: the binary parameter indicating whether agent k survived the competitionNagent: the number of agents (equal to Ncity: the number of cities)Ncity: the set of citiescityx (s, t): city where the agent x is in at step scityy (s, t): city where the agent y is in at step sℓx (s, t): accumulated tour length of agent x at step sℓy (s, t): accumulated tour length of agent y at step sLk: tour length of the solution found by agent kTk: set of edges included in the solution found by agent kIf the following two conditions are satisfied, then a competition occurs among agents:(i)
The parameters satisfy the relationships/Ncity>θstep(ii)
There are other agents in the same cityWhen one agentx encounters another agent y, i.e., cityx (s, t) = cityy (s, t), the agents mutually compare the accumulated tour lengths at tour step s of this tour to determine whether there is enough difference between their accumulated tour lengths. Using their accumulated tour lengths ℓx (s, t) and ℓy (s, t), an evaluation value ratio is calculated. If the ratio exceeds the threshold in agent competition φratio (ratio > φratio), one long-length solution is defeated. In this case, 0 is assigned to the parameter Ck of the defeated agent. Here, the competition process is defined as follows:(1)ratio=lxs,t−lys,tlxs,t+lys,t,(2)Cx←0,if ratio≤φratio,ℓxs,t≥ℓys,t,(3)Cy←0,if ratio≤φratio,ℓxs,t≤ℓys,t.The following prerequisites should be noted as well:(i)
All parameters ofCk are initialised to 1 at the beginning of a tour(ii)
If an agentx is defeated even once in the middle of a tour, Cx remains 0 until the end of that tour(iii)
If three or more agents exist simultaneously in the same city, comparison for agentk is performed in all pairs until Ck is replaced with 0Finally, some agents who have never been defeated after completing a tour (Ck = 1) can perform pheromone deposition. In this method, each agent decides about whether to take part in pheromone deposition using the information from contacted agents. As this method does not require the viewpoint of the external third party for summarising the agent’s information, such as ASrank, it is faithful to the actual habits of ant swarms. After creating a tour, the pheromone update process is executed as follows:(4)τijt+1=ρτijt+∑k1Lk,ifi,j∈Tkt,Ck=1,0,otherwise.Agents inASmulti cannot perform pheromone deposition when they encounter other agents with better information. To this end, agents determine whether they are in a good/bad position in the global (system) hierarchy by using the subjective local hierarchy to confirm whether they have better/worse information than the agents encountered. However, identifying the local hierarchy as a subhierarchy of the global hierarchy does not enable convergence to specific solutions. To solve this problem, we proposed AShierarchy.


### 2.2. Hierarchical Rank-BasedAS (AShierarchy)

Here, we describe the hierarchical rank-based ant system (AShierarchy) proposed in this study. Agents in AShierarchy sometimes deposit pheromones even if they have worse solutions. From the viewpoint of a specific agent, the greater the number of encountered agents offering better solutions, the fewer the opportunities to get away from a local solution. To this end, agents in the proposed AShierarchy sometimes deposit pheromones even when they have inferior information than the agents encountered to prevent the system from falling into a local solution.Here, we define the parameters as followsmemk (t): lost-competition counterωmem: threshold for weak pheromone depositionweak: pheromone value for weak pheromone depositionInAShierarchy, equations (2) and (3) are modified as follows:(5)if ratio≤φratio,ℓxs,t≥ℓys,t,thenmemx←memx+1,Cx←0,if ratio≤φratio,ℓys,t≥ℓxs,t,thenmemy←memy+1,Cy←0.Equation (4) is also modified as follows:(6)τijt+1=ρτijt+∑k1Lk,ifi,j∈Tkt,Ck=1,∑kweakLk,ifi,j∈Tkt,Ck=0,memk≥ωmem,0,otherwise,where memk is reset to 0 at the beginning of each iteration t. Figure 1 shows the algorithm flowchart. The computational complexity of AShierarchy can be almost similar with that of ASrank because agents in AShierarchy need not be sorted according to tour lengths before pheromone updates; instead, the encounter between agents is considered.Figure 1
Flowcharts ofAShierarchy. (a) A tour iteration. (b) The pheromone update after each iteration. Note that ratio can be ratio=lxs,t−lys,t/lxs,t+lys,t, where lx (s, t) and ly (s, t) means accumulated tour length of agent x and y at step s. Lx means tour length of solution the agent x found.
(a)(b)


## 2.1. Multirank-BasedAS (ASmulti)

We propose a multirank-based ant system (ASmulti) [8] as an improved version of ASrank [7]. In ASmulti, the probability of the next destination selection determined in the same manner as in ASrank, but a new approach is used for regulating agents who contribute to pheromone deposition. The new method of pheromone update in ASmulti is explained here. First, we define the parameters as follows:s: step count in one tourθstep: threshold for tour step in agent competitionratio: the value calculated in agent competitionφratio: threshold for ratio in agent competitionCk: the binary parameter indicating whether agent k survived the competitionNagent: the number of agents (equal to Ncity: the number of cities)Ncity: the set of citiescityx (s, t): city where the agent x is in at step scityy (s, t): city where the agent y is in at step sℓx (s, t): accumulated tour length of agent x at step sℓy (s, t): accumulated tour length of agent y at step sLk: tour length of the solution found by agent kTk: set of edges included in the solution found by agent kIf the following two conditions are satisfied, then a competition occurs among agents:(i)
The parameters satisfy the relationships/Ncity>θstep(ii)
There are other agents in the same cityWhen one agentx encounters another agent y, i.e., cityx (s, t) = cityy (s, t), the agents mutually compare the accumulated tour lengths at tour step s of this tour to determine whether there is enough difference between their accumulated tour lengths. Using their accumulated tour lengths ℓx (s, t) and ℓy (s, t), an evaluation value ratio is calculated. If the ratio exceeds the threshold in agent competition φratio (ratio > φratio), one long-length solution is defeated. In this case, 0 is assigned to the parameter Ck of the defeated agent. Here, the competition process is defined as follows:(1)ratio=lxs,t−lys,tlxs,t+lys,t,(2)Cx←0,if ratio≤φratio,ℓxs,t≥ℓys,t,(3)Cy←0,if ratio≤φratio,ℓxs,t≤ℓys,t.The following prerequisites should be noted as well:(i)
All parameters ofCk are initialised to 1 at the beginning of a tour(ii)
If an agentx is defeated even once in the middle of a tour, Cx remains 0 until the end of that tour(iii)
If three or more agents exist simultaneously in the same city, comparison for agentk is performed in all pairs until Ck is replaced with 0Finally, some agents who have never been defeated after completing a tour (Ck = 1) can perform pheromone deposition. In this method, each agent decides about whether to take part in pheromone deposition using the information from contacted agents. As this method does not require the viewpoint of the external third party for summarising the agent’s information, such as ASrank, it is faithful to the actual habits of ant swarms. After creating a tour, the pheromone update process is executed as follows:(4)τijt+1=ρτijt+∑k1Lk,ifi,j∈Tkt,Ck=1,0,otherwise.Agents inASmulti cannot perform pheromone deposition when they encounter other agents with better information. To this end, agents determine whether they are in a good/bad position in the global (system) hierarchy by using the subjective local hierarchy to confirm whether they have better/worse information than the agents encountered. However, identifying the local hierarchy as a subhierarchy of the global hierarchy does not enable convergence to specific solutions. To solve this problem, we proposed AShierarchy.


## 2.2. Hierarchical Rank-BasedAS (AShierarchy)

Here, we describe the hierarchical rank-based ant system (AShierarchy) proposed in this study. Agents in AShierarchy sometimes deposit pheromones even if they have worse solutions. From the viewpoint of a specific agent, the greater the number of encountered agents offering better solutions, the fewer the opportunities to get away from a local solution. To this end, agents in the proposed AShierarchy sometimes deposit pheromones even when they have inferior information than the agents encountered to prevent the system from falling into a local solution.Here, we define the parameters as followsmemk (t): lost-competition counterωmem: threshold for weak pheromone depositionweak: pheromone value for weak pheromone depositionInAShierarchy, equations (2) and (3) are modified as follows:(5)if ratio≤φratio,ℓxs,t≥ℓys,t,thenmemx←memx+1,Cx←0,if ratio≤φratio,ℓys,t≥ℓxs,t,thenmemy←memy+1,Cy←0.Equation (4) is also modified as follows:(6)τijt+1=ρτijt+∑k1Lk,ifi,j∈Tkt,Ck=1,∑kweakLk,ifi,j∈Tkt,Ck=0,memk≥ωmem,0,otherwise,where memk is reset to 0 at the beginning of each iteration t. Figure 1 shows the algorithm flowchart. The computational complexity of AShierarchy can be almost similar with that of ASrank because agents in AShierarchy need not be sorted according to tour lengths before pheromone updates; instead, the encounter between agents is considered.Figure 1
Flowcharts ofAShierarchy. (a) A tour iteration. (b) The pheromone update after each iteration. Note that ratio can be ratio=lxs,t−lys,t/lxs,t+lys,t, where lx (s, t) and ly (s, t) means accumulated tour length of agent x and y at step s. Lx means tour length of solution the agent x found.
(a)(b)


## 3. Results

We conducted a tour exploration experiment on TSP benchmark datasets and compared theAShierarchy simulation results with that of ASmulti as we have already compared the performance of ASmulti with ASrank [8]. We found that AShierarchy yielded better solutions than ASrank. We used four TSP datasets: Eil51.tsp (Ncity = 51), Berlin52.tsp (Ncity = 52), Lin105.tsp (Ncity = 105), and Pr124.tsp (Ncity = 124). Some of these datasets have often been used for benchmark tests [14, 15]. The TSP datasets used here are classified as symmetric travelling salesman problem wherein the edge length between two cities in the opposite directions is the same. We focused on the TSP datasets adopting 2EUD. As shown in Table 1, the same values were adopted for the parameters common to ASmulti and AShierarchy [8]. AShierarchy also has characteristic parameters ωmem and weak; these parameter values were selected after a series of preliminary experiments comprising 10 attempts for each dataset. The parameters common to ASmulti and AShierarchy were set according to the previous study where we found that ASmulti outperformed ASrank [8].Table 1
Parameter settings.
ACO modelAShierarchyASmulti(α, β)(1, 1)(1, 1)Ρ0.50.5Loop tour per 1 trial10001000Simulation trial100100θstep0.90.9φratio0.0010.001ωmem5—Weak0.01—For each model, Table2 shows the averaged best solutions obtained from 100 trials. In these benchmark datasets, AShierarchy outperformed ASmulti for averaged best solutions. The p value in Table 2 shows that there is significant difference between the averaged best solutions of both models in the U test. In addition, the term “(optimal)” denotes the tour length of the optimal solution in each benchmark dataset. From the results in Table 2, it is seen that AShierarchy, which allows agents who became a loser several times to update small quantities of pheromone, performs better than ASmulti.Table 2
Mean best solutions.
TSPAShierarchyASmultip value (optimal)Eil51434.31436.440.021 (426)Berlin527557.457589.50.047 (7552)Lin10514630.3414709.19<1.0e − 06 (14379)Pr12460334.4660586.770.0067 (59030)Figure2 shows the step interval of usual/weak pheromone depositions. We calculated the step interval of one agent using Eil51. According to Figure 2, the agent deposits weak pheromones more often than usual pheromones, satisfying equation (6). Such behaviours might inhibit rapid pheromone evaporation and result in the system getting away from local solutions.Figure 2
Step interval of pheromone addition (Eil51). (a) The step interval of the usual pheromone addition. (b) The step interval of weak pheromone addition.
(a)(b)Finally, we examined the parameter effect usingEil51. Here, we used the parameter value of ωmem as 10 (instead of 5). Table 3 shows the results. Again, AShierarchy performed better than ASmulti even after the parameter replacement.Table 3
Mean best solutions after parameter replacement.
TSPAShierarchyASmultip value (optimal)Eil51434.28436.440.013 (426)


## 4. Discussion

In this paper, we investigated whetherAShierarchy outperforms ASmulti. ASmulti is the basis for the proposed model. However, AShierarchy allows agents who become a loser several times to update small quantities of pheromone. By contrast, agents in ASmulti are never allowed to deposit any pheromones if they encounter other agents with better solutions. Weak pheromone depositions frequently occur in AShierarchy, which might improve the performance of AShierarchy. The important point in the proposed model is that a group that has relatively better information than a specific agent does not always exhibit better information because agents are allowed to use only limited information via interaction with local other agents.ACO does not guarantee convergence to the optimal solution [16, 17]. Usual/weak pheromone depositions can serve as a key to achieve the balance between convergence and divergence to overcome this problem [18]. In this paper, we focused only on the proposed model’s performance in terms of finding solutions; we did not consider other aspects such as the time required to find a correct solution or comparing our model with metaheuristics other than ACO. We would like to emphasise the importance of separation between third-party viewpoints and the first-person point of individual agents in multiagent systems. Researchers often introduce third-party viewpoints on metaheuristic systems derived from living systems that may not represent the original meaning of living/natural systems to find better solutions. The strength of our findings is that individual agents decide to deposit pheromones based only on their experiences, which does not require seeing the system from a higher viewpoint. To do so, a system comprising many agents solves complex tasks flexibly without falling into a certain solution [19].In future studies, we will investigate whether a stable solution can be obtained in other TSP datasets and find methods for parameter selection and for improving the algorithm’s efficiency by considering the program execution steps.



---

*Source: 8372318-2021-09-08.xml*