APENAS:An Asynchronous Parallel Evolution Based Multi-Objective Neural .

��濢濗濙濧濣濦濨濝濢濛have predecessor node or successor node. In checking step,APENAS guarantees all nodes have predecessor node andsuccessor node. If node Ni has neither predecessor node norsuccessor node, it will be discarded, as node 4 in Fig. 2 andFig. 3. If node Ni only owns successor node, the predecessorof node Ni will be pointed to node N0 , as node 2 in Fig .2 andFig. 3. If node Ni only has predecessor node, the successorof node Ni will be pointed to node N6 , as node 3 in Fig .2and Fig. 3.The encoding space in APENAS is governed by our encoding method as shown in equation 濞濙濗濨濙濘Fig. 1. NSGA-IIT III. APENASN (1! 2!. (Si 1)!)(2)iIn this section, we illustrate the details of multi-objectiveNAS based on non-dominated sorting and asynchronous parallel evolution based on multi-generation undifferentiated fusionscheme. We also introduce the election pool and the bufferpool are employed in APENAS to improve the diversity andelitism of the evolution algorithm.濅濃A. Multi-objective NASAPENAS employs non-dominated sorting to sort the accuracy and the number of parameters for balancing the tradeoffbetween time consumption and classification accuracy. Wesearch over the entire architecture of the network instead ofrepeating the same stage throughout the entire network. Thesearch strategy ensures the flexibility of APENAS.1) Multi-objective: To reduce the error rate and the complexity of the network architecture at the same time, APENAS chooses the classification accuracy and the number ofparameters as the multi-objective. Several metrics can be usedto quantify the performance of models. Finally, we adopt thenumber of parameters in the literature as performance metrics.Many metrics could be used as computational complexityof model, such as inference time, floating point operations(FLOPs), activate nodes. However, FLOPs is influenced bythe size of the dataset, and inference time cannot be estimatedwith the different computing environments. Other metrics onlyrelate to one aspect of computational complexity.Particularly, we have to point out that multi-objective optimization is a scientific problem. For objectives that otherapplications focus on, the method proposed in this article isstill valid.2) Encoding: In evolution algorithms, a chromosome composed of several genes represents a possible solution to theoptimization problem. In APENAS, the whole network architecture composed of several stages. We use N to representthe number of stages, and the Si represent the number ofnodes in ith stage (0 i n, Si 1). The edge betweennodes could be encoded by a binary number, represented asEdgei,j . Edgei,j 0 represents that nodei and nodej arenot connected. Otherwise, nodei is connected to nodej . Theencoding process of APENAS includes two steps, connectingand checking. In connecting step, we keep the connectivity ofgraph from node0 to nodeSi but do not keep all the nodes濈濄濆濉濇Fig. 2. Connecting step濅濃濈濄濆濉濇Fig. 3. Checking step3) Selction: APENAS selects individuals by torunamentmethod to crossover and mutate. The tournament method takesa certain number of individuals from the population (BootstrapSample), and then selects the best one to enter the offspring.This operation is repeated until the new population size equalsto the original population size. When the better individualis selected by tournament method, crossover and mutationoperations performed directly. Since a amount of individualsdo not dominate each other in the later period of the parallelevolution, we adopt a random selection method. And APENASconsiders roulette algorithm in crossover operation, whichguarantees the elite individuals are inherited.4) Crossover and Mutation: Crossover and mutation operations are employed after a selection operation to ensurethe diversity of population. In this paper, stage is used as the155

