# Ant Colony Optimization Using Common Social Information and Self-Memory

Authors: Yoshiki Tamura; Tomoko Sakiyama; Ikuo Arizono
Journal: Complexity
 (2021)

---

## Abstract

Ant colony optimization (ACO), which is one of the metaheuristics imitating real ant foraging behavior, is an eﬀective method to ﬁnd a solution for the traveling salesman problem (TSP). The rank-based ant system (ASrank) has been proposed as a developed version of the fundamental model AS of ACO. In the ASrank, since only ant agents that have found one of some excellent solutions are let to regulate the pheromone, the pheromone concentrates on a specific route. As a result, although the ASrank can find a relatively good solution in a short time, it has the disadvantage of being prone falling into a local solution because the pheromone concentrates on a specific route. This problem seems to come from the loss of diversity in route selection according to the rapid accumulation of pheromones to the specific routes. Some ACO models, not just the ASrank, also suffer from this problem of loss of diversity in route selection. It can be considered that the diversity of solutions as well as the selection of solutions is an important factor in the solution system by swarm intelligence such as ACO. In this paper, to solve this problem, we introduce the ant system using individual memories (ASIM) aiming to improve the ability to solve TSP while maintaining the diversity of the behavior of each ant. We apply the existing ACO algorithms and ASIM to some TSP benchmarks and compare the ability to solve TSP.


---

## Body

## 1. Introduction

Dorigo proposed ant colony optimization (ACO) as a metaheuristic for solving combination optimization problems [1, 2]. ACO is one of the metaheuristics imitating the group intellectual behavior of social insects, especially foraging behavior of ants. When real ants succeed in finding food sources and so on, they get back to the nest site while laying pheromones on the ground. Other ants are induced by pheromones, and induced ants can reach a target place. Furthermore, they will also back to the nest site while laying pheromones on the ground. Since pheromones have volatility, the pheromone of longer path will disappear compared to the pheromone of shorter path. In this way, ant colony can ﬁnd a short path from the nest to the feeding site, and they can transport resources eﬀectively. ACO is a system developed by imitating such a mechanism in ant foraging behavior and is used as a method to ﬁnd a solution for combinatorial optimization problems represented by TSP. Then, ACO might be a useful solving tool for TSP and some manufacturing problems in the real world [3–7].Since the ant system (AS) which is the basic model of ACO has been proposed by Dorigo [1, 2], various improved models have been constructed. The rank-based ant system (ASrank) proposed by Bullnheimer is one of them [8]. This model has a feature at the procedure for pheromone regulation. In solving TSP by using Saran, after completing making tours by all ant agents, ant agents are sorted in descending order of tour lengths which have been found out by each ant agent. Then, only a certain number of superior ant agents called elite agents who have succeeded in ﬁnding short tours are allowed to deposit pheromones. Pheromones on only the speciﬁc paths belonging to the shorter tours are added by this feature. As a result, this feature that the pheromone converges on a specific route makes all ant agents converge rapidly to a tour with short length. Although it contributes to ﬁnding the comparative reasonable solution within early time in solving TSP, it has an issue that the system easily falls into a local solution because pheromones on only some specific paths will be deposited. Falling into a local optimal solution means finding no better new solution compared to the current solution. That is, it means that the ability to solve a problem in ASrank is impaired because all ant agents converge rapidly to a tentative tour with comparatively shorter length.Such a trouble exists in many ACO algorithms, not just ASrank. For this trouble, Liu et al. [9] have noted that particle swarm optimization (PSO) has a disadvantage of quickly losing population diversity although it is a useful tool as a metaheuristic because of its simple concept and easy implementation. Also, Mahapatra et al. [10] have considered the diversity in the swarm intelligence- (SI-) based centralized clustering solutions an important factor. Hence, it can be considered that the diversity in the selection of solutions is an important factor in ACO as the solution system. Furthermore, it might be considered for ASrank to have an incongruous mechanism as one of nature-inspired algorithms. That is, although the ASrank has introduced the mechanism to select elite ant agents from the outside viewpoint of the system, the habits of actual ants in the swarm do not have such a mechanism based on the outside viewpoint.On the one hand, Gruter et al. [11] have reported that individual ants make decisions using both social information as pheromones and own memories as individual information during foraging activities in the natural world. Therefore, it can be seen that the swarm of actual ants keeps the diversity in the decision making as a swarm. In contrast, while many existing ACO algorithms including AS and ASrank imitate the behavior of ants, all ant agents act using only social information shared by the system and not individual information.Therefore, in this paper, we propose a novel ant system maintaining the diversity of the behavior of each ant agent by incorporating the mechanism of making decisions based on one’s own memory and social information. Then, this novel ant system would be named the ant system using individual memories (ASIM). Further, ASIM does not require the outside viewpoint of the system, and agents in ASIM build solutions using their own memory in addition to the common social information, such as heuristic and pheromone information. Through the unique behavior in ASIM that all ant agents make decision using individual own memory in addition to the common social information, it can be expected for ASIM to keep diversity as solving system and avoid falling into the local solution. Based on numerical results about four TSP benchmarks of different sizes [12], the solving ability of ASIM with the purpose of keeping diversity of solutions using nature-inspired memory information is evaluated by comparing with the existing ACO models, that is, AS and ASrank.


