## 4 Non-Dominant Sorting Adaptive Memetic Algorithm (NSAM)
### Basic Structure of the NSAM
#### 4.2.1 Destroy Operators

All destroyed operators are uniformly stored in set \(B\), and three different types of destroy operators are defined as follows:

R-destroy: randomly selects solutions for the existing population and deletes them. Max-destroy: calculates the single solution by summing elements, sorts and deletes the solution with the maximum value. Rank-destroy: deletes all the solutions whose rank value is not 0. \(\Delta V\)-destroy: traverses \(\Delta V\) in the solutions, sorts and deletes the solution with the maximum \(\Delta V\). Distance-destroy: traverses the distances to the target in the solutions, sorts and deletes the solution with the maximum mean distance to targets accessed. Figure 3: Flow chart of NSAM algorithm. Access-destroy: traverses the targets access time in the solutions, sorts and deletes the solution with the minimum targets access time. #### 4.2.2 Repair Operators

Save all non-elite solutions in set \(F\). Solutions are selected from the set \(F\) and inserted into the destroyed population to generate a new population, and five different types of repair operators are defined as follows:

R-repair: randomly selects several solutions from the set \(F\) and inserts them into the destroyed population. Min-repair: calculates the single solution by summing elements, sorts and inserts the solution with the minimum value. \(\Delta V\)-repair: traverses \(\Delta V\) in the solutions, sorts and inserts the solution with the minimum \(\Delta V\). Distance-repair: traverses the distances to the target in the solutions, sorts and inserts the solution with the minimum mean distance to targets accessed. Access-repair: traverses the targets access time in the solutions, sorts and inserts the solution with the maximum targets access time. ### Adaptive Strategy Design and Termination Criterion Design

Six kinds of destroy operators and five kinds of repair operators were designed in Section 4.2. Each operator has a score and weight, and the score and weight are updated according to the performance of the operator; thus, affecting the probability of the operator being selected. The update methods of the operator scores and weight are described as the following:

Set \(\pi_{i}^{d}\) and \(\pi_{i}^{r}\) as the scores of the \(i^{th}\) destroy operator and repair operator; \(\omega_{i}^{d}\) and \(\omega_{i}^{r}\) as the weight of the \(i^{th}\) destroy operator and repair operator. The score of all heuristics is set to zero at the start of each segment. We set the weights of the destroy operator \(\pi_{i}^{d}=\frac{1}{6}\); the weights of the repair operator are the same as \(\omega_{i}^{r}=\frac{1}{5}\). The score is used to judge the validity of the operator, the weight is used to determine the probability of the operator being selected, and the weight is updated according to the score of the operator. As for destroy operators and repair operators, each \(\varphi\) times iteration as a stage, and the scores of all selected operators are updated according to the returns of the new solutions at the end of each iteration. At the end of each phase, the weights of all operators are updated according to the scores accumulated by the operators in this stage, and the operator scores are initialized. The update equation for operator weights is shown:

\[\omega_{i}=(1-\rho)\omega_{i}+\rho\frac{\pi_{i}}{\sum_{i=1}^{H}\pi_{i}} \tag{22}\]

where \(\rho\in[0,1]\) is the operator weight update coefficient and means the degree to which the operator is affected by historical data. The operator performance is graded in the iteration process: the higher the score the better the operator's performance. The four kinds of changing score scenarios are set as follows:

If the new solution is better than all the other solutions: \(\sigma_{1}\). If the new solution is better than one of the current dominant solutions: \(\sigma_{2}\). If the new solution is dominated by the current solution but accepted under certain criteria: \(\sigma_{3}\).