A novel intelligent hyper-heuristic algorithm for solving optimization problems

Abstract

In recent years, solving combinatorial optimization problems involves more complications, high dimensions, and multi-objective considerations. Combining the advantages of other evolutionary algorithms to enhance the performance of a unique evolutionary algorithm and form a new hybrid heuristic algorithm has become a way to strengthen the performance of the algorithm effectively. However, the intelligent hybrid heuristic algorithm destroys the integrity, universality, and robustness of the original algorithm to a certain extent and increases its time complexity. This paper implements a new idea “ML to choose heuristics” (a heuristic algorithm combined with machine learning technology) which uses the Q-learning method to learn different strategies in genetic algorithm. Moreover, a selection-based hyper-heuristic algorithm is obtained that can guide the algorithm to make decisions at different time nodes to select appropriate strategies. The algorithm is the hybrid strategy using Q-learning on StudGA (HSQ-StudGA). The experimental results show that among the 14 standard test functions, the evolutionary algorithm guided by Q-learning can effectively improve the quality of arithmetic solution. Under the premise of not changing the evolutionary structure of the algorithm, the hyper-heuristic algorithm represents a new method to solve combinatorial optimization problems.

Keywords

Arithmetic solution combinatorial optimization genetic algorithm hyper-heuristic algorithm Q-learning

1 Introduction

The heuristic algorithm is a new type of computing mode with a strong search ability that is used to solve nondeterministic polynomial (NP) problems in various fields and has been actively implemented [1, 2]. Meta-heuristic scheduling involves algorithms such as the genetic algorithm (GA) [3, 4], particle swarm optimization (PSO) [5], and ant colony optimization (ACO) [6, 7]. It has been widely used in tasks such as task scheduling, control strategy, path planning, and multi-objective solving [8 –10]. With the in-depth study of meta-heuristic algorithms, the defects of this type of algorithm have been gradually discovered (e.g., premature convergence to non-global optimal solutions, excessive search time, too much sensitivity to parameters, lack of effective iterative termination conditions). In general, to further exploit the advantages of this type of algorithm and avoid defects, researchers have improved some steps in the algorithm or combined the advantages of other algorithms’ strategies in the algorithm. For example, Khatib et al. [11] developed the GA and proposed the stud genetic algorithm (StudGA). The main improvement is that the best individual in the contemporary population (called the stud) is exchanged with the rest of the individuals at each time, which facilitates the rapid sharing of useful genetic information. The principle of StudGA algorithm is simple, and its optimization ability has been confirmed [12].

For some standard meta-heuristic algorithms, there are more reasonable strategies. For example, in the classical evolutionary GA, there are exchange methods such as single-point exchange and multi-point exchange in the chromosome exchange link. The use of these methods is reasonable for the entire algorithm in the optimization process; the difference is that the degree of exploration of the solution space is different. For the target problem, determining when to use a particular strategy is a combinatorial optimization problem. The hyper-heuristic algorithm starts from an empty solution, formulates control strategies or feedback values from the high-level expert level, and gradually establishes a feasible solution to the problem from a set of pre-prepared low-level construction heuristic algorithms (specific problem areas) [13]. In the heuristic algorithm of the low-level structure, different rational strategies are used to construct the low-level space, which reduces the space cost and time complexity of building the low-level area. This method is consistent with the evolutionary system of the algorithm, and it is easier to obtain better solutions than the original algorithm. In recent years, machine learning has become a research hotspot. Researchers hope to improve the problems that require human decision-making by using machine learning methods, making machines more “intelligent” and algorithm performance more “excellent” and achieving the lowest reduction in errors caused by social factors. The intensive learning method is based on unsupervised learning and is a trending research direction in the field of machine learning [14]. Among the methods, Q-learning [15] is widely studied and applied by researchers as a typical intensive learning method. The algorithm is based on Markov decision processes (MDPs) [16], which can effectively solve the problem of how agents make decisions in complex environments. In general, the Q-learning process uses the Monte Carlo method to train, obtain potential Q-values between different states, and finally make decisions based on the trained Q-table and the various states in which they are located. When the decision-making options are limited, the use of reinforcement learning methods to learn decisions under different scenarios (states) is reliable and stable. In general, if the system can switch states and has appropriate choices in different states, the relevant decisions are often better suited to the currentsystem.

Many researchers have conducted significant work on hyper-heuristic algorithms. For example, Wang Ling et al. [17] noted that coevolution has become an effective way to improve the performance of evolutionary algorithms, such as population coordination, proper coordination, algorithm coordination, strategy coordination, and human-machine coordination. In general, collaborative design methods, improvement points, and characteristic points often require a detailed analysis and a large number of experiments to verify, and they increase the complexity of the algorithm and consume more time. Islam et al. [18] used the Q-learning method to learn to use different dynamic voltage and frequency scaling (DVFS) techniques in different scenarios and relied on learning to provide enough technology to scene mapping, which was obtained on multi-core chips. A better solution for each indicator.

Choong et al. [19] proposed a heuristic architecture that uses the enhanced Q-learning technique to design a hyper-heuristic model automatically. Correctly, the Q-learning hyper-heuristic model is used to select the appropriate components. Finally, the proposed algorithm is validated on six benchmark examples. The experimental results show that the method is comparable with other models. To adapt to the dynamic software engineering environment, Shen et al. [20] proposed a multi-objective two-archive memetic algorithm based on Q-learning (MOTAMAQ) to actively re-schedule. The solves the problem of software project scheduling. In this paper, the Q-learning method is used to learn the most suitable global and local search methods in different software project environmental states. Finally, the experiment compares other heuristic algorithms, and the results show that the algorithm has better convergence and higher quality solutions.

