Hybrid bat algorithm and direct search methods for solving minimax problems

Abstract

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.

Keywords

Bat algorithm direct search methods pattern search Nelder-Mead method minimax problemsMathematics Subject Classification. 90C47 90C30 49K35 68U20 68W01.

1. Introduction

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.

2. 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.

2.1 Minimax problem definition

The general form of the minimax problem as reported in [38] is defined by:

$\displaystyle\min F(x)$ (1)

where

$\displaystyle F(x)=\max f_{i}(x),i=1,\ldots,m$ (2)

with $f_{i}(x)\!:S\subset\mathbb{R}^{n}\rightarrow\mathbb{R},i=1,\ldots,m$ .

The nonlinear programming problems of the form:

$\displaystyle\min F(x),g_{i}(x)\geqslant 0,i=2,\ldots,m,$

can be transformed to minimax problems as follows:

$\displaystyle\min\max f_{i}(x),i=1,\ldots,m$ (3)

where

$\displaystyle f_{1}(x)=F(x),f_{i}(x)=F(x)-\alpha_{i}g_{i}(x),\alpha_{i}>0,i=2,% \ldots,m$ (4)

It has been proved that for sufficiently large $\alpha_{i}$ , the optimum point of the nonlinear programming problem coincides with the optimum point of the minimax problem [5].

2.2 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 $\Delta$ 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 $\Delta$ 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.

Table 1
The parameters of the pattern search algorithm

Parameter	Definition
$\Delta_{0}$	Initial mesh size
$d$	Variable dimension
$\sigma$	Reduction factor of mesh size
$m$	Pattern search repetition number
$\varepsilon$	Tolerance

Exploratory searchINPUT: Get the values of $x^{0}$ , $k$ , $\Delta_{0}$ , $d$ OUTPUT: New base point $x^{k}$ [1] Set $i=1$ Set $k=1$ Set $x_{i}^{k}=x_{i}^{k-1}+\Delta_{k-1}x_{i}^{k-1}$ $f(x_{i}^{k})<f(x_{i}^{k-1})$ Set $x_{i}^{k+1}=x_{i}^{k}$ Set $i=i+1$ Set $k=k+1$ $i>d$

The basic pattern search algorithmINPUT: Get the values of $x$ OUTPUT: Best solution $x^{\ast}$ [1] Set the values of the initial values of the mesh size $\Delta_{0}$ , reduction factor of mesh size $\sigma$ and termination parameter $\varepsilon$ Set $k=1$ Parameter settingSet the starting base point $x^{k-1}$ Initial solutionPerform exploratory search as shown in Algorithm 1exploratory move success Go to 16 $\|\Delta_{k}\|<\varepsilon$ , Stop the search and the current point is $x^{\ast}$ Set $\Delta_{k}=\sigma\Delta_{k-1}$ Incremental change reductionGo to 5 Perform pattern move, where $x_{p}^{k+1}=x^{k}+(x^{k}-x^{k-1})$ Perform exploratory move with $x_{p}$ as the base point Set $x^{k+1}$ equal to the output result exploratory move $f(x_{p}^{k+1})<f(x^{k})$ Set $x^{k-1}=x^{k}$ Set $x^{k}=x^{k+1}$ New base pointGo to 16 Go to 9 The pattern move failsSet $k=k+1$ $k>m$ The pattern search algorithm is summarized in the following steps.

Step 1. Step 1.

The algorithm starts by setting the initial values of the mesh size $\Delta_{0}$ , reduction factor of mesh size $\sigma$ and termination parameter $\varepsilon$ .

Step 2.

Apply exploratory search as shown in Algorithm 1 by calculating $f(x^{k})$ in order to obtain a new base point

Step 3.

If the exploratory move succeeds, perform pattern search move, otherwise check the value of the mesh size $\Delta$ , if $\Delta<\varepsilon$ , where $\varepsilon$ is a very small value, stop the search and produces the current solution.

Step 4.

If the exploratory move fails and $\Delta$ is not less than $\varepsilon$ , reduce the mesh size as shown in the following equation

$\displaystyle\Delta_{k}=\sigma\Delta_{k-1}.$ (5)

Step 5.

Apply pattern move by calculating $x_{p}$ , where

$x_{p}^{k+1}=x^{k}+(x^{k}-x^{k-1})$ .

Step 6.

Set $x_{p}$ as a new base point and apply exploratory move on it.

Step 7.

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).

Step 8.

The steps are repeated until the termination criteria are satisfied (number of iterations).

Figure 1.

Nelder-Mead search strategy in two dimensions.