## 2. Materials and Methods

### 2.1. Ant System (AS)

In this section, we explain the ant system (AS) that is the fundamental model of ACO proposed by Dorigo [1,2]. To solve TSP with AS, the artificial ant agents are placed one by one in all cities. Then, every ant agent makes a tour under the condition of transiting every city exactly once in one tour. The probability pijkt that city j is selected to be visited immediately after city i can be written in a formula as follows:(1)pijkt=τijtαηijtβ∑l∈Nkτiltαηiltβ,ifj∈Nk,0,otherwise,where t: iteration counter; τij: intensity of pheromone trail between cities i and j; α: weight for τij; ηij: visibility of city i from city j (ηij=1/dij); β: weight for ηij; Nk: set of cities that the ant agent k has not visited yet; and dij: distance cities i and j.This city selection process is repeated until all ant agents have completed a tour. After creating one tour, every ant agent deposits pheromone on all paths where they have passed. The amount of pheromone deposited depends on the length of the tour. The pheromone regulation process is deﬁned as follows:(2)τijt+1=1−ρτijt+Δτijt,where Δτijt=∑k=1m1/Lkt,if antktravels on edgei,j,0,otherwise,ρ: evaporation rate of the pheromone which is parameter to regulate τij, Δτij: total increase of trail level on edge i,j, m: number of ant agents, and Lk: tour length found out by ant agent k.The amount of existing pheromone on edgeτij is reduced by the evaporation rate of the pheromone ρ before the next tour, and the pheromones on the unpassed edge will only evaporate. Therefore, long-distance tours are eliminated through the above pheromone regulation, and this regulation promotes early convergence for exploring tour. The best solution will be updated when the solution is newly found that has the shorter tour length than the current best solution. In tour exploration by using AS, successive procedures of traveling, pheromone regulation, and updating the best solution are repeated as mentioned above. The exploring simulation finishes when the exit condition is completed.


### 2.2. Rank-Based Ant System (ASrank)

