Adaptive Structural Hyper-Parameter Configuration by Q-Learning

2020·arXiv

Abstract

I. INTRODUCTION

Evolutionary algorithm (EA) is an important research area in computation intelligence. Over several decades, fruitful research studies have been conducted. Example EAs, such as differential evolution (DE) [1], [2], particle swarm optimization (PSO) [3], CMA-ES [4] and many others, have attracted a great amount of attentions.

The hybridization of EAs has also achieved great success, such as DE/EDA [5], [6], SaDE [7], jSO [8] and others. The aim of hybrid EAs is to take advantages of the pros of different EAs and to compensate the cons of these EAs for favorable algorithmic performance. Very recently, the combination of univariate sampling and CMA-ES [4], [9], called HSES [10], has achieved the best performance for the CEC 2018 test functions.

In all the developed EAs, these always exist more or less hyper-parameters. Those hyper-parameters can be categorized in two dimensions as shown in Fig. 1. In one hand, the hyper-parameters can be time variant or invariant. For instances, the scaling factor F and crossover rate CR can be either fixed like in traditional DE, or adaptively changed such as in JADE [11]. Since the scaling factor and crossover rate are directly responsible for creating new solutions through arithmetic and/or logic operations, they are also categorized as “numerical hyper-parameters”. On the other hand, for hyper-parameters such as the population size, the integer p in the current-to-best DE operator [8], the tournament size and

Fig. 1. Categories of hyper-parameters in EAs.

others, are categorized as “structural hyper-parameters” since they do not directly involve in the solution creation procedure. The performance of an EA depends not only on its core components including recombination and selection operations, but also on its hyper-parameters. Tuning hyper-parameter for optimal algorithmic performance can be cumbersome, timeconsuming and tedious. What’s worse, hybrid algorithms can bring extra structural hyper-parameters. For example, they will require not only the tuning of each composing algorithm’s parameters, but also need to control the resource allocation for each of them. Taking the winner of CEC 2018, HSES [10], as an example, two heuristics including a univariate sampling algorithm and CMA-ES are carried out sequentially. In HSES, except the numerical hyper-parameters used in univariate sampling and CMA-ES, the allocation of resources, or precisely the number of iterations K used by the first univariate sampling, is an important structural hyper-parameter. It could significantly influence the performance of HSES. Algorithms such as Bayesian optimization (BOA) [12], sequential model-based optimization for algorithm configuration (SMAC) [13] and others, can be applied on tuning time-invariant numerical hyper-parameter. For examples, BOA has been successfully applied to tune numerical hyper-parameters in [14] [15]. Interested readers please see [16] for a review of the tuning techniques. In these methods, tuning time-invariant numerical hyper-

parameters is modeled as optimizing black-box optimization problem. Once optimized, the resultant hyper-parameters are fixed during the optimization procedure. However, for time-variant hyper-parameters, we cannot use these methods simply because of the time-dependence.

It is usually beneficial to adaptively set the hyper-parameters during the search procedure in an EA. A great number of EAs with adaptive hyper-parameters have been studied (see [17] for detail). In most of these studies, it is the numerical hyper-parameters that are made time-variant, e.g. the scaling and crossover rate in DE are adaptively updated during the search by summarizing previous information in JADE [11]. Only recently, some EAs proposed to update structural hyper-parameter adaptively, e.g., the population size in jSO [8] is designed to be linearly decreasing.

However, there is no principle way to tune structural hyper-parameters. Their tuning is case-sensitive. For instance, controlling the selection of DE operators in SaDE [7] can be totally different from the switching between univariate sampling and CMA-ES in HSES.

Recall that to adaptively configure numerical hyper-parameters, new hyper-parameters are updated based on learning from previous search history as seen in JADE. The updating can be broadly considered as a learning problem. This perspective can be applied for adaptively tuning structural parameters. To implement this idea, we resort to reinforcement learning (RL) by modeling the tuning procedure as a finite-horizon Markov Decision Process [18].

