# Multi-Objective Evolutionary Neural Architecture Search with Weight-Sharing Supernet
## 4 Multi-Objective Evolutionary Neural Architecture Search Algorithms
### Bi-Population MOEA/D-Based Neural Architecture Search Algorithm  
As analyzed in [21], the DARTS search space contains \((4\times 10^{12})^{2}\approx 10^{25}\) candidate neural network architectures in total. In such a huge search space, we find that the two traditional algorithms discussed above cannot achieve satisfactory results in architecture optimization. In fact, the traditional multi-objective evolutionary algorithms tend to concentrate the early search on smaller models, which may ignore the larger models with similar performance. This observation is termed the small model trap [14], where the evolutionary algorithms tend to select the well-performing small models in the early stages, ignoring the larger models that may outperform the selected small models in the subsequent periods. Thus, individuals representing these large models may be eliminated and cannot participate in the subsequent optimization, which may discard the genes with high potential. To address this issue, CARS [14] made improvements on the traditional NSGA-II algorithm. Specifically, two rounds of non-dominated sorting are performed separately when performing the environmental selection. The first non-dominated sorting is based on the model's error rate and the model size, followed by the second non-dominated sorting in terms of the reciprocal of the model error rate and the model size. Then, the two Pareto fronts are merged to select the retained individuals. In this way, the algorithm can select both small and large models with high accuracy at the same time in the early stages and maintain a good diversity in the population. Therefore, inspired by this idea, we also make improvements to the traditional MOEA/D and propose a bi-population MOEA/D-based NAS method. MOEA/D can generally better discover well-distributed individuals based on the decomposition strategy compared to NSGA-II. Additionally, MOEA/D has advantages in solving more complex optimization problems. The main process of the bi-population MOEA/D-based NAS algorithm is shown in Algorithm 1. Specifically, the original population \(A\) in the MOEA/D algorithm is split into two sub-populations, namely, \(A_{1}\) and \(A_{2}\). Each sub-population is assigned a reference point, and the weight vectors are shared between the two sub-populations. In sub-population \(A_{1}\), the fitness of an individual is defined by the validation error rate (_error_rate_) and the model size (_model_size_) of the represented network architecture, whereas, in sub-population \(A_{2}\), the fitness is defined by the validation error rate and \(1-model\_size\) (in fact, it is only necessary to convert the model size metric to a reverse order compared to the original one. Since the model size will not exceed 0.5 M during the experimental search process, \(1-model\_size\) is adopted in the proposed algorithm). As a result, reference point \(Z_{1}\) stores the historical lowest validation error rate and the smallest model size in sub-population \(A_{1}\), while reference point \(Z_{2}\) keeps track of the historical lowest model error rate and the largest model size in sub-population \(A_{2}\). ```
0: Number of warm-up epochs \(E_{\text{warmup}}\), number of update periods \(N_{\text{period}}\), number of weight optimization epochs \(E_{\omega}\), population size \(N_{\text{pop}}\), the number of neighbours of each weight vectors \(T\), the aggregation function \(g\), the crossover ratio \(pc\) and the mutation ratio \(pm\), number of individuals to communicate with the other sub-population \(N_{\text{comm}}\). 0: The evolved population after \(N_{\text{period}}\) periods.