Koulin and Anagnostopoulos [21] proposed a Tabu search-based hyper-heuristic algorithm (THH) to solve the resource balance problem under resource constraints. The algorithm uses a hyper-heuristic algorithm to control a group. A low-level heuristic modifies the priority of a selected activity by performing simple operations such as “replace” and “swap”. According to the application in three engineering examples, the algorithm has good resource optimization performance. Dokerog and Cosar [22] proposed a multistart hyper-heuristic algorithm (MSH-QAP) based on a grid for high-performance multistart. In the first phase of the algorithm, the most appropriate (meta) heuristic approximate optimal parameters are selected by using an adaptive parameter setting method for a given problem instance; in the second phase of the algorithm, if the optimal solution cannot be found, then parallel processing selects the best performing (meta) heuristic on the grid (its parameter settings are fine-tuned) and performs multiple starts to improve the quality of the solution. The experimental results show that the total deviation of the algorithm to solve the problem instance is 0.013 percent on average. Qian et al. [23] proposed a multi-objective hyper-heuristic algorithm (MOHH) for universality, which considers carbon emission factors in location routing problems and establishes carbon emissions and a multi-objective location routing problem (LRP) model that combines total costs. In the MOHH framework, LRP-related operations are constructed as low-level heuristics, and different high-level strategies are designed. Experiments show that the MOHH algorithm can better solve the multi-objective problem of LRP and can quickly find a better solution and improve the search efficiency and stability of the algorithm. Yao et al. [24] proposed a multi-objective hyper-heuristic framework for pedestrian path planning in smart cities. In the search framework, a set of low-level heuristic algorithms are designed to generate new routes, and the reinforcement learning algorithm is used to select better low-level heuristics to speed up the search. The experimental results show that the algorithm has a faster processing speed than other comparison algorithms, and a more than 80 percent Pareto optimal solution can be obtained in the large-scale road network.

The evolutionary algorithm is considered as a transition between different states in the time dimension, and different states have different decisions. In this way, the optimal determination between different states can be ascertained through the Q-learning method. Based on this design idea, this paper uses the Q-learning algorithm to learn the different strategies existing in the evolutionary algorithm (taking the StudGA algorithm as an example) and obtains a new type of selection that can guide the algorithm to choose the appropriate strategy for decision-making at different time nodes. Hyper-heuristic algorithm.

In this paper, we propose a new hyper-heuristic algorithm, a hybrid strategy using Q-learning on StudGA (HSQ-StudGA) combined with different strategies to solve the problems encountered in explaining the extreme values in the mathematical test function. The experimental results show that the StudGA algorithm guided by Q-learning can effectively improve the quality of the solution, provide a new combination method for the hybrid evolutionary algorithm to solve the optimization problem without changing the evolutionary structure of the original algorithm and help promote the development of hyper-heuristic algorithms moreintelligently.

The main contributions of this paper are as follows:

First, to solve the optimization problem, a hyper-heuristic algorithm is proposed by combining the heuristic algorithm with reinforcement learning technology.

Second, combining the advantages of a genetic algorithm and Q-learning, the HSQ-StudGA algorithm formed has a faster rate of convergence and can obtain higher quality solutions.

Finally, since the environment of Q-learning decision is always changing, the problem of Q-value jitter is solved by using a greedy strategy.

The rest of the paper is organized as follows. The related work is introduced in Section II. The model framework is shown in Section III. The experiments and analysis are presented in Section IV. The conclusion is performed in Section V.

1.1 Overview of basic methods of genetic algorithms

A genetic algorithm is a computational model that simulates the natural evolution of Darwin’s biological evolution theory and the biological evolution process of the gene mechanism. It is a method to search for optimal solutions by affecting natural evolutionary processes. The genetic algorithm begins with a population. After initial generation of the population by encoding, according to the principle of survival of the fittest, the evolution of generations produces increasingly better approximate solutions in each generation and, according to the individual’s fitness in the problem domain, selects the individual and combines the crossover and mutation with the genetic operators of natural genetics to produce a new solution set. This process will result in a population of natural evolution such that the descendant population is more adaptable to the environment than the previous generation, and the best individual in the last generation population is decoded, which can be used as a problem to approximate the optimal solution.

Some hybrid algorithms based on open structures are described in [25] and are used in various fields. The genetic algorithm consists of several steps: initialization, selection, exchange, mutation, and optimal global convergence. The simple and widely used exchange operations are the following: single-point exchange, double-point exchange, multipoint exchange, and uniform exchange [26, 27]. Different exchange methods should be adopted for different application scenarios. Khatib et al. [11] improved the GA and proposed the stud genetic algorithm (StudGA), which is mainly enhanced by using the best individual (called the stud) and the remaining individuals in each contemporary population. Exchange operations facilitate good sharing of useful genetic information. The principle of the StudGA algorithm is simple, and its optimization ability has been confirmed [28]. The genetic algorithm chromosome single-point exchange model is shown in Fig. 1. Specifically, a single-point exchange can be described as follows: in each round of a transaction, take two chromosomes as source chromosomes (also known as parent chromosomes), and exchange some of the genes on both sides of the exchange point to form new offspring. The two-point exchange process is based on the single-point exchange, taking two points to be exchanged, and selecting the middle part of the two chromosome interchanges for transfer. The process is shown in Fig. 2. Different from the above two exchanges, each gene of two chromosomes in the uniform exchange mode has the opportunity to exchange, which can also be called random transfer; the exchange process is shown in Fig. 3.

