On the hybridization of global and local search methods

1 Introduction

Optimization means finding the best solution for an objective function (s) subject to constraints. Optimization problems can be categorized as single objective, multi-objective, and many objective unconstrained/constrained real-parameter or discrete optimization problems. The problem having just one objective to be optimized is called single objective optimization problem. When there are two to three objectives, the problem is called multi-objective optimization problem, while with more than three objectives the problem becomes many objective optimization problem [18]. In unconstrained optimization the main issue is to get to optimal value for the objective function (s), while in constrained optimization the constrains, both bound and functional, are also meant to be satisfied along with optimizing the objective function (s) [21].

Evolutionary optimization is inspired from Darwinian theory of evolution [28]. Algorithms belonging to this category are very efficient for finding global optimum of many real world problems, including problems from mathematics, engineering, economics, business, and medicines etc. In general, each EA starts with a population of candidate solutions (individuals). The quality of each solution is evaluated according to a fitness function, which represents the problem at hand. In each iteration of an EA, a selection process is applied to select a new set of solutions (population). The selection in EA is biased towards the most promising traits of the current population of solutions to increase their chances of being propagated to the new generation. At each iteration (generation), the population is evolved through a predefined set of operators, like mutation and recombination. This procedure is repeated until convergence is achieved. The best solution found by this procedure is expected to be a nearly optimum solution [14, 39].

Among different variants of EAs, Differential Evolution (DE) [39, 41] is a relatively recent algorithm. DE is efficient in solving many optimization problems [1, 46]. DE has many advantages. For example, it is easy to understand and implement, has a few parameters to control [43], and is robust. There is no doubt that DE is a remarkable optimizer but different reviews suggested that due to large step sizes in mutation, it is not very capable of exploiting the existing solutions than the exploration of search area [20]. Unlike the traditional deterministic methods, DE has the inherent drawback of skipping the true optima [20].

With higher reliability and modern technology, systems are getting complex day by day. It is very difficult to find a failure free algorithm, stand alone or hybrid, to solve above mentioned optimization problems [16]. Hybrid algorithms have shown performance improvement over stand alone algorithms. In he following, we briefly review some hybrid algorithms.

In [33], water cycle algorithm (WCA) (population based approach) is combined with gradient based LS; the new hybrid showed good performance against algorithms in comparison. In another recent experiment [30], particle swarm optimization (PSO) is hybridized with functional calculus (FC) as a LS. Some researchers combined two global search techniques, GA and PSO [17] and time varying acceleration (TVAC) with PSO [34] for constrained optimization problems. Their proposed hybrid algorithm works well for constrained optimization [29]. Likewise, harmony search (HS) is enhanced to heal its parameter sensitivity [3]. In all of these algorithms, experiments are conducted on discrete, constrained and multi-objective optimization problems.

Although there exist many DE variants [7, 47–50] for coping with complex real-world optimization problems, the performance of DE for some real-life problems can be further improved to bring better solutions. Moreover, various studies have disclosed that entrenching LS method can greatly improve the search capability of DE [22, 37]. In recent years the hybridization of DE with LS methods have gained much attraction due to their individual merits. Many hybrid algorithms have shown significant performance improvement. Here we review some of the methods in this category, which some how are related to our work as well.

In [38], the Levy Flight inspired LS mechanism is hybridized with DE known as Levy Flight DE (LFDE). LFDE exploits the search region brought by the best solution. A recent experiment [11] incorporated orthogonal LS in DE, denoted by (OLSDE). In every iteration of OLSDE, a DE process is used at first, and then to enhance the quality of some solutions an OLS based local search information is utilized. In an other improved DE algorithm, LSDE [19], an LS operator is merged in DE. In [27], an LS mechanism is employed in DE to enhance its poor LS ability. A new DE algorithm with localization around the best point (DELB) is proposed in [23]. In DELB, the initial steps are the same as DE except that the mutation scale factor F is chosen randomly for each mutant vector. DELB also modifies the selection step by introducing reflection and contraction. The trial vector is compared with the current best and the parent vector. If the parent is worse than the trial vector, it is replaced by a new concentrated or reflected vector. Thus in DELB, the trial vector can be replaced by its parent vector, reflected vector or contracted vector, while in classic DE only the trial vector replaces the parent. In NSDE [2], DE is hybridized with nonlinear simplex method. Here, a nonlinear simplex method with uniform random numbers is applied to initialize DE population. Initially, N^(p) individuals are generated uniformly and then next N^(p) individuals are generated from these N^(p) points by application of Nelder-Mead Simplex (NMS) [15, 25]. Then from 2N^(p) population, the fittest N^(p) individuals are selected as DE’s initial population and the rest of DE is unaltered in their algorithm. Thus, NSDE only modifies DE in the population step. It has shown good performance in reducing function evaluations and the CPU time. In an other experiment, Janez et al. [8] hybridized DE with Sequential Quadratic Programming (SQP), an efficient but expensive gradient-based LS method. Their hybrid applies the DE algorithm until function evaluations reach 30% of the maximum function evaluations. It then applies SQP for the first time to the best point thus obtained. Afterwards, SQP is applied after each 100 generations to the best solution of the current search. In their hybrid the population size keeps reducing and the process ends with a minimum population size.