In this section, we explain the rank-based ant system (ASrank) proposed by Bullnheimer et al. [8] as the improved algorithm from AS. In ASrank, the way of determining the probability for next destination selection from the present city is same as that in AS shown in equation (1). However, the way of pheromone regulation is different from AS. In pheromone regulation process of ASrank, all ant agents are ranked by sorting in ascending order of tour lengths. At that time, ant agents ranked between the top and the σ−1-th become elite ant agents who can contribute to pheromone deposition. In addition, ant agent who has found the best so-far solution until current exploring iteration has been identified as the virtual ant agent, and the virtual ant agent can also deposit extra pheromones. These superior ant agents and the virtual ant agent are deﬁned as the elite ant agents. The pheromone regulation by the elite ant agent is defined as follows:(3)τijt+1=1−ρτijt+Δτijt+Δτij∗t,where (4)Δτijt=∑μ=1σ−1Δτijμt,Δτijμt=σ−μQLμt,if theμ−th best ant travels on edgei,j,0,otherwise,Δτij∗t=σQL∗,if edgei,jis part of best solution found so far,0,otherwise,σ: number of elite ant agents, μ: ranking index, Δτijμ: increase of trail level on the edge i,j caused by the μ-th best ant agent, Lμ: tour length of the μ-th best ant agent, Δτij∗: increase of trail level on the edge i,j caused by the elite ant agents, L∗: tour length of best solution found so far, and Q: quantity of pheromone laid by an ant agent per tour.ASrank intends to ﬁnd a good solution eﬃciently by making a diﬀerence of pheromone strength between the paths included in short traveling tours and nonpopular paths.


### 2.3. Ant System Using Individual Memories (ASIM)

As mentioned previously, it can be considered that the diversity of solutions as well as the selection of solutions is an important factor in the solution system by swarm intelligence such as ACO. Hence, we would like to propose the ant system using individual memories (ASIM) as a new ACO algorithm considering the diversity in the artificial ant behavior. The heuristic information based on intercity distance and the pheromone information applied to intercity routes means common social information which every ant agent uses commonly. ASIM has a new aspect of using its own memory of each ant agent in addition to heuristic information based on intercity distance and pheromone information applied to intercity routes. In ASIM, each ant agent constructs a solution using both common social information and personal information which is its own memory. Specifically, as personal information, each ant agent can remember the personal best solution it has found so far. In the case of regulating the pheromone, the personal pheromone for each ant agent is applied additionally on the path including the best solution that each ant agent has found out in the past tours, apart from the pheromone as social information. In the natural world, it is known that when real ants discover a shorter path from the nest to the feeding site, they increase the amount of pheromone they apply along that route [13, 14]. On the one hand, in ASIM, when the best solution cannot be updated, each ant agent can regulate the personal pheromones on the path in the best solution that has been found so far. Here, note that each ant agent cannot recognize the personal pheromones applied by the other ant agents. The regulation of the personal pheromone is defined as follows:(5)ϕijkt+1=1−θϕijkt+Δϕijkt,where (6)Δϕijkt=ZCk∗,if edgei,jis part of antk's best solution found so far,0,otherwise,ϕijk: intensity of the ant agent k′s personal pheromone trail between cities i and j, θ: evaporation rate of the personal pheromone which is parameter to regulate ϕijk, Δϕijk: increase of trail level by ant agent k on edge i,j, Z: quantity of personal pheromone laid by an ant agent per tour, and Ck∗: tour length of the best solution of that ant agent k has ever found.In the pheromone regulation,Z means the parameter to adjust the amount of the personal pheromone applied by each ant agent. In addition, pheromones τijt are regulated based on equation (2) in the same way as AS. In ASIM, by including the personal pheromone ϕijk, the probability pijkt that city j is selected to be visited immediately after city i can be rewritten in a formula as follows:(7)pijkt=τijt+ϕijktαηijtβ∑l∈Nkτilt+ϕilktαηiltβ,ifj∈Nk,0,otherwise.Note that ASIM uses personal pheromonesϕijkt which is the personal information in addition to the common social information τijt and ηijt to select the next visited city. By using the personal information which each ant agent has individually, the diversity of tour in the ACO system can be maintained, and then it is expected that it is possible to search for a path while avoiding falling into a local solution. In addition, note that the computation complexity of the proposed algorithm ASIM is almost even to the existing algorithms, AS and ASrank, except for memorizing the information of the personal best solution in the past and the personal pheromone ϕijkt.


## 2.1. Ant System (AS)

