The aim of this paper is to produce a new hybrid algorithm to solve minimax problems by combining the bat algorithm with direct search methods. The proposed algorithm is called hybrid bat direct search algorithm (HBATDS). In HBATDS, the global exploration and the local exploitation process are balanced. The bat algorithm has a good ability to make exploration and exploitation search. The exploitation capability of the proposed algorithm is increased by invoking the pattern search method as a local search method instead of the random walk method in the standard bat algorithm. In the final stage of the algorithm, the Nelder-Mead method is applied in order to refine the best found solution from the bat and pattern search method instead of running the algorithm more iterations without any improvements in the fitness function value. The performance of the HBATDS algorithm is investigated by applying it on 10 minimax problems and comparing it against 8 benchmark algorithms. The experimental results indicate that HBATDS is a promising algorithm and outperforms the other algorithms in most cases.
Swarm intelligence (SI) algorithms are a new meta-heuristics algorithms, which take inspiration from the behavior of a group of social organisms. These algorithms are applied to solve global optimization problems and their applications such as ant colony optimization (ACO) [8], artificial bee colony [14], particle swarm optimization (PSO) [2, 15], bacterial foraging [25], bat algorithm [41], bee colony optimization (BCO) [35], wolf search [31], cat swarm [7], cuckoo search [40], firefly algorithm [39], fish swarm/ school [17], etc.
These algorithms and some meta-heuristics algorithms such as differential evolution (DE) [30], genetic algorithm [29], tabu search (TS) and variable neighborhood search (VNS) [6], artificial bee colony (ABC) [9] have been widely used to solve unconstrained and constrained problems and their applications, however they have been applied in a few works to solve minimax and integer programming problems [1, 3, 4, 32, 33, 34].
There are some smoothing techniques have been applied for solving minimax problems. These techniques are solving a sequence of smooth problems, which approximate the minimax problems in the limit [18, 27, 38]. The algorithms based in these techniques aim to generate a sequence of approximations, which converges to Kuhn-Tucker point of the minimax problem, for a decreasing sequence of positive smoothing parameters. However, the drawback of these algorithms is these parameters are small too fast and the smoothing problems become significantly ill-conditioned.
Some swarm intelligence algorithms have been applied to solve minimax problems such as PSO [26], however these algorithms suffer from increasing the evaluation function value.
Bat algorithm (BA) is a new population based algorithm inspired from the echolocation behavior of the microbats [41]. BA has a good capability to balance the global exploration and the local exploitation during the search process. Due to the powerful performance of the bat algorithm, many researchers have applied it to solve various applications, for example, Yang [42] applied BA to solve multi-objective optimization and benchmark engineering problems. Komarasamy and Wahi [16] presented a combination of K-means and bat algorithm (KMBA) for efficient clustering. Lin et al. [19] carry out parameter estimation in dynamic biological systems using a chaotic bat algorithm by combining Levy flights and chaotic maps. Nakamura et al. [22] developed a discrete version of bat algorithm to solve classifications and feature selection problems. Xie et al. [37] presented a variant of bat algorithm combining differential operator and Levy flights to solve function optimization problems. Zhang and Wang [43] enhanced the diversity of solutions by using the mutation with bat algorithm for image matching. In addition, Wang and Guo [36] combined bat algorithm with harmony search and produced a hybrid bat algorithm for numerical optimization of function benchmarks.
The main objective of this paper is to produce a new hybrid bat algorithm with direct search methods to solve minimax problems [10]. The proposed algorithm is called hybrid bat direct search algorithm (HBATDS). In HBATDS, the pattern search is used as a local search method to exploit the search around the best found solution at each iteration and in the final stage of the algorithm, the Nelder-Mead method is invoked in order to refine the best obtained solution from the bat and pattern search method. Using of the Nelder-Mead method can accelerate the search and avoid running the algorithm with more iterations without any improvements in the results.
We compare the HBATDS algorithm against 8 various algorithms, namely, Heuristic Pattern Search algorithm (HPS2) [13], Random Walk Memetic Particle Swarm Optimization (RWMPSOg) [26], Genetic Algorithm (GA) [11], standard Particle Swarm Optimization (PSO) [15], Firefly (FF) [39], Cuckoo Search (CS) [40] and Grey Wolf Optimization Algorithms (GWO) [21]. The rest of this paper is organized as follows. In Section 2, the minimax problems and the applied direct search methods are presented. The standard bat algorithm is presented in Section 3. In Section 4, the main concepts of the proposed HBATDS algorithm are given. The numerical experimental results are presented in Section 5. Finally, The conclusion is given in Section 6.
Definition of the problem and an overview of the applied algorithms
In this section and its subsections, the definition of the minimax problems is presented and an overview of the bat algorithm and the pattern search method is given as follows.
Minimax problem definition
The general form of the minimax problem as reported in [38] is defined by:
where
with .
The nonlinear programming problems of the form:
can be transformed to minimax problems as follows:
where
It has been proved that for sufficiently large , the optimum point of the nonlinear programming problem coincides with the optimum point of the minimax problem [5].
Pattern search method
Hook and Jeeves (HJ) [12] proposed the pattern search method (PS). Pattern search method is one of the most applied direct search method to solve a global optimization problems. Direct search method is a method for solving optimization problem that dose not require any information about the gradient of the objective function. In PS method, there are two type of moves, the exploratory moves and the pattern moves. In the exploratory moves a coordinate search is applied around a selected solution with a step length of as shown in Algorithm 1. The exploratory move succeeds if the function value of the new solution is better than the current solution. Otherwise, the step length is reduced as shown in Eq. (5). If the exploratory move succeeds, then the pattern search is applied in order to generate the iterate solution. If the iterate solution is better than the current solution, then exploratory move is applied on the iterate solution and the iterate solution is accepted as a new solution. Otherwise, if the exploratory move is unsuccessful, the pattern move is rejected and the step length is reduced. The operation is repeated until termination criteria are satisfied. The algorithm of HJ pattern search and the main steps of it are presented in Algorithm 1. The parameters in Algorithms 1 and 1 are reported in Table 1.
The parameters of the pattern search algorithm
Parameter
Definition
Initial mesh size
Variable dimension
Reduction factor of mesh size
Pattern search repetition number
Tolerance
Exploratory searchINPUT: Get the values of , , , OUTPUT: New base point [1] Set Set Set Set Set Set
The basic pattern search algorithmINPUT: Get the values of OUTPUT: Best solution [1] Set the values of the initial values of the mesh size , reduction factor of mesh size and termination parameter Set Parameter settingSet the starting base point Initial solutionPerform exploratory search as shown in Algorithm 1exploratory move success Go to 16 , Stop the search and the current point is Set Incremental change reductionGo to 5 Perform pattern move, where Perform exploratory move with as the base point Set equal to the output result exploratory move Set Set New base pointGo to 16 Go to 9 The pattern move failsSet The pattern search algorithm is summarized in the following steps.
The algorithm starts by setting the initial values of the mesh size , reduction factor of mesh size and termination parameter .
Apply exploratory search as shown in Algorithm 1 by calculating in order to obtain a new base point
If the exploratory move succeeds, perform pattern search move, otherwise check the value of the mesh size , if , where is a very small value, stop the search and produces the current solution.
If the exploratory move fails and is not less than , reduce the mesh size as shown in the following equation
Apply pattern move by calculating , where
.
Set as a new base point and apply exploratory move on it.
If the pattern move succeeds, repeat the pattern search move on the new point. Otherwise the pattern search fails, reduce the mesh size as in Eq. (5).
The steps are repeated until the termination criteria are satisfied (number of iterations).
Nelder-Mead search strategy in two dimensions.
Nelder Mead method
In 1965 [23], Nelder and Mead proposed the Nelder-Mead algorithm (NM). NM algorithm is one of the most popular derivative-free nonlinear optimization algorithms. It starts with points (vertices) . The vertices are evaluated, ordered and re-labeled in order to assign the best point and the worst point. In minimization problems, the is considered as the best vertex or point if it has the minimum value of the objective function, while the worst point with the maximum value of the objective function. At each iteration, new points are computed, along with their function values, to form a new simplex. Four scalar parameters must be specified to define a complete Nelder-Mead algorithm: coefficients of reflection , expansion , contraction , and shrinkage where , , , and . The main steps of the Nelder-Mead algorithm are presented as shown below in Algorithm 3.2. The vertices are ordered according to their fitness functions. The reflection process starts by computing the reflected point , where is the average of all points except the worst. If the reflected point is lower than the point and greater than the best point , then the reflected point is accepted and the iteration is terminated. If the reflected point is better than the best point, then the algorithm starts the expansion process by calculating the expanded point . If is better than the reflected point , the expanded point is accepted. Otherwise, the reflected point is accepted and the iteration will be terminated. If the reflected point is greater than the point the algorithm starts a contraction process by applying an outside or inside contraction depending on the comparison between the values of the reflected point and the point . If the contraction point or is greater than the reflected point , the shrink process is starting. In the shrink process, the points are evaluated and the new vertices of simplex at the next iteration will be , where .
In Fig. 1, the main steps of the Nelder-Mead algorithm in two dimensions is presented as follows.
Given the current solution , two neighborhood trial points and are generated in a neighborhood of as shown in Fig. 1a.
A simplex is constructed in order to find a local trial point as shown in Fig. 1b.
If is a worst point, the Nelder-Mead algorithm is applied to find a better movement, as shown in Fig. 1c. If a better movement is found, this point is referred as a local trial point.
Overview of the bat algorithm
In this section, an overview of the main concepts and structure of the bat algorithm is given.
Main concepts
Bat algorithm (BA) is a population based metaheuristic algorithm, was developed by Xin-She Yang in 2010 [41]. BA is based on the echolocation of microbats, which use a type of sonar (echolocation) to detect prey and avoid obstacles in the dark. The main advantage of the BA is that it can provide a fast convergence at a very initial stage by switching from exploration to exploitation, however, switching from exploration to exploitation quickly may lead to stagnation after some initial stage.
The rules of the bat algorithm
Based on the bat characteristics, Yang [41] developed the bat algorithm with the following rules.
All bats can distinguish between pray and barriers/obsteculs by using echolocation to sense distance.
Each bat randomly moves with velocity at a position with a frequency varying loudens and pulse emission rate .
Assume that the loudness varies from a large value to a minimum value .
[H] The Nelder-Mead Algorithm1. Let denote the list of vertices in the current simplex, . 2. Order. Order and re-label the vertices from lowest function value to highest function value so that . 3. Reflection. Compute the reflected point by , where is the centroid of the best points, . Replace with the reflected point and go to Step 7. 4. Expansion. Compute the expanded point by . Replace with and go to Step 7. Replace with and go to Step 7. 5. Contraction.Perform a contraction between and the best among and . Calculate Outside contract.Replace with and go to Step 7. Go to Step 6. Calculate . Inside contractReplace with and go to Step 7. Go to Step 6. 6. Shrink. Evaluate the new vertices . Replace the vertices with the new vertices . 7. Stopping Condition. Order and re-label the vertices of the new simplex as such that Stop, where is a small predetermined tolerance. Go to Step 3.
Bat movement
The bat algorithm is a population based method, where the population size consists of bats (solutions). Each bat (solution) in the population is randomly moving with velocity and a location . Also each bat is randomly assigned a frequency drawn uniformly from . The position of each bat in the population is updated as shown in the following equations.
where is a random vector drawn from a uniform distribution.
Variation of loudness and pulse emission rates
The loudness and the pulse rate emission are very important to let the algorithm switch between exploration and exploitation process. When the bat has found its pray, the loudness decreases and the rate of pulse emission increases. The bat algorithm starts with an initial value of the loudness and the rate of pulse emission , then these values are updated as shown in the following equations.
where and are constant, the parameter plays a similar role as the cooling factor in the simulated annealing algorithm.
Bat algorithm
The main steps of the standard bat algorithm are shown in Algorithm 3.5 and can be summarized in the following steps.The bat algorithm[1] Set the initial values of the minimum frequency , maximum frequency , population size , the loudness constant , the rate of pulse emission constant , the initial loudens , the minimum loudness , the initial rate of pulse emission and the maximum number of iterations . Parameters initializationSet Counter initialization() Generate the initial bat population randomly.Generate the initial bat velocities randomly. Assign the initial frequency to each . Evaluate the initial population by calculating the objective function for each solution in the population. Set the initial values of the pulse rates and loudness . Population initializationGenerate new bat solutions by adjusting frequency as in Eq. (8). Update the bat velocities as in Eqs (6) and (7). Evaluate the new population by calculating the objective function for each solution in the population. Select the best solution from the population. Select a solution among the best solutions. Generate a local search solution around the selected best solution. Generate a random new solution. Accept the new solutions. Increase the rate of pulse emission and reduce the loudness Evaluate the new population by calculating the objective function for each solution in the population. Rank the population and select the best solution from the population. () Termination criteria are satisfiedProduce the best solution.
The algorithm starts by setting the initial values of its parameters and setting zero to the main iteration counter (Lines 1–2).
The initial population is randomly generated by generating the initial position and the initial velocity for each bat (solution) in the population. The initial frequency is assigned to each solution in the population, where is randomly generated from . The initial population is evaluated by calculating the objective function for each solution via the initial population , the values of pulse rate and initial loudness where and varies from a large to (Lines 3–9).
The new population is generated by adjusting the position and the velocity for each solution in the population as in Eqs (6)–(8) (Lines 12–13).
The new population is evaluated by calculating the objective function for each solution and the best solution is selected from the population (Lines 14–15).
The local search method is applied in order to refine the best found solution at each iteration (Lines 16–19).
The new solution is accepted with some proximity depending on parameter , increasing the rate of pulse emission and decreasing the loudness. The values of and are updated as in Eqs (9) and (10).
The new population is evaluated and the best solution is selected from the population. The operations are repeated until termination criteria are satisfied and the overall best solution is produced (Lines 25–28).
The proposed HBATDS algorithm
The main steps of the proposed HBATDS algorithm are presented in Algorithm 4 and the description of the proposed algorithm can be summarized as follows. The HBATDS algorithm[1] Set the initial values of the minimum frequency , maximum frequency , population size , the loudness constant , the rate of pulse emission constant , the initial loudens , the minimum loudens , the initial rate of pulse emission and the maximum number or iterations . Parameters initializationSet Counter initialization() Generate the initial bat population randomly.Generate the initial bat velocities randomly. Assign the initial frequency to each Evaluate the initial population by calculating the objective function for each solution in the population. Set the initial values of the pulse rates and loudness Population initializationGenerate new bat solutions by adjusting frequency as in Eqs (6)–(8). Update the bat velocities as in Eq. (7). Evaluate the new population by calculating the objective function for each solution in the population. Select the best solution from the population. Select a solution among the best solutions. Apply the pattern search method as shown in Algorithm 1 on the best solution from the best solutions list. Exploitation processGenerate a random new solution. Accept the new solutions Increase the rate of pulse emission and reduce the loudness as in Eqs (9) and (10). Evaluate the new population by calculating the objective function for each solution in the population. Rank the population and select the best solution from the population. () Termination criteria are satisfied.Apply Nelder-Mead method on the best solutions, , as shown in Algorithm 3.2. Final intensification
The parameters of the minimum frequency , maximum frequency , population size , the loudness constant , the rate of pulse emission constant , the initial loudness , the minimum loudness , the initial rate of pulse emission , the maximum number of iterations and the initial iteration counter are set to their initial values (Lines 1–2).
The initial population is randomly generated by generating the initial position and the initial velocity for each bat (solution) in the population. The initial frequency is assigned to each solution in the population. The initial population is evaluated by calculating the objective function for each solution via the initial population and the values of pulse rate and initial loudness (Lines 3–9).
The new population is generated by adjusting the position and the velocity for each solution in the population as in Eqs (6)–(8) (Lines 12–13).
The new population is evaluated by calculating the objective function for each solution and the best solution is selected from the population (Lines 14–15).
The pattern search method as a local search method is applied as shown in Algorithm 1 in order to refine the best found solution at each iteration (Lines 16–19).
The new solution is accepted with some proximity depending on parameter , increasing the rate of pulse emission and decreasing the loudness as in Eqs (9) and (10) (Lines 21–24).
The new population is evaluated and the best solution is selected from the population. The operations are repeated until termination criteria are satisfied.
In order to accelerate the search and avoid running the algorithm with more iterations without any improvement in the results, the Nelder-Mead method is applied on the best found solution in the previous stage as a final intensification process (Line 28).
Numerical experiments
In this section, the efficiency of the HBATDS algorithm is evaluated by presenting its general performance on different benchmark functions and comparing the results of the proposed algorithm against various algorithms. In the following subsections, the parameters setting of the proposed algorithm and the properties of the applied test functions are reported. Also the performance analysis of the proposed algorithm is presented with the comparative results between it and the other algorithms.
The efficiency of the proposed HBATDS algorithm on minimax problems.
The performance of HBATDS algorithm with minimax problems.
Minimax test functions properties
Function
Dimension (d)
Desired error goal
2
1.95222245
2
2
4
40.1
7
247
2
10
2
4
44
7
680
4
0.1
The efficiency of invoking the Nelder-Mead method in the final stage of HBATDS for – minimax problems
Function
HBATDS without NM
HBATDS with NM
941.12
435.58
970.23
418.52
1115.76
530.38
4106.25
3170.22
722.12
252.14
3615.61
2915.34
1815.22
1195.2
20,000
2310.3
2110.21
1356.91
1217.61
637.9
Parameter setting
The parameters of the HBATDS algorithm have been summarized with their assigned values in Table 2. Note that the parameters values are based on the common setting in the literature.
Population size . The experimental tests show that the best population size is , increasing this number will increase the evaluation function values without any improvement in the obtained results.
Frequency parameter . Bat movement is based on the value of the frequency parameter . In HBATDS algorithm, the quality of the solution is related to the value of parameter. The experimental tests show that the best maximum value of is and the minimum value of is .
Loudness parameters , . Loudness parameter is one of the most important parameters in the bat algorithm. The acceptance of the new generated solutions is depending on the value of . The parameter plays a similar role as the cooling factor in the simulated annealing algorithm. The initial value of is set to and the value of is set to .
Pulse emission rate . The value of the rate of pulse emission parameter is very important to apply the local search method in the algorithm. The experimental tests show that the best value of is 0.9 and the rate of pulse emission constant is .
Pattern search parameters. HBATDS uses PS as a local search method in order to refine the best obtained solution from the bat algorithm at each iteration. In PS the mesh size is initialized as , in our experiments and when no improvement achieved in the exploration search process, the mesh size is deducted by using reduction factor . The experimental results show that the best value of is 0.01. The PS steps are repeated times, in order to increase the exploitation process of the algorithm. In our experiment as a pattern search iteration number.
Stopping condition parameters. HBATDS terminates the search when the number of iterations reaches to the desired maximum number of iterations or any other termination depending on the comparison with other algorithms. In our experiment, the value of the maximum iteration number , where is the dimension of the problems.
Final intensification. The best obtained solutions from the bat algorithm and the pattern search method are collected in a list in order to apply the Nelder-Mead method on them, the number of the solutions in this list is called , in order to avoid increasing the value of the function evaluation value, .
Minimax optimization test problems
In order to investigate the efficiency of the proposed algorithm, we test it on 10 benchmark minimax functions, their properties are reported in Table 4 and the form of each function is listed in Table 3.
The efficiency of the proposed HBATDS algorithm with minimax problems
We test the efficiency of the HBATDS algorithm by comparing it against the standard bat algorithm. The values of the parameters for both algorithms are set the same in order to make a fair comparison. The functions , , , and have been selected to show the efficiency of the proposed algorithm by plotting the values of function values versus the number of iterations as shown in Fig. 2. In Fig. 2, the solid line refers to the proposed HBATDS results, while the dotted line refers to the standard bat algorithm results after 50 iterations. Figure 2 shows that the function values rapidly decrease as the number of iterations increases for HBATDS results than those of the standard bat algorithm. The results in Fig. 2 show that the combination between the standard bat algorithm and the pattern search method can improve the performance of the standard bat algorithm and accelerate the convergence of the proposed algorithm.
The performance of the HBATDS algorithm on minimax problems
The proposed HBATDS has been investigated to verify of the general performance of it with the minimax problems by plotting the values of function values versus the number of iterations as shown in Fig. 3 for five test functions , , , and . The results in Fig. 3 are the results of the proposed algorithm without applying the Nelder-Mead method in the final stage of the algorithm after 50 iterations. The results in Fig. 3 show that the function values of the proposed HBATDS algorithm rapidly decrease as the number of iterations increases which verify that the hybridization between the bat algorithm and the pattern search method can accelerate the search and help the algorithm to obtain the optimal or near optimal solution in few iterations.
Evaluation function for the minimax problems –
Algorithm
Problem
Avg
SD
%Suc
HPS2
1848.7
2619.4
99
635.8
114.3
94
141.2
28.4
37
8948.4
5365.4
7
772.0
60.8
100
1809.1
2750.3
94
4114.7
1150.2
100
–
–
–
283.0
123.9
64
324.1
173.1
100
UPSOm
1993.8
853.7
100
1775.6
241.9
100
1670.4
530.6
100
12,801.5
5072.1
100
1701.6
184.9
100
18,294.5
2389.4
100
3435.5
1487.6
100
6618.50
2597.54
100
2128.5
597.4
100
3332.5
1775.4
100
RWMPSOg
2415.3
1244.2
100
–
–
–
3991.3
2545.2
100
7021.3
1241.4
100
2947.8
257.0
100
18,520.1
776.9
100
1308.8
505.5
100
–
–
–
–
–
–
4404.0
3308.9
100
HBATDS
435.58
30.24
100
418.52
33.48
100
530.38
66.14
100
3170.22
558.01
36
252.14
20.44
100
2915.34
20.17
90
1195.2
116.7
90
2310.3
861.9
5
1356.91
134.69
60
637.9
117.398
95
The comparison results (function evaluation values) between HBATDS algorithm and other algorithms for minimax problems.
HBATDS and other meta-heuristics and swarm intelligence algorithms for – minmax problems
Function
GA
PSO
FF
CS
GWO
HBATDS
Avg
1080.45
3535.46
1125.61
5375.52
2940.2
435.58
SD
83.11
491.66
189.56
613.35
490.22
30.24
Avg
1120.15
20,000
785.17
6150.34
3740.14
418.52
SD
65.14
0.00
31.94
519.65
712.19
33.48
Avg
1270.65
2920.15
695.54
3745.19
1120.25
530.38
SD
95.26
269.48
50.03
878.09
417.04
66.14
Avg
2220.45
9155.35
1788.26
11,455.17
4940.35
3170.22
SD
488.45
649.12
118.09
1511.69
313.60
558.01
Avg
1040.84
5680.17
582.52
5845.23
3520.45
252.14
SD
55.89
937.44
86.77
804.36
946.36
20.44
Avg
20,000
20,000
13,692.13
7895.14
2080.35
2915.34
SD
0.00
0.00
900.12
1077.07
938.33
20.17
Avg
1120.25
5643.65
2685.25
11,915.24
1020.45
1195.34
SD
65.89
4.3.22
610.07
341.45
219.90
116.7
Avg
1280.35
20,000
7659.45
20,000
1620.46
2310.3
SD
78.23
0.00
583.21
1788.18
281.25
861.9
Avg
20,000
6220.25
8147.45
14,754.14
3760.54
1356.91
SD
0.00
727.44
1026.22
1391.58
246.52
134.69
Avg
1080.65
6680.19
748.17
6765.24
1630.4
637.9
SD
68.15
509.34
98.59
843.49
37.36
117.398
The efficiency of applying the Nelder-Mead method in the proposed HBATDS algorithm with minimax problems
Another test has been applied in order to investigate the efficiency of the proposed algorithm by invoking NM method in the final stage as a final intensification process. The results in Table 5 show the mean evaluation function values of the proposed HBATDS algorithm without and with applying Nelder-Mead method, respectively. The termination criteria, the algorithm terminates the search when the fitness value of the function reaches to within 20,000 function evaluation value, are set the same for both algorithms. The best results are reported in boldface text. The results in Table 5, show that invoking the Nelder-Mead method in the final stage can accelerate the search to reach to the optimal or near optimal solution faster than the proposed algorithm without applying the Nelder-Mead method.
HBATDS and other algorithms
HBATDS is compared with three benchmark algorithms in order to verify of the efficiency of the proposed algorithm. Before discussing the comparison results of all algorithms, a brief description about the comparative three algorithms is presented.
HPS2 [13]. HPS2 is Heuristic Pattern Search algorithm, which is applied for solving bound constrained minimax problems by combining the Hook and Jeeves (HJ) pattern and exploratory moves with a randomly generated approximate descent direction.
UPSOm [24]. UPSOm is Unified Particle Swarm Optimization algorithm, which combines theglobal and local variants of the standard PSO and incorporates a stochastic parameter to imitate mutation in evolutionary algorithms.
RWMPSOg [26]. RWMPSOg is Random Walk Memetic Particle Swarm Optimization (withglobal variant), which combines the particle swarmoptimization with random walk as direction exploitation.
Comparison between HPS2, UPSOm, RWMPSOg and HBATDS for minimax problems
In this subsection, the comparison results between our HSAPSMP algorithm and the other algorithms is presented in order to verify of the efficiency of our proposed algorithm. The four comparative algorithms are tested on 10 benchmark functions and reported. The results of the comparative algorithms are taken from there original papers. In Table 6, the average (Avg), standard deviation (SD) and Success rate (%Suc) are reported over 50 runs. The mark (–) for , in RWMPSOg algorithm and in HPS2 and RWMPSOg algorithms in Table 6 means that the results of these algorithm are not reported in their original paper. The run is considered successful if the algorithm reaches the global minimum of the solution within an error of before the 20,000 function evaluation value. The results in Table 6 and Fig. 4 show that the proposed HBATDS algorithm obtains the objective value of each function faster than the other algorithms, except for functions , , and . The main reason of increasing the values of function evaluations in HBATDS for these functions is the use of the Nelder-Mead algorithm in the final stage, especially, when . In the final stage of the algorithm, when the bat algorithm and the pattern search method fail to reach the optimal solution, then the Nelder-Mead method will increase the iterations to obtain the desired value of the objective functions, i.e., increasing the function evaluation value.
HBATDS and other meta-heuristics and swarm intelligence algorithms for minmax problems
We test the HBATDS algorithm against different meta-heuristics and swarm intelligence algorithms (SI) such as genetic algorithm (GA) [11], standard particle swarm optimization (PSO) [15], firefly (FF) [39], cuckoo search (CS) [40] and grey wolf optimization algorithms (GWO) [21]. We make fair comparison by setting the population size 20 for all algorithms and the termination criteria for all algorithm are the same, i.e., the algorithm reaches to the global minimum of the solution within an error of before the 20,000 function evaluation value. For the GA, the probability of crossover is set to be , probability of mutation and we apply the roulette wheel selection. For the other SI algorithms we apply the standard parameter setting for each algorithm. We report the average (Avg) and standard deviation (SD) of all algorithms over 50 runs as shown in Table 7.
The results in Table 7 show that the proposed HBATDS algorithm is outperform the other SI algorithm
Conclusion
In this paper, a new hybrid algorithm is proposed by combining the bat algorithm with direct search methods in order to solve minimmax problems. The proposed algorithm is called hybrid bat direct search algorithm (HBATDS). In the proposed algorithm, The performance of the standard bat algorithm is accelerated by invoking the pattern search method as a local search method and the Nelder-Mead method in the final stage of the algorithm. The HBATDS algorithm is intensely tested on 10 minimax problems. The proposed algorithm is compared against other 8 algorithms to test its performance for minimax problems. The numerical results indicate that the proposed HBATDS algorithm is a promising algorithm and suitable to find a global optimal solution or near optimal solution in reasonable time.
Footnotes
Acknowledgments
The research of the 2nd author is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC). The postdoctoral fellowship of the 1st author is supported by NSERC.
References
1.
AliA.F. and TawhidM.A., Hybrid-simulated annealing and pattern search method for solving minimax and integer programming problems, Pacific Journal of Optimization12(1) (2016), 151–184.
2.
AliA.F. and TawhidM.A., A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems, Ain Shams Engineering Journal (2016).
3.
AliA.F. and TawhidM.A., Direct gravitational search algorithm for global optimisation problems, East Asian Journal on Applied Mathematics6(3) (2016), 290–313.
4.
AliA.F. and TawhidM.A., A hybrid cuckoo search algorithm with Nelder Mead method for solving global optimization problems, Springer Plus5(1) (2016), 1–22.
5.
BandlerJ.W. and CharalambousC., Nonlinear programming using minimax techniques, Journal of Optimization Theory and Applications13 (1974), 607–619.
6.
Bernabe-LorancaM.B.Ruiz-VanoyeJ.VelazquezR.G.AnalcoM.E.López AnalcoA.S.ZezzatiA.O.GuzmanG.M. and DiazM.B., An approximation method for the P-median problem: A bioinspired tabu search and variable neighborhood search partitioning approach, International Journal of Hybrid Intelligent Systems13(2) (2016), 87–98.
7.
ChuS.A.TsaiP.-W. and PanJ.-S., Cat swarm optimization, Lecture Notes in Computer Science (including sub-series Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4099 LNAI (2006), 854–858.
8.
DorigoM., Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
9.
HarfouchiF. and HabbiH., A cooperative learning artificial bee colony algorithm with multiple search mechanisms, International Journal of Hybrid Intelligent Systems13(2) (2016), 113–124.
10.
HillierF.S. and LiebermanG.J., Introduction to Operations Research, MCGraw-Hill, 1995.
11.
HollandJ.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.
12.
HookeR. and JeevesT.A., Direct search solution of numerical and statistical problems, J Assoc Comput Mach (1961), 212–229.
13.
IsabelA.C.P.SantoE. and FernandesE., Heuristics pattern search for bound constrained minimax problems, Computational Science and its Applications, ICCSA6784 (2011), 174–184.
14.
KarabogaD. and BasturkB., A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, Journal of Global Optimization39(3) (2007), 459–471.
15.
KennedyJ. and EberhartR.C., Particle swarm optimization, Proceedings of the IEEE International Conference on Neural Networks4 (1995), 1942–1948.
16.
KomarasamyG. and WahiA., An optimized K-means clustering technique using bat algorithm, European J Scientific Research84(2) (2012), 263–273.
17.
LiX.L.ShaoZ.J. and QianJ.X., Optimizing method based on autonomous animats: Fish-swarm algorithm, System Engineering Theory and Practice22(11) (2002), 32.
18.
LiuzziG.LucidiS. and SciandroneM., A derivative-free algorithm for linearly constrained finite minimax problems, SIAM Journal on Optimization16 (2006), 1054–1075.
19.
LinJ.H.ChouC.W.YangC.H. and TsaiH.L., A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems, J Computer and Information Technology2(2) (2012), 56–63.
20.
LukanL. and VlcekJ., Test problems for nonsmooth unconstrained and linearly constrained optimization, Technical Report 798, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, Czech Republic, 2000.
21.
MirjaliliS.MirjaliliS.M. and LewisA., Grey Wolf Optimizer, Advances in Engineering Software69 (2014), 46–61.
22.
NakamuraR.Y.M.PereiraL.A.M.CostaK.A.RodriguesD.PapaJ.P. and YangX.S., BBA: A binary bat algorithm for feature selection, 25th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), IEEE Publication (2012), 291–297.
23.
NelderJ.A. and MeadR., A simplex method for function minimization, Computer Journal7 (1965), 308–313.
24.
ParsopoulosK.E. and VrahatisM.N., Unified particle swarm optimization for tackling operations research problems, In Proceeding of IEEE 2005 Swarm Intelligence Symposium, Pasadena, USA (2005), 53–59.
25.
PassinoM.K., Biomimicry of bacterial foraging for distributed optimization and control, Control Systems, IEEE22(3) (2002), 52–67.
26.
PetalasY.G.ParsopoulosK.E. and VrahatisM.N., Memetic particle swarm optimization, Ann Oper Res156 (2007), 99–127.
27.
PolakE.RoysetJ.O. and WomersleyR.S., Algorithms with adaptive smoothing for finite minimax problems, Journal of Optimization Theory and Applications119 (2003), 459–484.
28.
SchwefelH.P., Evolution and Optimum Seeking, New York, Wiley, 1995.
29.
SopovE., A selection hyper-heuristic with online learning for control of genetic algorithm ensemble, International Journal of Hybrid Intelligent Systems13(2) (2016), 125–135.
30.
TakahamaT. and SakaiS., Improving an adaptive differential evolution using hill-valley detection, International Journal of Hybrid Intelligent Systems13(1) (2016), 1–13.
31.
TangR.FongS.YangX.S. and DebS., Wolf search algorithm with ephemeral memory, In Digital Information Management (ICDIM), 2012 Seventh International Conference on Digital Information Management (2012), 165–172.
32.
TawhidM.A. and AliA.F., Direct Search Firefly Algorithm for Solving Global Optimization Problems, Applied Mathematics & Information Sciences (2016), 841-860.
33.
TawhidM.A. and AliA.F., Simplex particle swarm optimization with arithmetical crossover for solving global optimization problems, OPSEARCH (2016), 1–36.
34.
TawhidM.A. and AliA.F., A simplex social spider algorithm for solving integer programming and minimax problems, Memetic Computing Feb (2016).
35.
TeodorovicD. and DellOrcoM., Bee colony optimization a cooperative learning approach to complex transportation problems, In Advanced OR and AI Methods in Transportation, Proceedings of 16th Mini EURO Conference and 10th Meeting of EWGT (13-16 September 2005). Poznan: Publishing House of the Polish Operational and System Research (2005), 51–60.
36.
WangG. and GuoL., A novel hybrid bat algorithm with harmony search for global numerical optimization, Journal of Applied Mathematics2013 (2013).
37.
XieJ.ZhouY.Q. and ChenH., A novel bat algorithm based on differential operator and Levy flights trajectory, Computational Intelligence and Neuroscience2013 (2013).
38.
XuS., Smoothing method for minimax problems, Computational Optimization and Applications20 (2001), 267–279.
39.
YangX.S., Firefly algorithm, stochastic test functions and design optimization, International Journal of Bio-Inspired Computation2(2) (2010), 78–84.
40.
YangX.S. and DebS., Cuckoo search via Lévy fights, Proc of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), December 2009, India? IEEE Publications, USA (2009), 210–214.
41.
YangX.S., A new metaheuristic bat-inspired algorithm, Nature Inspired Cooperative Strategies for Optimization (NICSO 2010) (2010), 65–74.
42.
YangX.S., Bat algorithm for multi-objective optimization, Int J BioInspired Computation3(5) (2011), 267–274.
43.
ZhangJ.W. and WangG.G., Image matching using a bat algorithm with mutation, Applied Mechanics and Materials (Edited by DuZ.Y. and LiuB.) 203(1) (2012), 88–93.