2.3 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 $n+1$ points (vertices) $x_{1},$ $x_{2},\ldots,x_{n+1}$ . The vertices are evaluated, ordered and re-labeled in order to assign the best point and the worst point. In minimization problems, the $x_{1}$ is considered as the best vertex or point if it has the minimum value of the objective function, while the worst point $x_{n+1}$ 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 $\rho$ , expansion $\chi$ , contraction $\tau$ , and shrinkage $\phi$ where $\rho>0$ , $\chi>1$ , $0<\tau<1$ , and $0<\phi<1$ . 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 $x_{r}=\bar{x}+\rho(\bar{x}-x_{(n+1)})$ , where $\bar{x}$ is the average of all points except the worst. If the reflected point $x_{r}$ is lower than the $n{\rm th}$ point $f(x_{n})$ and greater than the best point $f(x_{1})$ , 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 $x_{e}=\bar{x}+\chi(x_{r}-\bar{x})$ . If $x_{e}$ is better than the reflected point $n{\rm th}$ , the expanded point is accepted. Otherwise, the reflected point is accepted and the iteration will be terminated. If the reflected point $x_{r}$ is greater than the $n{\rm th}$ point $x_{n}$ the algorithm starts a contraction process by applying an outside $x_{oc}$ or inside contraction $x_{ic}$ depending on the comparison between the values of the reflected point $x_{r}$ and the $n{\rm th}$ point $x_{n}$ . If the contraction point $x_{oc}$ or $x_{ic}$ is greater than the reflected point $x_{r}$ , 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 $x^{\prime}_{2},\ldots,x^{\prime}_{n+1}$ , where $x^{\prime}=x_{1}+\phi(x_{i}-x_{1}),i=2,\ldots,n+1$ .

In Fig. 1, the main steps of the Nelder-Mead algorithm in two dimensions is presented as follows.

Step 1. Step 1.
Given the current solution $x$ , two neighborhood trial points $y_{1}$ and $y_{2}$ are generated in a neighborhood of $x$ as shown in Fig. 1a.
Step 2.
A simplex is constructed in order to find a local trial point as shown in Fig. 1b.
Step 3.
If $y_{2}$ 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.

3. Overview of the bat algorithm

In this section, an overview of the main concepts and structure of the bat algorithm is given.

3.1 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.

3.2 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 $v_{i}$ at a position $x_{i}$ with a frequency $f_{\min}$ varying loudens $A_{0}$ and pulse emission rate $r$ .
•
Assume that the loudness varies from a large value $A_{0}$ to a minimum value $A_{\min}$ .

