# Laser Ablation Manipulator Coverage Path Planning Method Based on an Improved Ant Colony Algorithm
## 4 Improved Ant Colony Algorithm
### Improved Max-Min Ant System  
After the ant colony algorithm was proposed, many scholars studied measures for improving the ant colony algorithm. In comparison with the ant colony algorithm, the performance of the max-min ant system (MMAS) proposed by German scholar [PERSON] and others has been significantly improved [44]. The main improvement made to the MMAS algorithm is to allow only the best individual in each generation to update the pheromone while limiting the pheromone in a certain range. In solving discrete problems, one improvement measure is to combine the ant colony algorithm with other algorithms [45]. However, [PERSON] et al. [46] suggested that the development of a hybrid metaheuristic is advised only when excellent solutions cannot be obtained by any complete method in a feasible time frame. Other measures mainly focus on improving the global search ability of the algorithm to avoid stagnation behaviour or accelerating the convergence rate, for instance, by dynamically varying the algorithm parameters, and improving the pheromone update strategy, or concentration [47]. Here, an improved max-min ant system (IMMAS) based on the MMAS algorithm is proposed to improve the global search ability of the algorithm. The IMMAS algorithm includes the following improvements. In the IMMAS algorithm, to avoid stagnation behaviour and improve the global search ability of the algorithm, the transition probability \(P_{ij}^{k}(t)\) is calculated according to Equations (21)-(24). \[\theta_{ij}^{k}(t)=\left\{ \begin{array}{ll}\frac{[\tau_{ij}(t)^{a}\cdot[\eta _{ij}]]^{g}}{\sum_{s\in\textit{allocual}_{k}}[\tau_{is}(t)]^{a}\cdot[\eta_{is }]^{g}},&\text{if }j\in\textit{allowed}_{k}\\ 0,&\textit{otherwise}\end{array} \right. \tag{21}\]  
where \(\textit{allowed}_{k}\) is a point set of allowed from point \(i\), \(\tau_{ij}\) is the pheromone between point \(i\) and point \(j\), and \(\eta_{ij}\) is the visibility, which is generally \(\frac{1}{p}\), \(F\) following Equation (12). If \(\theta_{ij}^{k}(t)\geq\gamma\cdot\theta_{max}\), then  
\[P_{ij}^{k}(t)=\left\{ \begin{array}{ll}1,&(1-\mu)\cdot(1-\theta_{k}^{ij}(t)) +\mu\leq p_{0}\\ \theta_{ij}^{k}(t),&(1-\mu)\cdot(1-\theta_{ij}^{k}(t))\leq p_{0}<(1-\mu) \cdot(1-\theta_{ij}^{k}(t))+\mu\\ 0,&p_{0}<(1-\mu)\cdot(1-\theta_{ij}^{k}(t))\end{array} \right. \tag{22}\]  
If \(\theta_{ij}^{k}(t)<\gamma\cdot\theta_{max}\), then  
\[P_{ij}^{k}(t)=\left\{ \begin{array}{ll}\gamma\cdot\theta_{max}&(1-\mu)\cdot (1-\theta_{k}^{ij}(t))+\mu\leq p_{0}\\ \theta_{ij}^{k}(t),&(1-\mu)\cdot(1-\theta_{ij}^{k}(t))\leq p_{0}<(1-\mu) \cdot(1-\theta_{ij}^{k}(t))+\mu\\ \sigma,&p_{0}<(1-\mu)\cdot(1-\theta_{ij}^{k}(t))\end{array} \right. \tag{23}\]  
where \(p_{0}\) is a random number, \(p_{0}\in[0,1]\), \(\gamma\) is the critical factor, \(\gamma\in(0,1)\), \(\mu\) is the probability factor, \(\mu\in(0,1)\), and \(\sigma\) follows Equation (24). \[\sigma=\frac{(1-\gamma\cdot\theta_{max})\cdot\theta_{ij}^{k}(t)}{(1-\theta_{ij }^{k}(t))} \tag{24}\]  
The practical significance of the above rule is that, after the transition probability is calculated, under the premise that the mathematical expectation of the transition probability value is unchanged, the calculated transition probability randomly increases, decreases, or is unchanged. The increase in randomness helps the algorithm emerge from the local optimal solution. In the IMMAS algorithm, the updating pheromone rule follows Equations (18), (25), and (26)  
\[\Delta\tau_{ij}^{k}(t)=\left\{ \begin{array}{cc}\frac{Q}{L_{k}}\cdot\varepsilon,& \text{if $k_{th}$ ant select $(i,j)$ in its tour}\\ 0&\text{otherwise}\end{array} \right. \tag{25}\]  
\[\varepsilon=\frac{L_{ave}-L_{k}}{L_{wor}-L_{ave}} \tag{26}\]  
where \(L_{ave}\) is the average optimisation value of all ants in one iteration, \(L_{wor}\) is the optimisation value of the worst ant in one iteration, and \(L_{k}\) is the \(k\)-th ant's optimisation value.