PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning adaptive differential evolution algorithm from optimization experiences by policy gradient

Jianyong Sun, Xin Liu, Thomas Bäck, Zongben Xu

arXiv:2102.03572v1cs.NE

TL;DR

Choosing DE parameters is difficult because effective settings vary with the problem and search state, while trial-and-error tuning is time-consuming. The paper learns an adaptive controller with policy gradient and evaluates it on CEC’13 and CEC’17. The learned DE is reported as competitive on those suites, though its performance on unrelated functions is uncertain.

  • Problem

    DE parameter settings are problem- and search-state-dependent, and trial-and-error tuning is time-consuming.

    Source: §I · p. 1

  • Method

    The paper models adaptive parameter control as an MDP and uses policy gradient to train a recurrent neural-network controller from CEC’13 optimization experience.

    Source: §VII · p. 13

  • Results

    The learned DE is reported as very competitive on the CEC’13 and CEC’17 suites; it ranks third on CEC’17 after training on CEC’13.

    Source: B. The Comparison Results on the… · p. 12, §VII · p. 13

  • Takeaways & Limitations

    On CEC’17, the learned controller uses its trained knowledge on new test functions without requiring further algorithm-parameter tuning.

    Source: B. The Comparison Results on the… · p. 12

    Because training and test functions share basic-function features, performance on unrelated functions, including real-world problems, is not predictable and may be limited.

    Source: §VII · p. 13

Abstract

from arXiv · show

Differential evolution is one of the most prestigious population-based stochastic optimization algorithm for black-box problems. The performance of a differential evolution algorithm depends highly on its mutation and crossover strategy and associated control parameters. However, the determination process for the most suitable parameter setting is troublesome and time-consuming. Adaptive control parameter methods that can adapt to problem landscape and optimization environment are more preferable than fixed parameter settings. This paper proposes a novel adaptive parameter control approach based on learning from the optimization experiences over a set of problems. In the approach, the parameter control is modeled as a finite-horizon Markov decision process. A reinforcement learning algorithm, named policy gradient, is applied to learn an agent (i.e. parameter controller) that can provide the control parameters of a proposed differential evolution adaptively during the search procedure. The differential evolution algorithm based on the learned agent is compared against nine well-known evolutionary algorithms on the CEC'13 and CEC'17 test suites. Experimental results show that the proposed algorithm performs competitively against these compared algorithms on the test suites.

I. INTRODUCTION

DE control parameters can be difficult to set because suitable values depend on the problem and the search state, while trial-and-error tuning fixes values after a time-consuming process. The paper motivates learning-based parameter control as an alternative to fixed rules and proposes a policy-gradient controller.

I. INTRODUCTION

  • Trial-and-error tuning fixes parameters during the search and is described as time-consuming, unreliable, and inefficient.The paper notes that suggested parameter ranges may still require adjustment for a new test problem.Source: §I · p. 1
  • Suitable DE settings depend on problem characteristics and search state, making balanced performance across effectiveness, efficiency, and robustness difficult to achieve.The scale factor F, crossover rate CR, and population size N are among the control parameters whose poor choice can contribute to stagnation or premature convergence.Source: §I · p. 1

1) Parameter Control Without Learning:

  • Without learning, parameter-control rules may use no online information, vary with time, or use information collected from the current generation.Examples include random selection, generation-dependent schedules, and rules based on population fitness ranges, diversity, or ranks.Source: 1) Parameter Control Without Learning · pp. 1–2

2) Parameter Control With Learning from the Search Process:

  • Learning-based methods use information gathered during search, especially successful trials, to update control parameters.Prior approaches include ϵ-greedy selection, storing successful settings in a memory or pool, and updating distribution means from stored and current parameters.Source: 2) Parameter Control With Learning… · p. 2
  • The proposed controller models parameter control as a finite-horizon MDP and uses policy gradient to learn a neural network that adaptively sets F and CR.The learned approach is presented as an alternative to trial-and-error that does not require extra adjustment for a new test problem.Source: 2) Parameter Control With Learning… · p. 2