In this section, we explain the ant system (AS) that is the fundamental model of ACO proposed by Dorigo [1,2]. To solve TSP with AS, the artificial ant agents are placed one by one in all cities. Then, every ant agent makes a tour under the condition of transiting every city exactly once in one tour. The probability pijkt that city j is selected to be visited immediately after city i can be written in a formula as follows:(1)pijkt=τijtαηijtβ∑l∈Nkτiltαηiltβ,ifj∈Nk,0,otherwise,where t: iteration counter; τij: intensity of pheromone trail between cities i and j; α: weight for τij; ηij: visibility of city i from city j (ηij=1/dij); β: weight for ηij; Nk: set of cities that the ant agent k has not visited yet; and dij: distance cities i and j.This city selection process is repeated until all ant agents have completed a tour. After creating one tour, every ant agent deposits pheromone on all paths where they have passed. The amount of pheromone deposited depends on the length of the tour. The pheromone regulation process is deﬁned as follows:(2)τijt+1=1−ρτijt+Δτijt,where Δτijt=∑k=1m1/Lkt,if antktravels on edgei,j,0,otherwise,ρ: evaporation rate of the pheromone which is parameter to regulate τij, Δτij: total increase of trail level on edge i,j, m: number of ant agents, and Lk: tour length found out by ant agent k.The amount of existing pheromone on edgeτij is reduced by the evaporation rate of the pheromone ρ before the next tour, and the pheromones on the unpassed edge will only evaporate. Therefore, long-distance tours are eliminated through the above pheromone regulation, and this regulation promotes early convergence for exploring tour. The best solution will be updated when the solution is newly found that has the shorter tour length than the current best solution. In tour exploration by using AS, successive procedures of traveling, pheromone regulation, and updating the best solution are repeated as mentioned above. The exploring simulation finishes when the exit condition is completed.


## 2.2. Rank-Based Ant System (ASrank)

In this section, we explain the rank-based ant system (ASrank) proposed by Bullnheimer et al. [8] as the improved algorithm from AS. In ASrank, the way of determining the probability for next destination selection from the present city is same as that in AS shown in equation (1). However, the way of pheromone regulation is different from AS. In pheromone regulation process of ASrank, all ant agents are ranked by sorting in ascending order of tour lengths. At that time, ant agents ranked between the top and the σ−1-th become elite ant agents who can contribute to pheromone deposition. In addition, ant agent who has found the best so-far solution until current exploring iteration has been identified as the virtual ant agent, and the virtual ant agent can also deposit extra pheromones. These superior ant agents and the virtual ant agent are deﬁned as the elite ant agents. The pheromone regulation by the elite ant agent is defined as follows:(3)τijt+1=1−ρτijt+Δτijt+Δτij∗t,where (4)Δτijt=∑μ=1σ−1Δτijμt,Δτijμt=σ−μQLμt,if theμ−th best ant travels on edgei,j,0,otherwise,Δτij∗t=σQL∗,if edgei,jis part of best solution found so far,0,otherwise,σ: number of elite ant agents, μ: ranking index, Δτijμ: increase of trail level on the edge i,j caused by the μ-th best ant agent, Lμ: tour length of the μ-th best ant agent, Δτij∗: increase of trail level on the edge i,j caused by the elite ant agents, L∗: tour length of best solution found so far, and Q: quantity of pheromone laid by an ant agent per tour.ASrank intends to ﬁnd a good solution eﬃciently by making a diﬀerence of pheromone strength between the paths included in short traveling tours and nonpopular paths.


## 2.3. Ant System Using Individual Memories (ASIM)

