Runtime Analysis of Crossover-based Evolutionary Neural Architecture Search for Multiclass Classification Problems

Crossover-based evolutionary algorithms (EAs), which generate offspring through recombination and mutation, have been widely applied to neural architecture search for automated design of deep neural architectures. However, it remains unclear whether and when the crossover operator benefits the evolutionary neural architecture search (ENAS) algorithm. To bridge this gap, this work analyzes its role by conducting runtime analysis, which is an essential theoretical aspect of EAs for understanding whether evolutionary operators can accelerate the search for optimal or approximate solutions and under which conditions such acceleration occurs. Specifically, we first develop a runtime analysis framework that captures both progress and potential regress occurring in each generation. Based on this, we analyze the runtime of the ENAS algorithm with crossover on multiclass classification problems, and the results reveal that crossover may not always accelerate ENAS, particularly when it is frequently applied to similar or identical individuals. Motivated by the observation, we further introduce a diversity-preserving mechanism through a duplicate-based tie-breaking rule into the ENAS algorithm with crossover to prevent similar or identical individuals from surviving to the next generation, and analyze its effect on the expected runtime. Our results show that maintaining population diversity may improve the efficiency of crossover. We hope this work may provide theoretical support to deepen the understanding of crossover in ENAS and offer insights into designing effective ENAS algorithms.