Fig. 1

Model of single-point crossover.

Fig. 2

Model of double-point crossover.

Fig. 3

Model of uniform crossover.

1.2 Unsupervised learning

At this stage, the most important macrotrend in machine learning is that the algorithm is gradually shifting from a supervised learning mode to an unsupervised learning mode.

The realization of most traditional machine learning relies on supervised learning. In other words, they are only useful when training with a large number of labeled training data. While supervised learning works well, the process of collecting and tagging large data sets is time-consuming, expensive, and error-prone. These challenges become more pronounced as the size of the data set increases. Based on the flaws of supervised learning, unsupervised learning methods have significant advantages because they do not require a large number of training data sets, do not need to be labeled and have excellent training effects. However, in real life, there is often a problem of the lack of sufficient prior knowledge, so the cost of manual labeling is too high. Therefore, this has prompted the machine learning algorithm to change from a supervised learning model to an unsupervised learning model. Q-learning is a typical unsupervised intensive learning method. Through continuous training and updating, the final Q-value is obtained.

2 Models

In this section, we first introduce the process of the genetic algorithm and the StudGA algorithm. Second, we describe the Markov decision process and Q-learning. Finally, we present the hybrid strategy learning model.

2.1 Model of genetic algorithm

The genetic algorithm consists of several steps: initialization, selection, exchange, mutation, and optimal global convergence. The primary process is shown in Fig. 4.

Fig. 4

The process of the genetic algorithm.

The stud genetic algorithm formed by the improvement of the genetic algorithm is to exchange the best individuals (called the stud) in the contemporary population of genetic algorithms with the remaining individuals. The pseudocode of the standard StudGA algorithm containing exchange and mutation operations is shown in Algorithm 1:

Algorithm 1 StudGA Algorithm
Input: Initialize habitat parameters
Output: The best solution and finished
Initialize habitat parameters.
Initialize a random set of habitats that consist of
potential solutions to the given problem.
According to the generated habitats, calculate
the fitness.
if the determined termination conditions are
satisfied, then turn to output the best solution
and finished then
for each habitat, select the best one and combine
another one to generate new children.
for each habitat, execute mutation operation under the
mutation probability.
Traverse every habitat to clear duplication.
Turn to step 4.else
end if

2.2 Reinforcement learning

2.2.1 Markov decision process

Markov decision processes (MDPs) refer to decision makers using Markov theory for optimal decision-making by observing continuous or periodic stochastic dynamic systems [29 –31].

Agents in the environment only make decisions based on the state of the current situation and do not rely on historical information. The agent can observe its own state at each moment and choose a possible action to reach the next state. The symbols used in this section are defined in Table 1.

Table 1
Notations

Notations Descriptions

A A set of available actions

E ₁ The first feasible strategy

E _(1...n) A set of optional policy

P ₁ The chromosome of sequence number 1

P _(1...m) A set of all chromosomes

P _a A probability of making an action in the current state to the next state

Q(s_t,a_t) The expected gain from taking action a in state s at t-moments

Q(s_t+1,a_t) The expected gain from taking action a in state s at the next moment

r _t The reward obtained at t-moment

R _a A feedback function

R _(s,a) A feedback value obtained after the state s performs the action a

S A set of states of the environment

α The learning rate

ɛ The exploration rate

λ The discount factor

Notations	Descriptions
A	A set of available actions
E ₁	The first feasible strategy
E _(1...n)	A set of optional policy
P ₁	The chromosome of sequence number 1
P _(1...m)	A set of all chromosomes
P _a	A probability of making an action in the current state to the next state
Q(s_t,a_t)	The expected gain from taking action a in state s at t-moments
Q(s_t+1,a_t)	The expected gain from taking action a in state s at the next moment
r _t	The reward obtained at t-moment
R _a	A feedback function
R _(s,a)	A feedback value obtained after the state s performs the action a
S	A set of states of the environment
α	The learning rate
ɛ	The exploration rate
λ	The discount factor

MDPs can be defined as a four-tuple of the form < S,A, P_a, R_a>, with S representing a set of states of the environment, A representing a set of available actions, P_a representing a probability of making an action in the current state to reach the next state, R_a representing a feedback function, and R_(s,a) representing a feedback value obtained after the state performs the action.

When executing MDPs, the total reward value for the current action can be calculated:

$R = r_{1} + r_{2} + . . . + r_{n}$ (1)

If considering the composition of the total reward value in the time dimension, the total reward value at the current time t is:

$R_{t} = r_{t} + r_{t + 1} + . . . + r_{t + n}$ (2)

In the dynamic random environment, the influence of the future on the decision at the present moment tends to be smaller as time goes by, so the above equation (2) plus the discount factor can be expressed as:

$R_{t} = r_{t} + λ r_{t + 1} + λ^{2} r_{t + 2} ... + λ^{n - t} r_{n}$ (3)

The finishing equation (3) can be expressed as:

$R_{t} = r_{t} + λ (r_{t + 1} + λ (r_{t + 2})) = r_{t} + λ R_{t + 1}$ (4)

The action that obtains the optimal decision in the current state is the action with maxR_t+1.

2.2.2 Q-learning

Q-learning is an intensive learning framework based on MDPs that can make optimal action decisions in a limited MDP environment. The working mechanism is continuous trial and error in the background, and by obtaining a reasonable feedback value, the Q-value of the state that arrives after performing different actions is learned, and the final converged Q-table is obtained. In a given state, the agent queries the Q-table for the maximum Q-value of the current state and performs the corresponding action. The Q-learning model includes an agent, a rule set S, and an available state action set A, and all learned information is stored in the Q-table.