As mentioned previously, it can be considered that the diversity of solutions as well as the selection of solutions is an important factor in the solution system by swarm intelligence such as ACO. Hence, we would like to propose the ant system using individual memories (ASIM) as a new ACO algorithm considering the diversity in the artificial ant behavior. The heuristic information based on intercity distance and the pheromone information applied to intercity routes means common social information which every ant agent uses commonly. ASIM has a new aspect of using its own memory of each ant agent in addition to heuristic information based on intercity distance and pheromone information applied to intercity routes. In ASIM, each ant agent constructs a solution using both common social information and personal information which is its own memory. Specifically, as personal information, each ant agent can remember the personal best solution it has found so far. In the case of regulating the pheromone, the personal pheromone for each ant agent is applied additionally on the path including the best solution that each ant agent has found out in the past tours, apart from the pheromone as social information. In the natural world, it is known that when real ants discover a shorter path from the nest to the feeding site, they increase the amount of pheromone they apply along that route [13, 14]. On the one hand, in ASIM, when the best solution cannot be updated, each ant agent can regulate the personal pheromones on the path in the best solution that has been found so far. Here, note that each ant agent cannot recognize the personal pheromones applied by the other ant agents. The regulation of the personal pheromone is defined as follows:(5)ϕijkt+1=1−θϕijkt+Δϕijkt,where (6)Δϕijkt=ZCk∗,if edgei,jis part of antk's best solution found so far,0,otherwise,ϕijk: intensity of the ant agent k′s personal pheromone trail between cities i and j, θ: evaporation rate of the personal pheromone which is parameter to regulate ϕijk, Δϕijk: increase of trail level by ant agent k on edge i,j, Z: quantity of personal pheromone laid by an ant agent per tour, and Ck∗: tour length of the best solution of that ant agent k has ever found.In the pheromone regulation,Z means the parameter to adjust the amount of the personal pheromone applied by each ant agent. In addition, pheromones τijt are regulated based on equation (2) in the same way as AS. In ASIM, by including the personal pheromone ϕijk, the probability pijkt that city j is selected to be visited immediately after city i can be rewritten in a formula as follows:(7)pijkt=τijt+ϕijktαηijtβ∑l∈Nkτilt+ϕilktαηiltβ,ifj∈Nk,0,otherwise.Note that ASIM uses personal pheromonesϕijkt which is the personal information in addition to the common social information τijt and ηijt to select the next visited city. By using the personal information which each ant agent has individually, the diversity of tour in the ACO system can be maintained, and then it is expected that it is possible to search for a path while avoiding falling into a local solution. In addition, note that the computation complexity of the proposed algorithm ASIM is almost even to the existing algorithms, AS and ASrank, except for memorizing the information of the personal best solution in the past and the personal pheromone ϕijkt.


## 3. Results and Discussion