[H] The Nelder-Mead Algorithm1. Let $x_{i}$ denote the list of vertices in the current simplex, $i=1,\ldots,n+1$ . 2. Order. Order and re-label the $n+1$ vertices from lowest function value $f(x_{1})$ to highest function value $f(x_{n+1})$ so that $f(x_{1})\leqslant f(x_{2})\leqslant\ldots\leqslant f(x_{n+1})$ . 3. Reflection. Compute the reflected point $x_{r}$ by $x_{r}=\bar{x}+\rho(\bar{x}-x_{(n+1)})$ , where $\bar{x}$ is the centroid of the $n$ best points, $\bar{x}=\sum(x_{i}/n),i=1,\ldots,n$ . $f(x_{1})\leqslant f(x_{r})<f(x_{n})$ Replace $x_{n+1}$ with the reflected point $x_{r}$ and go to Step 7. 4. Expansion. $f(x_{r})<f(x_{1})$ Compute the expanded point $x_{e}$ by $x_{e}=\bar{x}+\chi(x_{r}-\bar{x})$ . $f(x_{e})<f(x_{r})$ Replace $x_{n+1}$ with $x_{e}$ and go to Step 7. Replace $x_{n+1}$ with $x_{r}$ and go to Step 7. 5. Contraction. $f(x_{r})\geqslant f(x_{n})$ Perform a contraction between $\bar{x}$ and the best among $x_{n+1}$ and $x_{r}$ . $f(x_{n})\leqslant f(x_{r})<f(x_{n+1})$ Calculate $x_{oc}=\bar{x}+\tau(x_{r}-\bar{x})$ Outside contract. $f(x_{oc})\leqslant f(x_{r})$ Replace $x_{n+1}$ with $x_{oc}$ and go to Step 7. Go to Step 6. $f(x_{r})\geqslant f(x_{(n+1)}$ Calculate $x_{ic}=\bar{x}+\tau(x_{n+1}-\bar{x})$ . Inside contract $f(x_{ic})\geqslant f(x_{(n+1)}$ Replace $x_{n+1}$ with $x_{ic}$ and go to Step 7. Go to Step 6. 6. Shrink. Evaluate the $n$ new vertices $x^{\prime}=x_{1}+\phi(x_{i}-x_{1}),i=2,\ldots,n+1$ . Replace the vertices $x_{2},\ldots,x_{n+1}$ with the new vertices $x^{\prime}_{2},\ldots,$ $x^{\prime}_{n+1}$ . 7. Stopping Condition. Order and re-label the vertices of the new simplex as $x_{1},x_{2},\ldots,x_{n+1}$ such that $f(x_{1})\leqslant f(x_{2})\leqslant\ldots\leqslant f(x_{n+1})$ $f(x_{n+1})-f(x_{1})<\epsilon$ Stop, where $\epsilon>0$ is a small predetermined tolerance. Go to Step 3.
3.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 $v_{i}$ and a location $x_{i}$ . Also each bat is randomly assigned a frequency drawn uniformly from $[f_{\min},f_{\max}]$ . The position of each bat in the population is updated as shown in the following equations.

$\displaystyle f_{i}=f_{\min}+(f_{\max}-f_{\min})\beta$ (6) $\displaystyle v^{t}_{i}=v^{t-1}_{i}+(x^{t-1}_{i}-x^{\ast})f_{i},$ (7) $\displaystyle x^{t}_{i}=x^{t-1}_{i}+v^{t}_{i},$ (8)

where $\beta\in[0,1]$ is a random vector drawn from a uniform distribution.

3.4 Variation of loudness and pulse emission rates

The loudness $A_{i}$ and the pulse rate emission $r_{i}$ 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 $A_{0}$ and the rate of pulse emission $r_{0}$ , then these values are updated as shown in the following equations.

$\displaystyle A_{i}^{(t+1)}=\alpha A_{i}^{(t)}$ (9) $\displaystyle r_{i}^{(t)}=r_{i}^{(0)}[1-\exp(-\gamma t)]$ (10)

where $\alpha\in[0,1]$ and $\gamma>0$ are constant, the $\alpha$ parameter plays a similar role as the cooling factor in the simulated annealing algorithm.

3.5 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 $f_{\min}$ , maximum frequency $f_{\max}$ , population size $P$ , the loudness constant $\alpha$ , the rate of pulse emission constant $\gamma$ , the initial loudens $A_{0}$ , the minimum loudness $A_{\min}$ , the initial rate of pulse emission $r^{0}$ and the maximum number of iterations $\emph{Max}_{itr}$ . Parameters initializationSet $t=0.$ Counter initialization( $i=1;i<{P};i{++}$ ) Generate the initial bat population $x^{t}_{i}$ randomly.Generate the initial bat velocities $v^{t}_{i}$ randomly. Assign the initial frequency $f_{i}$ to each $x^{t}_{i}$ . Evaluate the initial population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Set the initial values of the pulse rates $r_{i}$ and loudness $A_{i}$ . Population initialization $t=t+1$ Generate new bat solutions $x^{t}_{i}$ by adjusting frequency as in Eq. (8). Update the bat velocities $v^{t}_{i}$ as in Eqs (6) and (7). Evaluate the new population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Select the best solution $x^{\ast}$ from the population. $\textit{rand}>r_{i}$ Select a solution among the best solutions. Generate a local search solution around the selected best solution. Generate a random new solution. $\textit{rand}<A_{i}\&f(x^{t}_{i}<f(x^{\ast}))$ Accept the new solutions. Increase the rate of pulse emission $r_{i}$ and reduce the loudness $A_{0}.$ Evaluate the new population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Rank the population and select the best solution $x^{\ast}$ from the population. ( $t>\emph{Max}_{itr}$ ) Termination criteria are satisfiedProduce the best solution.

Step 1. Step 1.
The algorithm starts by setting the initial values of its parameters and setting zero to the main iteration counter (Lines 1–2).
Step 2.
The initial population is randomly generated by generating the initial position $x^{0}$ and the initial velocity $v^{0}$ for each bat (solution) in the population. The initial frequency $f_{i}$ is assigned to each solution in the population, where $f$ is randomly generated from $[f_{\min},f_{\max}]$ . The initial population is evaluated by calculating the objective function for each solution via the initial population $f(x^{0}_{i})$ , the values of pulse rate $r_{i}$ and initial loudness $A_{i}$ where $r\in[0,1]$ and $A_{i}$ varies from a large $A_{0}$ to $A_{\min}$ (Lines 3–9).
Step 3.
The new population is generated by adjusting the position $x_{i}$ and the velocity $v_{i}$ for each solution in the population as in Eqs (6)–(8) (Lines 12–13).
Step 4.
The new population is evaluated by calculating the objective function for each solution and the best solution $x^{\ast}$ is selected from the population (Lines 14–15).
Step 5.
The local search method is applied in order to refine the best found solution at each iteration (Lines 16–19).
Step 6.
The new solution is accepted with some proximity depending on parameter $A_{i}$ , increasing the rate of pulse emission and decreasing the loudness. The values of $A_{i}$ and $r_{i}$ are updated as in Eqs (9) and (10).
Step 7.
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).

4. 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 $f_{\min}$ , maximum frequency $f_{\max}$ , population size $P$ , the loudness constant $\alpha$ , the rate of pulse emission constant $\gamma$ , the initial loudens $A_{0}$ , the minimum loudens $A_{\min}$ , the initial rate of pulse emission $r^{0}$ and the maximum number or iterations $\emph{Max}_{itr}$ . Parameters initializationSet $t=0.$ Counter initialization( $i=1;i<{P};\emph{i++}$ ) Generate the initial bat population $x^{t}_{i}$ randomly.Generate the initial bat velocities $v^{t}_{i}$ randomly. Assign the initial frequency $f_{i}$ to each $x^{t}_{i}.$ Evaluate the initial population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Set the initial values of the pulse rates $r_{i}$ and loudness $A_{i}.$ Population initialization $t=t+1.$ Generate new bat solutions $x^{t}_{i}$ by adjusting frequency as in Eqs (6)–(8). Update the bat velocities $v^{t}_{i}$ as in Eq. (7). Evaluate the new population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Select the best solution $x^{\ast}$ from the population. $(\textit{rand}>r_{i})$ 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. $(\textit{rand}<A_{i})\&f(x^{t}_{i}<f(x^{\ast}))$ Accept the new solutions Increase the rate of pulse emission $r_{i}$ and reduce the loudness $A_{0}$ as in Eqs (9) and (10). Evaluate the new population by calculating the objective function $f(x^{t}_{i})$ for each solution in the population. Rank the population and select the best solution $x^{\ast}$ from the population. ( $t>\textit{Max}_{itr}$ ) Termination criteria are satisfied.Apply Nelder-Mead method on the best solutions, $N_{\textit{elite}}$ , as shown in Algorithm 3.2. Final intensification

Step 1. Step 1.
The parameters of the minimum frequency $f_{\min}$ , maximum frequency $f_{\max}$ , population size $P$ , the loudness constant $\alpha$ , the rate of pulse emission constant $\gamma$ , the initial loudness $A_{0}$ , the minimum loudness $A_{\min}$ , the initial rate of pulse emission $r_{0}$ , the maximum number of iterations $\textit{Max}_{itr}$ and the initial iteration counter are set to their initial values (Lines 1–2).
Step 2.
The initial population is randomly generated by generating the initial position $x^{0}$ and the initial velocity $v^{0}$ for each bat (solution) in the population. The initial frequency $f^{0}_{i}$ 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 $f(x^{0}_{i})$ and the values of pulse rate $r_{i}$ and initial loudness $A_{i}$ (Lines 3–9).
Step 3.
The new population is generated by adjusting the position $x_{i}$ and the velocity $v_{i}$ for each solution in the population as in Eqs (6)–(8) (Lines 12–13).
Step 4.
The new population is evaluated by calculating the objective function for each solution and the best solution $x^{\ast}$ is selected from the population (Lines 14–15).
Step 5.
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).
Step 6.
The new solution is accepted with some proximity depending on parameter $A_{i}$ , increasing the rate of pulse emission and decreasing the loudness as in Eqs (9) and (10) (Lines 21–24).
Step 7.
The new population is evaluated and the best solution is selected from the population. The operations are repeated until termination criteria are satisfied.
Step 8.
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).