Motivated by concerns about the complexity of systems and real-life problems, the rich literature of hybrid algorithms and it performance improvement over other stand alone algorithms (particularly of DE), and to avoid the inherent drawback of trapping in local optima of DE and thus improve it performance, this study proposes a hybrid DE algorithm, called hybridJADE, which combines two different gradient based LS strategies, one expensive and one inexpensive, with an improved variant of DE, JADE [49]. In hybridJADE, we incorporate gradient based information to the elite individuals to promote the balance between exploration and exploitation [9]. Also, we design a simple restart mechanism to enhance the robustness. Furthermore, in this work, we focus on single objective unconstrained optimization.

The rest of the paper is organized as follows. Section 2 describes the basic DE, JADE, SDM and BFGS algorithms. Section 3 details the proposed algorithm. Section 4 gives the experimental results. Finally, Section 5 concludes this paper and discusses future research direction.

2 Basic DE, JADE, SDM and BFGS

Our new hybrid algorithm will rely on basic DE variant, JADE [49], BFGS [15] and SDM [15]. Thus this section presents the basic operators of DE, BFGS and SDM, whereas the detailed description of JADE is already given in our previous work [26].

The iterative process of a standard DE algorithm [39, 41] relies on four basic steps: initialization, mutation, crossover, and selection. The iterations terminate when a termination criteria is met. It starts with a random initial population of N^(p) n-dimensional real-valued vectors in the search space, which is bounded by l = (l₁, l₂, l₃, … l _n ) and u = (u₁, u₂, u₃, … u _n ). Each element, also known as chromosome, forms a candidate solution to the problem to be optimized. We symbolize each individual by y ⁱ = (y ⁱ ₁, y ⁱ ₂, y ⁱ ₃, … y ⁱ _n ), where i = 1, 2, 3, …, N^(p). After initialization, the evolution progresses with the application of the mutation operator. In which for each individual y ⁱ of the current population a new individual, called the donor individual v ⁱ , is formulated by adding the scaled difference of two randomly selected individuals, y ⁱ _{s 2} , y ⁱ _{s 3} to a pre-specified base vector y ⁱ _{s 1} . The indices s₁, s₂, s₃ are uniformly generated integers mutually exclusive and different from running index i. The parameter F is normally used as a scaling factor. This parameter controls the amplification of the difference between two candidates and is used to ward off stagnation of the optimization process. Following mutation, the parameters of the parent vector y ⁱ and mutant vector v ⁱ are mixed by a crossover operator and a trial vector u ⁱ is produced. At the end, the trial vector u ⁱ generated by evolutionary operators is compared with its parent vector y ⁱ on the basis of its fitness (objective function value), i.e., if f (u ⁱ ) ≤ f (y ⁱ ), then yⁱ⁺¹ = u ⁱ ; otherwise, yⁱ⁺¹ = y ⁱ . The fittest of the two will get a chance to become a member of the next generation. The evolutionary cycle of DE is demonstrated in Fig. 1. More details about DE and the multi-faceted literature on it can be found in [12, 42] and in a most recent comprehensive survey [14].

OPEN IN VIEWER

Fig. 1

Differential evolution.

JADE [49] is an efficient version of DE. JADE updates the control parameters F and Cr of the probability distributions adaptively. The values of F and Cr that yield successful offspring in the recent generations are considered in the updating scheme of these parameters. It also employs a new mutation strategy DE/current/to-pbest and keeps a record of the inferior solutions of the selection scheme in an external archive (For more details readers are referred to [26, 49]).

The Quasi Newton search/BFGS algorithm is basically gradient-dependent approach, which employs the Hessian matrix in locating a suitable search direction. BFGS is considered as a very good LS method due to its efficiency. The Pseudo-code of BFGS is given in our previous work [24]. For more details on BFGS see [44].

The SDM is also a gradient based method. The gradient of a function at a point indicates the rapid increase in the function at that point. So the negative gradient will be the direction of most rapid decrease in the function at that point [44]. The method which searches the minimum along the negative gradient is called steepest descent method [10]. The details of SDM are presented in Algorithm 1.

In this section, a new hybrid algorithm based on hybridization of JADE and two LS techniques with a restart strategy, namely hybridJADE is presented. Before presenting the algorithm, the main idea on which it is based is given. The key idea of hybridJADE is to examine whether the performance of a hybrid algorithm can be improved by applying two LSs, one cheap and one costly, instead of only implementing a costly LS method. hybridJADE not only incorporates the two LSs together, but it also applies a restart if it stucks in a local optimum. The restart in hybridJADE is a local restart strategy instead of an entire restart. By local restart we mean that the new solutions will be generated in the neighborhood of the local optimum. The newly sampled solutions increase the diversity of the algorithm. Thus we hope that it will increase the performance of hybridJADE. Moreover, we are interested in examining the performance of hybridJADE when it relies on only expensive LS after restart instead of both LSs.

3.1 hybridJADE

The detailed description of hybridJADE is given in Algorithm 2, and its flowchart is presented in Fig. 2. OPEN IN VIEWER

Fig. 2

Flowchart of hybridJADE.

OPEN IN VIEWER

Algorithm 2

Algorithmic scheme for hybridJADE

Control Parameters:

REST: restart constant;

q: the number of points selected for LS;

γ: the number of iterations of LS before restart;

N(p): population size;

FES: number of function evaluations;

ξ: interval between the LS calls;

η: interval of generations between the LS calls after restart;

ς: the number of iterations of LS after the restart;

G: generation counter;

Step 0 Initialization: Uniformly and randomly sample N(p) solutions y i = (y i 1, y i 2, y i 3, … y i n ) for i = 1, 2, 3, …, N(p), from the search hyper rectangle [L, U] to form the initial population P. Evaluate each member of the population P, set FES = N p and G = 0.