To evaluate the solving ability of each ACO algorithm, AS, ASrank, and ASIM have been applied to four TSP benchmarks [12]. The four TSP benchmarks as shown in Table 1 are taken from “TSPLIB” [12]. In all three ACO algorithms, the number of artificial ant agents has been set equal to the number of cities and one ant agent has been allocated in each city at the start of the tour. The parameters used in each ACO algorithm are shown in Table 2. The parameters used for AS and ASrank have been given the values that are generally considered to give a good solution for the respective algorithms. The values of parameters in ASIM have been set based on the results of preliminary experiments. As mentioned previously, Z is the parameter to adjust the amount of the personal pheromone applied by each ant agent. To adjust the amount of personal pheromone according to the scale of the problem, the value of Z has been set as the number of cities m in the considered TSP. Artiﬁcial ant agents in simulations have traveled 500 tours per one trial, and 20 trials have been conducted in each model and each TSP benchmark.Table 1
TSP datasets for the evaluation experiment.
TSPNumber of citiesbayg2929att4848eil5151berlin5252Table 2
Simulation condition and parameter settings.
ASASrankASIMα,β(1, 5)(1, 5)(1, 5)ρ0.50.50.5Other parameters—σ=6θ=0.1—Q=100Z=The number of antsAs mentioned previously, the diversity of solutions is an important factor in ACO. In ASIM, all ant agents use their own memory information in addition to common social information. ASIM intends to maintain the diversity of solutions through this feature. Figures1–3 illustrate an example of the transition of the best solution for each TSP benchmark by respective ACO algorithms. From Figure 1, it is found that the search of the best solution by using AS converges rapidly to a solution. This feature seems to have arisen since all ant agents search the pathway using common social information. Figure 2 shows that the search of the best solution by using ASrank converges more rapidly to a solution than by using AS. Since, in ASrank algorithm, only elite ant agents are allowed to update pheromone information, pheromones tend to concentrate to a specific path. It can be seen that this trend has derived the feature that the search of the best solution by using ASrank converges more rapidly to a solution than by using AS. On the other hand, in Figure 3 based on ASIM, it can be seen that the best solution has been updated even as the tour time progresses, and ASIM algorithm has increased the number of update times of the best solution compared with AS and ASrank algorithms. This feature has been caused from the ASIM algorithm with the diversity in the behavior of each ant. That is, since all ant agents use their own memories in addition to common social information, the ASIM algorithm maintains the diversity in the behavior of each ant. As a result, the ASIM algorithm maintains the diversity of solutions.Figure 1
Best solution update in AS. (a) bayg29. (b) att48. (c) eil51. (d) berlin52.
(a)(b)(c)(d)Figure 2
Best solution update in ASrank. (a) bayg29. (b) att48. (c) eil51. (d) berlin52.
(a)(b)(c)(d)Figure 3
Best solution update in ASIM. (a) bayg29. (b) att48. (c) eil51. (d) berlin52.
(a)(b)(c)(d)In addition, we compare the number of update times of the best solution in the three ACO algorithms. The average number of update times of the best solution updating in 20 trials of each ACO algorithm is shown in Table3. The fact that the number of update times of the best solution is large suggests that ACO algorithm constructs the solution while avoiding falling into a local solution. Table 3 shows that the ASIM algorithm has a larger number of update times of the best solution than the conventional AS and ASrank algorithms, and it is considered that ASIM has searched the optimal solution while avoiding falling into a local solution.Table 3
Average number of update times of the best solution in 20 trials.
TSPASIMASASrankbayg2912.09.36.3att4818.38.211.3eil5114.98.611.7berlin5220.79.111.3Furthermore, in order to confirm the solving ability of the proposed ASIM algorithm, we compare the solutions by ASIM to the solutions by the conventional methods AS and ASrank. For each TSP benchmark, the values of the best solution obtained in 20 trials are shown in Table 4. In addition, the average of the best solution obtained over 20 trials is shown in Table 5. From these results, it is found that for all TSP benchmarks, the proposed algorithm ASIM obtained superior solutions compared to the conventional methods AS and ASrank. This is considered to be due to the fact that ASIM maintains the diversity of behavior while searching for a pathway, thus producing a variety of solutions. As a result, it can be said that the solving ability of ASIM has been superior to those of AS and ASrank.Table 4
The best solution in 20 trials.
TSPASIMASASrankbayg29914091959233att48335493509034106eil51431443438berlin52754476647549Table 5
The average of the best solutions in 20 trials.
TSPASIMASASrankbayg29914692489349att48335563523434741eil51434451447berlin52754676817762As a consequence, from the comparisons about the number of update times of the best solution and the comparisons about the best solutions, it is seen that ASIM with the superior escape ability from the local solution has the superior solving ability compared to the conventional algorithms AS and ASrank.


## 4. Conclusions

In this paper, we have proposed the novel ACO algorithm ASIM using the individual personal information in addition to the common social information. Then, each ant agent constructs a solution based on the common social information and its own memory. In ASIM, each ant agent remembers the best solution it has followed and applies a personal pheromone regulation along the path. Then, the next city to be selected is based on the common social information and the personal pheromone information that is specific to each ant agent. The experimental results have shown that the proposed ACO algorithm ASIM is more effective than the conventional methods AS and ASrank in some TSP benchmarks. We consider that this is because the proposed ACO algorithm ASIM has been able to search the path while maintaining the diversity of the solutions by using different personal information for each ant agent. It can be concluded that ASIM is a more effective algorithm than conventional algorithms such as AS and ASrank because it can search for paths while maintaining the diversity of solutions through autonomous process of decision making.



---

*Source: 6610670-2021-01-08.xml*