TABLE IT HE COMPARISON OF DIFFERENT VERSIONArchitectureAPENAS-ssAPENAS-spAPENASSerial Parallel Sysnchronous We refer to Fig. 5 for an illustration as well as Algorithm 1for pseudo code. APENAS trains individuals on each node.After an individual training, the individual is put into theelection pool for non-dominated sorting and crowding distancesorting. Particularly, non-dominated sorting and crowdingdistance sorting are just to obtain Pareto front not for theselection operator. Subsequently, APENAS only selects twoindividuals from the election pool for tournament method andAPENAS uses random method to avoid a large number ofindividuals do not dominate each other in the later periodof asynchronous parallel evolution. Once the individuals areselected from election pool, APENAS adopts the tournamentmethod to select elite individual. Then the worse individualis discarded, the better individual is put into the buffer poolfor preparing training. APENAS considers the buffer pool tosave the pre-trained individuals of the offspring. In the trainingphase, individuals in the buffer pool are submitted for trainingby roulette algorithm.Asynchronous basic unit of crossover and mutation operations. The positionof crossover operation is C(0 C S) and the positionof mutation operation is M (0 M S). After thecrossover operation, individuals are put into the buffer pool.The individuals in the buffer pool are submitted for training bythe roulette algorithm. However, the random bit mutation maycause the network architecture to be disconnected or illegal.Therefore, when the mutation probability is satisfied, the stageis searched again. APENAS only keeps one stage is mutated,guaranting the diversity of the population and the legality ofthe network architecture.Algorithm 1 APENAS asynchronous evolution on nodesRequire: population size P, generation size G, the number ofnodes K. (P K)1: train different individuals on different nodes2: while i G P do3:if the individual P0 training is finished then4:put P0 into election pool5:if election pool is full then6:non-dominated sorting7:crowding distance sorting8:drop the worst individual9:if P0 is the worst individual in election pool then10:pick individual from buffer pool to retrain11:continue12:end if13:end if14:pick the individual P1 from election pool by roulettealgorithm15:perform crossover and mutation operations betweenP0 and P116:put children to buffer pool17:pick a individual from buffer pool to retrain18:i i 119:else20:wait for the end of individuals training21:end if22: end whileB. Asynchronous Parallel EvolutionFor ease of description, sysnchronous serial APENAS andsysnchronous parallel APENAS as shown in Table I, calledAPENAS-ss and APENAS-sp, respectively. In APENAS-ss,only one node is used, and all individuals train on thisnode sequentially. when all individuals in a population aretrained, the crossover and mutation operations are executed.In APENAS-sp, the number of nodes is equal to populationsize, and each individual trained on one node. When allindividuals in a population are trained, operations such asselection, crossover are performed.APENASChromosome: idden layershidden layersoutput layersCommunicationlayershidden layersoutput layerinput layersoutput layersinput layersModel 1:NetworkArchitectureAccuracyParams Model 2:NetworkArchitectureModel N:NetworkArchitectureAccuracyParamsAccuracy2) Election Pool: Once the individual is trained, it will beadded to the election pool. All individuals in election poolperformed non-dominated sorting and crowding distance sorting. APENAS employs election pool to ensure the efficiencyof APENAS. APENAS sets the size of election pool equal topopulation size to keep more diversity and elite individuals.In Fig.5, we present the election pool in APENAS.3) Buffer Pool: In order to avoid mismatch the populationsize of offspring caused by asynchronous parallel evolution,ParamsFig. 4. Parallel evolution1) Algorithm Description: The process of parallel evolutionis shown in the Fig. 4. The individuals are assigned oneach node to evolve parallelly. When any individual on thenode is finished, this individual is put into the election poolimmediately as shown in Fig. 5.156

