# Path Planning for Conformal Antenna Surface Detection Based on Improved Genetic Algorithm
## 3 Improved Genetic Algorithm Combining the Historical Optimal Population  
### Encoding and Population Initialization Methods  
The first step of the genetic algorithm is encoding, which involves determining how to express the solution to a problem in the form of individuals. The encoding method generally needs to satisfy the principles of completeness, soundness, and non-redundancy. For TSPs, the general encoding methods include neighbor representation, sequence representation, and path representation. Among these, path representation is simple and clear. That is, if there are nine cities, a feasible path can be expressed as (5 1 6 8 9 4 7 2 3). When the genetic algorithm solves the TSP, it generally adopts the method of random initialization or nearest-neighbor initialization. The random initialization method randomly selects each city to ensure the diversity of the initial population, but the quality of the initial population is poor. The nearest-neighbor initialization method, also known as the greedy initialization method, uses the method of randomly selecting the starting point and finding the nearest point as the next point to construct the path, which ensures the quality of the initial population. When the genetic algorithm solves the TSP, if the population size is about twice the size of the cities, better results can be obtained [19]. However, the nearest-neighbor initialization method must have duplicate individuals in the population, which reduces the diversity of the population. Studies have shown that for medium- and small-scale TSPs, most of the points in the optimal path are connected to the four nearest points [20]. Moreover, for a certain type of conformal antenna, the number of feature points on it will not exceed 300, which is a medium- and small-scale problem. Therefore, a probability-based four-nearest-neighbor method is proposed for initialization, and the specific steps for randomly forming a path are as follows:  
Step 1. Randomly select a point from the city set as the starting point;  
Step 2. Record the four points closest to the point, set the probability of the four points being selected as 0.05, 0.1, 0.15, and 0.7 from far to near, and select the next passing point according to the cumulative probability;  
Step 3. Determine whether a complete path has been formed; if so, complete the initialization of the individual, otherwise, go to Step 2;  
Step 4. Determine whether the population has been generated; if so, end the algorithm, otherwise, go to Step 1.  
Take the bayg29 problem in TSPLIB as an example. Combined with Formula (2) [21], the population diversity and average path length of the initial population formed by the above three methods were compared, and the results are shown in Table 1.  
\[D=\sqrt{\frac{1}{N}\sum_{q=1}^{N}\left(f_{q}-\frac{1}{N}\sum_{l=1}^{N}f_{l} \right)^{2}} \tag{2}\]  
where \(D\) represents the diversity of the population, and the larger the value, the better the diversity of the population; \(f_{q}\) represents the fitness of the individual \(q\); and the total length of the path is used as the fitness in this paper.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  
It can be seen from Table 1 that compared with random initialization, both the probability-based four-nearest-neighbor initialization and the nearest-neighbor initialization greatly reduced the path length. The probability-based four-nearest-neighbor initialization was only at most 26% longer than the nearest neighbor initialization, while the diversity increased at most by 1850%. Therefore, the probability-based four-nearest-neighbor initialization can be used as a better initialization method to maintain the diversity of the population under the premise of generating better paths.