II. PARAMETERIZED KNOWLEDGE REPRESENTATION BY DEEP AND REINFORCEMENT LEARNING

The paper introduces deep and reinforcement learning concepts, then describes the typical differential-evolution operators used in its adaptive-control method. Its DE uses current-to-pbest/1 mutation and binomial crossover, with control parameters learned from optimization experience.

A. Deep Learning

  • Deep learning uses multiple nonlinear processing layers to represent knowledge and extract meaningful features.The passage describes a deep neural network as a parameterized model that can make decisions from a system's current state when trained.Source: A. Deep Learning · p. 2

B. Reinforcement Learning

  • Reinforcement learning seeks an agent policy that maximizes cumulative reward through interaction with an environment.The MDP formulation associates states, actions, rewards, and transition probabilities; a policy gives action probabilities conditioned on state.Source: B. Reinforcement Learning · p. 3

III. ADAPTIVE PARAMETER CONTROL VIA POLICY GRADIENT

  • The paper introduces a procedure for learning the adaptive settings of a typical differential-evolution algorithm.The section introduces the notation used in the paper before presenting the algorithm.Source: §III · p. 3

A. The Typical DE

  • The typical DE uses current-to-pbest/1 mutation and binomial crossover, and its control parameters include N and per-individual F values.pbest is selected randomly from the best N × p individuals; crossover compares a uniform draw with CR and also uses a randomly chosen index jrand.Source: A. The Typical DE · p. 3

B. Embed Recurrent Neural Network within the Typical DE

The section embeds a recurrent neural network in the DE loop as a controller for adapting parameters from search information. An LSTM carries information across generations, while mutation, crossover, and selection continue to form each new population.

B. Embed Recurrent Neural Network within the Typical DE

  • At each generation, mutation produces a mutated population, crossover forms the trial population, and selection forms the next population.The controller output Θ_t^F is used as input to mutation.Source: B. Embed Recurrent Neural Network… · pp. 3–4
  • The neural network is motivated as an approximator of the nonlinear mapping from collected search information to control parameters.The network is embedded in the evolution procedure as a parameter controller.Source: B. Embed Recurrent Neural Network… · pp. 3–4
  • The controller uses an LSTM to retain search information across generations, reflecting the view that earlier information matters with greater influence from more recent generations.The paper motivates the LSTM by its ability to capture long-term dependencies.Source: B. Embed Recurrent Neural Network… · p. 4
  • The LSTM input combines the current fitness vector F_t with statistics U_t, while H_t and C_t represent its short- and long-term memory.The section describes the controller as taking the concatenated F_t and U_t as input.Source: B. Embed Recurrent Neural Network… · p. 4

C. Model the Evolution Search Procedure as an MDP

The proposed DE evolution procedure is modeled as a Markov decision process to define the components needed for learning its parameter controller.

C. Model the Evolution Search Procedure as an MDP

1) Environment:

The controller is learned in an environment of related training functions, using population fitness and statistics as state information. It samples control parameters from a policy and receives reward based on improvement in best fitness.

1) Environment:

  • The learning environment comprises training functions used to evaluate the controller, which should share characteristics relevant to learning a good parameter controller.Source: 1) Environment · p. 4
  • The state includes population fitness F_t, statistics U_t, and memories H_t; U_t combines the current normalized-fitness histogram with a moving average over the past g generations.The statistics are computed for the current population, not for individual members.Source: 2) State (St) · p. 5
  • Given state S_t, the policy samples the control-parameter action A_t from a probability distribution, with a normal policy assumed for continuous-valued parameters.Source: 3) Action (At) and Policy · p. 5
  • The reward is the relative improvement in best fitness after applying the sampled parameters, with greater improvement corresponding to higher reward.Source: 4) Reward (rt+1) · p. 5

