# 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.2 Optimization Procedure for Cutting Paths  
Trajectory point optimization is essentially the solution to the bi-objective traveling salesman problem (TSP). The bi-objective TSP is a combinatorial optimization challenge aiming to balance conflicting objectives such as minimizing travel distance and maximizing customer satisfaction. Solution methods include the weighted sum method, \(\varepsilon\)-constraint method, and multi-objective evolutionary algorithms [23]. NSGA-II, an improved genetic algorithm, excels in multi-objective optimization by efficiently managing multiple objectives through rapid non-dominated sorting, crowding distance assessment, and elitist selection, enhancing solution set convergence and diversity. Adaptive improvements to NSGA-II are made to address the cutting trajectory optimization problem. In the NSGA-II algorithm, setting the sharing radius relies on experience, which is a limitation. To address this, the concept of crowding distance is introduced. As illustrated in Figure 6, points marked within solid circles belong to the same non-dominated front. Crowding distance reflects the density of individuals in space, defined as the perimeter of the quadrilateral formed by adjacent solutions \(i-1\) and \(i+1\). A larger crowding distance indicates a sparser area around the solution, facilitating the maintenance of population diversity. The NSGA-II algorithm incorporates an elite strategy to retain superior individuals and eliminate inferior ones, expanding the selection scope for the next generation by merging parental and offspring individuals into a new population, as illustrated in Figure 7.  
The direct application of the NSGA-II algorithm falls short in addressing the cutting trajectory problem. Hence, an improved NSGA-II algorithm flowchart, specifically designed for the optimization of cutting trajectories, is presented in Figure 8.  
Figure 6: Crowding distance calculation. The specific procedure is as follows:  
(1) Obtain Path Points and Design Adjacency Matrix. The process begins by obtaining the feasible cutting space for the roadheader under its current pose. The path points are then numbered, and an adjacency constraint model is established in the joint space. The adjacency matrix is computed based on these constraints, which governs the connections between path points. Figure 8: Flowchart of improved NSGA-II algorithm with adjacency constraints. Figure 7: Elite strategy execution steps. (2) Initialize Population. The population is initialized, with the first generation (Gen = 1) being created. However, since the standard NSGA-II algorithm initializes the population randomly, it does not fully respect the adjacency constraints of the roadheader. Therefore, adaptive improvements are introduced to ensure the population initialization is feasible with respect to the constraints. (3) Generate First Generation of Offspring Population. If the first generation of offspring has already been generated, the algorithm proceeds by setting Gen = 2. Otherwise, non-dominated sorting, selection, crossover, and mutation are performed on the initial population to generate the first generation of offspring. The crossover and mutation processes are modified to adapt to the kinematic constraints of the roadheader. (4) Merge Parent and Offspring Populations. The parent and offspring populations are merged into a new population. If a new parent population has not been generated, the algorithm calculates the objective functions of the individuals in the new population. Then, it performs rapid non-dominated sorting, crowding distance calculation, and applies an elite strategy to generate the new parent population. (5) Generate New Offspring Population. Once a new parent population is generated, selection, crossover, and mutation operations are performed on the parent population to generate the offspring. This process is again constrained by the adjacency model to maintain feasibility for the roadheader's movement. (6) Check Evolution Generation Limit.