5. 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.

Figure 2.

The efficiency of the proposed HBATDS algorithm on minimax problems.

Table 2

Parameter setting

Parameters	Definitions	Values
$P$	Population size	20
$f_{\min}$	Minimum frequency	0
$f_{\max}$	Maximum frequency	5
$A_{0}$	The initial loudness	1
$r_{0}$	The initial pulse rate	0.5
$\alpha$	The loudness constant	0.9
$\gamma$	The rate of pulse emission	0.9
	constant
$\varepsilon$	Step size for checking	$10^{-3}$
	descent directions
$m$	Local PS repetition number	5
$\Delta_{0}$	Initial mesh size	$(U_{i}-L_{i})/3$
$\sigma$	Reduction factor of mesh size	0.01
$m$	Local PS repetition number	5
$\emph{Max}_{itr}$	Maximum iterations number	$2d$
$N_{\textit{elite}}$	No. of best solution for final	1
	intensification

Table 3

Minimax optimization test problems

Test problem	Problem defination
Problem 1 [38]	$\emph{FM}_{1}(x)=\max{f_{i}(x)},i=1,2,3,$
	$f_{1}(x)=x_{1}^{2}+x_{2}^{4},$
	$f_{2}(x)=(2-x1)^{2}+(2-x_{2})^{2},$
	$f_{3}(x)=2\exp(-x_{1}+x_{2})$
Problem 2 [38]	$\emph{FM}_{2}(x)=\max{f_{i}(x)},i=1,2,3,$
	$f_{1}(x)=x_{1}^{4}+x_{2}^{2}$
	$f_{2}(x)=(2-x1)^{2}+(2-x_{2})^{2},$
	$f_{3}(x)=2\exp(-x_{1}+x_{2})$
Problem 3 [38]	$\emph{FM}_{3}(x)=x_{1}^{2}+x_{2}^{2}+2x_{3}^{2}+x_{4}^{2}-5x_{1}-5x_{2}-21x_{3% }+7x_{4},$
	$g_{2}(x)=-x_{1}^{2}-x_{2}^{2}-x_{3}^{3}-x_{4}^{2}-x_{1}+x_{2}-x_{3}+x_{4}+8,$
	$g_{3}(x)=-x_{1}^{2}-2x_{2}^{2}-x_{3}^{2}-2x_{4}+x_{1}+x_{4}+10,$
	$g_{4}(x)=-x_{1}^{2}-x_{2}^{2}-x_{3}^{2}-2x_{1}+x_{2}+x_{4}+5$
