The global structure of the hyperparameter spaces of neural networks is not well understood and it is therefore not clear which hyperparameter search algorithm will be most effective. In this paper we analyze the landscapes of convolutional neural network architecture search spaces to provide insight into appropriate search algorithms for these spaces. Using a classical fitness landscape analysis approach (fitness distance correlation) and a more recent tool (local optima networks) we study the global structure of these spaces. Our analysis on six image classification datasets reveals that the landscapes are multi-modal, but with relatively few local optima from which it is not hard to escape with a simple perturbation operator. This led us to explore the performance of iterated local search, which we found to more effectively search the training landscapes than three evolutionary algorithm variants. Evolutionary algorithms, however, outperformed iterated local search in terms of generalization on problems with larger discrepancies between the training and testing landscapes.