The agent makes the action aɛA according to the value in the Q-table. The update process of the Q-value is based on the Monte Carlo estimation method, that is, by simulating random selection, selecting the appropriate rule to obtain the feedback value, then choosing the proper round learning rate through the accumulated return of each round, and calculating the arrival to the next state. The possibility exists to update the current state to an estimate of the future state.

The variable learning ranges from [0-1], which controls the learning weight per round. The closer the value is to 0, the more the agent pays attention to the current reward. Conversely, the closer the cost is to 1, the more the agent pays attention to the future reward. The Q-learning update formula is shown in equation (5):

$\begin{matrix} Q (s_{t + 1}, a_{t}) = & Q (s_{t}, a_{t}) + \\ α [r_{t + 1} + λ max Q (s_{t + 1}, a) - Q (s_{t}, a_{t})] \end{matrix}$ (5)

The pseudocode form of the Q-learning algorithm is shown in Algorithm 2:

Algorithm 2 Q-learning Algorithm
Input: Random states
Output: Q-table
Initialize Q (s, a) arbitrarily.
repeat
Initialize current state.
Choose action using policy derived from
Q (e . g . , ɛ - greedy, ɛɛ (0, 1)).
Take action a, observe r,s′.
Update Q (s, a) with Equation (5).
s′->s.
Until end(s=terminal)

2.3 Hybrid strategy

2.3.1 Learning process of HSQ-StudGA model

In the critical operations of evolutionary algorithms to explore the solution space, the exchange operation of the algorithm is the most effective means to explore the solution space. According to the introduction in the previous section, this paper takes the StudGA algorithm as an example.

The use of the Q-learning method must clarify the representation of the current state. In the StudGA algorithm, this paper uses the time plus action as the state of the current exploration. In the different exchange modes of StudGA, this paper chooses three exchange modes that perform well and are simple to implement, namely, single-point crossover, double-point crossover, and uniform crossover; they represent three different actions, and the three actions are numbered 0, 1, and 2. Thus, the current state s₁ can be expressed as s₁ = (1, 0), indicating that the current algebra is 1, the action is 0. Assuming that the time (evolution algebra) is 100 and the action space is 3, the size of the solution space s is approximately 3³³ (the next state at time point 1 can only go to time point 2). The maximum number of different states is 100 × 3. It can be known that the size of the Q-table is (300 × 300), which is within the acceptable range of computer storage and calculation.

The Q-learning algorithm is in the stage of acquiring environmental information, and the most important thing is to obtain enough random states as input. Appropriate feedback values can capture the process of securing decision values in different states in the process of trial and error and the optimal decision in different states. In the hybrid strategy, after the current agent selects the action, the two chromosomes adopt the corresponding exchange mode according to the chosen work. According to the optimal cost value obtained by the current algebraic exchange, an appropriate feedback r value is received, and the feedback value is directly related to the optimal amount of each round. The algorithm proposed in this paper uses the offline learning method to obtain enough training data from the solution space for training the Q-table. To facilitate the convergence of the numerical function, the design of the feedback value is as follows: the slope of the optimal solution of each generation is greater than the slope of the optimal solution of the previous generation. Thus, from the current state s, action a is made, the feedback value r is obtained, the next state s′ is observed, the Q-table is updated using equation (5), and the update operation is completed. The update process is shown in Fig. 5.

Fig. 5

Learning process of HSQ-StudGA system.

2.3.2 Model of HSQ-StudGA algorithm

Without loss of generality, this paper proposes a model designed to have multiple options, as shown in Fig. 6. In the figure, the set E_(1...n) represents an optional policy set, E₁ represents the first feasible strategy, n possible approaches constitute a viable policy set, and the set P_(1...m) represents all chromosomes, where P₁ represents a chromosome of sequence number 1.

Fig. 6

Model of HSQ-StudGA algorithm.

The pseudocode form of the HSQ-StudGA algorithm is shown in Algorithm 3.

Algorithm 3 HSQ-StudGA Algorithm
Input: Initialize habitat parameters
Output: The best solution and finished
Initialize habitat parameters.
Initialize the trained Q-table.
Initialize a random set of habitats that consist of
potential solutions to the given problem.
According to the generated habitats, calculate the fitness.
If the determined termination conditions are satisfied,
then turn to output the best solution and finished then
Using current state s to get the action a in Q-table
to guide the crossover part.
for each habitat, select the best one and combine
another one to generate new children.
for each habitat, execute mutation operation
under the mutation probability.
Traverse every habitat to clear duplication.
Turn to step 5.
end If

3 Experiments and analysis

In this section, we mainly describe the experimental setup and conduct the experimental analysis.

3.1 Experimental setup

The system running environment used in this article is Windows 10, and MATLAB 2016b is used as the test platform.

In [32], the performance of the BBO algorithm is verified. The specific parameters of the comparison algorithm used in this paper are consistent with the settings in the paper. Some parameters of the standard StudGA algorithm are shown in Table 2. It should be noted that from the experimental results in [33], the effect of using the uniform exchange method in the exchange part of the StudGA algorithm is better than that obtained by using several other exchange methods. Therefore, to ensure the objectivity of the algorithm, this paper uses the uniform exchange method used in the standard algorithm and implements it in the StudGA algorithm.

Table 2
Benchmark functions

ID Function Dimension Range of each Minimum

