Population-based search has recently emerged as a possible alternative to
Reinforcement Learning (RL) for black-box neural architecture search (NAS). It
performs well in practice even though it is not theoretically well understood.
In particular, whereas traditional population-based search methods such as
evolutionary algorithms (EAs) draw much power from crossover operations, it is
difficult to take advantage of them in NAS. The main obstacle is believed to be
the permutation problem: The mapping between genotype and phenotype in
traditional graph representations is many-to-one, leading to a disruptive
effect of standard crossover. This paper presents the first theoretical
analysis of the behaviors of mutation, crossover and RL in black-box NAS, and
proposes a new crossover operator based on the shortest edit path (SEP) in
graph space. The SEP crossover is shown theoretically to overcome the
permutation problem, and as a result, have a better expected improvement
compared to mutation, standard crossover and RL. Further, it empirically
outperform these other methods on state-of-the-art NAS benchmarks. The SEP
crossover therefore allows taking full advantage of population-based search in
NAS, and the underlying theory can serve as a foundation for deeper
understanding of black-box NAS methods in general.

本论文提出了一种新的基于最短编辑路径的交叉操作符，该操作符在图结构上克服了排列问题，并在黑盒神经架构搜索中实现了比变异、标准交叉和强化学习更好的预期进展，因此允许充分利用种群搜索。新的交叉操作符可以作为黑盒神经架构搜索方法的基础理论。