TABLE IIC OMPARISON OF RESULTS WITH DIFFERENT METHODSAPENAS adopts the buffer pool to save pre-trained individualsof the offspring. The individuals in the buffer pool are selectedfor training by roulette algorithm in the training phase. Fig. 5shows the buffer pool in etNASNet-A cutoutNASNet-B cutoutBlockQNNAmoebaNet-AAmoebaNet-A cutoutAmoebaNet-B cutoutDARTAPENASIV. E XPERIMENTSIn this section, we consider experiments to evaluate theperformance of APENAS. Experimental setup and metricsis shown in section IV-A. In section IV-B1, we present theclassification accuracy and the number of parameters of thebest architecture searched by APENAS. In section IV-B2,we test the transferability of the best architecture learnedfrom CIFAR-10 on CIFAR-100. We also use different numberof nodes to evaluate the scalability of APENAS by weakscalability experiments in section IV-B3.1) Dataset: We use CIFAR-10 for our classification taskand CIFAR-100 for evaluating the transferability. We randomlysplit the original training set of CIFAR-10 and CIFAR-100 by9:1 to obtain the training and validation sets. The originaltesting set is only used at the end of the search process toobtain the test accuracy for the models on the final tradeofffront.2) Platform: We use private workstation with 2 NVIDIA2080 GPU and Hygon with 600 nodes as experimental platform. In Hygon, each node includes 64 CPUs. Due to resourceconstraints, we evaluate performance of APENAS on privateworkstation. We test the scalability by using different nodeson Hygon.3) The parameters of evolution algorithm : The probabilities of crossover and mutation operations are set to 0.8 and0.01 respectively. The population size is 10 and the numberof generations is 20 in evolution algorithm.4) The hyper-parameters of NAS: Our experiments consider3 stages on CIFAR-10. In each stage, the maximum numberof nodes is 6. After the first and the second stage, a maxpooling with stride 2 are both placed. After the last stage, afully-connected layer with 4096 channels is placed. We set theconvolution kernel size to 3 * 3 and the padding size to 1 *1, fixing the stride values to 1. For each generated networkarchitecture, we limit the number of filters in all nodes to16. We also use standard stochastic gradient descent (SGD)back-propagation algorithm and a multiple step learning rateschedule to train models on our datasets. Our initial learningrate is 0.1. In the architecture search phase, each model trainedfor 200 epochs, which takes about 4 days on a NVIDIA 2080GPU implementation in PyTorch [19]. Then the classificationerror is measured on our validation set.5) Parallel efficiency metrics: The experiments useP ara ef fsysn to evaluate the acceleration effect and thescalability of APENAS-sp. Let Ts be the running time of theAPENAS-ss, and Tp be the running time of the APENAS-sp,then parallel efficiency is defined as equation arch nGradient-basedEvolutionThe experiments use P ara ef fasyn to evaluate the acceleration effect and the scalability of APENAS. Let Ts be therunning time of the APENAS-ss, and Ta be the running time ofthe APENAS, then parallel efficiency is defined as equation 4:A. Experimental Setup and MetricsP ara ef fsysn 95P ara ef fasyn TsTa(4)B. Results AnalysisWe use the experimental setup on CIFAR-10 as explainedin section IV-A.1) Network Architecture: We choose network architectureas shown in Fig. 6 from Pareto set. The second individualwas choosen with the highest classification accuracy fromthe parato front. The individual achieves test error of 9.95%with 0.07 millions of parameters on the CIFAR-10 testing set.In Table II, we summarize the performance of the choosennetwork architecture and state of the art, training on the entireofficial CIFAR-10 dataset. In this table, the first block presentsstate of the art architectures designed by human experts. Thesecond block presents NAS methods that design the entirenetwork. Imperssiveley, APENAS only spends 0.07 millionparameters, which achieving accuracy suparss to other manualapproaches and comparable with other NAS. The number ofparameters we used are reduced by 48x compared to otherNAS.2) Transferability: To study the transferability of chosennetwork architecture as shown in Fig. 6(a), we consider usingCIFAR-100 dataset to evaluate the tranferability of the foundarchitecture by APENAS. We use the same setup on CIFAR10 dataset as explained in section IV-A. The entire processof APENAS takes about 3 hours on a single NVIDIA 2080GPU. Table III shows that the architecture learned on CIFAR10 is suitable for CIFAR-100, and could be compared withthe architecture generated by manual design.3) Evaluation of Asynchronous Parallel Evolution: In orderto demonstrate the scalability of APENAS, we search architecture on CIFAR-10 by different nodes. The orange line in Fig.7shows the parallel efficiency of APENAS. It is a slow upwardtrend with the increasing number of nodes. When 64 nodes areused, the parallel efficiency P ara ef fasyn achieves 92.5%.The experimental results show that the APENAS has a good(3)157

�瀃瀈瀇Fig. 5. The flow chart of asynchronous parallel ��澤澥澨澦澩澧(b)Fig. 6. Network architecture searched by APENASTABLE IIIT RANSFERRING THE NETWORK ARCHITECTURE SEARCHED ON CIFAR-10TO CIFAR-100.ArchitectureWide h Cost(GPU-days)969684.12is 81.49%.By comparing the parallel efficiency of APENAS andAPENAS-sp, we find that our method improves the evolutionefficiency on different nodes. In summary, the experimentson Hygon show that asynchronous parallel evolution couldachieves 92.5% parallel efficiency on 64 nodes, which improves 11.01% compared with sysnchronous parallel evolution.SearchMethodManualRLRLRLEvolutionV. C ONCLUSIONThis paper presents APENAS, an asynchronous parallelevolution based multi-objective NAS, which find the solutionwith good accuracy and a very small number of parameterscompared to state of the art. Especially, APENAS showsthe high scalability on multiple GPUs or CPUs. It helps theresearchers with lacking machine learning experience to utilizemachine learning easily. The experiments on CIFAR-10 showacceleration effect. To demostrate the parallel efficiency ofasynchronization, we design APENAS-sp to be compared withAPENAS. The blue line in Fig.7 shows the parallel efficiencyof APENAS-sp. It is a more quick upward trend than theorange line with the increasing number of nodes. When thenumber of nodes is 64, the parallel efficiency P ara ef fasyn158

