1. Introduction

Researchers have proposed the Ant Colony Algorithm (ACA) by exploring the process and behavior of ant foraging. Scholars have found that ants will release a volatile pheromone on the path they pass through during the process of going out. And different ant individuals can perceive the existence of pheromones and decide their own moving routes according to the concentration of pheromones. In the end, most ants will follow the shortest path.

The Ant Colony Algorithm (ACA) is an optimization bionic algorithm inspired by these behaviors. It has good robustness and the ability to find better solutions, and it has strong positive feedback characteristics. ACA is a typical parallel algorithm, and it can be applied to any combinatorial optimization problem like the traveling salesman problem, network routing problem, or sequencing problem. The algorithm has achieved fruitful research results in many fields. However, it also has some drawbacks. At the beginning of the search, this algorithm will increase the blindness of the search and the iteration time. What’s more, it is easy to fall into the local optimal solution. Therefore, many improved ACAs have appeared one after another.

The paper will begin with the fundamental concept of ACA and then combine some typical examples of improved ACAs to analyze the current state of ACAs in application. Each scholar's improvement focus is different. After careful consideration and summary, the advantages and disadvantages of today's ACA can be found, and the future can be expected.

2. Ant colony algorithm

The ACA was first proposed by Marco Dorigo in 1992. The algorithm was inspired by the behavior of ants in finding their way when they were looking for food. It is essentially a heuristic global optimization algorithm. This algorithm has many excellent characteristics, and once it was proposed, it quickly attracted the extensive attention of researchers.

Here is a basic model of the ACA by using an example of the Traveling Salesman Problem (TSP): The number of artificial ants is \( m \) , and the distance between city \( i \) and city \( j \) is \( {d_{ij}} \) ( \( i,j=1,2,……,n \) ). \( {b_{i}}(t) \) is the number of ants in city \( i \) at time \( t \) ( \( m=\sum _{i=1}^{n}{b_{i}}(t) \) ). \( {τ_{ij}}(t) \) represents the residual information between city \( i \) and city \( j \) at time \( t \) ( \( {τ_{ij}}(0)=C \) , \( C \) is constant). Ant \( k \) ( \( k=1,2,……,m \) ) chooses its path during movement based on the pheromones along each path. And the probability rule for this choice is as follows:

\( p_{ij}^{k}=\begin{cases} \begin{array}{c} \frac{τ_{ij}^{a}(t)η_{ij}^{β}(t)}{\sum _{s∈{allowed_{k}}}τ_{is}^{a}(t)η_{s}^{β}(t)}, j∈{allowed_{k}} \\ 0, otherwise \end{array} \end{cases}\ \ \ (1) \)

\( p_{ij}^{k} \) is the probability of the ant \( k \) moving from position \( i \) to the position \( j \) at time \( t \) . And \( allowe{d_{k}} \) which is a set represents the cities where ant \( k \) has not yet walked. What’s more, \( {η_{ij}} \) , the heuristic factor, is the expected degree from position \( i \) to the position \( j \) ( \( {η_{ij}}=1/{d_{ij}} \) ). \( α \) , \( β \) represent the relative importance of residual information and expectation.

And here is the formula for pheromone renewal:

\( {τ_{ij}}(t+n)=ρ∙{τ_{ij}}(t)+∆{τ_{ij}}(t)\ \ \ (2) \)

\( ∆{τ_{ij}}=\sum _{k=1}^{m}∆τ_{ij}^{k}\ \ \ (3) \)

In this formula, \( ρ \) represents the degree of pheromone disappearance. \( Δτ_{ij}^{k} \) represents the amount of information that the \( k \) th ant left on path ( \( i \) , \( j \) ) during the cycle. And \( Δ{τ_{ij}} \) represents the amount information that all the ants left on this path.

This is the definition of \( Δτ_{ij}^{k} \) :

\( ∆τ_{ij}^{k}=\begin{cases} \begin{array}{c} \frac{Q}{{L_{k}}}, if the kth ant goes through the path(i,j) in this cycle \\ 0, otherwise \end{array} \end{cases}\ \ \ (4) \)

According to the formula, \( {L_{k}} \) means the total length of the path traveled by the \( k \) th ant in this cycle.

This model updates the pheromones along the path by using the overall information after ants complete a cycle. In general, this method has good performance in solving TSP.

3. Solving practical problems by using ant colony

3.1. Path planning problem

With ACA, it can solve many problems. Path planning is one of them, and it is also an unavoidable problem in daily life. There are many kinds of path planning problems, including vehicle routing problem (VRP), urban road network planning, mobile robot’s path planning and so on. VRP is one of the most important applications. VRP is about the distribution center according to the requirements of different distribution destinations to arrange vehicles to transport orderly. It requires the distribution center to find the optimal scheduling scheme that satisfies the constraints. And other path problems also have strong practicality.

Zhang et al. (2022) considered the barrier and the scale of the map, so they improved the two-layer ACA by dividing the ant colony into the guidance layer and the ordinary layer [1]. According to the guidance layer heuristic function, it can be found that the improved algorithm can avoid the deadlock effectively. And the ordinary layer function reduces the case of ant colony entering a locally optimal solution. Compared with the basic ACA, their algorithm can speed up the operation efficiency under certain conditions.

Moreover, Li et al. (2021) improved the ACA by changing the path searching strategy according to different searching status [2]. The algorithm will judge the status of the search first, and then adjust the heuristic function by itself so that it can meet the needs of users. As a result, this improved algorithm design has better accuracy and practicability.

