Distance-based Kernels for Surrogate Model-based Neuroevolution

Jörg Stork, Martin Zaefferer, Thomas Bartz-BeielsteinarXiv 2018 · OpenReview

Abstract: The topology optimization of artificial neural networks can be particularly difficult if the fitness evaluations require expensive experiments or simulations. For that reason, the optimization methods may need to be supported by surrogate models. We propose different distances for a suitable surrogate model, and compare them in a simple numerical test scenario.

Introduction

Neuroevolution algorithms, such as Cartesian Genetic Programming (CGPANN), are powerful tools for evolving both the topology and parameters of artificial neural networks. However, these methods typically require thousands of fitness evaluations, which is computationally prohibitive when evaluations involve expensive simulations or real-world experiments. To mitigate this, surrogate model-based optimization (SMBO) can be employed. The effectiveness of SMBO depends heavily on the distance measure used to determine similarity between networks in the surrogate model's kernel.

Methods

The study integrates SMBO with CGPANN using a Kriging model (Gaussian process) as the surrogate. Three primary distance measures were compared:

  1. Genotypic Distance (GD): A comparison of raw genes (weights, connections, function types) using Euclidean and Hamming distances.
  2. Genotypic ID Distance (GIDD): A structural comparison analyzing active topology subgraphs and node IDs.
  3. Phenotypic Distance (PD): A behavioral comparison measuring the Euclidean distance between network outputs (softmax values) on a small dataset.

The experimental setup utilized the IRIS dataset as a benchmark for a low-budget optimization scenario, limited to 250 evaluations. The parameters for the evolutionary process and surrogate models are detailed in the table below.

Experimental parameters for the CGPANN and SMBO methods, including mutation rates and evaluation budgets.

Key Insights and Results

The results demonstrate a clear advantage for phenotypic distance measures over structural ones. Genotypic distances (GD and GIDD) struggled due to the "rugged" nature of the fitness landscape, where small structural changes often lead to massive behavioral shifts. In contrast, Phenotypic Distance (PD) provided a smoother and more reliable metric for the surrogate model by focusing on how the network actually behaves.

Comparison of adjusted accuracy across different optimization methods. PD-based methods significantly outperform genotypic and baseline approaches within the 250-evaluation budget.

As shown in the figure, PD-based SMBO variants (PD Base, PD RSM 60, PD RSM 15) achieved significantly higher median accuracy compared to standard CGPANN and random search. Notably, using a reduced sample set for PD (Response Surface Method with 15 or 60 samples) maintained high performance, suggesting that full dataset evaluation is not necessary for effective distance calculation, which further reduces computational overhead.

Conclusion

Phenotypic distance is a superior metric for surrogate-assisted neuroevolution, effectively capturing behavioral similarity that structural metrics miss. While this study used the IRIS benchmark to demonstrate proof-of-concept, the results suggest that SMBO with PD can drastically reduce the evaluation budget required for complex network optimization. Future work will focus on evaluating generalization performance on unseen data and scaling these methods to higher-dimensional tasks and reinforcement learning environments.

Summary updated

Abstract

The topology optimization of artificial neural networks can be particularly difficult if the fitness evaluations require expensive experiments or simulations. For that reason, the optimization methods may need to be supported by surrogate models. We propose different distances for a suitable surrogate model, and compare them in a simple numerical test scenario.
BibTeX
@misc{stork2018distance,
  author = {Jörg Stork and Martin Zaefferer and Thomas Bartz-Beielstein},
  title = {{Distance-based Kernels for Surrogate Model-based Neuroevolution}},
  year = {2018},
  eprint = {1807.07839},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.07839},
}
Figure