Step 1: Exploration: To improve initial population P, implement global optimizer (say JADE) for ξ generations.

Step 2: Concentration: Apply SDM for ς iterations to q elite solutions in P to generate q new concentrated solutions.

Step 3: Refinement: Apply an efficient LS, BFGS for ς iterations to the best solution of q new solutions generated in Step 2. If the objective value of the resultant solution is close to the current best value, then go to Step 5; otherwise, go to Step 4

Step 4: Update Population: Swap the q worse solutions in P with the q new solutions generated in Steps 2-3 and go to Step 7.

Step 5: Computation of Initialization Search Bounds for Restart: Uniformly and randomly generate N(p) - 1 solutions in the search range defined by Algorithm 3 to form population for restarting, together with the previous best solution, and go to Step 6.

Step 6: Restart the algorithm hybridJADE by implementing Algorithm 4 and go to Step 7

Step 7: If a present stopping condition is met, stop and output the best solution obtained so far. Elseif REST = 1 go to Algorithm. Otherwise, set G = G + 1 and go to Step 1.

OPEN IN VIEWER

Algorithm 3

Algorithmic framework of initialization of the search range for restart

Step 1: Compute the Euclidean distance between the q points found by inexpensive LS, SDM and the best member found by BFGS in Algorithm 1.

Step 2: Identify the point with the maximum Euclidean distance and denote it as x ˘ .

Step 3: [ x ˘ , x ˘ + θ ] is the search range for the new population to generate for the restart.

In the following, we discuss the implementation of hybridJADE.

3.1.1 Global search

Since the issue is to design a model which has capabilities of both global and local search and, as a result a balance between exploration and exploitation is achieved, implementing JADE (as a global search method) at the beginning of the algorithm (Step 1) is a wise choice when the population is randomly scattered in the search space. That is why, hybridJADE starts with JADE. Also as it is a population-based method, it concentrates the initial population generation by generation due to its adaptive mutation scale factor F.

OPEN IN VIEWER

Algorithm 4

Algorithmic framework of restart strategy

Control Parameters:

η: interval between the LS calls after restart;

γ iterations of LS after restart.

Step 0 Initialization: Uniformly and randomly generate N(p) - 1 solutions, to form the new population in a region around the resultant solution of Algorithm.

Step 1: Use JADE as a main search engine to search the new population generated in Step 0.

Step 2: Apply efficient LS with ς iterations to refine the best solution after each η generations.

Step 3: Stopping Condition: If a present stopping condition is met, stop and output the best solution obtained so far. Otherwise go to Step 1

3.1.2 Concentration

The population which is brought by JADE is already concentrated to some extent. The implementation of an inexpensive LS to the top, say q individuals would hopefully decrease their function values, which would be further refined later. An appropriate number for parameter q, say q = 3 is very important, because if it is chosen one in population of size 100, it will have no effect on the population. On the other hand if it is too large, it will waste function evaluations. SDM is less expensive as compared to BFGS. Because it approximates the gradient and incorporates some line search technique to compute the step lenght α ⁱ as given in Algorithm 1, for searching a new direction. SDM does not require Hessian approximation. That is why its computational complexity is less than that of BFGS. Thus it can be implemented in global search at regular intervals and for more than one iterations. That is why, SDM iteration counter, γ is set to 2 in our experiments.

3.1.3 Refinement

BFGS is applied to the best solution among the q solutions found by the cheap LS of Step 2 of Algorithm, after concentration. Since this is the best solution, it always deserves more investment, because it can potentially be the desired optimum. Hence, BFGS can be applied to it more than one iterations (2 here) to improve its quality or to explore it further. Thus, the number of iterations γ of expensive LS to the best solution is set to 2.

In the restart strategy, the initial population is already concentrated, so BFGS is applied ς, set to 1 here, iterations to the current best solution of the search. Moreover, the LS call of BFGS is implemented after each η generations after restart with a hope that it will find the desired optimum. The parameter η is set to 30 generations such that BFGS can do the LS after a significant gap of global search by JADE during restart. Thus, it is expected that in this way a balance between exploration and exploitation could be established during the restart.

3.1.4 Updating the population

Adding promising solutions to the population of hybridJADE and removing the worst points from it can improve the quality of offspring in the next generations. Contrary to good parents which can produce good offspring, worse parents have the chance of producing worse solutions. So their removal can have a good effect on the entire population.

3.1.5 Stopping condition

The stopping condition is borrowed from [36] for hybridJADE. hybridJADE stops when one or both of the following conditions are met.

The maximum number of function evaluations is reached.

|f (y) - f (y^∗) | < error where y is the best individual found in a run, and y^∗ is the known global optimum of the test instance.

3.1.6 Deciding the neighborhood size

When BFGS in Step 3 of hybridJADE finds a solution whose objective value is worse than the current best value but is in the neighborhood of the existing best value, a restart is employed. For the restart, there are two conditions: the distance at which the new solutions should be sampled we call it neighborhood radius, and the initialization of the search range for the new population. The computation of parameter θ, which is used to determine the search range, is defined as follows: θ = U - L ⌊ ( 2 / 3 ) n ⌋(1) where U and L are the upper and lower bounds on the variables.