Problem 4 [38]	$\emph{FM}_{4}(x)=\max{f_{i}(x)},i=1,\ldots,5$
	$f_{1}(x)=(x_{1}-10)^{2}+5(x_{2}-12)^{2}+x_{3}^{4}+3(x_{4}-11)^{2}+10x_{5}^{6}+% 7x_{6}^{2}+x_{7}^{4}-4x_{6}x_{7}-10x_{6}-8x_{7},$
	$f_{2}(x)=f_{1}(x)+10(2x_{1}^{2}+3x_{2}^{4}+x_{3}+4x_{4}^{2}+5x_{5}-127),$
	$f_{3}(x)=f_{1}(x)+10(7x_{1}+3x_{2}+10x_{3}^{2}+x_{4}-x_{5}-282),$
	$f_{4}(x)=f_{1}(x)+10(23x_{1}+x_{2}^{2}+6x_{6}^{2}-8x_{7}-196),$
	$f_{5}(x)=f_{1}(x)+10(4x_{1}^{2}+x_{2}^{2}-3x_{1}x_{2}+2x_{3}^{2}+5x_{6}-11x_{7})$
Problem 5 [28]	$\emph{FM}_{5}(x)=\max{f_{i}(x)},i=1,2,$
	$f_{1}(x)=\|x_{1}+2x_{2}-7\|$ ,
	$f_{2}(x)=\|2x_{1}+x_{2}-5\|$
Problem 6 [28]	$\emph{FM}_{6}(x)=\max{f_{i}(x)},$
	$f_{i}(x)=\|x_{i}\|,i=1,\ldots,10$
Problem 7 [20]	$\emph{FM}_{7}(x)=\max{f_{i}(x)},i=1,2,$
	$f_{1}(x)=\left(x_{1}-\sqrt{(x_{1}^{2}+x_{2}^{2})}\cos\sqrt{x_{1}^{2}+x_{2}^{2}% }\right)^{2}+0.005(x_{1}^{2}+x_{2}^{2})^{2},$
	$f_{2}(x)=\left(x_{2}-\sqrt{(x_{1}^{2}+x_{2}^{2})}\sin\sqrt{x_{1}^{2}+x_{2}^{2}% }\right)^{2}+0.005(x_{1}^{2}+x_{2}^{2})^{2}$
Problem 8 [20]	$\emph{FM}_{8}(x)=\max{f_{i}(x)},i=1,\ldots,4,$
	$f_{1}(x)=(x_{1}-(x_{4}+1)^{4})^{2}+(x_{2}-(x_{1}-(x_{4}+1)^{4})^{4})^{2}+2x_{3% }^{2}+x_{4}^{2}-5(x_{1}-(x_{4}+1)^{4})$
	$-5(x_{2}-(x1-(x_{4}+1)^{4})^{4})-21x_{3}+7x_{4},$
	$f_{2}(x)=f_{1}(x)+10[(x_{1}-(x_{4}+1)^{4})^{2}+(x_{2}-(x_{1}-(x_{4}+1)^{4})^{4% })^{2}+x_{3}^{2}+x_{4}^{2}+(x_{1}-(x_{4}+1)^{4})$
	$-(x_{2}-(x_{1}-(x_{4}+1)^{4})^{4})+x_{3}-x_{4}-8],$
	$f_{3}(x)=f_{1}(x)+10[(x_{1}-(x_{4}+1)^{4})^{2}+2(x_{2}-(x_{1}-(x_{4}+1)^{4})^{% 4})^{2}+x_{3}^{2}+2x_{4}^{2}-(x_{1}-(x_{4}+1)^{4})$ ,
	$-x_{4}-10]$
	$f_{4}(x)=f_{1}(x)+10[(x_{1}-(x_{4}+1)^{4})^{2}+(x_{2}-(x_{1}-(x_{4}+1)^{4})^{4% })^{2}+x_{3}^{2}+2(x_{1}-(x_{4}+1)^{4})$
	$-(x_{2}-(x_{1}-(x_{4}+1)^{4})^{4})-x_{4}-5]$
Problem 9 [20]	$\emph{FM}_{9}(x)=\max{f_{i}(x)},i=1,\ldots,5,$
	$f_{1}(x)=(x_{1}-10)^{2}+5(x_{2}-12)^{2}+x_{3}^{4}+3(x_{4}-11)^{2}+10x_{5}^{6}+% 7x_{6}^{2}+x_{7}^{4}-4x_{6}x_{7}-10x_{6}-8x_{7}$ ,
	$f_{2}(x)=-2x_{1}^{2}-2x_{3}^{4}-x_{3}-4x_{4}^{2}-5x_{5}+127$ ,
	$f_{3}(x)=-7x_{1}-3x_{2}-10x_{3}^{2}-x_{4}+x_{5}+282$ ,
	$f_{4}(x)=-23x_{1}-x_{2}^{2}-6x_{6}^{2}+8x_{7}+196$ ,
	$f_{5}(x)=-4x_{1}^{2}-x_{2}^{2}+3x_{1}x_{2}-2x_{3}^{2}-5x_{6}+11x_{7}$
Problem 10 [20]	$\emph{FM}_{10}(x)=\max{\|f_{i}(x)\|},i=1,\ldots,21,$
	$\displaystyle f_{i}(x)=x_{1}\exp(x_{3}t_{i})+x_{2}\exp(x_{4}t_{i})-\frac{1}{1+% t_{i}},$
	$\displaystyle t_{i}=-0.5+\frac{i-1}{20}$

Figure 3.

The performance of HBATDS algorithm with minimax problems.

Table 4

Minimax test functions properties

