# The Path Planning of Mobile Robots Based on an Improved Genetic Algorithm
## 3 Improved Genetic Algorithm
### Improved Mutation Strategy  
Traditional mutation methods typically rely on single random mutations, but due to the lack of directionality, they often result in difficulties in controlling the quality of the path and may even disrupt individuals with higher fitness, negatively affecting overall optimization performance. Therefore, this paper employs a dual-layer mutation approach. The first layer, random mutation, enhances population diversity, prevents premature convergence, and increases the likelihood of escaping local optima. The second layer, goal-oriented mutation, combines the current search direction to guide the solution towards better regions, thereby improving convergence speed and search efficiency. Furthermore, with the progress of iterations, the dynamic adjustment of layer selection probability enables the algorithm to focus on exploration in the early stages, avoiding premature convergence to local optima while concentrating efforts on searching for better solution regions in the later stages, thus enhancing the convergence speed. The flowchart of the improved mutation strategy is shown in Figure 4.  
As the iterations progress, the probability of random mutations should gradually reduce to avoid damaging excellent individuals and to accelerate convergence. Therefore, the layer selection probability b needs to be gradually adjusted, and its expression is given by  
\[\mathrm{B=b*cos((\frac{t-1}{T-1})*\frac{\pi}{2})} \tag{10}\]  
where B is the layer selection probability, b is the probability adjustment coefficient for selection, t is the current iteration number, and T is the maximum number of iterations.  
Figure 4: Mutation flowchart.  
Random mutation is performed by randomly selecting two nodes from the path as mutation nodes and connecting these two nodes using the multi-step method. In reference [26], a target-oriented mutation method is used, where a circular area is drawn with the parent node as the center and a radius 1.4 times the straight-line distance from the parent node to its previous and next nodes. Nodes within the circle are selected as candidate mutation nodes. This results in the traversal of too many mutation nodes, consuming a large amount of hardware resources. To address this, the method in this paper is optimized. First, the two nodes before and after the parent node are connected to form a straight line L1. Then, a perpendicular line L2 is drawn from the parent node to line L1, denoted as L2. Then, the symmetric line L3 of L2 with respect to line L1 is constructed, denoted as L3. Using the improved Bresenham algorithm, we obtain all the grid cells traversed by the straight lines L2 and L3 and designate them as candidate mutation nodes. Then, we use the multi-step method to make the two nodes before and after the parent node pass through the candidate mutation nodes. The probability of selecting each candidate mutation node is given by  
\[P_{i}=\frac{f_{i}}{\sum\limits_{j=i}^{n}f_{j}} \tag{11}\]  
where \(P_{i}\) is the probability of selecting the i-th candidate mutation node and \(f_{i}\) is the fitness value of the path formed by the parent node's adjacent nodes passing through the i-th candidate mutation node. As shown in Figure 5, the black line represents the parental path, with the deep-blue grid P1 indicating the parent node. The deep-blue grids P2 and P3 correspond to the previous and next points relative to the parent node, respectively. The yellow solid line represents line L1, while the green dashed lines represent lines L2 and L3. The light-blue grids P4-P7 represent the candidate mutation nodes.