The search range, illustrated in Fig. 3, varies with the problem dimension n and the values of L and U. To avoid manual adjustment of θ, we made it dimension dependent so that it can choose appropriate values with varying dimension. For example, in case of test instance F1, the values of L and U are -100 and 100, respectively. Thus the value of θ with n = 30 is 10. Similarly, in case of test instance F8, θ = 3.20 with n = 30 and L = -32 and U = 32. Moreover, if θ < 0.50, then θ = 0.50 is taken as the default value. An example of the latter case is test instance F11, where θ = 0.05 with L = -0.5, U = 0.5 and n = 30. In this case, we take θ = 0.50, because a very small region (θ < 0.50) would not be an ideal space for search of hybridJADE.

OPEN IN VIEWER

Fig. 3

2D Concept of neighborhood size.

The advantage of θ defined in Equation (theta) is that it adjusts itself according to the dimension and search bounds. Hence, it helps the algorithm to sample a new population at an appropriate distance from the local optimum. We hope it will discourage the pre-mature convergence of the algorithm.

Next to answer the question that why the initialization of the search range is necessary for the new population, we comment that if we initialize again the population in its previous search range within the same function evaluations, it would be unwise as the majority of the function evaluations are already done. Doing the same search again will waste function evaluations and the algorithm would not be able to reach the desired optimum. On the other hand, if we generate the new population just around the best solution, then there is a big chance of getting into the same local optimum again. Thus, it is necessary to generate a new population at a certain distance and within bounds.

3.1.7 Restart strategy

If the BFGS found a local optimum, N^(p) - 1 new solutions are generated in the predefined search range [ x ˘ , x ˘ + θ ] given by Algorithm to incorporate the restart. The population size for restart is kept N^(p) in which N^(p) - 1 are newly sampled solutions, while the one is the best solution found in the previous search. The benefit of the restart is that the algorithm gets an additional opportunity to explore the search region. Since the population is randomly generated, we hope it will also help in maintaining diversity. Thus, the purpose of restart is to avoid local optima and early convergence in hybridJADE. The step by step algorithm of restart strategy is given in Algorithm 4.

4 Comparison studies

Two sets of experiments are carried out. The first set of experiments was carried out to compare the hybridJADE with DE variant, JADE. In the second set of experiments, a set of comparison studies was made to state-of-the-art algorithm jDE. All these experiments were carried out using MATLAB software. A t-test was also applied for validation of these results. We compare hybridJADE with JADE and jDE for 30 dimensional problems.

4.4 Comparison with JADE

The average and standard deviation of function error values obtained in each run are used to compare the performance of both algorithms. They are shown in Table 1. The function evaluations are recorded when an algorithm has achieved the desired accuracy level during a run, within the maximum function evaluations.

4.4.1 Unimodal test instances (F1 - F5)

Table 1 shows that on two out of five unimodal functions, F1 and F2, both algorithms, JADE and hybridJADE performed equally in terms of function average error values and SRs, while on three unimodal functions, F3, F4 and F5, JADE surpasses hybridJADE. This poor performance of hybridJADE may be due to the restart, in which the population gets random and diverse once again and the objective function values of new individuals in the population become bigger (large since we are minimizing).

OPEN IN VIEWER

Table 1

“Mean Error”, “Std Dev” and “SR” of the function error values of JADE and hybridJADE over 30 independent runs on 15 test instances of 30 variables with 3 × 10⁵ FES

Test Instance	JADE (Mean Error ± Std Dev)	hybridJADE (Mean Error ± Std Dev)	JADE SR	hybridJADE SR
F1	8.75E - 09 ± 7.96E - 10≈	9.08E - 09 ± 8.15E - 10	100%	100%
F2	9.50E - 09 ± 3.73E - 10≈	9.63E - 09 ± 2.85E - 10	100%	100%
F3	6.29E + 03 ± 5.57E+ 03 +	1.02E + 04 ± 6.24E + 03	0	0
F4	9.58E - 09 ± 4.01E - 10+	2.86E + 04 ± 8.10E + 03	100%	0
F5	2.13E - 08 ± 4.36E - 08+	2.36E + 03 ± 4.77E + 02	93.3%	0
F6	1.99E + 01 ± 3.88E + 01-	1.24E + 01 ± 5.13E + 01	63.3%	80%
F7	4.70E + 03 ± 2.67E - 12-	1.05E + 01 ± 4.44E - 01	0	0
F8	2.09E + 01 ± 1.80E - 01≈	2.09E + 01 ± 1.77E - 01	0	0
F9	9.25E - 09 ± 7.92E - 10+	3.09E - 02 ± 1.43E - 02	100%	100%
F10	2.42E + 01 ± 5.33E+ 00 ≈	2.50E + 01 ± 4.30E + 00	0	0
F11	2.54E + 01 ± 1.70E+ 00 +	2.69E + 01 ± 2.01E + 00	0	0
F12	5.30E + 03 ± 4.92E+ 03 ≈	5.69E + 03 ± 5.49E + 03	0	3.3%
F13	1.45E + 00 ± 1.12E - 01+	5.27E + 00 ± 1.82E + 00	0	0
F14	1.23E + 01 ± 3.09E - 01+	1.30E + 01 ± 2.84E - 01	0	0
F15	3.47E + 02 ± 1.31E+ 02 ≈	3.45E + 02 ± 1.20E + 002	6.7%	0
-	2
+	7
≈	6

“-”, “+” and “≈” denote that the performance of JADE is worse than, better than or similar to that of hybridJADE, respectively.