In this paper, we propose to use RL, specifically the Qlearning algorithm, to tune the structural hyper-parameter of HSES, i.e. the number of iterations used by the first univariate sampling. In the rest of the paper, Section II briefly review HSES, and concepts and algorithms of RL. The proposed structural hyper-parameter tuning algorithm, called Q-HSES, is presented in Section III. Section IV summarizes experimental results on the CEC 2018 test functions in comparison with HSES. The conclusion is given in Section V.

II. PRELIMINARIES

A. Reinforcement learning

RL has been playing an important role in the thriving of artificial intelligence. It aims to find a policy so that an agent is able to take optimal actions in an environment. Fig. 2 shows a typical representation of RL model. It can be modeled as a Markov decision process (MDP). Consider a finite-horizon MDP with discrete and finite state and action space defined by the tuple where denotes the state space, the action space, the initial distribution of the state, the reward, and T the time horizon, respectively. At each time t, there is an and a transition probability , where denotes the transition probability of conditionally based on and . The policy , where is the probability of choosing action when observing current state . The goal is to find a policy so as to maximize the expectation of total

Fig. 2. The basic idea and elements involved in a RL model, where s, a, r represents state, action and reward, respectively, and represents the policy and state transition probability, respectively.

rewards where denote time-step dependent weighting factors. In practice, weighting factors is always set to exponential power of constant i.e. .

There are many RL algorithms, such as Q-learning, sarsa, deep Q network and policy gradient (interested readers please see details in [19]), which are developed to deal with different environments. Among them, Q-learning is developed for MDP with discrete state and action space, based on value iteration. Its core idea is to use the action-value function Q(s, a) to estimate the reward in case and , which is defined as

As A is discrete and finite, policy can be regarded as

The Q-learning algorithm can be summarized in Alg. 1 (taken from [19]).