Function	Dimension (d)	Desired error goal
$\emph{FM}_{1}$	2	1.95222245
$\emph{FM}_{2}$	2	2
$\emph{FM}_{3}$	4	$-$ 40.1
$\emph{FM}_{4}$	7	247
$\emph{FM}_{5}$	2	$10^{-4}$
$\emph{FM}_{6}$	10	$10^{-4}$
$\emph{FM}_{7}$	2	$10^{-4}$
$\emph{FM}_{8}$	4	$-$ 44
$\emph{FM}_{9}$	7	680
$\emph{FM}_{10}$	4	0.1

Table 5

The efficiency of invoking the Nelder-Mead method in the final stage of HBATDS for $\textit{FM}_{1}$ – $\textit{FM}_{10}$ minimax problems

Function	HBATDS without NM	HBATDS with NM
$\emph{FM}_{1}$	941.12	435.58
$\emph{FM}_{2}$	970.23	418.52
$\emph{FM}_{3}$	1115.76	530.38
$\emph{FM}_{4}$	4106.25	3170.22
$\emph{FM}_{5}$	722.12	252.14
$\emph{FM}_{6}$	3615.61	2915.34
$\emph{FM}_{7}$	1815.22	1195.2
$\emph{FM}_{8}$	20,000	2310.3
$\emph{FM}_{9}$	2110.21	1356.91
$\emph{FM}_{10}$	1217.61	637.9

5.1 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 $P$ . The experimental tests show that the best population size is $P=20$ , increasing this number will increase the evaluation function values without any improvement in the obtained results.
•
Frequency parameter $f$ . Bat movement is based on the value of the frequency parameter $f$ . In HBATDS algorithm, the quality of the solution is related to the value of $f$ parameter. The experimental tests show that the best maximum value of $f$ is $f_{\max}=5$ and the minimum value of $f$ is $f_{\min}=0$ .
•
Loudness parameters $A$ , $\alpha$ . Loudness parameter $A$ is one of the most important parameters in the bat algorithm. The acceptance of the new generated solutions is depending on the value of $A$ . The $\alpha$ parameter plays a similar role as the cooling factor in the simulated annealing algorithm. The initial value of $A$ is set to $1$ and the value of $\alpha$ is set to $0.9$ .
•
Pulse emission rate $r$ . The value of the rate of pulse emission parameter $r$ is very important to apply the local search method in the algorithm. The experimental tests show that the best value of $r$ is 0.9 and the rate of pulse emission constant is $\gamma=0.9$ .
•
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 $\Delta_{0}$ , in our experiments $\Delta_{0}=(U_{i}-L_{i})/3$ and when no improvement achieved in the exploration search process, the mesh size is deducted by using reduction factor $\sigma$ . The experimental results show that the best value of $\sigma$ is 0.01. The PS steps are repeated $m$ times, in order to increase the exploitation process of the algorithm. In our experiment $m=5$ 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 $\emph{Max}_{itr}=2d$ , where $d$ 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 $N_{\textit{elit}}$ , in order to avoid increasing the value of the function evaluation value, $N_{\textit{elit}}=1$ .

5.2 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.

5.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 $\textit{FM}_{1}$ , $\textit{FM}_{2}$ , $\textit{FM}_{3}$ , $\textit{FM}_{6}$ and $\textit{FM}_{7}$ 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.

5.4 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 $\textit{FM}_{4}$ , $\textit{FM}_{5}$ , $\textit{FM}_{8}$ , $\textit{FM}_{9}$ and $\textit{FM}_{10}$ . 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.

Table 6
Evaluation function for the minimax problems $\emph{FM}_{1}$ – $\emph{FM}_{10}$

Algorithm	Problem	Avg	SD	%Suc
HPS2	$\emph{FM}_{1}$	1848.7	2619.4	99
	$\emph{FM}_{2}$	635.8	114.3	94
	$\emph{FM}_{3}$	141.2	28.4	37
	$\emph{FM}_{4}$	8948.4	5365.4	7
	$\emph{FM}_{5}$	772.0	60.8	100
	$\emph{FM}_{6}$	1809.1	2750.3	94
	$\emph{FM}_{7}$	4114.7	1150.2	100
	$\emph{FM}_{8}$	–	–	–
	$\emph{FM}_{9}$	283.0	123.9	64
	$\emph{FM}_{10}$	324.1	173.1	100
UPSOm	$\emph{FM}_{1}$	1993.8	853.7	100
	$\emph{FM}_{2}$	1775.6	241.9	100
	$\emph{FM}_{3}$	1670.4	530.6	100
	$\emph{FM}_{4}$	12,801.5	5072.1	100
	$\emph{FM}_{5}$	1701.6	184.9	100
	$\emph{FM}_{6}$	18,294.5	2389.4	100
	$\emph{FM}_{7}$	3435.5	1487.6	100
	$\emph{FM}_{8}$	6618.50	2597.54	100
	$\emph{FM}_{9}$	2128.5	597.4	100
	$\emph{FM}_{10}$	3332.5	1775.4	100