In order to improve the solving speed and degree of accuracy of the algorithm, Wan et al. (2019) added the demand factor and the time window span factor to the heuristic value, and reconstructed the state transition rule [3]. In addition, the pheromone update strategy avoids falling into the local optimum to some extent. Therefore, compared with the basic ACA, this improvement meets the requirements for both the solving speed and the degree of accuracy. Thinking from another angle, Liu et al. (2021) modeled the adjustment problem in the temporal dimension as a path search problem in the three-dimension space and constructed the solution space in order to obtain the optimal solution in scheduling [4]. Then they adjusted the ant colony optimization algorithm, including heuristic function, pheromone mechanism, and so on. After adjusting the parameters adaptively and conducting comparative simulation, it can be found that convergence speed and searching performance are improved. This kind of algorithm also has its own unique superior. What’s more, to make the results more stable, Yi et al. (2021) considered the multiple inspirational factors [5]. They established a distance correction function, a security function, and a smoothness function so that they forms a closed loop feedback. And they also set upper and lower limits on volatilization factors and pheromones. The scholars’ improved algorithm makes the path length shorter and the number of iterations reduced.

Liu et al. (2022) introduced the conservation matrix and used piecewise functions to improve the performance of ACA [6]. They reasonably set the value of volatilization factor, and they set different values in different iteration periods. At the same time, the authors used the two elements optimization method to make it easier to find the global optimal solution. According to their simulation data, this algorithm is superior to the basic ACA in all scales. And it really has a stronger optimization ability. It's a potential improved algorithm.

In addition, a lot of improved ACAs for path planning problem are constantly proposed. They all improve the performance of the algorithm to a certain extent. Although these improved algorithms still have some limitations, they do have strong advantages in some aspects and have their own unique features.

3.2. Assignment problem

ACA is also widely used in assignment problem. It refers to some people are assigned to complete a certain number of tasks. However, each person’s expertise is different, resulting in different tasks and completion efficiency. And in order to maximum the overall completion efficiency, it is necessary to assign different people to different tasks.

Wang et al. (2012) reconstructed the analytic diagram of the static solution, and strengthened the memory function of ants and gave them the ability to choose paths [7]. In addition, they studied the rule of this improved ACA for task assignment and scheduling optimization through simulation. The results show that this algorithm overcomes the shortcomings of the ACA to a certain extent and effectively solves the assignment problem.

For the problem of the quadratic assignment problem, Yin and Liu (2005) mixed the local optimization algorithm with the ACA, and improved the solution of each generation due to improve the quality of solution [8]. As a result, this kind of algorithm finally optimizes the local search ability of ACA. The improvement measures are effective.

In response to the assignment problem in the emergency repair of war damaged equipment, Cai et al. (2012) proposed a targeted approach based on the characteristics of equipment support and the actual situation of emergency repair of battle-damaged equipment in the battle [9], as well as the issue of prioritizing the distinction between urgency and unbalances distribution. Ideas and algorithms that enable allocation problems to be solved faster and more accurately.

Zhang et al. (2012) set about solving the problem of aircraft assignment problem (AAP) [10]. The solution of aircraft assignment problem (AAP) facilitates safe and punctual operation of the flight so that the economic benefits of airlines can be maximized. The authors transformed this problem into a vehicle routing problem and proposed the concept of virtual flight string. Based on these preparations, a mixed integer programming model is established. As a result, this algorithm reduces the connection time between flight strings effectively and improved the aircraft utilization.

Although the assignment problem is not as large as the path planning problem, it also has many classification methods and extension models. As ACA has strong global search ability, it has better ability to find better solutions so that it is really suitable for solving such assignment problems to some degree. And the ACA has also achieved a lot of research results on the extension of assignment problem.

3.3. Routing problem

With the development of science and technology, and the increasing frequency of people surfing the Internet, the network structure becomes more and more complex, and the management becomes more and more difficult. Therefore, many scholars have done a lot of research on the routing strategy of communication networks and have achieved some results. In order to meet the development needs of network routing, ACA with strong advantages is used to solve this problem.

Liu et al. (2022) made path planning according to the dynamic setting of routing frequency and mobile rules [11]. They reset the obstacle avoidance rules to reduce the distance of the communication path. What’s more, they increased the sensitivity of the route to the identification of key nodes. And the improvement points reduce the range of optimal paths. In terms of results, this optimization scheme makes routing have higher efficiency in communication transmission. Meanwhile, the transmission path is more stable and the speed is also improved.

Moreover, Shang et al. (2021) improved the heuristic strategy and global and local update rules [12]. Then they considered the problem of flow balance to avoid link congestion. The authors established a routing model with constraints such as delay and number of paths, and used an improved ACA for path selection. The improved algorithm has a more uniform load distribution. And the delay and packet loss rate are also relatively reduced.

To optimize speed and improve the success rate of the network, Wang (2020) made full use of the parallel and distributed advantages of ACA to improve it [13]. First of all, it is necessary to improve the state transition rules to realize rapid acquisition of route transfer mode with high pheromone intensity. After that, the pheromone updating rules need to be improved. Therefore, the convergence speed of the algorithm is relatively improved.

The algorithm of routing problem has been constantly improved. According to different routing problems, researchers have proposed many effective schemes from improving pheromone adjustment mechanism and integrating with other optimization algorithms. In short, the application of ACA in routing problems has also made great progress.

4. Conclusion

Many scholars have made unremitting efforts in improving the ACA, which has made it improve in all aspects of the algorithm, including solving the deadlock problem of ants, improving the pheromone updating strategy, improving the heuristic function and so on. These methods have significantly improved the efficiency of the algorithm to a certain extent.

While introducing the ACA, this paper also summarizes and analyzes the research status of some common fields of ACA by combining the improved algorithm model of many scholars. ACA is a new bionic optimization algorithm. As a new bionic optimization algorithm, compared with other algorithms, the research time of ACA is not so long. Although ACA has developed rapidly in recent years, there are still many aspects to be improved, which need to be strengthened and further studied in the future.