## 4 Non-Dominant Sorting Adaptive Memetic Algorithm (NSAM)  
### Basic Structure of the NSAM  
[PERSON] [26] defined the Memetic Algorithm (MA) in 1989, which was initially improved on the basis of Genetic Algorithm (GA). He combined the GA with local search to solve the Travelling Salesman Problem (TSP). In recent years, with the successful and high-performance application of the two-layer search architecture of memetic algorithm on solving complex real-world problems, the concept of memetic algorithm has attracted widespread attention from the academic community [27]. Memetic algorithms are no longer a specific algorithm, but generally refer to a class of population-based heuristics. Algorithms of this type combine the evolution algorithm with the local search algorithm, so that it cannot only retain the advantages of the evolutionary algorithm based on population evolution during operation, but also has the excellent local optimization ability of the local search algorithm. The NSAM algorithm is a two-layer modal approach comprised the Non-dominated Sorting Genetic Algorithm II (NSGA-II) and Adaptive Large Neighborhood Search (ALNS). The two-layer optimization approach not only allows the population to quickly reach the Pareto frontier using an evolutionary mechanism, but also quickly reproduces progeny solutions by improving the quality of the searched solutions using the ALNS. Thus, the generation of local optimal solutions is avoided. The NSGA [28] is a genetic algorithm based on Pareto optimal concept proposed by [PERSON] et al. in 1995. [PERSON] [29] proposed the NSGA-II algorithm on the basis of this algorithm. The algorithm greatly reduces the computation time by using fast non-dominated sorting (the elite strategy) to ensure the excellent individuals can have a higher probability of being retained; the crowding degree method replaces the fitness sharing strategy to ensure individual diversity in the population. This makes the NSGA-II algorithm more suitable for solving multi-objective optimization problems. The ALNS is a heuristic local search method proposed by [PERSON] [30] in 2007. On the basis of the neighbourhood search, this method adds the measurement of operator effect. By means of roulette, the better operator of destroy and repair will be automatically selected to optimize the solution. This two-layer architecture plays a significant role in solving highly complex and large-scale constellation reconstruction problems. The flow chart of the NSAM is shown in Figure 3. The algorithm's code framework is shown in Algorithm 1. ``` Input: target trajectory, satellite parameters, initial population size (IPS), offspring population size (OPS), and maximum iterations (MaxIter) Output: elitist solutions (ES)
1 Repeat: generate initial solution
2 According to the input elements to generate initial solutions
3 End: until parent population size = IPS + OPS
4 The solutions were optimized by selection, crossover, and mutation in \(NSGA-II\)
5 Select and update elite solutions with elite strategies in \(NSGA-II\)
6 ALNS: improve the solutions
7 Select destroy operators and repair operators according to the adaptive layer
8 Based on the current elitist solutions, use operators to update populations
9 Combine the offspring solutions and the current elitist solutions
10 Update the elite solutions and update the scores and weights of operators in the adaptive layer
11 End until iteration achieves MaxIter
12 Output

### Design of Destroy Operator and Repair Operator

Destroy operators and repair operators are used to optimize the generated elite population. The destroy operator changes the population composition by deleting some target solutions, while the repair operator takes some solutions from the non-elite solutions to repair the parent solutions to generate a new population. In this paper, we designed six kinds of destroy operators and five kinds of repair operators.