RWMPSOg	$\emph{FM}_{1}$	2415.3	1244.2	100
	$\emph{FM}_{2}$	–	–	–
	$\emph{FM}_{3}$	3991.3	2545.2	100
	$\emph{FM}_{4}$	7021.3	1241.4	100
	$\emph{FM}_{5}$	2947.8	257.0	100
	$\emph{FM}_{6}$	18,520.1	776.9	100
	$\emph{FM}_{7}$	1308.8	505.5	100
	$\emph{FM}_{8}$	–	–	–
	$\emph{FM}_{9}$	–	–	–
	$\emph{FM}_{10}$	4404.0	3308.9	100
HBATDS	$\emph{FM}_{1}$	435.58	30.24	100
	$\emph{FM}_{2}$	418.52	33.48	100
	$\emph{FM}_{3}$	530.38	66.14	100
	$\emph{FM}_{4}$	3170.22	558.01	36
	$\emph{FM}_{5}$	252.14	20.44	100
	$\emph{FM}_{6}$	2915.34	20.17	90
	$\emph{FM}_{7}$	1195.2	116.7	90
	$\emph{FM}_{8}$	2310.3	861.9	5
	$\emph{FM}_{9}$	1356.91	134.69	60
	$\emph{FM}_{10}$	637.9	117.398	95

Figure 4.

The comparison results (function evaluation values) between HBATDS algorithm and other algorithms for minimax problems.

Table 7

HBATDS and other meta-heuristics and swarm intelligence algorithms for $\textit{FM}_{1}$ – $\textit{FM}_{10}$ minmax problems

Function		GA	PSO	FF	CS	GWO	HBATDS
$\emph{FM}_{1}$	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
$\emph{FM}_{2}$	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
$\emph{FM}_{3}$	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
$\emph{FM}_{4}$	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
$\emph{FM}_{5}$	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
$\emph{FM}_{6}$	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
$\emph{FM}_{7}$	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
$\emph{FM}_{8}$	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
$\emph{FM}_{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
$\emph{FM}_{10}$	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

5.5 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 $10^{-4}$ 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.

5.6 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.

5.6.1 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 $\textit{FM}_{2}$ , $\textit{FM}_{9}$ in RWMPSOg algorithm and $\textit{FM}_{8}$ 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 $10^{-4}$ 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 $\textit{FM}_{3}$ , $\textit{FM}_{6}$ , $\textit{FM}_{9}$ and $\textit{FM}_{10}$ . 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 $D\geqslant 4$ . 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.

5.7 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 $10^{-4}$ before the 20,000 function evaluation value. For the GA, the probability of crossover is set to be $\textit{PC}=0.8$ , probability of mutation $\textit{PM}=0.01$ 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

6. 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

Ali

A.F.

and Tawhid

M.A.

, Hybrid-simulated annealing and pattern search method for solving minimax and integer programming problems, Pacific Journal of Optimization 12(1) (2016), 151–184.

Ali

A.F.

and Tawhid

M.A.

, A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems, Ain Shams Engineering Journal (2016).

Ali

A.F.

and Tawhid

M.A.

, Direct gravitational search algorithm for global optimisation problems, East Asian Journal on Applied Mathematics 6(3) (2016), 290–313.

Ali

A.F.

and Tawhid

M.A.

, A hybrid cuckoo search algorithm with Nelder Mead method for solving global optimization problems, Springer Plus 5(1) (2016), 1–22.

Bandler

J.W.

and Charalambous

, Nonlinear programming using minimax techniques, Journal of Optimization Theory and Applications 13 (1974), 607–619.

Bernabe-Loranca

M.B.

Ruiz-Vanoye

Velazquez

R.G.

Analco

M.E.

López Analco

A.S.

Zezzati

A.O.

Guzman

G.M.

and Diaz

M.B.

, An approximation method for the P-median problem: A bioinspired tabu search and variable neighborhood search partitioning approach, International Journal of Hybrid Intelligent Systems 13(2) (2016), 87–98.

Chu

S.A.

Tsai

P.-W.

and Pan

J.-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.

Dorigo

, Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, Italy, 1992.

Harfouchi

and Habbi

, A cooperative learning artificial bee colony algorithm with multiple search mechanisms, International Journal of Hybrid Intelligent Systems 13(2) (2016), 113–124.

10.

Hillier

F.S.

and Lieberman

G.J.

, Introduction to Operations Research, MCGraw-Hill, 1995.

11.

Holland

J.H.

, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.

12.

Hooke

and Jeeves

T.A.

, Direct search solution of numerical and statistical problems, J Assoc Comput Mach (1961), 212–229.

13.

Isabel

A.C.P.

Santo

and Fernandes

, Heuristics pattern search for bound constrained minimax problems, Computational Science and its Applications, ICCSA 6784 (2011), 174–184.

14.

Karaboga

and Basturk

, A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, Journal of Global Optimization 39(3) (2007), 459–471.

15.

Kennedy

and Eberhart

R.C.

, Particle swarm optimization, Proceedings of the IEEE International Conference on Neural Networks 4 (1995), 1942–1948.

16.

Komarasamy

and Wahi

, An optimized K-means clustering technique using bat algorithm, European J Scientific Research 84(2) (2012), 263–273.

17.

X.L.

Shao

Z.J.

and Qian

J.X.

, Optimizing method based on autonomous animats: Fish-swarm algorithm, System Engineering Theory and Practice 22(11) (2002), 32.

18.

Liuzzi

Lucidi

and Sciandrone

, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM Journal on Optimization 16 (2006), 1054–1075.

19.

Lin

J.H.

Chou

C.W.

Yang

C.H.

and Tsai

H.L.

, A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems, J Computer and Information Technology 2(2) (2012), 56–63.

20.

Lukan

and Vlcek

, 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.

Mirjalili

S.M.

and Lewis

, Grey Wolf Optimizer, Advances in Engineering Software 69 (2014), 46–61.

22.

Nakamura

R.Y.M.

Pereira

L.A.M.

Costa

K.A.

Rodrigues

Papa

J.P.

and Yang

X.S.

, BBA: A binary bat algorithm for feature selection, 25th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), IEEE Publication (2012), 291–297.