5) Transition:

The transition distribution is unavailable in this formulation, but the authors state that it does not affect learning.

5) Transition:

  • The transition probability is unavailable, and the authors state that its distribution does not affect learning.Source: 5) Transition · p. 5

D. Learn the Control Parameter by Policy Gradient

The paper models finite-generation DE parameter control as a finite-horizon MDP and uses policy gradient to learn a controller from optimization trajectories sampled on training functions. The controller’s policy parameters are updated using trajectory rewards and stochastic gradient ascent.

D. Learn the Control Parameter by Policy Gradient

  • Policy gradient updates policy parameters by stochastic gradient ascent on expected reward, including when transition probabilities are unknown.The gradient is the gradient of cumulative reward, and the update uses learning rate α.Source: D. Learn the Control Parameter by… · p. 5
  • A finite-generation evolutionary search is modeled as a finite-horizon MDP, with each trajectory comprising states, actions, and rewards across T generations.The trajectory probability and cumulative reward underpin the policy-gradient expectation.Source: D. Learn the Control Parameter by… · p. 5
  • For each of M training functions, the algorithm samples L trajectories over T generations, computes generation rewards, and uses them to update W.The LSTM computes DE control parameters from W at each generation.Source: D. Learn the Control Parameter by… · p. 5
  • The L trajectories from each of M functions provide L × M optimization experiences for learning the parameter controller.Each trajectory represents an optimization experience for a particular training function.Source: D. Learn the Control Parameter by… · p. 5

E. Embed the Learned Controller within the DE

The learned DE (LDE) embeds a trained controller in the DE search loop, using controller outputs for control parameters alongside information gathered during the search. The experimental study evaluates the approach on unused CEC’13 or CEC’17 functions and notes that several comparator methods were manually tuned on other test sets.

E. Embed the Learned Controller within the DE

  • LDE uses samples from the controller’s output as control parameters within an otherwise typical DE evolution procedure.The controller is applied directly to a new test problem after training.Source: E. Embed the Learned Controller within… · p. 6
  • The controller combines offline knowledge from optimization experiences with online search information, and one generation has time complexity O(H^2+N·H+N·n).Ut is computed at each generation, while Ht and Ct are initialized and maintained; H is the number of hidden-layer neurons.Source: E. Embed the Learned Controller within… · p. 6

IV. EXPERIMENTAL STUDY

  • Testing uses functions not used for training from CEC’13 or CEC’17, with 51 runs per function and termination at MAXNFE > n×10^4 or function error < 10^-8.CEC’13 includes unimodal, basic multimodal, and composition functions; CEC’17 includes unimodal, simple multimodal, hybrid, and composition functions.Source: §IV · pp. 6–7
  • Several comparator methods were manually grid-searched on different benchmarks, so their performance might improve with tuning on CEC’13 or CEC’17.The authors note that JADE, cDE, and CoBiDE were not originally tested on those suites; comparator parameters otherwise follow their original references.Source: §IV · p. 7

A. The Comparison Results on the CEC’13 Test Suite

At MAXNFE, LDE performs better overall than DE/rand/1/bin and JADE with archive, similarly to JADE without archive, but behind jSO; at T = 50 it performs worse than the compared algorithms. Its APS ranking places it second, behind jSO.