f01 Ackley′s function 20 ±30 0

f02 Fletcher-Powell 20 ±π 0

f03 Griewank 20 ±600 0

f04 Generalized Penalized function 1 20 ±50 0

f05 Generalized Penalized function 2 20 ±50 0

f06 Quartic function 20 ±1.28 0

f07 Generalized Rastrigin′s function 20 ±5.12 0

f08 Generalized Rosenbrock′s function 20 ±2.048 0

f09 Schwefel′s Problem 1.2 20 ±65.536 0

f10 Schwefel′s Problem 2.21 20 ±100 0

f11 Schwefel′s Problem 2.22 20 ±10 0

f12 Schwefel′s Problem 2.26 20 ±512 0

f13 Sphere Model 20 ±5.12 0

f14 Step function 20 ±200 0

ID	Function	Dimension	Range of each
f01	Ackley′s function	20	±30
f02	Fletcher-Powell	20	±π
f03	Griewank	20	±600
f04	Generalized Penalized function 1	20	±50
f05	Generalized Penalized function 2	20	±50
f06	Quartic function	20	±1.28
f07	Generalized Rastrigin′s function	20	±5.12
f08	Generalized Rosenbrock′s function	20	±2.048
f09	Schwefel′s Problem 1.2	20	±65.536
f10	Schwefel′s Problem 2.21	20	±100
f11	Schwefel′s Problem 2.22	20	±10
f12	Schwefel′s Problem 2.26	20	±512
f13	Sphere Model	20	±5.12
f14	Step function	20	±200

In this experiment, the performance of the proposed algorithm is tested using a wide range of 14 standard test functions [34 –37]. The names and some parameters of these functions are shown in Table 2.

3.2 Performance evaluation

3.2.1 Q-table convergence

The environment in which Q-learning decisions are used is always evolving, which increases the instability of the system. Using the extensive trial and error method (completely random selection strategy), the Q-values of the two states are always in the jitter state. A wide greedy strategy approach –Q (e . g . , ɛ - greedy, ɛɛ (0, 1)) is used to eliminate this problem. The StudGA algorithm used in this paper has the same parameters as those in the Simon paper. The function labeled f14 in Table 3 is used as the test function for 200 generations of training. The comparison of the Q-value changes of a row in the Q-table is shown in Fig. 7. It can be seen from the figure that both algorithms start to converge from approximately 50 generations. Since the random action is always used in Fig. 7, the Q-value is always in the jitter state. As seen from Fig. 8, when the two algorithms use the greedy strategy, the random actions are stopped at approximately 70 generations. The Q-value tends to be stable. Therefore, this experiment proves that the greedy strategy can effectively accelerate the convergence of Q-values and can increase the stability of the system when the feedback value is unstable. To ensure the objectivity and fairness of the comparison results, the algorithm proposed in this paper also uses the parameters given in Table 3.

Table 3
Experimental parameter settings

Parameters Value

Crossover type of StudGA Uniform

Generation 50

Mutation probability of StudGA 0.01

Number of elitism habitats 2

Number of habitats 50

Parameters	Value
Crossover type of StudGA	Uniform
Generation	50
Mutation probability of StudGA	0.01
Number of elitism habitats	2
Number of habitats	50

Fig. 7

Strategies with random action selection.

Fig. 8

Strategies with greedy action selection.

3.2.2 Convergence

Some test functions f03 and f09 were randomly selected, and the convergence experiments were carried out under the condition that the evolutionary algebra was 50 generations. Each algorithm was run ten times, and the average value was taken. The convergence under test functions f03 and f09 are shown in Figs. 9 and 10, respectively.

Fig. 9

The convergence rate comparison for f03.

Fig. 10

The convergence rate comparison for f09.

Figure 9 depicts the convergence of the HSQ-StudGA algorithm and the StudGA algorithm within 50 generations under the test function f03. As shown, the cost result obtained by the HSQ-StudGA algorithm rapidly drops to a small value within the first 5 generations, starts to flatten in the 20th generation, and basically reaches a convergence state. Additionally, the cost result of the StudGA algorithm.

The rate of decline is significantly slower until the 45th generation converges to essentially the same results as the HSQ-StudGA algorithm.

Figure 10 depicts the convergence of the HSQ-StudGA algorithm and the StudGA algorithm within 50 generations under the test function f09. As seen, the HSQ-StudGA algorithm has a faster convergence speed in the first 20 generations and tends to converge in the 40th generation; the StudGA algorithm has a relatively slow convergence rate. This experiment shows that HSQ-StudGA has better convergence than the traditional StudGA algorithm.

3.2.3 HSQ-StudGA algorithm performance comparison

The primary purpose of this experiment is to show the performance improvement of the hybrid strategy compared to the original algorithm. The evolutionary algebra is selected for 50 generations, and each algorithm runs 50 times under each objective function and is averaged.

Table 5 shows a comparison between the traditional optimal solution and the low historical optimal solution of the HSQ-StudGA algorithm and the StudGA algorithm. As seen from Table 4, all data are normalized, and the minimum value is set to a value of 1.

Table 4
Comparison with HSQ-StudGA and StudGA for the best solution and mean minimum solution

ID HSQ- StudGA(best) StudGA (best) HSQ- StudGA(mean) StudGA(mean)

f01 1.01 1.00 1.05 1.00

f02 1.00 1.60 1.00 1.05

f03 1.00 1.02 1.00 1.14

f04 1.00 1.00 1.00 1.20

f05 1.00 1.23 1.00 1.41

f06 1.10 3.71 1.00 1.26

