# Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search

arXiv: https://arxiv.org/abs/2210.14016 · HTML: https://mlsanity.com/paper/2210.14016/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 53 references that are in the map.
- First posted on arXiv 25 Oct 2022.

## Builds on (most cited first, 28 of 28)

- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [PathNet: Evolution Channels Gradient Descent in Super Neural Networks](https://mlsanity.com/paper/1701.08734/) (2017)
- [Large-Scale Evolution of Image Classifiers](https://mlsanity.com/paper/1703.01041/) (2017)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Searching for A Robust Neural Architecture in Four GPU Hours](https://mlsanity.com/paper/1910.04465/) (2019)
- [Random Search and Reproducibility for Neural Architecture Search](https://mlsanity.com/paper/1902.07638/) (2019)
- [Hierarchical Representations for Efficient Architecture Search](https://mlsanity.com/paper/1711.00436/) (2017)
- [Primer: Searching for Efficient Transformers for Language Modeling](https://mlsanity.com/paper/2109.08668/) (2021)
- [Efficient Multi-objective Neural Architecture Search via Lamarckian Evolution](https://mlsanity.com/paper/1804.09081/) (2018)
- [A Survey on Evolutionary Neural Architecture Search](https://mlsanity.com/paper/2008.10937/) (2020)
- [Evaluating the Search Phase of Neural Architecture Search](https://mlsanity.com/paper/1902.08142/) (2019)
- [Searching for Efficient Multi-Scale Architectures for Dense Image Prediction](https://mlsanity.com/paper/1809.04184/) (2018)
- [Surrogate NAS Benchmarks: Going Beyond the Limited Search Spaces of Tabular NAS Benchmarks](https://mlsanity.com/paper/2008.09777/) (2020)
- [NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search](https://mlsanity.com/paper/2001.10422/) (2020)
- [NAS-Bench-NLP: Neural Architecture Search Benchmark for Natural Language Processing](https://mlsanity.com/paper/2006.07116/) (2020)
- [Evolving Deep Convolutional Neural Networks for Image Classification](https://mlsanity.com/paper/1710.10741/) (2017)
- [Evolving Reinforcement Learning Algorithms](https://mlsanity.com/paper/2101.03958/) (2021)
- [NAS-Bench-Suite: NAS Evaluation is (Now) Surprisingly Easy](https://mlsanity.com/paper/2201.13396/) (2022)
- [AutoBERT-Zero: Evolving BERT Backbone from Scratch](https://mlsanity.com/paper/2107.07445/) (2021)
- [Exploring the Loss Landscape in Neural Architecture Search](https://mlsanity.com/paper/2005.02960/) (2020)
- [Safe Crossover of Neural Networks Through Neuron Alignment](https://mlsanity.com/paper/2003.10306/) (2020)
- [Evolving Deep Convolutional Neural Networks by Variable-length Particle Swarm Optimization for Image Classification](https://mlsanity.com/paper/1803.06492/) (2018)
- [Policy Optimization by Genetic Distillation](https://mlsanity.com/paper/1711.01012/) (2017)

## Built on by (most cited first, 2 of 2)

- [Delta-NAS: Difference of Architecture Encoding for Predictor-based Evolutionary Neural Architecture Search](https://mlsanity.com/paper/2411.14498/) (2024)
- [Evolutionary Architecture Search through Grammar-Based Sequence Alignment](https://mlsanity.com/paper/2512.04992/) (2025)

## Abstract (arXiv)

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.