Limited evaluation cooperative co-evolutionary differential evolution for large-scale neuroevolution

Anil Yaman, Decebal Constantin Mocanu, Giovanni Iacca, George H. L. Fletcher, Mykola Pechenizkiy

TL;DR

This paper introduces LECCDE (Limited Evaluation Cooperative Co-evolutionary Differential Evolution), a novel algorithm designed to scale up the optimization of large artificial neural networks using direct-encoding neuroevolution. By combining Cooperative Co-evolution to break down high-dimensional parameter spaces and Limited Evaluation to speed up fitness scoring via data batching, the method achieves higher accuracy and drastically reduces compute time compared to standard Differential Evolution.

What Problem Does This Paper Address?

Neuroevolution (NE) is a powerful alternative to gradient-based methods (like backpropagation) for training neural networks, particularly in reinforcement learning or environments where gradients are noisy or unavailable. However, NE using direct encoding—where every single network weight is represented as a gene in the evolutionary population—struggles to scale.

There are two massive bottlenecks for large-scale direct-encoded NE:

  1. High Dimensionality: Standard evolutionary algorithms fail to efficiently search the massive parameter spaces required for modern neural networks.
  2. Computational Cost: Evaluating the fitness of a population of large networks across a massive training dataset at every generation is prohibitively slow.

While many researchers pivot to indirect encoding (evolving rules or generators that build the network) to solve this, the authors of this paper tackle the direct encoding scalability problem head-on.

Methods

The authors build upon standard Differential Evolution (DE), a popular population-based continuous optimization algorithm, and enhance it with two key mechanisms:

  1. Cooperative Co-evolution (CC): To handle the massive parameter space, the algorithm uses a divide-and-conquer strategy. The authors introduce a clever biological heuristic: they decompose the network by assigning the pre-synaptic weights of each post-synaptic neuron to a distinct subpopulation. These subpopulations evolve their specific weights separately, but cooperate by combining their best individuals to form a complete global network for fitness evaluation.
  2. Limited Evaluation (LE): To handle the computational bottleneck of evaluating large datasets, LE borrows a concept from stochastic gradient descent: mini-batches. Instead of evaluating networks on the entire dataset, LE evaluates them on small random batches. To prevent noisy batch evaluations from derailing the evolutionary process, it uses fitness inheritance—blending the network's score on the current batch with the historical fitness inherited from its parent.

Datasets

The authors evaluated their algorithm on standard classification benchmarks of varying sizes to test scalability:

  • Wisconsin Breast Cancer (WBC): 30 features, 569 instances.
  • Epileptic Seizure Recognition (ESR): 178 features, 4,600 instances.
  • Human Activity Recognition (HAR): 561 features, 7,144 instances.
  • MNIST (in Appendix): 784 features, 60,000 instances.

No new datasets were introduced; these were selected to demonstrate how the algorithm's performance scales as feature and instance counts grow.

Key Insights and Ideas

  • Structural Decomposition Works: Decomposing the evolutionary problem at the level of post-synaptic neurons is a highly effective heuristic. It naturally partitions a massive, unwieldy weight matrix into logically grouped, manageable chunks that can be optimized in parallel.
  • Evolutionary Mini-batching is Viable: The LE scheme proves that evolutionary algorithms don't need full-dataset evaluations every generation to converge. Fitness inheritance provides enough signal stability to guide the population accurately, mirroring the efficiency gains seen in mini-batch gradient descent.
  • Synergy of CC and LE: CC handles the spatial complexity (too many weights), while LE handles the temporal/data complexity (too many training examples). Together, they make direct-encoded neuroevolution viable for networks with tens of thousands of parameters.

Key Results

  • Accuracy Boosts: The Cooperative Co-evolution (CC) scheme significantly improved classification accuracy over standard DE. This was most pronounced on the larger HAR dataset, where CCDE and LECCDE outperformed standard DE by roughly 15-20%.
  • Massive Speedups: The Limited Evaluation (LE) scheme slashed runtimes without degrading accuracy. On the HAR dataset, LECCDE ran about 4x faster than standard DE.
  • Extreme Scaling: In preliminary tests on the massive MNIST dataset (detailed in the appendix), the LE scheme's impact was staggering—LECCDE was approximately 25x faster than standard DE and CCDE, achieving 90.8% test accuracy in a fraction of the time.

Limitations and Future Work

  • Fixed Topologies: Currently, LECCDE only optimizes the weights of networks with fixed, predefined architectures. The authors suggest extending this approach to topology optimization (similar to NEAT) in the future.
  • Parameter Sensitivity: The algorithm's performance on MNIST (~90.8%) lags slightly behind state-of-the-art backpropagation for the same architecture. The authors note that DE is highly sensitive to its hyperparameters (crossover rate, scale factor) and suggest that implementing self-adaptive parameter control could close this gap.
  • Decomposition Heuristics: While grouping by post-synaptic neurons worked well, the authors acknowledge that automated decomposition methods might discover even more optimal ways to split up the network parameters for co-evolution.

Summary updated

Abstract

Many real-world control and classification tasks involve a large number of features. When artificial neural networks (ANNs) are used for modeling these tasks, the network architectures tend to be large. Neuroevolution is an effective approach for optimizing ANNs; however, there are two bottlenecks that make their application challenging in case of high-dimensional networks using direct encoding. First, classic evolutionary algorithms tend not to scale well for searching large parameter spaces; second, the network evaluation over a large number of training instances is in general time-consuming. In this work, we propose an approach called the Limited Evaluation Cooperative Co-evolutionary Differential Evolution algorithm (LECCDE) to optimize high-dimensional ANNs. The proposed method aims to optimize the pre-synaptic weights of each post-synaptic neuron in different subpopulations using a Cooperative Co-evolutionary Differential Evolution algorithm, and employs a limited evaluation scheme where fitness evaluation is performed on a relatively small number of training instances based on fitness inheritance. We test LECCDE on three datasets with various sizes, and our results show that cooperative co-evolution significantly improves the test error comparing to standard Differential Evolution, while the limited evaluation scheme facilitates a significant reduction in computing time.
BibTeX
@inproceedings{yaman2018limited,
  author = {Anil Yaman and Decebal Constantin Mocanu and Giovanni Iacca and George H. L. Fletcher and Mykola Pechenizkiy},
  title = {{Limited evaluation cooperative co-evolutionary differential evolution for large-scale neuroevolution}},
  booktitle = {GECCO},
  year = {2018},
  doi = {10.1145/3205455.3205555},
}

Loading related content...

Figure