The SRs of both algorithms are given in Table 1. This table shows that the SRs of JADE are better than those of hybridJADE on two unimodal test instances F4 and F5, while on three unimodal functions, F1-F3 the SRs of both algorithms are equal. The lower SRs of hybridJADE than JADE on test functions F4 and F5 could be due to our two techniques, firstly, the restart utilized extra N^(p) - 1 function evaluations, and also we use the efficient LS which is fast but utilize more function evaluations. Hence, sometimes hybridJADE might finish the maximum number of function evaluations before reaching the desired local optimum. Another possible cause of failure could be the parameter η which is the interval between the LS calls after restart, chosen 30 here. Since LS after restart is BFGS and calling it after each 30 generations may not be an appropriate gape between the LS calls. The convergence graphs of function error values against FES are also plotted in Fig. 4.

OPEN IN VIEWER

Fig. 4

Convergence graphs of JADE and hybridJADE for six representative test functions at n=30, with population size=100. (a) F1 (b) F2 (c) F7 (d) F8 (e) F9 (f) F10.

4.4.2 Multimodal test instances (F6 - F14)

Table 1 shows that hybridJADE is better, in terms of function average error values, than JADE on basic two multimodal functions, F6 and F7. On three test instances, F8, F10 and F12, both algorithms are equivalent, while on four test instance, F9, F11, F13 and F14 JADE is superior in getting better value of mean than that of hybridJADE. Though hybridJADE performance is worse than JADE on four instances in multimodal test instances, it has higher success rate, SR, than JADE on two test instances F6 and F12; 80% SR against 63.3% SR of JADE. This good value may be due to the combination of LS methods which increases the exploitation ability of the hybridJADE and helps it to reach a better solution.

On expanded multimodal functions, F13 and F14, JADE is better than hybridJADE in terms of function error values, although both have the same SR, 0.

4.4.3 Hybrid composition test instance (F15)

On hybrid composition function F15, JADE and hybridJADE had the same performance in terms of function error values. But JADE got higher SR than hybridJADE, as shown in Table 1.

Hence from the above results it can be concluded that JADE showed good performance on eight test instances out of 15.

4.5 Comparison with jDE

We further compare the hybridJADE with jDE [6]. jDE introduced a self adaptive mechanism for control parameters F and CR. The experimental results for both algorithms hybridJADE and jDE were obtained in 30 independent runs. The function error values and SR are presented in Table 2 and the convergence graphs of both algorithms are shown in Fig. 5. The detailed comparison of both algorithms is presented below. OPEN IN VIEWER

Fig. 5

Convergence graphs of jDE and hybridJADE for eight representative test functions at n = 30, with population size=100.

4.5.1 Unimodal test instances (F1 - F5)

As shown in Table 2 and Fig. 5, hybridJADE algorithm is better for two unimodal test instances F2 and F3 in terms of function error values. Considering SR for these test instances, on F2 hybridJADE had 100% SR against 0% SR of jDE. On F4 and F5 jDE performed well regarding function error value. But it could not reach the desired accuracy in any run as shown by its 0 SR in Table 2; on the other hand hybridJADE obtained 3· 3 % SR for F5. For F1 both algorithms showed 100% success which can also be observed in the convergence graphs presented in Figure 5.

OPEN IN VIEWER

Table 2

“Mean Error”, “Std Dev” and “SR” of the function error values of jDE and hybridJADE over 30 independent runs on 15 test instances of 30 variables with 3 × 10⁵ FES

Test Instance	jDE (Mean Error ± Std Dev)	hybridJADE (Mean Error ± Std Dev)	jDE SR	hybridJADE SR
F1	8.8970E - 09 ± 8.6491E - 10≈	9.10E - 09 ± 9.15E - 10	100%	100%
F2	7.1768E - 07 ± 1.3401E - 06-	9.51E - 09 ± 4.01E - 10	0	100%
F3	1.9017E + 05 ± 1.0843E + 05-	5.20E + 03 ± 4.62E + 03	0	0
F4	1.4889E - 01 ± 4.1883E - 01+	2.64E + 04 ± 8.87E + 03	0	0
F5	6.4288E + 02 ± 4.4950E+ 02 +	2.27E + 03 ± 6.34E + 02	0	3.3%
F6	3.2179E + 01 ± 2.9522E+ 01 +	9.48E + 05 ± 1.15E + 06	0	40%
F7	4.6963E + 03 ± 1.2061E - 12-	1.08E + 01 ± 4.20E - 01	0	0
F8	2.0937E + 01 ± 4.9735E - 02≈	2.09E + 01 ± 1.17E - 01	0	0
F9	9.1001E - 09 ± 6.4309E - 10+	1.10E + 01 ± 1.28E + 01	100%	50%
F10	5.4637E + 01 ± 1.0562E + 01-	2.40E + 01 ± 5.10E + 00	0	0
F11	2.7762E + 01 ± 2.1542E+ 00 ≈	2.68E + 01 ± 2.22E + 00	0	0
F12	1.6777E + 04 ± 8.0533E + 03-	4.62E + 03 ± 3.20E + 03	0	3.3%
F13	1.6686E + 00 ± 1.2116E - 01+	5.28E + 00 ± 2.60E + 00	0	0
F14	1.3004E + 01 ± 2.5768E - 01≈	1.30E + 01 ± 3.06E - 01	0	0
F15	3.2226E + 02 ± 9.5596E+ 01 ≈	3.68E + 02 ± 1.35E + 02	0	0
-	5
+	5
≈	5

“-”, “+” and “≈” denote that the performance of jDE is worse than, better than or similar to that of hybridJADE, respectively.

