Source-linked AI summary
Deep Reinforcement Learning Based Parameter Control in Differential Evolution
Mudita Sharma, Alexandros Komninos, Manuel Lopez Ibanez, Dimitar Kazakov
TL;DR
Choosing a useful DE mutation strategy is difficult because operators can vary in usefulness across problems and stages of a run. DE-DDQN trains a neural network offline and uses it to select strategies online; its results differ significantly from five baselines, random selection, and single-strategy DEs, but not from the other methods compared.
Problem
The most useful DE mutation operator can vary across optimization problems and run stages, making operator choice difficult for previously unseen problems.
Source: §1 · p. 1Method
Results
DE-DDQN2 differed significantly from five baselines, random operator selection, and single-strategy DEs, but not from the other methods compared.
Source: §5.2 · p. 7Takeaways & Limitations
R2 assigns ten times more reward to improving the best-so-far solution than to improving over the parent and is unaffected by function range.
Source: §5.2 · p. 7Training costs significantly more than a single DE run, though it is performed offline once; broader applicability is conjectured to require training on more data from different function classes.
Source: §5.1 · p. 6
Abstract
from arXiv · showhide
Adaptive Operator Selection (AOS) is an approach that controls discrete parameters of an Evolutionary Algorithm (EA) during the run. In this paper, we propose an AOS method based on Double Deep Q-Learning (DDQN), a Deep Reinforcement Learning method, to control the mutation strategies of Differential Evolution (DE). The application of DDQN to DE requires two phases. First, a neural network is trained offline by collecting data about the DE state and the benefit (reward) of applying each mutation strategy during multiple runs of DE tackling benchmark functions. We define the DE state as the combination of 99 different features and we analyze three alternative reward functions. Second, when DDQN is applied as a parameter controller within DE to a different test set of benchmark functions, DDQN uses the trained neural network to predict which mutation strategy should be applied to each parent at each generation according to the DE state. Benchmark functions for training and testing are taken from the CEC2005 benchmark with dimensions 10 and 30. We compare the results of the proposed DE-DDQN algorithm to several baseline DE algorithms using no online selection, random selection and other AOS methods, and also to the two winners of the CEC2005 competition. The results show that DE-DDQN outperforms the non-adaptive methods for all functions in the test set; while its results are comparable with the last two algorithms.
1 INTRODUCTION
The paper addresses how to select DE mutation strategies as their usefulness varies across problems and stages of a run. It introduces offline-trained DDQN for this task and evaluates it against adaptive and non-adaptive methods.
1 INTRODUCTION
- DE mutation strategies can perform differently across problems and run stages, making operator choice during optimization an adaptive control problem.AOS measures an operator’s effect and adapts future choices according to a reward function.Source: §1 · p. 1
- The authors position DE-DDQN as an offline-trained reinforcement-learning approach, noting that prior offline-trained AOS methods were not reinforcement-learning based.Related approaches include offline learning for parameter control and reinforcement-learning AOS methods.Source: §1 · pp. 1–2
- DDQN uses offline training on DE runs and 99 state features to predict mutation strategies for unseen problems, with three alternative reward definitions analyzed.The authors report that reward definition strongly affects DE-DDQN performance.Source: §1 · p. 2
- The evaluation trains on 16 CEC2005 functions at dimensions 10 and 30, then tests on five different functions at both dimensions against DE, AOS, and CMA-ES baselines.The test set contains 10 function-dimension cases.Source: §1 · p. 2
- The DE variants using AOS completely outperform DE variants using a fixed mutation strategy or random selection; DE-DDQN is second best behind IPOP-CMAES in mean rank, while post-hoc testing finds no statistically significant differences between CMAES and AOS-enabled DE algorithms.Source: §1 · p. 2
2 BACKGROUND
The background describes DE mutation and crossover, then introduces reinforcement learning and its DDQN implementation. In DE, DDQN selects mutation strategies as actions within an optimization run.
2.1 Differential Evolution
- DE mutation creates offspring from parent solutions; strategies differ in exploration and exploitation, and no single strategy is best across all problems and run stages.The described mutation strategies combine three or more parent solutions.Source: §2.1 · p. 2
- The scaling factor F and crossover rate CR govern mutation, with CR determining whether mutation applies to each dimension and at least one dimension mutated per parent.The mutation equations also use the best parent and randomly selected population indexes.Source: §2.1 · p. 2
2.2 Deep Reinforcement Learning
- Reinforcement learning selects actions from states to maximize cumulative reward; for large or continuous state spaces, a neural network approximates the policy.The policy maps state features to actions rather than using an explicit lookup table.Source: §2.2 · p. 2
- DDQN uses a primary network to select an action and a target network to generate its target Q-value, addressing DQN’s tendency to overestimate action values.The target network’s weights are fixed and updated periodically or slowly from the primary network.Source: §2.2 · p. 2
- Integrated into DE, DDQN treats mutation strategies as actions and each optimization run as the environment, selecting a strategy at each generation.The DE state comprises features of the problem or algorithm, and applying an action yields a reward and next state.Source: §2.2 · p. 2
3 DE-DDQN
DE-DDQN adapts Double Deep Q-Networks to select DE mutation strategies using the algorithm’s state and rewards. It learns offline from repeated benchmark runs, then selects strategies online for unseen problems.
3 DE-DDQN
- DE-DDQN treats the DE run as the learning environment, with state features, mutation strategies as actions, and rewards measuring action benefits.The resulting state–action–reward–next-state tuples are observations.Source: §3 · p. 3
3.1 Training phase
- During training, repeated runs on benchmark functions populate an observation memory used to train the primary network to approximate target Q-values.An ε-greedy policy selects random strategies with probability ε and otherwise chooses the strategy with the highest predicted Q-value.Source: §3.1 · p. 3
- Training targets combine the current reward with a discounted estimate of future reward, using a separate target network whose weights are periodically synchronized.The target network’s weights remain fixed between synchronizations.Source: §3.1 · p. 3
3.2 Online phase
- After training, the primary network’s weights are frozen; on unseen functions, DE-DDQN selects each mutation strategy online with a greedy policy and does not update weights or compute rewards.The network predicts strategy Q-values from each newly observed state.Source: §3.2 · p. 4
4 STATE FEATURES AND REWARD
The state representation combines normalized landscape and population information with operator-performance history. Three reward definitions measure offspring improvement at each action, including improvements relative to the current best or known optimum.
4.1 State representation
- Current-state features cover parent and population fitness, remaining evaluation budget, problem dimension, stagnation, and parent-to-solution distances and fitness differences.The features are designed to capture landscape properties and are normalized to [0, 1].Source: §4.1 · p. 4
- Operator-history features track success rates and improvements over recent generations, while a FIFO window retains a competing set of recent solutions for each operator.The recent-history span is 10 generations and the fixed-size window is 50.Source: §4.1 · pp. 4–5
4.2 Reward definitions
- Rather than rely on sparse full-run rewards, the method computes a reward after each offspring; R1 measures offspring–parent improvement, while R2 rewards improvement over the best-so-far solution more.R3 is a variant of R1 relative to the offspring’s distance from the optimum.Source: §4.2 · p. 5
- R3 requires the training functions’ optimum values to be known in advance.Its definition targets larger parent-to-offspring fitness improvement and smaller offspring-to-optimum difference.Source: §4.2 · pp. 5–6
5 EXPERIMENTAL DESIGN
The experiments train DE-DDQN on CEC2005 functions and evaluate it on a separate test set against fixed, random, adaptive, and CMAES baselines. DE-DDQN2 significantly outperforms random and fixed-strategy DEs, while comparisons with other methods are not statistically significant.
5 EXPERIMENTAL DESIGN
- The comparison included ten baselines, among them random selection, four fixed-strategy DEs, three other AOS methods, and two CEC2005-winning CMAES variants.DE baselines used population size 100, F = 0.5, and CR = 1.0; the AOS baselines' hyperparameters were tuned offline.Source: §5 · p. 6
5.1 Training and testing
- Training used 16 CEC2005 functions and testing used five different functions, each evaluated at dimensions 10 and 30.This yields 32 training problems and 10 test problems; the split included multiple function classes.Source: §5.1 · p. 6
- Training cost was significant relative to one DE run, but was incurred offline and could be reduced through parallelisation and GPUs.The authors conjecture that training on more data from additional function classes could extend application to a larger range of unknown functions.Source: §5.1 · p. 6
5.2 Discussion of results
- R2 showed ranking evidence of better performance than R1 and R3, although differences among reward definitions were not statistically significant.R2 assigns fixed rewards and is unaffected by function range; the authors argue raw function values in R1 and R3 can mislead the network across different fitness ranges.Source: §5.2 · p. 7
- Across 25 runs, DE-DDQN2 found a lower overall minimum function value than the other AOS methods on every test problem except F9-10 and F16-30.Its median solution values were better on six of the ten problems.Source: §5.2 · p. 7
- DE-DDQN2 differed significantly from random and fixed-strategy DEs, but not from the other methods in pairwise comparisons.The comparisons use adjusted post-hoc tests with DE-DDQN2 as the control.Source: §5.2 · p. 7, Table 5 · p. 8
- DE-DDQN2 performed consistently on unimodal F3 at both dimensions, but showed higher variance on F16-30 and F23-30.The authors suggest higher-dimensional multimodal functions can confuse the network and lead to suboptimal behavior.Source: §5.2 · p. 8
6 CONCLUSION
DE-DDQN learns online to select Differential Evolution mutation strategies using an offline-trained neural network based on 99 state features and reward data. On the held-out test functions, the proposed methods outperform non-AOS baselines, while DE-DDQN2 ranks second overall behind IPOP-CMAES.
6 CONCLUSION
- DE-DDQN uses offline training data from DE runs to optimize a neural network that predicts mutation strategies for online use on new problems.The method collects 99 state features and reward values; experiments used 32 training and 10 test problems from CEC2005 at dimensions 10 and 30.Source: §6 · p. 8
- All three proposed methods outperform non-AOS baselines on mean error, while DE-DDQN2 ranks second overall after IPOP-CMAES.Differences between the best proposed method and literature AOS methods were not statistically significant.Source: §6 · p. 8
- Future work will explore controlling more evolutionary-algorithm parameters, including combinations of discrete and continuous parameters, and tuning features and hyperparameters.The authors expect extensive tuning to further improve performance.Source: §6 · p. 8