23.

Nelder

J.A.

and Mead

, A simplex method for function minimization, Computer Journal 7 (1965), 308–313.

24.

Parsopoulos

K.E.

and Vrahatis

M.N.

, Unified particle swarm optimization for tackling operations research problems, In Proceeding of IEEE 2005 Swarm Intelligence Symposium, Pasadena, USA (2005), 53–59.

25.

Passino

M.K.

, Biomimicry of bacterial foraging for distributed optimization and control, Control Systems, IEEE 22(3) (2002), 52–67.

26.

Petalas

Y.G.

Parsopoulos

K.E.

and Vrahatis

M.N.

, Memetic particle swarm optimization, Ann Oper Res 156 (2007), 99–127.

27.

Polak

Royset

J.O.

and Womersley

R.S.

, Algorithms with adaptive smoothing for finite minimax problems, Journal of Optimization Theory and Applications 119 (2003), 459–484.

28.

Schwefel

H.P.

, Evolution and Optimum Seeking, New York, Wiley, 1995.

29.

Sopov

, A selection hyper-heuristic with online learning for control of genetic algorithm ensemble, International Journal of Hybrid Intelligent Systems 13(2) (2016), 125–135.

30.

Takahama

and Sakai

, Improving an adaptive differential evolution using hill-valley detection, International Journal of Hybrid Intelligent Systems 13(1) (2016), 1–13.

31.

Tang

Fong

Yang

X.S.

and Deb

, Wolf search algorithm with ephemeral memory, In Digital Information Management (ICDIM), 2012 Seventh International Conference on Digital Information Management (2012), 165–172.

32.

Tawhid

M.A.

and Ali

A.F.

, Direct Search Firefly Algorithm for Solving Global Optimization Problems, Applied Mathematics & Information Sciences (2016), 841-860.

33.

Tawhid

M.A.

and Ali

A.F.

, Simplex particle swarm optimization with arithmetical crossover for solving global optimization problems, OPSEARCH (2016), 1–36.

34.

Tawhid

M.A.

and Ali

A.F.

, A simplex social spider algorithm for solving integer programming and minimax problems, Memetic Computing Feb (2016).

35.

Teodorovic

and DellOrco

, 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.

Wang

and Guo

, A novel hybrid bat algorithm with harmony search for global numerical optimization, Journal of Applied Mathematics 2013 (2013).

37.

Xie

Zhou

Y.Q.

and Chen

, A novel bat algorithm based on differential operator and Levy flights trajectory, Computational Intelligence and Neuroscience 2013 (2013).

38.

, Smoothing method for minimax problems, Computational Optimization and Applications 20 (2001), 267–279.

39.

Yang

X.S.

, Firefly algorithm, stochastic test functions and design optimization, International Journal of Bio-Inspired Computation 2(2) (2010), 78–84.

40.

Yang

X.S.

and Deb

, 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.

Yang

X.S.

, A new metaheuristic bat-inspired algorithm, Nature Inspired Cooperative Strategies for Optimization (NICSO 2010) (2010), 65–74.

42.

Yang

X.S.

, Bat algorithm for multi-objective optimization, Int J BioInspired Computation 3(5) (2011), 267–274.

43.

Zhang

J.W.

and Wang

G.G.

, Image matching using a bat algorithm with mutation, Applied Mechanics and Materials (Edited by Du

Z.Y.

and Liu

) 203(1) (2012), 88–93.

Hybrid bat algorithm and direct search methods for solving minimax problems

Abstract

Keywords

1. Introduction

2. Definition of the problem and an overview of the applied algorithms

2.1 Minimax problem definition

Table 1 The parameters of the pattern search algorithm

3.1 Main concepts

3.2 The rules of the bat algorithm

5.3 The efficiency of the proposed HBATDS algorithm with minimax problems

5.4 The performance of the HBATDS algorithm on minimax problems

Table 6 Evaluation function for the minimax problems FM 1 – FM 10

5.6 HBATDS and other algorithms

5.7 HBATDS and other meta-heuristics and swarm intelligence algorithms for minmax problems

6. Conclusion

Footnotes

Acknowledgments

References

Table 1
The parameters of the pattern search algorithm

Table 6
Evaluation function for the minimax problems $\emph{FM}_{1}$ – $\emph{FM}_{10}$