f07 1.12 1.00 1.10 1.00

f08 1.02 1.00 1.13 1.00

f09 1.00 1.44 1.00 1.05

f10 1.02 1.00 1.03 1.00

f11 1.00 1.03 1.06 1.00

f12 1.00 1.29 1.08 1.00

f13 1.34 1.00 1.21 1.00

f14 1.00 1.50 1.16 1.00

ID	HSQ- StudGA(best)	StudGA (best)	HSQ- StudGA(mean)	StudGA(mean)
f01	1.01	1.00	1.05	1.00
f02	1.00	1.60	1.00	1.05
f03	1.00	1.02	1.00	1.14
f04	1.00	1.00	1.00	1.20
f05	1.00	1.23	1.00	1.41
f06	1.10	3.71	1.00	1.26
f07	1.12	1.00	1.10	1.00
f08	1.02	1.00	1.13	1.00
f09	1.00	1.44	1.00	1.05
f10	1.02	1.00	1.03	1.00
f11	1.00	1.03	1.06	1.00
f12	1.00	1.29	1.08	1.00
f13	1.34	1.00	1.21	1.00
f14	1.00	1.50	1.16	1.00

Table 5

Results of benchmark functions for the best solution

ID	ACO	BBO	DE	ES	GA	PBIL	PSO	StudGA	HSQ-StudGA
f01	2.98E+00	1.51E+00	2.35E+00	4.15E+00	3.47E+00	4.48E+00	3.08E+00	1.00E+00	1.01E+00
f02	2.83E+01	1.51E+00	1.09E+01	3.42E+01	4.49E+00	2.90E+01	4.95E+01	1.60E+00	1.00E+00
f03	2.96E+00	1.84E+00	5.56E+00	3.19E+01	5.36E+00	8.27E+01	2.73E+01	1.02E+00	1.00E+00
f04	1.00E+00	1.90E+02	1.05E+03	1.44E+08	4.36E+02	7.07E+08	1.15E+07	3.65E+01	3.64E+01
f05	1.00E+00	2.79E+01	2.16E+05	3.34E+07	2.03E+04	1.04E+08	3.17E+06	6.43E+00	5.22E+00
f06	8.39E+02	3.19E+01	4.37E+02	2.48E+04	3.13E+02	5.07E+04	4.30E+03	3.71E+00	1.00E+00
f07	9.30E+00	1.42E+00	8.79E+00	1.41E+01	7.58E+00	1.52E+01	1.08E+01	1.00E+00	1.12E+00
f08	4.04E+01	1.09E+00	5.61E+00	4.78E+01	6.85E+00	5.77E+01	4.11E+00	1.00E+00	1.12E+00
f09	6.47E+00	2.57E+00	1.70E+01	2.34E+01	2.85E+00	3.01E+00	2.19E+00	1.44E+00	1.00E+00
f10	2.10E+00	1.00E+00	3.52E+00	4.04E+00	1.76E+00	3.67E+00	4.04E+00	1.08E+00	1.10E+00
f11	1.17E+01	1.48E+00	4.98E+00	1.33E+01	6.79E+00	1.57E+01	9.54E+00	1.03E+00	1.00E+00
f12	1.66E+00	1.97E+00	3.15E+00	3.69E+00	2.61E+00	4.15E+00	2.72E+00	1.29E+00	1.00E+00
f13	4.52E+01	2.76E+00	1.25E+01	1.59E+02	2.72E+01	1.55E+02	5.33E+01	1.00E+00	1.34E+00
f14	1.28E+01	3.13E+00	1.63E+01	1.41E+02	1.34E+01	2.38E+02	6.63E+01	1.50E+00	1.00E+00

It can also be seen from the detailed comparison data of the average historical optimal solution in Table 4 that HSQ-StudGA has achieved nine optimal results in the traditional optimal solution and six in the standard historical optimal solution. From the fluctuation of each of the two deviations from the superior value, HSQ-StudGA has better stability, which shows that when using the Q-learning algorithm to learn two strategies, the two strategies are complementary, thus enabling stronger exploration ability and stability.

Finally, this paper selects a variety of metaheuristic algorithms, such as ACO, BBOS, and ES algorithm, to conduct a detailed evaluation of HSQ-StudGA performance. As seen from Table 5, the HSQ-StudGA algorithm has obtained seven optimal solutions, accounting for half of the entire test algorithm. Due to its inherent advantages, StudGA also has four optimal solutions. The other three optimal solutions are ACO with two optimal solutions and BBO with one optimal solution. From the perspective of the optimal solution distribution, HSQ-StudGA’s ability to explore the optimal solution is significantly stronger than that of other algorithms, further verifying the strength of the hybrid strategy algorithm to investigate the optimal global solution. From the degree of deviation of the normalized value, HSQ-StudGA is significantly better than StudGA in each test set, which shows that the former is more capable of exploring the optimal solution.

Table 6 presents a comparison of the average historical optimal solution. As seen in the table, the performance of HSQ-StudGA and StudGA is the same. The results show that HSQ-StudGA also ensures the stability of the algorithm while achieving the optimal solution. Finally, in terms of the total time normalization result of the given CPU running all test sets, HSQ-StudGA is slightly inferior to StudGA in terms of running time because it needs to find a decision from the Q-table.

Table 6

Results of benchmark functions for the mean minimum solution