Overall, in case of unimodal test instances, both jDE and hybridJADE performed equally well.

4.5.2 Multimodal test instances (F6 - F14)

The performance of hybridJADE in this category of multimodal test instances can be observed in Table 2. hybridJADE performed well for three out of nine multimodal test instances, F7, F10 and F12 in getting a better local optimal solution. This success can also be observed from graphs presented in Fig. 5. For these instances SR is 0 for both algorithms except F12 where hybridJADE succeeded in achieving the desired accuracy with SR of 3· 3 %.

These test instances have many local optima, so it is usually difficult for any algorithm to get the desired accuracy in each run. For three test instances, F6, F9 and F13, jDE performed good in attaining a better average value than hybridJADE as can be seen in Table 2. Though jDE performed well on F6 in function error value, hybridJADE was good on F6 in finding a higher SR. Overall hybridJADE’s performance is better than that of jDE for multimodal test instances in SRs as it reached the desired level in few runs for three test instances, while jDE got it for only one test instance, F9.

4.5.3 Hybrid composition test instance (F15)

For this hard composition test instance jDE’s performance is similar to that of hybridJADE in function error values. None of the algorithm could have a positive SR for this tricky test instance.

Overall hybridJADE dominates jDE in terms of function error values, on five test instances, F2, F3, F7, F10 and F12 and jDE on the other hand also surpasses hybridJADE in exactly five test instances, F4, F5, F6, F9 and F13. However the performance of hybridJADE is better in terms of SR, as evident by Table 2 for six (F1, F2, F5, F6, F9 and F12) out of fifteen test instances. It has reached the required accuracy for some of the runs, but jDE could do it only for two test instances, F1 and F9. The cause for the good performance in SRs is that hybridJADE utilizes two local search methods, which can be of great help in exploring the small regions. jDE on the other hand is a global search method, hence it may suffer poor exploitation. The inferior performance of hybridJADE to jDE on some test instances may be due to gradient based LS which some times get trapped in local optimum.

4.6 Sensitivity study of hybridJADE to its parameters

To investigate the behaviour of proposed algorithm to various parameters we conducted experiments on F8 as representative test instance.

4.6.1 Sensitivity of hybridJADE to parameter ξ

To illustrate the sensitivity of the performance of hybridJADE to the interval between the LS calls, ξ, we have tested 6 values of ξ (i.e., ξ = 5, 10, 15, 20, 25, 30) on F8. Each value of ξ is executed 30 times. All other parameters are kept the same.

Figure 6 (a) displays the objective function average error values versus values of ξ. The graph shows high sensitivity of hybridJADE to the increasing different values of ξ. Thus, small value of ξ is suggested. OPEN IN VIEWER

Fig. 6

The objective function average error values vs. parameters ξ, q, η, and γ obtained with hybridJADE on F8 (CEC2005) representative test function.

4.6.2 Impact of parameter q on hybridJADE

To analyze the behaviour of hybridJADE to parameter q (the number of solutions undergoing LS), hybridJADE is tested with 10 values of q (i.e., q = 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) on F8. Each value of q is tested in 30 independent runs. All other parameters remain the same. Figure 6 (b) gives the objective function average error values versus values of q. The graph shows sensitive behaviour of hybridJADE to various values of q. A higher value of this parameter can produce better results.

4.6.3 Sensitivity of hybridJADE to parameter η

To illustrate the sensitivity of the performance of hybridJADE to the interval between the LS calls, η, we have experimented with 6 values of η (i.e.,η = 10, 20, 30, 40, 50, 60) on F8. Each value of η is tested with 30 independent runs. All other parameters were kept the same. Figure 6 (c) plots the objective function average error values versus values of η. The graph shows sensitivity of hybridJADE to different values of η. It also confirms our appropriate choice (η = 30) of this parameter.

4.6.4 Influence of parameter γ on hybridJADE

In order to study the sensitivity of hybridJADE to parameter γ, we have tried 5 values of γ (i.e., γ = 1, 2, 3, 4, 5) on F8. Each value of γ is tried 30 independent times. All other parameters remain the same. Figure 6 (d) displays the objective function average error values versus different values of γ. The graph in this figure indicate that hybridJADE is sensitive to changes in values of γ; a high value of γ can produce better results.

In general, hybridJADE is sensitive to all its parameters, as shown by the graphs in Fig. 6. Thus, appropriate choice of values for these parameters is necessary for the better performance of hybridJADE.

5 Conclusion

In this paper, a hybrid algorithm, hybridJADE of a global search optimizer, JADE with two local search optimizers, SDM and BFGS is proposed to complement the exploration strength of JADE with the exploitation strengths of SDM and BFGS. Whenever the algorithm gets trapped in a local optima, a restart strategy is called and BFGS is applied. In fact, we want to spend much efforts on good points that are identified during the evolution. That is why, an efficient LS, BFGS is called after the restart strategy. From experimental results, the following points can be concluded.

HybridJADE obtained better statistics than JADE on two CEC2005 test instances, F6 and F7, it also performed equally good on six test instances. However, it showed inferior performance on eight test instances against JADE. The failure could be due to its restart strategy, which utilizes an expensive LS, or may be the neighborhood size is not suited to each test instance.

The comparison of hybridJADE with state-of-the-art jDE on CEC2005 test instances indicated that hybridJADE had found better function error values for five test instances, F2, F3, F7, F10 and F12. However, it loses performance on the other five instances, F4, F5, F6, F9 and F13 against jDE. For the rest both had the same performance.