A. The Comparison Results on the CEC’13 Test Suite

  • At T = 50, LDE performs worse than the compared algorithms, but its learned knowledge can benefit search as evolution continues to MAXNFE.The agent was trained for T = 50 generations, whereas training did not terminate at MAXNFE.Source: A. The Comparison Results on the… · p. 7
  • At MAXNFE, LDE outperforms DE/rand/1/bin and JADE with archive overall, matches JADE without archive, but jSO beats it on five of eight 10-D and six of eight 30-D functions.The MAXNFE comparisons are reported for CEC’13 at n = 10 and n = 30.Source: A. The Comparison Results on the… · pp. 7, 9, Table IV · p. 8, Table V · p. 8
  • On 10-D functions, LDE beats DE on six and JADE with and without archive on three and two; at 30-D it beats DE on five and both JADE variants on f25, f26, and f27, but loses to jSO on six.Source: A. The Comparison Results on the… · p. 9
  • By APS, jSO ranks ahead of LDE, which ranks second and ahead of the other compared algorithms.APS averages performance scores across test functions; lower APS indicates better performance.Source: A. The Comparison Results on the… · p. 9, Table VI · p. 9
  • For f21, high-quality individuals generally have smaller F values and middle-quality individuals higher CR values under the learned controller, while jSO’s values become scattered.The figure groups the population’s fitness into three clusters and averages associated F and CR values.Source: A. The Comparison Results on the… · p. 9, Figure 4 · p. 9

B. The Comparison Results on the CEC’17 Test Suite

On CEC’17, LDE ranked third overall after training on CEC’13 functions. Its relative performance varied by dimension, with jSO and HSES stronger at 30-D.

B. The Comparison Results on the CEC’17 Test Suite

V. SENSITIVITY ANALYSIS

The sensitivity analysis examines how hidden-layer neuron size and population size affect LDE. Results show that the best neuron size varies across functions and that population and neuron sizes interact.

V. SENSITIVITY ANALYSIS

  • LDE performance varied with hidden-layer neuron size, and a larger size did not consistently improve results across functions.The 10-D experiment tested sizes from 500 to 3,000 in increments of 500 with population size fixed at 50.Source: §V · p. 12
  • For different functions, the best result was obtained with different neuron sizes.The study examined the final eight CEC’13 functions at 10-D and 30-D.Source: §V · p. 12
  • At 30-D, population size and neuron size together had a complex effect on learned-controller performance.Five controllers with different population and neuron sizes were trained on CEC’13 f1–f20 and tested on f21–f28.Source: §V · p. 12

VI. RELATED WORK

Prior reinforcement-learning approaches adapt evolutionary algorithms using online search information, while this paper learns DE parameter control from optimization experiences. The conclusion reports competitive benchmark performance alongside training and generalization limits.

VI. RELATED WORK

  • Related GA studies use Q-learning or SARSA to regulate parameters or select reproduction operators, with distinct state, reward, and update designs.One cited approach combines Q-learning and SARSA to regulate four GA parameters.Source: §VI · p. 12
  • Earlier RL-based controllers use online information from a single run on one test problem, whereas this approach learns from optimization experiences across training functions.The paper also distinguishes existing discrete-state/action Q-learning or SARSA methods from its policy-gradient approach to learning a stable policy.Source: §VI · p. 12
  • DE-DDQN is identified as the closest similar approach: it learns over training functions but uses double deep Q-learning to select mutation operators.Its neural network receives defined features as states at each generation.Source: §VI · pp. 12–13

VII. CONCLUSION

  • The proposed LDE models parameter control as an MDP, uses an LSTM controller learned by policy gradient, and applies the controller to new test problems.CEC’13 functions were used for training, followed by evaluation on CEC’13 and CEC’17 suites.Source: §VII · p. 13
  • LDE was reported as very competitive with the compared algorithms on the evaluated benchmark suites.The conclusion presents this result as evidence of the proposed controller’s effectiveness.Source: §VII · p. 13
  • Training the controller for 30-D problems required considerable CPU/GPU resources, and performance on unrelated functions is unpredictable and may be limited.The training and test functions share features because they use the same basic functions; the learned algorithm also has greater time complexity than compared algorithms.Source: §VII · p. 13
  • Future work includes testing LDE on real-world optimization and engineering problems and exploring other networks, statistics, and RL applications.The authors also propose studying adaptive mutation/crossover strategies and learning hyperparameters for evolutionary algorithms.Source: §VII · p. 13
Loading 2102.03572v1…