ID	ACO	BBO	DE	ES	GA	PBIL	PSO	StudGA	HSQ-StudGA
f01	2.54E+00	1.36E+00	2.04E+00	3.16E+00	2.86E+00	3.30E+00	2.74E+00	1.00E+00	1.05E+00
f02	1.30E+01	1.47E+00	4.99E+00	1.27E+01	5.52E+00	1.15E+01	2.33E+01	1.05E+00	1.00E+00
f03	3.54E+00	2.31E+00	5.86E+00	2.94E+01	1.18E+01	6.53E+01	2.28E+01	1.14E+00	1.00E+00
f04	1.50E+07	2.02E+03	6.68E+04	1.07E+07	1.91E+05	2.68E+07	2.11E+06	1.20E+00	1.00E+00
f05	4.00E+05	5.38E+02	5.32E+03	2.42E+05	1.10E+04	5.06E+05	4.78E+04	1.41E+00	1.00E+00
f06	2.01E+02	1.81E+01	6.98E+01	2.40E+03	2.26E+02	3.25E+03	5.00E+02	1.26E+00	1.00E+00
f07	6.77E+00	1.56E+00	6.19E+00	9.61E+00	6.35E+00	9.94E+00	7.45E+00	1.00E+00	1.10E+00
f08	2.25E+01	1.36E+00	3.38E+00	3.08E+01	5.43E+00	2.43E+01	3.30E+00	1.00E+00	1.13E+00
f09	3.74E+00	1.86E+00	7.15E+00	8.74E+00	3.05E+00	1.12E+01	1.08E+01	1.05E+00	1.00E+00
f10	1.61E+00	1.00E+00	2.05E+00	2.36E+00	1.73E+00	2.38E+00	5.24E+00	1.17E+00	1.20E+00
f11	1.01E+01	1.46E+00	4.35E+00	1.57E+01	7.49E+00	1.25E+01	9.68E+00	1.00E+00	1.06E+00
f12	1.24E+00	1.26E+00	1.63E+00	1.96E+00	1.74E+00	2.13E+00	1.69E+00	1.00E+00	1.21E+00
f13	3.89E+01	2.71E+00	7.24E+00	8.16E+01	2.61E+01	8.33E+01	2.99E+01	1.00E+00	1.21E+00
f14	6.88E+00	3.28E+00	8.33E+00	5.60E+01	1.51E+01	8.99E+01	3.25E+01	1.00E+00	1.16E+00
CPU	4.58	2.12	2.76	1.92	2.13	1.00	2.76	1.49	1.64

4 Conclusion

The hyper-heuristic algorithm is a combination of multiple heuristics or multiple strategies and operations for optimization, and its hybrid strategy design is very critical, and the design corresponds to different problems. To solve combinatorial optimization problems, this paper combines the characteristics of Q-learning and evolutionary algorithms and learns the different strategies existing in the evolutionary algorithm through the Q-learning algorithm. A Q-learning-based heuristic algorithm HSQ-StudGA is proposed. This also allows HSQ-StudGA to acquire skills in interacting with the environment and learning from experience.

In the HSQ-StudGA model, by learning different reasonable policies in the StudGA algorithm, an adaptive hyper-heuristic algorithm that can guide the algorithm to select appropriate strategies for decision-making at different time nodes is obtained. In the experiments, there are 14 standard test functions in StudGA for Q-learning to choose to learn. HSQ-StudGA compares the best solution, the average minimum solution, and the average historical optimal solution with StudGA, and compares the performance with other metaheuristics ACO, BBOS, and ES. The results show that the proposed hyper-heuristic algorithm has a faster convergence speed and can achieve higher quality solutions. Meanwhile, the super heuristic algorithm also improves the search capability of the original algorithm solution and effectively improves the overall quality of the solution.

In the next step, we will enhance the stability of the training process, use more detailed reference values as the states, increase the number of states, further improve the quality of the solution, and apply the method to an actual problem.

Footnotes

Acknowledgment

This work was supported by the Program of National Natural Science Foundation of China (Grant Nos. 62072174, 61502165, 61602170), the National Natural Science Foundation of Hunan Province, China (Grant No. 2020JJ5370).

References

Tong

, Deng

, Chen

, Mei

and Liu

, Ql-heft: a novel machine learning scheduling scheme base on cloud computing environment, Neural Computing and Applications 32 (2020), 5553–5570.

Liang

, Zhang

, Sun

and Huang

, Containment control of semi-markovian multiagent systems with switching topologies, IEEE Transactions on Systems, Man, and Cybernetics: Systems PP(99) (2021), 1–11.

Holland

J.H.

, et al, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press, 1992.

Gao

, Liu

and Kaushik

, Hierarchical multi-agent optimization for resource allocation in cloud computing, IEEE Transactions on Parallel and Distributed Systems 32(3) (2021), 692–707.

Zhan

Z.-H.

, Zhang

, Li

and Chung

H.S.-H.

, Adaptive particle swarm optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 39(6) (2009), 1362–1381.

Zhang

, Wang

, Lin

and Lin

, Continuous-domain ant colony optimization algorithm based on reinforcement learning, International Journal of Wavelets, Multiresolution and Information Processing, 2020.

Dorigo

and Stützle

, The ant colony optimization metaheuristic: Algorithms, applications, and advances, In Handbook of metaheuristics, pages 250–285, Springer, 2003.

Feng

, Luo

, Wang

and Ye

, Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm, Journal on Communication 38(3) (2017), 112–123.

Liu

J.F.

and Li

, Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints, Science China Information Sciences 53(5) (2010), 885–895.

10.

Zhang

, Li

, Liu

and Buyya

, An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in clouds, Distributed and Parallel Databases 36(2) (2018), 339–368.