Sensitivity analysis to newly introduced parameters is provided, which identified a bit receptive behaviour of hybridJADE to these parameters.

In the future, with intend to embed some other LSs, e.g., conjugate gradient and Davidon-Fletcher-Powel methods in PSO, Firefly algorithm (FA) and some other promising EAs. The existing algorithm can be further improved and extended to solve latest CEC test function suits and constrained multiplicative real life engineering optimization problems.

Footnotes

Acknowledgment

The authors would like to thank King Khalid University of Saudi Arabia for supporting this research under the grant number R.G.P.2/7/38.

References

1.

Al-Dabbagh R.D. , Neri F. , Idris N. , Baba M.S. , Algorithm design issues in adaptive differential evolution: Review and taxonomy, 2018.

Go to Reference

2.

Ali M. , Pant M. and Abraham A. , Simplex differential evolution, Acta Polytechnica Hungarica 6(5) (2009).

Go to Reference

3.

Ameli K. , Alfi A. and Aghaebrahimi M. , A fuzzy discrete harmony search algorithm applied to annual cost reduction in radial distribution systems, Engineering Optimization 48 (2016), 1529–1549.

Go to Reference

4.

Awad N.H. , Ali M.Z. , Mallipeddi R. and Suganthan P.N. , An improved differential evolution algorithm using efficient adapted surrogate model for numerical optimization, Information Sciences 451 (2018), 326–347.

Go to Reference

5.

Betzig L.L. , Despotism, social evolution, and differential reproduction, Routledge, 2018.

Go to Reference

6.

Brest J. , Greiner S. , Boskovic B. , Zumer V. , Maucec M.S. , Self-adaptive control parameters in differential evolution: A comparative study on numerical benchmark problems, 2006.

Go to Reference

7.

Brest J. , Zamuda A. , Boskovic B. , Greiner S. , Zumer V. , Advances in Differential Evolution, volume SCI143, chapter An Analysis of the control parameters’ Adaptation in Differential Evolution, 2008.

Go to Reference

8.

Brest J. , Zamuda A. , Bošković B. , S. Greiner , M.S. Maučce , and V. Žumer , Self-adaptative differential evolution with sqp local search, In 3rd International Conference on Bio-Inspired Optimization Methods and Their Applications(BIOMA), (2008), pp. 59–66.

Go to Reference

9.

črepinšek M. , S.H. Liu and M. Mernik , Exploration and exploitation in evolutionary algorithms: A survey, ACM Computing Surveys (CSUR) 45(3) (2013).

Go to Reference

10.

Curry H.B. , The method of steepest descent for nonlinear minimization problems, Quart Apple Math 2(3) (1944), 250–261.

Go to Reference

11.

Dai Z. , Zhou A. , Zhang G. and Jiang S. , A differential evolution with an orthogonal local search, In Evolutionary Computation (CEC), 2013 IEEE Congress on, IEEE, 2013, pp. 2329–2336.

Go to Reference

12.

Das S. and Suganthan P.N. , Differential evolution: A survey of the state-of-the-art, Evolutionary Computation, IEEE Transactions on 99 (2011), 1–28. ISSN 1089-778X.

Go to Reference

13.

Das S. and Suganthan P.N. , Tutorial: Differential evolution, foundations, prospectives and applications, In IEEE Symposium Series on Computational Intelligence (SSCI), Paris, France, 2011, pp. 1–59.

Go to Reference

14.

Das S. , Mullick S.S. and Suganthan P.N. , Recent advances in differential evolution an updated survey, Swarm and Evolutionary Computation (2016).

+ Show References

15.

Fletcher R. , Practical Methods of Optimization Second ed, Wiley, 1987, pp. 80–87.

+ Show References

16.

Garg H. , An approach for solving constrained reliabilityredundancy allocation problems using cuckoo search algorithm, Beni-Suef University Journal of Basic and Applied Sciences 4(1) (2015), 14–25.

Go to Reference

17.

Garg H. , A hybrid pso-ga algorithm for constrained optimization problems, Applied Mathematics and Computation 274 (2016), 292–305.

Go to Reference

18.

Garg H. and Sharma S.P. , Multi-objective reliabilityredundancy allocation problem using particle swarm optimization, Computers & Industrial Engineering 64(1) (2013), 247–255.

Go to Reference

19.

Gu J. , Gu G. , Differential evolution with a local search operator, In Informatics in Control, Automation and Robotics (CAR), 2010 2nd International Asia Conference on, volume 2, IEEE, 2010, pp. 480–483.

Go to Reference

20.

Guo Z. , Huang H. , Deng C. , Yue X. and Wu Z. , An enhanced differential evolution with elite chaotic local search, Computational Intelligence and Neuroscience 2015 (2015), 6.

+ Show References

21.

Jan M.A. , Tairan N. , Khanum R.A. and Mashwani W.K. , Performance of a constrained version of MOEA/D on CTP-series test instances, International Journal of Advanced Computer Science and Applications 7(6) (2016), 496–505.

Go to Reference

22.

Jia D. , Zheng G. and Khan M.K. , An effective memetic differential evolution algorithm based on chaotic local search, Information Sciences 181(15) (2011), 3175–3187.

Go to Reference

23.

Kaelo P. and Ali M.M. , A numerical study of some modified differential evolution algorithms, European Journal of Operational Research 169(3) (2006), 1176–1184.

Go to Reference

24.