In Alg. 1, a maximum number (maxE) of epoch is used to learn the action-value function Q(s, a) for each and is initialized to be zero (line 1). Then at each epoch, a trajectory is obtained by applying the -greedy policy (line 3, which means in probability , action is taken as and in probability , action is randomly chosen from A. Based on the state and action at time t, the action-value function is updated according to the equation in line 6. The algorithm terminates at the maxE epoch.

Fig. 3. The schematic diagram of HSES and Q-HSES.

B. HSES

HSES [10] is the winner algorithm in CEC 2018 competition. Its schematic diagram can be seen in the left plot of Fig. 3. The pseudo-code of HSES is shown in Alg. 2.

In Alg. 2, the function UniSamplingperforms univariate sampling for iterations and returns a population of solutions with relatively high qualities, the number of fitness evaluations used (NFE), and the best solution found by univariate sampling. is then used as the initial population of CMA-ES with parameter . CMA-ES returns a population , the fitness evaluations used NFEand the best solution it found . Once CMA-ES has terminated, the function Detectis used to find which variables should be fixed for the next univariate sampling. In the new univariate sampling, a maximum of iterations is carried out so that the whole number of evaluations is no more than the given constant MaxNFE. Interested readers please refer to [10] for algorithm details. The algorithm returns the best solution found at termination.

In HSES, except the parameters like population size N in univariate sampling and the parameter of CMA-ES, the switch iteration is vital to algorithmic performance. It determines how much resources are allocated for the first univariate sampling, which reflects the tradeoff between exploration and exploitation.

In our study, we care only on how to determine the structural hyper-parameter . The other hyper-parameters, such as N and , are fixed as used in the original paper of HSES.

III. METHOD

We model the tuning procedure of structural hyper- parameters as a finite-horizon MDP with discrete state and action space and horizon T. At each state, the RL agent chooses an action, i.e. switching to CMA-ES or not. If the action is not to switch, univariate sampling will be carried out. The next state will be observed. Otherwise, if the action is to switch to CMA-ES, the agent will stop and execute the rest of HSES (line 3-5 of Alg. 2).

In the following, we shall present the components used in RL, including state, action, transition probability and reward. We denote the minimum function value obtained up to the k-th iteration.

State: In our RL, includes two parts and which are defined as follows:

and . In the definition, is used to measure the difference between the best function values in adjacent 20 steps; measures the descent rate from the first population. We use 10 times t because we don’t want to judge switching or not every iteration but every 10 iterations.

make the state space discrete and finite, we divide the range to

for , and for .

Action: The action space is {0, 1}. That is, the agent can either choose to switch (action equals to 1) to CMA-ES or do not switch (action equals to 0).

Transition probability: When t < T and is 0, the next state is defined as mentioned above. When or is 1, will be the “terminal state”. Here T is the horizon. It constrains the maximum iterations that can be used by univariate sampling. In this paper, we set T = 20.

Reward: In the terminal state, the reward will be the logarithm of the minimum function value found by the search. Otherwise, the reward is set to zero since the algorithm’s performance is not known before the terminal state.

A. The proposed Q-learning based HSES

Given above definitions, the Q-learning algorithm, i.e. Alg. 1, can be used to train the agent. However, directly using Q-learning can result in the following three problems. First, to make Q-learning converge, the maximal number of epoch, MaxE, is generally large. This means HSES needs to be executed many times, which is not acceptable. Second, in Q-learning, the action value function is updated at each trajectory based on current policy. Since EAs are stochastic, the performance of one trajectory is not stable, which means the learning of the action value function is not efficient. Third, the trajectory created based on current policy is unbalanced (as using -greedy policy). That is, some states may be rarely observed in the trajectories. This can make the learning converge slowly.

Our training process is summarized in Alg. 3. In line 4, we generate T trajectories Tr. Each trajectory corresponds to the average of 51 runs of the HSES algorithm with switch iteration to be for a given training function. With these trajectories, the action value function Q(s, a) is updated as seen in line 8. To eliminate the influence of different function scales, an auxiliary action-value function metais applied. It records the rank relationship between Q(s, 0) and Q(s, 1) from line 12 to line 19 for each training function. After training, the policy is set to be meta(line 21). Note that for a state s, metametameans that there is no evidence to tell which action (switch or not) is better. If this is the case, an action will be randomly chosen.

The reason that the proposed training process can handle the mentioned learning problems is simply because the created trajectories Trcontains all possible situations for the switch iteration. That is, the performance of HSES with every possible switch iteration from 10 to 200 is observed, which is measured by the average of 51 HSES runs. This can make the training steady and the observed states balanced. Since we do not need to sample new trajectories during training, the training efficiency can be guaranteed.

Once the agent is learned (i.e. the optimal is found), it is embedded within the HSES algorithm. The resultant algorithm is called Q-HSES. The right plot of Fig. 3 shows the digram of Q-HSES. Alg. 4 summarizes the algorithm. In the algorithm, after univariate sampling runs for M iterations (line 3), the current state is computed (line 4) and an action is taken (line 5). If action is 0, it returns to the univariate sampling. The procedure repeats until action is 1, which means that the algorithm switches to CMA-ES. The rest operations are the same as in Alg. 2.

IV. EXPERIMENTS

In this paper, the 29 functions in the CEC 2018 competition (except ) is used as benchmark. Metrics, including the rank and average function value, used in the competition are adopted for comparison. The proposed algorithm, Q-HSES, is compared with HSES.

A. Training

Training: The CEC 2018 test functions contain unimodal functions and , multimodal functions , hybrid functions and composition functions . Our training functions cover these 4 function types. 11 CEC 2018 functions () are used as the training functions. Parameters used in the Qlearning are set as and MaxE = 100, 000. As 50D and 100D problems are more complicated and the performance of algorithm is worse than 10D and 30D, the division to the range of is a little bit forward. For 50D and 100D, the interval node of is multiplied by 0.05 and 0.025. Except the switch iteration, the other hyper-parameters are held the same as HSES (such as population size and the parameters of CMA-ES).

Testing: Q-HSES is used to optimize all the 29 functions of CEC 2018.

B. Comparison Results

In the original HSES, the switch iteration is fixed to be 100. The statistics of the obtained results of Q-HSES on test functions of CEC 2018 are summarized in Tables I,II,III and IV for 10D, 30D, 50D and 100D, respectively, in which the best, worst, mean and std. values are given.

Each of the statistics is obtained over 200, 100, 51, 51 runs on the error values (i.e. the difference between the obtained optimum and the known global optimum). When the error values are smaller or equal to , they are treated as 0.

TABLE I RESULTS IN 10D FOR 200 RUNS OBTAINED BY Q-HSES.

The rank sum hypothesis test is carried out at 5% significance level between the results obtained by Q-HSES and HSES. The results are summarized in Table V. From Table V, we see that Q-HSES performs significantly better than HSES in general for all dimensions.

Table VI shows the average function values obtained for the test functions in four different dimensions. It is clear that the average function value obtained by Q-HSES is smaller than HSES in 10D, 30D, 50D, but a little bit greater in 100D.

Overall, we may conclude that the proposed control algorithm based on Q-learning can indeed find a better structural hyper-parameter setting for HSES.

TABLE II RESULTS IN 30D FOR 100 RUNS OBTAINED BY Q-HSES.

TABLE III RESULTS IN 50D FOR 51 RUNS OBTAINED BY Q-HSES.

TABLE IV RESULTS IN 100D FOR 51 RUNS OBTAINED BY Q-HSES.

TABLE V RANK COMPARISON OF Q-HSES AND HSES

C. Validation

The switch iteration is fixed in HSES as 100. To validate the performance of the learned agent, Q-HSES is compared with HSES on different switch iterations in 10D. Table VII summarizes the results, in which the hypothesis test results at 5% significant level are listed. The indices of the functions that Q-HSES performs better are also shown. The indices of the functions that belong to the training functions are typeset in bold.

From Table VII, it is seen that with different switch iterations, Q-HSES performs better than HSES in general: Q-HSES performs better on more functions than HSES. This indicates that the learned agent works well. It is seen that among the functions that Q-HSES performs better, half of them do not belong to the training functions. This indicates the learned agent generalizes well.

D. Training Process

To verify the training process is convergent, we define a criterion named “the rate of action value change”. As the

TABLE VI FUNCTION VALUE COMPARISON OF Q-HSES AND HSES

TABLE VII VALIDATION OF Q-HSES

state space is divided into 36 intervals (6 intervals for and 6 intervals for ) and action is {0, 1}, then the action-value function Q(s, a) is a matrix. Regarding it as a 72D vector, the rate of action value change is defined as the Frobenius norm between two adjacent epoch:

where and is the action value function at the eth and (e + 1)th epoch, respectively. This definition can be used to show how the training goes. Fig. IV-D shows the rates of change for the training functions. From the figure, it is clear that the training process of action value function is convergent. It also shows the range of the changes is very much different among different functions which roots from different function scales.

V. CONCLUSION

In this paper, we first categorized the hyper-parameters of EAs from two perspectives. We then proposed to model the adaptive control of the structural hyper-parameters as a Markov decision process. Based on the formalization, Qlearning was applied to learn an agent for time-variant hyper-parameter tuning for the winner algorithm of CEC 2018, called HSES. We proposed the fundamental elements of the Q-learning for the agent, including states, action and reward. In the experiments, we trained the agent on a selection of functions from the CEC 2018 competition. By embedding the learn agent, Q-HSES was developed. The comparison between Q-HSES and HSES showed that the structural hyper-parameter in HSES controlled by the learned agent performs generally better than HSES.

As a first attempt to use Q-learning for hyper-parameter controlling, the experiments showed that the proposed method is promising. In the future, we intend to combine RL to advancing the development of evolutionary algorithms.

VI. APPENDIX

In this section, we briefly introduce the concepts used in reinforcement learning. Basically, RL aims to maximize the

Fig. 4. The rate of function value change against epoch for the 11 training functions.

expected cumulative reward, i.e. . First define

The expectation of measures the benefit on time t. Further, we define the state-value function v(s) and action-value function Q(s, a) as follows:

Without loss of generality, set , we have the following Bellman’s equality:

For action value function, we also have the Bellman’s formula:

For optimal policy , we have:

which induces the optimal Bellman equation:

REFERENCES

[1] K. V. Price, An Introduction to Differential Evolution. GBR: McGrawHill Ltd., UK, 1999, pp. 79–108.

[2] S. Das and P. N. Suganthan, “Differential evolution: A survey of the state-of-the-art,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 4–31, 2011.

[3] R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, pp. 39–43.

[4] N. Hansen and A. Ostermeier, “Completely derandomized self adapta- tion in evolution strategies,” Evolutionary computation, vol. 9, no. 2, pp. 159–195, 2001.

[5] J. Sun, Q. Zhang, and E. Tsang, “DE/EDA: a new evolutionary algorithm for global optimization,” Information Sciences, vol. 169, no. 3, pp. 249– 262, 2005.

[6] J. Sun, “Two-stage EDA-based approach for all optical wdm mesh network survivability under srlg constraints,” Applied Soft Computing, vol. 11, pp. 916–926, 2011.

[7] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Transactions On Evolutionary Computation, vol. 13, no. 2, pp. 398–417, 2009.

[8] J. Brest, M. S. Maucec, and B. BOskovic, “Single objective realparame- ter optimization: Algorithm jSO,” in Proceedings of the IEEE Congress on Evolutionary Computation, 2017, pp. 1311–1318.

[9] N. Hansen, S. Muller, and P. Koumoutsakos, “Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES),” Evolutionary computation, vol. 11, no. 1, pp. 1–18, 2003.

