# An Improved NSGA-II-Based Method for Cutting Trajectory Planning of Boom-Type Roadheader
## 2 Methodology
### Optimizing Cutting Paths Using Improved NSGA-II
#### 2.3.4 Application of Improved NSGA-II to Path Optimization  
In this paper, we present the application of depth-first search (DFS) with adjacency constraints for initialization, crossover, and mutation operations in pathfinding. DFS is initiated from the starting path point and sequentially searches for adjacent, unvisited nodes until all potential paths are identified. However, its efficiency diminishes in the context of higher-dimensional path sequences. To mitigate this, we introduce pruning operations based on the unique constraint that each cutting trajectory point can only be traversed once. The pruning procedure entails updating the adjacency list by removing visited nodes, identifying connected components among unvisited nodes, and assessing the size of each component. If a component's size is smaller than the remaining nodes, it suggests fragmentation of the path, preventing the formation of a closed loop due to adjacency constraints. Consequently, the current node is bypassed for backtracking purposes. Additionally, this study introduces a DFS algorithm integrated with pruning optimization to refine the initialization and mutation processes, thereby ensuring path adjacency and maintaining high search efficiency.  
(1) Population Initialization with Adjacency Constraints  
The NSGA-II algorithm initializes its population using a random generation method, which introduces uncertainty. This randomness results in spatially uneven point sets, failing to guarantee adjacency constraints during each initialization. Given a population size m, NSGA- II randomly generates m path points, exhibiting randomness and uncertainty. While the path length is ensured, incomplete traversal and redundant traversal issues may arise, as illustrated in Figure 11. To address this, a depth-first search (DFS) algorithm with pruning optimization is employed for population initialization. A schematic diagram of one path after optimization is presented, demonstrating that the initialized path satisfies the predefined adjacency constraints without redundant traversal.  
Figure 10: Representation of path points on grid and generation of adjacency list and matrix.  
(2) Mutation with Adjacency Constraints  
In the mutation operation of NSGA-II, individuals from the current population are selected for mutation, with one or more genes on their chromosomes randomly chosen as mutation targets. The polynomial mutation operator is applied to these genes, resulting in mutated gene values that replace the corresponding values in the original individuals, thereby generating new mutated individuals. However, when performing mutation with adjacency constraints, it is necessary to ensure that the subsequent path points after the mutation point also satisfy adjacency.  
Given the limitations of NSGA-II in crossover and mutation handling, further adjacency processing is required for the crossover gene segments or mutated gene sequences after these operations. Therefore, we combine these two processing steps. Although this approach sacrifices some population diversity, it significantly improves the efficiency of generating offspring gene sequences due to the adjacency constraints.