With the rapid development of social economy and science and technology, fire hazards in all walks of life emerge in an endless stream, and the difficulty of fire prevention and control is gradually increasing. Aiming at the problem of fire patrol path planning, based on the classic ant colony algorithm, an adaptive improved ant colony algorithm is proposed to solve the problems of slow convergence and low efficiency of the classical ant colony algorithm. Matlab simulation experiments show that the ant colony algorithm can improve the efficiency of the algorithm while ensuring the found of the optimal path after adaptively changing the pheromone volatile factor and differentially processing the pheromone constant.
1. Introduction1
The problem of fire inspection path planning can be described as: a fire truck starts from the fire station to check whether the fire hydrants and fire extinguishers in each building are in normal operation. After completing the inspection task, it returns to the fire station. The distance between the fire station and each inspection target is known. And formulating a reasonable inspection route can enable the inspectors to complete the task smoothly and quickly. The fire inspection path planning problem is described as: an undirected graph G (V, E), where V is the set of all inspection targets, and E is the set of edges between the targets.
Ant colony algorithm is a probabilistic algorithm used to find optimal paths. Marco Dorigo proposed the algorithm in his doctoral dissertation in 1992 and was inspired by the behavior of ants to find paths in their search for food[6]. It was originally designed to solve the traveling salesman problem and was later applied to various aspects of the optimization problem domain[7].
The basic principle of the ant algorithm is that in the process of foraging, an ant can release a substance called " pheromone " on the path of its travels. And the pheromone itself will continue to volatilize over time. In the process of searching for food, ants choose the direction of movement according to the concentration of pheromone and finally reach the food site. The core functions of the traditional ant colony algorithm are the state transition probability function and pheromone update function. The state transition probability indicates that ants always tend to move in the direction of high pheromone concentration when choosing a path. The pheromone update can be understood as the pheromone concentration on the path from i to j at a certain time is equal to the remaining pheromone concentration after volatilization at the previous time, plus the sum of the pheromone concentrations released by all ants on this path in the previous period.
•
State transition probability formula
(
() 0 ( ) ∗ ()
∈ other
Among them: 1
have not been visited.
•
Pheromone update formula
is the probability of the kth ant from i to j at time t; α is the pheromone factor; β the heuristic function factor; (t) is the pheromone concentration from i to j at time t; () = is the reciprocal of the path distance between two points i, j; is the set of nodes that ( + 1 ) = ( ) ∗ (1 − ) + ∆ , 0 < < 1 from i to j at time t; ∆ from i to j. The update method is as follows.
Among them: ρ is the pheromone volatilization factor; ( ) is the pheromone concentration is the pheromone increment, that is, the sum of the pheromone left by m ants
∆ Δτ ikj = LK = ∆ Q , (i, j) ∈ω
k 0,
other Among them: Q is the pheromone constant; L k is the total path length traversed by the kth ant; ω k is the path traveled by the kth ant in this iteration.
At present, the traditional ant colony algorithm exists some problems such as slow convergence speed and easy falling into local optimum. The methods of algorithm improvement are mainly improved from the aspects of the structure of the algorithm, the optimization of the parameters of the algorithm, the way of pheromone initialization, and the rules of pheromone update. For example, Chen et al[8] increased the randomness of the search by integrating the chaotic disturbance factor in the ant colony algorithm; Yuan et al[9] combined simulated annealing algorithm and traditional ant colony algorithm for path planning; Xu et al[10] improved the traditional ant colony algorithm by changing the state transition probability and path selection strategy. • Improve how pheromones are updated
Pheromone renewal is a process of simulating the accumulation and volatilization of ant pheromones over time in nature. The pheromone update rule of the traditional ant colony algorithm is aimed at the ants reaching the destination, and the subsequent ants are easily misled by the ants on the worst path releasing pheromone, which affects the final path planning effect. To better distinguish the pheromone concentration on the path, the improvement idea based on the traditional ant colony algorithm in this paper is to increase the pheromone on the optimal path and weaken the pheromone on the worst path in each iteration, so that the ants can search for the best path. The concentration of pheromone released by the kth ant on each path is equal. By comparing the total path length traveled by the kth ant with the optimal path length in each generation, different pheromone enhancement coefficients are used to distinguish the pheromone constant Q, to improve the optimality of path planning. τ ij (t +1) =τ ij (t) * (1− p) + Δ*τ ij (5) (6) (7) (8) （9） The coefficient ε is:
m Δ*τ ij = Δ*τ k
k =1 ij Q Δ*τ k (t) = ε i L−k ，If ant k passes i, j ij 0，other
ε 1，Lk ≤ Lbs ε i ε ，Lk > Lbs
2
Among them: ρ is the pheromone volatilization factor; ε i is the pheromone enhancement coefficient; Lk is the total path length traversed by the kth ant.
• Adaptive Volatility Coefficient
The pheromone volatilization factor reflects the disappearance level of pheromone, and conversely reflects the retention level of pheromone. The value of the pheromone volatilization factor affects the global search ability and convergence speed of the algorithm. If it is too large, the pheromone volatilizes too fast, which will easily cause the optimal path to be excluded. If it is too small, the difference in pheromone content on each path will be small. The pheromone volatility factor of the traditional ant colony algorithm is a constant, which is not conducive to the search of the optimal value. Therefore, by adaptively changing the pheromone volatilization factor, if the current optimal path distance is less than the last one, more pheromone needs to be left for the next generation of ants, and if it is greater than the last one, more dilution is required to avoid subsequent ants repeat the same mistakes. ρ t+1 = ρ t , Lmin (t +1) ≤ Lm（int） ρ t+1 = 0.75ρ t , Lmin (t +1) > Lm（int）
Among them: Lmin (t) is the shortest path at time t; Lmin (t + 1) is the shortest path at time t+1.
In this paper, the eil51 instance in the TSP international general TSPLIB data set is used to simulate the fire inspection path planning. Dataset source: http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsp/eil51.tsp. The parameter values of the ant colony algorithm are different, and the efficiency of the algorithm is also different. Therefore, after many tests, the appropriate parameter values are determined as shown in Table 1 below.
Table 1. Algorithm parameter settings parameter name number of ants heuristic value 150 3 pheromone factor
pheromone volatile factor
The comparison of the convergence process trajectories between the traditional ant colony algorithm and the improved ant colony algorithm is shown in Figure 1; The worst path comparison is shown in Figure 2; after 10 repeated experiments, the experimental results of the algorithm are shown in Table 2.
(a) Figure 2: Comparison of the shortest path between the two algorithms (b)
Figure 2 shows that the relationship between the optimal path length and iterations of traditional ant colony algorithm and improved ant colony algorithm, respectively. It can be seen that the lowest point of the iterative curve of the improved ant colony algorithm is below the lowest point of the iterative curve of the traditional ant colony algorithm, which indicates that the optimal path length found by the improved ant colony algorithm is better than the optimal path found by the traditional ant colony algorithm. After 10 repeated experiments, it can be seen from Table 2 that the improved ant colony algorithm is slightly better than the traditional algorithm in terms of average path length and average optimization time, and the optimal path searched is also the shortest. Therefore, the improved ant colony algorithm is more stable than the traditional algorithm, which can help fire inspection vehicles quickly find the optimal route and improve work efficiency.
In this paper, the pheromone constant Q is differentiated based on the traditional ant colony algorithm, which is very helpful for distinguishing the pheromone concentration on the path. And by adjusting the pheromone volatile factor adaptively, the blindness caused by the influence of pheromone is avoided. Applying the improved ant colony algorithm to the fire inspection path planning can find the optimal inspection path quickly and improve the inspection work efficiency. Although the improved ant colony algorithm optimizes the pheromone updating method, it does not consider the influence of state transition probability. The follow-up work is to improve the state transition probability according to weather conditions and road congestion so that the inspection path planning method is more efficient and intelligent.
4. References