11.

Khatib

and Fleming

P.J.

, The stud ga: a mini revolution? In International Conference on Parallel Problem Solving from Nature, pages 683–691, Springer, 1998.

12.

Dong

M.G.

, Niu

Q.Z.

and Yang

, Opposition-based stud genetic algorithm, Computer Engineering 35(20) (2009), 239–241.

13.

Xie

, Hou

, Chen

and Kong

, Review of research progress of hyper-heuristic algorithms, Computer Engineering and Applications 2017(14) (2017), 1.

14.

Tian

, Lu

, Zhang

, Tan

K.C.

and Jin

, Solving large-scale multi-objective optimization problems with sparse optimal solutions via unsupervised neural networks, IEEE Transactions on Cybernetics PP(99) (2020).

15.

Watkins

C.J.C.H.

and Dayan

, Q-learning, Machine Learning 8(3-4) (1992), 279–292.

16.

Puterman

M.L.

, Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons, 2014.

17.

Wang

, Shen

J.N.

, Wang

S.Y.

and Deng

, Advances in co-evolutionary algorithms, Control and Decision 30(2) (2015), 193–202.

18.

ul Islam

F.M.M.

, Lin

, Yang

L.T.

and Choo

K.-K.R.

, Task aware hybrid dvfs for multi-core real-time systems using machine learning, Information Sciences 433 (2018), 315–332.

19.

Choong

S.S.

, Wong

L.-P.

and Lim

C.P.

, Automatic design of hyper-heuristic based on reinforcement learning, Information Sciences 436 (2018), 89–107.

20.

Shen

X.-N.

, Minku

L.L.

, Marturi

, Guo

Y.-N.

and Han

, A q-learning-based memetic algorithm for multi-objective dynamic software project scheduling, Information Sciences 428 (2018), 1–29.

21.

Koulinas

G.K.

and Anagnostopoulos

K.P.

, A new tabu search-based hyper-heuristic algorithm for solving construction leveling problems with limited resource availabilities, Automation in Construction 31 (2013), 169–175.

22.

Dokeroglu

and Cosar

, A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem, Engineering Applications of Artificial Intelligence 52 (2016), 10–25.

23.

Qian

, Zhao

, Wang

, Leng

and Wang

, A hyper heuristic algorithm for low carbon location routing problem, In International Symposium on Neural Networks, pages 173–182. Springer, 2018.

24.

Yao

, Peng

and Xiao

, Parallel hyper-heuristic algorithm for multi-objective route planning in a smart city, IEEE Transactions on Vehicular Technology 67(11) (2018), 10307–10318.

25.

Goldberg

D.E.

, Genetic algorithms, Pearson Education India, 2006.

26.

Syswerda

, Uniform crossover in genetic algorithms, In Proceedings of the 3rd international conference on genetic algorithms, pages 2–9, 1989.

27.

Tanese

, Distributed genetic algorithms for function optimization, 1989.

28.

Simon

, Biogeography-based optimization, IEEE Transactions on Evolutionary Computation 12(6) (2008), 702–713.

29.

Alagoz

, Hsu

, Schaefer

A.J.

and Roberts

M.S.

, Markov decision processes: A tool for sequential decision making under uncertainty, Medical Decision Making 30(4) (2010), 474–483.

30.

Yang

, Hou

, He

, Chan

and Guizani

, Offloading time optimization via markov decision process in mobile-edge computing, IEEE Internet of Things Journal 8(4) (2021), 2483–2493.

31.

Asheralieva

and Niyato

, Learning-based mobile edge computing resource management to support public blockchain networks, IEEE Transactions on Mobile Computing 20(3) (2021), 1092–1109.

32.

Ramya

, Somasundareswari

and Vijayalakshmi

, Gas chimney and hydrocarbon detection using combined bbo and artificial neural network with hybrid seismic attributes, Soft Computing 24(3) (2020), 2341–2354.

33.

Liang

and Xie

Y.Z.

, Maximizing radiated high-power electromagnetic threat to transmission line system under the constraints of bounded bandwidth and amplitude, IEEE Transactions on Electromagnetic Compatibility PP(99) (2020), 1–8.

34.

Yao

, Liu

and Lin

, Evolutionary programming made faster, IEEE Transactions on Evolutionary Computation 3(2) (1999), 82–102.

35.

, Lei

, Cai

, Hu

and Guo

, Species co-evolutionary algorithm: a novel evolutionary algorithm based on the ecology and environments for optimization, Neural Computing and Applications 31(7) (2019), 2015–2024.

36.

Hedar

A.-R.

and Fukushima

, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software 18(3) (2003), 265–282.

37.

, An analysis of the equilibrium of migration models for biogeography-based optimization, Information Sciences 180(18) (2010), 3444–3464.

A novel intelligent hyper-heuristic algorithm for solving optimization problems

Abstract

Keywords

1 Introduction

1.1 Overview of basic methods of genetic algorithms

2 Models

2.1 Model of genetic algorithm

2.2.1 Markov decision process

2.3.1 Learning process of HSQ-StudGA model

3.1 Experimental setup

3.2.1 Q-table convergence

Table 3 Experimental parameter settings Parameters Value Crossover type of StudGA Uniform Generation 50 Mutation probability of StudGA 0.01 Number of elitism habitats 2 Number of habitats 50

Footnotes

Acknowledgment

References

Table 3
Experimental parameter settings

Parameters Value

Crossover type of StudGA Uniform

Generation 50

Mutation probability of StudGA 0.01

Number of elitism habitats 2

Number of habitats 50