Sysnchronous efficiencyAsynchronous efficiencySysnchronous time[11] H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean, “Efficient neuralarchitecture search via parameters sharing,” in Proceedings of the 35thInternational Conference on Machine Learning, ser. Proceedings ofMachine Learning Research, J. Dy and A. Krause, Eds., vol. 80.Stockholmsmässan, Stockholm Sweden: PMLR, 10–15 Jul 2018, pp.4095–4104.[12] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, “Regularized evolutionfor image classifier architecture search,” Proceedings of the AAAIConference on Artificial Intelligence, vol. 33, no. 1, pp. 4780–4789,2019.[13] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le,and A. Kurakin, “Large-scale evolution of image classifiers,” in ICML’17Proceedings of the 34th International Conference on Machine Learning- Volume 70, 2017, pp. 2902–2911.[14] K. O. Stanley and R. Miikkulainen, “Evolving neural networks throughaugmenting topologies,” Evolutionary Computation, vol. 10, no. 2, pp.99–127, 2002.[15] M. Tan, B. Chen, R. Pang, V. Vasudevan, M. Sandler, A. Howard,and Q. V. Le, “Mnasnet: Platform-aware neural architecture search formobile,” in 2019 IEEE/CVF Conference on Computer Vision and PatternRecognition (CVPR), 2019, pp. 2820–2828.[16] S. Xie, H. Zheng, C. Liu, and L. Lin, “Snas: stochastic neural architecture search,” in ICLR 2019 : 7th International Conference on LearningRepresentations, 2019.[17] B. Zoph and Q. Le, “Neural architecture search with reinforcementlearning,” in ICLR 2017 : International Conference on Learning Representations 2017, 2017.[18] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learning transferablearchitectures for scalable image recognition,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018, pp. 8697–8710.[19] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin,A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation inpytorch,” 2017.[20] Z. Lu, I. Whalen, V. Boddeti, Y. Dhebar, K. Deb, E. Goodman, andW. Banzhaf, “Nsga-net: neural architecture search using multi-objectivegenetic algorithm,” in Proceedings of the Genetic and EvolutionaryComputation Conference on, 2019, pp. 419–427.[21] Y. Liu, Q. Liao, J. Sun, M. Hu, L. Liu, and L. Zheng, “A heterogeneousparallel genetic algorithm based on sw26010 processors,” in 2019IEEE 21st International Conference on High Performance Computingand Communications; IEEE 17th International Conference on SmartCity; IEEE 5th International Conference on Data Science and Systems(HPCC/SmartCity/DSS), 2019, pp. 54–61.[22] N. Srinivas and K. Deb, “Muiltiobjective optimization using nondominated sorting in genetic algorithms,” Evolutionary Computation, vol. 2,no. 3, pp. 221–248, 1994.[23] B. Baker, O. Gupta, N. Naik, and R. Raskar, “Designing neuralnetwork architectures using reinforcement learning,” arXiv preprintarXiv:1611.02167, 2016.[24] L. Xie and A. Yuille, “Genetic cnn,” in 2017 IEEE InternationalConference on Computer Vision (ICCV), 2017.[25] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of featuresfrom tiny images,” 2009.[26] Z. Zhong, J. Yan, W. Wu, J. Shao, and C.-L. Liu, “Practical block-wiseneural network architecture generation,” in 2018 IEEE/CVF Conferenceon Computer Vision and Pattern Recognition, 2018, pp. 2423–2432.Asysnchronous time5400100% 100%100%98.96%520096.86%95.80%94.34%95%PARALLEL 090%88.76%460085%440081.49%420014816326480%THE NUMBER OF NODESFig. 7. The scalability of APENAS and APENAS-spthat APENAS could find network architecture with 90.05%accuracy and 0.07 million parameters. The experimental results on hygon show that APENAS achieves 92.5% parallelefficiency on 64 nodes.There are several directions to improve APENAS further.For example, a more fine-grained structure could be consideredas the basic unit of network architecture search to improveclassification accuracy. It will also be considered to changethe methods of crossover and mutation operations during thesearch process.ACKNOWLEDGMENTThis work is supported by the the National Key Researchand Development Program of China (No.2020YFA0607902).R EFERENCES[1] D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation byjointly learning to ali

We consider an asynchronous parallel evolution based multi-objective neural architecture search, using a multi-generation undifferentiated fusion scheme to make full use of computing resource, which speeds up the process of neural architecture search. B. Multi-objective optimization Multi-objective optimization [9] deal with problems