[10] G. Zhang and Y. Shi, “Hybrid sampling evolution strategy for solving single objective bound constrained problems,” in Proceedings of the IEEE Congress on Evolutionary Computation, 2018, pp. 1–7.

[11] J. Zhang and A. C.Sanderson, “JADE: Adaptive differential evolution with optimal external archive,” IEEE Transactions On Evolutionary Computation, vol. 13, no. 5, pp. 945–458, 2009.

[12] P. I. Frazier, “A tutorial on bayesian optimization,” arXiv preprint arXiv:1807.02811, 2018.

[13] F. Hutter, H. H. Hoos, and K. Leytonbrown, “Sequential model-based optimization for general algorithm configuration,” in Proceedings of International Conference on Learning and Intelligent Optimization, 2011, pp. 507–523.

[14] I. Roman, J. Ceberio, A. Mendiburu, and J. A. Lozano, “Bayesian optimization for parameter tuning in evolutionary algorithms,” in Proceedings of the IEEE Congress on Evolutionary Computation, 2016, pp. 4839–4845.

[15] C. Huang, B. Yuan, Y. Li, and X. Yao, “Automatic parameter tuning using bayesian optimization method,” in Proceedings of the IEEE Congress on Evolutionary Computation, 2019, pp. 2090–2097.

[16] C. Huang, Y. Li, and X. Yao, “A survey of automatic parameter tuning methods for metaheuristics,” IEEE Transactions on Evolutionary Computation, pp. 1–16, 2019. [Online]. Available: 10.1109/TEVC. 2019.2921598

[17] A. Aleti and I. Moser, “A systematic literature review of adaptive pa- rameter control methods for evolutionary algorithms,” ACM Computing Surveys, vol. 49, no. 3, Oct. 2016.

[18] M. L. Puterman, Markov decision processes: Discrete stochastic dynamic programming. John Wiley and Sons, Inc., 1994.

[19] R. Sutton and A. Barto, Reinforcement Learning: An Introduction. The MIT Press, 1998.

Designed for Accessibility and to further Open Science