Khanum R.A. and Jan M.A. , Hybridization of adaptive differential evolution with an expensive local search, Journal of Optimization (2016), 1–15.

Go to Reference

25.

Khanum R.A. , Zari I. , Jan M.A. and Mashwani W.K. , Reproductive nelder-mead algorithms for unconstrained optimization problems, Science International 28(1) (2015), 19–25.

Go to Reference

26.

Khanum R.A. , Tairan N. , Jan M.A. , Mashwani W.K. and Salhi A. , Reflected adaptive differential evolution with two external archives for large-scale global optimization, International Journal of Advanced Computer Science and Applications 7(2) (2016), 675–683.

+ Show References

27.

Li H. and Tang J. , Improved differential evolution with local search, Journal of Convergence Information Technology 7(4) (2012), 197–204.

Go to Reference

28.

Mallipeddi R. , Suganthan P.N. , Pan Q.K. and Tasgetiren M.F. , Differential evolution algorithm with enble of parameters and mutation strategies, Applied Soft Computing 11 (2010), 1979–1696.

Go to Reference

29.

Mohamed A.W. , A novel differential evolution algorithm for solving constrained engineering optimization problems, Journal of Intelligent Manufacturing 29(3) (2018), 659–692.

Go to Reference

30.

Mousavi Y. and Alfi A. , A memetic algorithm applied to trajectory control by tuning of fractional order proportional-integralderivative controllers, Applied Soft Computing 36 (2015), 599–617.

Go to Reference

31.

Neri F. and Tirronen V. , Recent advances in differential evolution: A survey and experimental analysis, Artificial Intelligence Review 33(1) (2010), 61–106. ISSN 0269-2821.

Go to Reference

32.

Noman N. and Iba H. , Acceleratinging differential evolution using an adaptive local search, IEEE Transactions on Evolutionary Computation 12(3) (2008), 107–125.

Go to Reference

33.

Pahnehkolaei S.M.A. , Alfi A. , Sadollah A. and Kim J.H. , Gradient-based water cycle algorithm with evaporation rate applied to chaos suppression, Applied Soft Computing 53 (2017), 420–440.

Go to Reference

34.

Patwal R.S. , Narang N. and Garg H. , A novel tvac-pso based mutation strategies algorithm for generation scheduling of pumped storage hydrothermal system incorporating solar units, Energy 142 (2018), 822–837.

Go to Reference

35.

Qin A.K. and Suganthan P.N. , Self adaptive differential evolution algorithm for numerical optimization, In IEEE Congress on Evolutionary Computation (2005), volume 2, 2005, pp. 1785–1791.

+ Show References

36.

Qin A.K. , Huang V.L. and Sughanthan P.N. , Differential evolution algorithm with strategy adaptation for global numerical optimization, IEEE transactions on Evolutionary Computation 13(5) (2009), 398–417.

+ Show References

37.

Rahnamayan S. , Tizhoosh H.R. and Salama M.M.A. , Opposition-based differential evolution (ode), IEEE Transactions on Evolutionary Computation 12(1) (2008), 64–79.

+ Show References

38.

Sharma H. , Jadon S.S. , Bansal J.C. , Arya K.V. , Lèvy flight based local search in differential evolution, In International Conference on Swarm, Evolutionary, and Memetic Computing, Springer, 2013, pp. 248–259.

Go to Reference

39.

Storn R. . Differential Evolution (DE) Research-Trends and open questions, volume SCI 143. Springer, 2008.

+ Show References

40.

Storn R. , Price K. , Home page of differential evolution, 2003.

Go to Reference

41.

Storn R. and Price K.V. , Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization 11(4) (1997), 341–359.

+ Show References

42.

Suganthan P.N. and Das S. , Tutorial: Differential evolution, pp, In IEEE Symposium Series on Computational Intelligence (SSCI) (2011), 1–76.

Go to Reference

43.

Tang L. , Dong Y. and Liu J. , Differential evolution with an individual-dependent mechanism, IEEE Transactions on Evolutionary Computation 19(4) (2015), 560–574.

+ Show References

44.

Venkataraman P. , Applied Optimization with Matlab Programming, John Wiley and Sons, New York, 2002, pp. 238–240.

+ Show References

45.

Wang Y. , Cai Z. and Zhang Q. , Differential evolution with composite trial vector generation strategies and control parameters, IEEE Transactions on Evolutionary Computation 15(1) (2011) 55–66. ISSN 1089-778X.

Go to Reference

46.

Wu G. , Shen X. , Li H. , Chen H. , Lin A. and Suganthan P.N. , Enble of differential evolution variants, Information Sciences 423 (2018), 172–186.

Go to Reference

47.

Yang Z. , Tang K. and Yao X. , Self-adaptive differential evolution with neighborhood search, In IEEE Congress on Evolutionary Computation (CEC 2008), Singapore, 2008. IEEE Press.

Go to Reference

48.

Zaharie D. , A comparitive analysis of crossover varients in differential evolution, In Proceedings of international multiconference on Computer Science and Information Technology, 2007.

Go to Reference

49.

Zhang J. and Sanderson A.C. , JADE: Adaptive differential evolution with optional external archive, Evolutionary Computation, IEEE Transactions on 13(5) (2009), 945–958. ISSN 1089-778X.

+ Show References

50.

Zheng, K. Tang and X. Yao , Large scale evolutionary optimization using cooperative coevolution, Journal of Information Sciences 178(15) (2008), 985–2999. ISSN 0020-0255.

Go to Reference