论文标题
最短的编辑路径跨界：理论驱动的解决方案，解决了进化神经架构搜索中的排列问题
Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search
论文作者
论文摘要
最近，基于人群的搜索已成为黑盒神经体系结构搜索（NAS）的强化学习（RL）的可能替代方法。即使理论上不太了解它，它在实践中的表现也很好。特别是，尽管传统的基于人群的搜索方法（例如进化算法（EAS））从交叉操作中汲取了很多力量，但在NAS中很难利用它们。人们认为，主要障碍是置换问题：传统图表中基因型和表型之间的映射是多对一的，导致标准交叉的破坏性效果。本文介绍了Black-Box NAS中突变，交叉和RL行为的第一个理论分析，并根据图形空间中的最短编辑路径（SEP）提出了一个新的交叉操作员。理论上显示了SEP交叉以克服排列问题，因此与突变，标准交叉和RL相比，预期改善更好。此外，它在经验上优于最先进的NAS基准测试的其他方法。因此，SEP交叉允许在NAS中充分利用基于人群的搜索，而基础理论可以作为对一般黑盒NAS方法的更深入理解的基础。
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.
