1 Introduction

Along with the development of modern society, the real-life problems we face in the areas of science, engineering, economics and business are becoming more and more complex and difficult to solve. Searching for efficient methods to solve optimization problems has been one of the hottest topics in recent decades [1]. All the existing methods can be divided into two categories: exact methods and approximation methods. Exact methods can find the global optimum, but these methods are efficient only when the scale of the problem is small. However, in contrast, although the approximation methods cannot guarantee obtaining the global optimum, they can solve large-scale problems in a reasonable time. We all know that most real-life optimization problems are large scale problems. Therefore, the approximation methods are more suitable for these problems than exact methods. Thus, this paper focuses on approximation methods and proposes an effective novel method for unconstrained optimization problems.

The meta-heuristic algorithm that combines rules and randomness to imitate natural or social phenomena is one among the most important types of approximation methods. Research on meta-heuristic algorithms is the hottest topic in current studies on approximation methods. The phenomena of popular meta-heuristic algorithms include biological evolutionary processes (e.g., the genetic algorithm(GA) [2] and differential evolution (DE) [3, 4]); animal behavior (e.g., particle swarm optimization (PSO) [5], artificial bee colony (ABC) [6], ant colony optimization (ACO) [7] and cuckoo search (CS) [8]); physical process (e.g., simulated annealing (SA ) [9]); and chemical process (e.g., chemical reaction optimization (CRO) [10]). Over the last decades, many excellent meta-heuristic algorithms have been successfully applied to various real-life optimization problems and obtained better solutions than the classic methods.

The harmony search (HS) algorithm is one of the recently developed meta-heuristic algorithms [11]. It imitates the music improvisation process in which musicians continuously adjust the pitch of their instruments to achieve better harmony. The search process of global optimization problems is similar to the music improvisation process, in that each decision variable continuously changes its value during the search process to converge to the global optimum. Mahdavi [12] concluded that the HS algorithm has the characteristics of few mathematical requirements, easy implementation, and fast convergence speed. Hence, HS has caught many researchers’ attention and has been applied in many areas, such as water network design [13], structure optimization [14], medical physics [15], image segmentation [16], face-milling parameters optimization [17], scheduling [18], motion estimation [19], and others [20–22].

The HS algorithm has three important parameters includes harmony memory consideration rate HMCR, pitch adjustment rate PAR and bandwidth bw. HS algorithm is not efficient enough in performing local search in numerical optimization applications and is sensitive to the three parameter settings [23]. Thus, it is of great interest to improve the performance of the HS algorithm. Based on recent literature about the HS algorithm, the related work can be divided into two directions: to modify the structure of the HS algorithm; to apply more efficient parameter tuning strategies.

In the modification of HS structure, Oman and Mahdavi proposed a global-best harmony search (GHS) inspired by swarm intelligence [24]. In the GHS algorithm, new-harmony vectors can learn from the current best harmony vector in the harmony memory pool with probability HMCR*PAR. The experimental results showed that GHS could perform better than the classical HS. Wang et al. presented an effective differential harmony search (DHS) algorithm and applied it to solve economic load dispatch problems [25]. The main difference between DHS and HS is that DHS applies a mutation operation inspired by differential evolution algorithm to generate the new-harmony vectors. Abhik et al. proposed an opposition-based harmony search (OHS) algorithm [26]. In the OHS algorithm, the concept of opposition-based learning was employed in HM initialization and generation jumping, and the simulation results showed the effectiveness, robustness, and superiority of the OHS algorithm. In another work, Wang et al. presented an opposition-based learning HS with mutation (OLHS-M) for solving global continuous optimization problems [27]. Different from OHS, in OLHS-M, the opposition-based learning technique is incorporated to the process of improvisation to enlarge the search space. Zou et al. proposed a novel global harmony search (NGHS) [28]. NGHS designed a novel location updating strategy to make it easier to converge, and a genetic mutation operation was utilized to prevent the NGHS from being trapped into local optima. The concept of cellular automata has also been applied in HS [29, 30]. The main idea was to arrange the topological structure of the population as a two-dimensional grid, where each individual in the grid is a cell and interacts with its neighbors. Castelli et al. proposed an innovative improved version of HS named Melody Search (MS), which adopted the basic idea of HS but with quite a different structure [31]. The MS algorithm mimics the musical performance processes of group improvisation to find the best succession of pitches within a melody. In such a group, the memories of different players interact with each other and maintain the diversity of musicians (with different tastes, ideas and experiences), hence leading to a faster achievement of the best subsequence of pitches. Al-Betar et al. introduced the island model concepts and embedded them into the framework of HS algorithm where the new algorithm is refer to island HS (iHS) [32]. In iHS, the individuals are distributed in separated sub-population (islands) and evolve separately within specific generations. Then, the individuals on different islands exchange their information through a process named migration. The main idea of iHS is to maintain the diversity of the population and allow individuals on different islands interact with each other.

In utilizing efficient parameters tuning strategies, Mahdavi et al. proposed an improved harmony search (IHS) by dynamically updating the two control parameters PAR and bw [12]. Pan et al. presented a self-adaptive global best harmony (SGHS) where parameters such as HMCR and PAR were self-adapted by the proposed learning strategy and the parameter bw changed dynamically with iteration number [33]. The NDHS, which was developed by Chen et al. had a new memory consideration scheme based on the tournament selection rule, and the two parameters, PAR and bw, were dynamically adjusted with respect to the evaluation of the search process [23]. The intelligent tuned harmony search (ITHS), which was presented by Yadav et al., learned the concepts from decision making in a group [34]. The self-adaptive pitch adjustment strategy adopted by the dynamic sub-population based on the harmony memory helped ITHS to maintain the proper balance between diversification and intensification throughout the search process. Kattan et al. proposed a dynamic self-adaptive harmony search (DSHS) by introducing two criteria to drive the optimization process: the best-to-worst ratio to adjust the PAR value and a dynamic bw based on the standard deviation of each dimension variable in the harmony memory (HM) [35]. Enayatifar et al. proposed a novel harmony search algorithm based on learning automata (LAHS) [36]. The learning-based adjustment mechanism showed a new approach for parameter tuning. Kumar et al. proposed a parameter adaptive harmony search (PAHS) based on the combinations of linear and exponential changes of the parameters HMCR and PAR [37]. The numerical simulation results showed that linear change in HMCR and exponential change in PAR, provided better results than the other techniques in a noisy and scalable environment.

From the literature mentioned above, we can see that many novel improvements were inspired by other meta-heuristic algorithms, and the self-adaptation strategies became more and more complicated. Although these novel approaches performed much better than the classic HS algorithm, there was still considerable room for improvement in dealing with diverse problems.

Based on the idea of balanced intensification (exploitation) and diversification (exploration), this study proposes a modified HS algorithm with an intersect mutation operator and a cellular local search, which is abbreviated as MHS. To improve the diversity of HM, an intersect mutation operation is embedded into the HS structure: first, the harmony vectors in the initial harmony memory are divided into a better part and a worse part. Then, an intersect mutation operation between the better part and the worse part is proposed to generate new harmonies. Furthermore, after each harmony improvising procedure, a cellular local search based on cellular neighborhoods is performed to enhance the local exploitation. To further analyze the effects of the parameters in proposed algorithm, an orthogonal test is conducted, and a parameter settings recommendation is presented. Finally, two sets of famous benchmark functions are used to test and evaluate the performance of the proposed MHS algorithm. Computational results and comparisons show that the proposed algorithm not only outperforms the compared HS variants but is also competitive with other meta-heuristic algorithms in terms of solution accuracy and efficiency.

The rest of this paper is organized as follows: Section 2 introduces the classic HS algorithm. Section 3 describes the proposed algorithm in detail. Section 4 shows the orthogonal experiment for parameter settings, computational results, and comparisons. Finally, Section 5 presents the concluding remarks.

2 The classic harmony search algorithm

In the classic HS algorithm, each solution is called “harmony” and represented by an n-dimension real vector. An initial population of harmony vectors are randomly generated and stored in a HM. Then, a new candidate harmony is improvised from all of the solutions in the HM using a memory consideration rule, a pitch adjustment rule, and a random re-initialization. Finally, the HM is updated by comparing the fitness between the new candidate harmony and the worst harmony in the current HM. The worst harmony vector is replaced by the new candidate harmony vector if it is better than the worst harmony vector in the HM. The improvisation and updating processes are repeated until a predefined stopping criterion is reached. The harmony search procedure is as follows [12]:

  1. Step 1:

    Initialize the problem and algorithm parameters.

    The optimization problem is specified as follows:

    $$\text{Minimize}\;f(x)\;\text{subject}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\text{to}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}x_{i} \in [LB_{i} ,UB_{i} ],{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}i\,=\,1,2,...,n $$

    where f(x) is an objective function; X = (x 1, x 2, ... , x n ) is the set of decision variables; n is the number of decision variables; and L B i , U B i are the lower and upper bounds for decision variable x i , respectively.

    In addition, the HS algorithm parameters are specified in this step. These parameters are harmony memory size (HMS), or the number of solution vectors in the harmony memory; harmony memory considering rate (HMCR); pitch adjusting rate (PAR); distance bandwidth (BW); number of decision variables (N) and the number of improvisations (NI), or the stopping criterion.

  2. Step 2:

    Initialize the harmony memory (HM).

    In step 2, the initial solution variables are randomly generated from the feasible region and filled in the harmony memory matrix HM:

    $$ HM=\left[ {{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\left. {{\begin{array}{*{20}c} {{x_{1}^{1}} } \hfill & {{x_{2}^{1}} } \hfill & {\cdots} \hfill & {{x_{N}^{1}} } \hfill \\ {{x_{1}^{2}} } \hfill & {{x_{2}^{2}} } \hfill & {\cdots} \hfill & {{x_{N}^{2}} } \hfill \\ {\vdots} \hfill & {\vdots} \hfill & {\cdots} \hfill & {\vdots} \hfill \\ {x_{1}^{HMS} } \hfill & {x_{2}^{HMS} } \hfill & {\cdots} \hfill & {x_{N}^{HMS} } \hfill \end{array} }} \right|{\begin{array}{*{20}c} {f(x^{1})} \hfill \\ {f(x^{2})} \hfill \\ {\vdots} \hfill \\ {f(x^{HMS})} \hfill \end{array} }{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}} \right]{\kern 1pt}{\kern 1pt} $$
    (1)
  3. Step 3:

    Improvise a new harmony.

    A new harmony vector \(\text {\textbf {X}}_{\text {new}} =(x_{\text {new}}^{1} ,x_{\text {new}}^{2} ,...,x_{\text {new}}^{n} )\) is improvised based on three rules: memory consideration, pitch adjustment and random selection. First, a random number r 1 is generated in the range [0, 1]. If r 1 is less than HMCR, the decision variable \(x_{\text {new}}^{i} \) is generated by memory consideration; otherwise, \(x_{\text {new}}^{i} \) is obtained by random selection. In the memory consideration, another random number r 2 is generated in the range [0, 1], if r 2 is less than the value of the pitch adjustment rate (\(PAR),x_{\text {new}}^{i} \) is selected from any harmony vector in the harmony memory. Otherwise, \(x_{\text {new}}^{i} \) is generated as follows:

    $$ x_{\text{new}}^{i} =x_{\text{new}}^{i} \pm r_{3} \cdot BW $$
    (2)

    where r 3 is a random number in [0, 1].

  4. Step 4:

    Update the harmony memory.

    In this step, the decision of whether the new harmony vector improvised in step 3 should be included into the harmony memory is made. If the fitness of the new harmony vector is better than the worst harmony vector in the current harmony memory, it will be included into the HM. Meanwhile, the current worst harmony will be excluded from the HM.

  5. Step 5:

    Check the stopping criterion.

    The HS algorithm is terminated when the stopping criterion has been met, for example, when the maximum number of improvisations NIis met. Otherwise, Steps 3 and 4 are repeated.

Above steps are well illustrated using pseudo code in Fig. 1.

Fig. 1
figure 1

Pseudo code of the Harmony Search algorithm

Full size image

3 Proposed modified HS algorithm with intersect mutation operator and cellular local search

Intensification (exploitation ability) and diversification (exploration ability) are the two major aspects that determine the effectiveness of the meta-heuristic algorithms. If the algorithm focuses too much on diversification, it will converge very slowly. On the contrary, if the algorithm focuses too much on intensification, convergence can more easily be premature. Hence, algorithms should tradeoff these two aspects and maintain a good balance between them.

In this section, the modified HS algorithm with intersect mutation operator and cellular local search (MHS) is developed. MHS is similar to the HS algorithm, with the following main differences: (1) the parameter bandwidth bw is removed; (2) the algorithm includes an intersect mutation operation that uses the PAR parameter; (3) the algorithm performs a cellular local search after each new harmony improvisation. First, the initialized harmonies are ranked from better to worse according to their fitness values and then divided into two parts: the better part and the worse part. Here, we introduce a constant coefficient M (0<M<1), which stands for the proportion of better harmonies in the harmony memory pool. Then, the intersect mutation operator is embedded into the HS structure to maintain the diversity of harmony memory. Meanwhile, a cellular local search is adopted to enhance the exploitation ability of the MHS. In the proposed approach, intensification and diversification are well balanced.

3.1 HS with intersect mutation operator

Inspired by the work of Zhou et al.[38], we use the intersect mutation operation to improvise new harmonies with the probability of PAR. The whole procedure is shown in Fig. 2. For the better part, we mutate the vectors with one harmony (wr1) chosen from the worse part and two harmonies (br1 and br2) chosen from the better part, as the formula below shows:

$$ x_{i} =x_{wr1} +F\cdot (x_{br1} -x_{br2} ),br1\ne br2\ne wr1\ne i $$
(3)

where F (0 < F < 1) is the mutation parameter.

Fig. 2
figure 2

The procedure for improvising new harmony by the intersect mutation operation

Full size image

For the worse part, we mutate the vectors with one harmony (br1) chosen from the better part and two harmonies (wr1 and wr2) chosen from the worse part, as the formula below shows:

$$ x_{i} =x_{br1} +F\cdot (x_{wr1} -x_{wr2} ),br1\ne br2\ne wr1\ne i $$
(4)

The detailed pseudo code explaining the various steps of improvising new harmonies is shown in Fig. 3. for easier implementation and understanding of the proposed approach.

Fig. 3
figure 3

Pseudo code for improvising new harmonies

Full size image

3.2 Cellular local search

The cellular automata (CA) model is a discrete dynamical system that can produce complex phenomena [39]. The essential idea of the CA model is to simulate macro-behavior by the micro-dynamics, which is produced by the interaction of a population of individuals who are connected in particular neighborhood structures. The CA model consists of the following parts: cells, cell space, cell states, neighborhood, and transition rule discrete time. The basic operational principle of CA is that, for a given time t, the next state of a cell S t + 1 is the comprehensive result affected by its previous state S t and the previous states of other neighborhoods N t, as shown in (5):

$$ S^{t+1}=f(S^{t},N^{t}) $$
(5)

Since the concept of CA was first proposed, it has become a powerful tool to conduct scientific research in different field, including research in meta-heuristics. Alba et al [40, 41], proposed cellular GAs, Shi et al. [42] proposed a Cellular PSO (CPSO) algorithm and cellular HS algorithms have also been proposed [43, 44]. In these cellular algorithms, the CA model was employed to study the swarm system and consider algorithm iteration in a CA way, where each individual exchanges information within its neighborhood before changing its current state. However, interactions within the swarm have limitations, in that only one part of search space can be explored. To improve the search capability, individuals should be endued with more talent to free themselves from neighborhood interactions to exploit more potential search space outside the swarm. This idea has led to the proposed cellular local search (CLS).

In CLS, we extend a generalized cellular automata model to guide the local search of harmonies in the current harmony memory and thus enhance their exploitation capability. At first, the whole search space is assumed to be the cell space, and we can imagine that the cell space is cut by infinite virtual grids, where the cell space could not be further subdivided. Every grid in the search space represents a single solution. To distinguish current harmonies and potential candidate solutions, we define a “smart-cell” as a harmony in the current harmony memory. In contrast, a cell that is not “smart” is one that represents a candidate solution in the search space that is not visited by any of the harmonies in the current harmony memory. The comparison of the basic idea between cellular HS and cellular local search in MHS is illustrated in Fig. 4. As we can see in Fig. 4a, the harmonies in the harmony memory pool are mapped onto a grid structure so that harmonies can interact with their neighborhood; however, in the proposed cellular local search (Fig. 4b), harmonies interact with potential candidate solutions outside the swarm.

Fig. 4
figure 4

Comparison of the basic idea between cellular HS and cellular local search in MHS

Full size image

The CA model for the proposed cellular local search is as follows:

  1. 1.

    Cell: current harmonies in harmony memory.

  2. 2.

    Cell space: the search space.

  3. 3.

    Cell state: the harmony’s current position \({X_{i}^{t}} \) and current best harmony \({X_{g}^{t}}, \quad {S_{i}^{t}} =\left \{ {{X_{i}^{t}} ,{X_{g}^{t}} } \right \}\).

  4. 4.

    Neighborhood: a set of potential candidate solutions based on some type of lattice structure, defined by neighborhood functions. For details of neighborhood functions, see Eq. (7).

  5. 5.

    Transition rule:

    $$ \begin{array}{l} S_{i}^{t+1} =f\left( {{S_{i}^{t}} \cup S_{N(i)}^{t} } \right) = f\left( {{S_{i}^{t}} ,S_{i+\delta_{1} }^{t} ,...,S_{i+\delta_{l} }^{t} } \right) \\ (fitness({S_{i}^{t}} ),fitness(S_{i+\delta_{1} }^{t} ),...,fitness(S_{i+\delta_{l} }^{t} )) \end{array} $$
    (6)

    where l is the size of the neighborhood, we set l = 5, and δ is the index of the neighborhood, δ ∈ [1, l].

  1. 1.

    Discrete time step: iteration in MHS.

Every smart-cell constructs its neighborhood with a neighborhood function as follows:

$$ N(i) = \left\{ {{\begin{array}{ll} X_{i}^{t} +\frac{fitness(X_{g}^{t} )}{fitness(X_{i}^{t} )}R_{3} \circ \gamma_{i}^{t}&\ne 0,fitness(X_{g}^{t} )\ge 0 \\ X_{i}^{t} +\left| {\frac{fitness(X_{i}^{t} )}{fitness(X_{g}^{t} )}} \right|R_{3} \circ \gamma_{i}^{t} &(X_{i}^{t} )\ne 0,fitness(X_{g}^{t} )\le 0 \\ X_{i}^{t} +\left( \frac{e^{fitness(X_{g}^{t} )}}{e^{fitness(X_{i}^{t} )}}\right)^{2}R_{3} \circ \gamma_{i}^{t} &fitness(X_{i}^{t} )\,=\,0,fitness({X_{g}^{t}} )\!\ge\! 0 \\ X_{i}^{t} +\left( \frac{e^{fitness(X_{g}^{t} )}}{e^{fitness(X_{i}^{t} )}} \right)^{2}R_{3} \circ {\gamma_{i}^{t}} &fitness(X_{i}^{t} )\,=\,0,fitness(X_{g}^{t} )\!<\!0 \end{array} }} \right. $$
(7)

where R 3 is a 1 × d matrix composed by d uniform random numbers in [−1, 1], and “ ∘” is the operation symbol of the Hadamard product. For the jth dimension (j = 1, 2, … , d) of \({X_{i}^{t}} \), N(i) generates random points within a specific radius from \(x_{ij}^{t} \).

In general, Eq. (7) can be simplified as

$$ N(i) = {X_{i}^{t}} +{\xi_{i}^{t}} \circ {\gamma_{i}^{t}} $$
(8)

where \({\xi _{i}^{t}} \) is the radius ratio with a range of (-1,1) and \(\gamma _{i}^{t} \) is the search radius (or step size). In this research, the value of \({\gamma _{i}^{t}} \) is based on Lévy flights [8, 45]. Lévy flights are random walks in which the steps are defined in terms of the step-lengths, which have a certain probability distribution, with the directions of the steps being isotropic and random. They are very useful in simulations for random or pseudo random natural phenomena. Experiments have pointed out that Lévy flights are efficient in exploring an unknown, large-scale search space [46]. A simple scheme discussed in detail by Yang et al. can be summarized as

$$ {\gamma_{i}^{t}} =L\text{\'{e}}vy(\beta )\sim 0.01\frac{\mu }{\left| \nu \right|^{1/\beta }}({X_{i}^{t}} -{X_{g}^{t}} ) $$
(9)

where μ and ν are drawn from normal distributions. That is,

$$ \mu \sim N(0,{\sigma_{u}^{2}} ),\nu \sim N(0,\sigma_{\nu }^{2} ) $$
(10)

with \(\sigma _{\mu } =\left \{ {\frac {\Gamma (1+\beta )\sin (\pi \beta /2)}{\Gamma [(1+\beta )/2]\beta 2^{(\beta -1)/2}}} \right \}^{1/\beta }\), σ ν = 1. Here, Γ is the standard Gamma function.

3.3 Working steps of MHS algorithm

The working steps of the proposed MHS algorithm are as follows:

  1. Step 1:

    Initialization.

    First, the parameters in MHS are specified: the harmony memory size (HMS), the harmony memory consideration rate (HMCR), the pitch adjusting rate (PAR), and the max iteration number (NI), the proportion of the better part in harmony memories M(0<M<1), and the mutation parameter F. Then, the initial harmony memory of HMS harmonies is randomly generated: \(HM=\{ X_{\mathrm {1}},X_{\mathrm {2}},\ldots ,\;X_{HMS}\}, \text {with}\, X_{i}=\{ {x_{i}^{1}} ,{x_{i}^{2}} ,...,{x_{i}^{n}} \},\; i=1,2,{\ldots } ,HMS\) uniformly distributed in the range [X m i n , X m a x ].

  2. Step 2:

    Evaluate each harmony in the harmony memory, f HM = {f(X 1), f(X 2)…f(X H M S )}. Rank the harmonies according to their fitness value in ascending order, and then divide the harmonies into two parts with constant coefficient M.

  3. Step 3:

    Improvise new harmonies.

    HMS new harmony vectors are improvised in this step. The detailed procedure is given in Section 3.1. If the new harmonies are better than the current harmonies, then replace current harmonies.

  4. Step 4:

    Cellular local search.

    For each of the improvised harmonies, a cellular local search is conducted: see Section 3.2. If the fitness of the neighbors is better than the fitness of the current harmonies in HM, then replace the harmonies with the neighbors. Then, divide the updated harmonies into two parts again.

  5. Step 5:

    Check the stopping criterion.

    The MHS algorithm will repeat step 4 and step 5 until reaching the max iteration number NI.

    The flowchart of the proposed MHS is shown in Fig. 5.

Fig. 5
figure 5

Flowchart of MHS algorithm

Full size image

4 Experimental results

To evaluate the performance of the proposed MHS algorithm, two comparison tests with different benchmark problems are performed. The first is the comparison of MHS and other HS variants, which uses the benchmark functions shown in Table 1, which have been widely used in previous HS literature. The other is the comparison of MHS and other meta-heuristic algorithms, which uses the CEC2013 benchmark functions. The CEC2013 benchmark functions are more complicated than previous CECbbenchmarks.

Table 1 Test functions
Full size table

This section is organized as follows. A detailed description of the benchmark problems used in the study is described first, followed by the impact of the parameters on the MHS algorithm. Next, a performance evaluation of MHS on the benchmark problems shown in Table 1 are compared with the well-known HS variants. Further, a rank based analysis, statistical comparison analysis and convergence analysis are provided. Last, the performance of MHS and the other meta-heuristics in solving the CEC2013 benchmark problems are compared in this section.

4.1 Benchmark functions

The first set of benchmark problems consists of 19 classical benchmark functions [33, 38, 42, 47] with dimensions of D. Functions f 1 − f 5 are unimodal functions, functions f 6 − f 13are multimodal functions and f 14 − f 19 are shifted or shifted and rotated unimodal and multimodal functions. A brief description of the objective function, search range, and bias value for all 19 functions are shown in Table 1. The shifted global optimum for all of the functions is provided as o = {o 1 o 2, ... , o D }, and the functions are defined as z = x − o for shifted functions and z = (x − o )∗M for shifted and rotated functions, where M is the transformation matrix for the rotating matrices.

The second set of benchmark problems consists of 28 CEC2013 [48] functions with dimensions of D. Functions F 1− F 5 are unimodal functions, functions F 6 − F 20 are basic multimodal functions and F 21 − F 28 are composition functions.

4.2 Comparison of MHS and other HS variants

4.2.1 Study and effects of parameters in MHS

Before the performance comparison of MHS and other HS variants, it is first necessary to analyze how the five parameters HMS, HMCR, PAR, M and F affect the performance of MHS, and then to search for an optimum combination of them.

In this section, an analysis of these five parameters based on the orthogonal experimental design (OED) method is investigated. The OED method was first introduced by Taguchi [49]. This simplified design method has since been applied widely and rapidly all over the world. OED takes advantage of the two characteristics of an orthogonal array, namely, uniform distribution and regular comparability, thus ensuring that the representative experimental points are uniformly scattered over the design region and simultaneously providing mathematical tractability to the experimental data. Therefore, the OED method can make a comprehensive survey of the influence on experimental results due not only to the individual factors but also to the interaction effects between factors.

The OED method arranges experiments using an orthogonal array. The orthogonal array is represented as L a (b c), in which L is the orthogonal array, a is the number of experiments, b is the level of factors, and c is the number of factors or the number of columns. For example, consider the orthogonal array L 9(34), which represents nine experiments.

Considering the advantages of OED method, we apply it to our parameter analysis. Before the experiments begin, we assume that each of the five parameters, has five different level values. Detailed information on all of the factors is shown in Table 2.

Table 2 Influence factors and level values
Full size table

After the factors and their levels are determined, an appropriate orthogonal table can be chosen by considering the number of interactions between the factors from different levels. Because there are five influence factors and five level values for each factor, L 25(56) is chosen from the orthogonal table to arrange the orthogonal design. To obtain more convincing experimental results, an evaluation criterion is proposed to calculate the total score: ten benchmark functions with different characteristics, for example, unimodal or multimodal, are chosen from the test functions in Table 1. Each benchmark function earns a score s i in the range of [1,25] based on its mean fitness of 50 runs. Finally, the total scores are calculated as follow:

$$ T=\sum\limits_{i=1}^{10} {\omega_{i} \cdot s_{i} } $$
(11)

The orthogonal experimental results are shown in Table 3, where K i is the sum of the total score at the i level. The statistics are calculated by the following equations:

$$ K=\sum\limits_{i=1}^{25} {T_{i} } $$
(12)
$$P=\frac{1}{n}\cdot K^{2} $$
(13)
$$ Q_{i} =\frac{1}{5}\cdot \sum\limits_{i=1}^{5} {K_{i} } $$
(14)
$$ S_{i} =Q_{i} -P $$
(15)
$$ Q=\sum\limits_{i=1}^{25} {{T_{i}^{2}} } $$
(16)
$$ S_{T} =Q-P $$
(17)
Table 3 Orthogonal experimental results
Full size table

The results of the analysis of variance are listed in Table 4. F A ∼ F E obey the F distribution with freedom as (4, 4). For a specified significance level α, we can believe that factor A has a significant effect on the experimental results with probability 1 − α if F A > F 1−α . From Rice[50], we can find F 0.90(4,4) = 4.11, F 0.95(4,4) = 6.39 and F 0.99(4,4) = 15.98, so it is easy to conclude that HMS and HMCR are the two main factors with significant effects on the behavior of MHS algorithm. In contrast, PAR, M and F are subordinate factors that affect the search ability of the MHS algorithm less significantly. The trends of the average score are shown in Fig. 6: for the average score, the bigger the better. From the result that A 5 > A 4 > A 3 > A 2 > A 1 for factor A, B 5 > B 4 > B 3 > B 2 > B 1 for factor B, C 5 > C 4 > C 2 > C 3 > C 1 for factor C, D 2 > D 1 > D 4 > D 3 > D 5 for factor D, and E 3 > E 5 > E 1 > E 2 > E 4 for factor E, we can obtain an optimal combination of these five parameters, A 5 B 5 C 5 D 2 E 3 in Table 2, namely H M S = 100, H M C R = 0.99, P A R = 0.90, M = 0.30 and F = 0.60.

Table 4 Analysis of variance
Full size table
Fig. 6
figure 6

Trends of the average scores

Full size image

4.2.2 Computational results

This section focuses on comparing MHS and other HS variants in solving the first set of benchmark problems. These HS variants include not only the well-known HS variants, such as HS [11], IHS [12], GHS [24], SGHS [33] and NGHS [28], but also some new HS variants, such as LAHS [36], GSHS [51] and Island-based HS (i-HS) [32]. All of the listed HS variants were coded in C ++ and implemented on a computer with a 2.3 GHz CPU and 4GB RAM. The detailed settings of the parameters in these algorithms are shown in Table 5.

Table 5 Parameter settings of the compared HS algorithms
Full size table

In these experiments, each benchmark problem runs 30 independent replications. The maximum number of FEs is set to 6.0 × 104 for 30-D functions and 1.0 × 105 for 50-D functions. The optimization results for functions with 30-D functions and 50-D functions are reported in Tables 6-7, respectively. Here, “Best”, “Worst” “Mean” and “Std” are the best results, worst results, average values over 30 replications and the corresponding standard deviations, respectively.

From Table 6, one can observe that MHS performs better than the other HS variants. MHS has provided better mean, best and worst performances and has outperformed all of the other algorithms by a significant margin. For unimodal functions f 1 − f 5, most of the HS variants shows relatively good performances. In the case of function f 4, SGHS, NGHS, GSHS, and MHS converge to the global optimum. However, in case of function f 3, the gaps in performance are obvious. The best mean value obtained by MHS is e-02, while the worst is e + 04, which is obtained by i-HS. Based on these observations, it may be inferred that MHS provides significantly better solutions for unimodal functions than other HS variants. For multimodal functions f 6 − f 13, MHS also provides competitive results. In the cases of function f 9, f 10, f 12, and f 13, MHS provides the best results for the mean, best, and worst values. In the cases of function f 6 and f 11, MHS provides the best mean values. In the cases of functions f 7 and f 8, NGHS finds the best results. For the shifted and rotated functions f 14 − f 19, MHS provides satisfactory results again. In the cases of function f 14, f 15, and f 18, MHS provides the best results on both mean, best and worst values. In case of function f 16, MHS provides the best mean values. In the cases of function f 17 and f 19, NGHS shows the best performance, followed by MHS.

Table 6 The optimization results of all variants of HS for test functions f 1- f 19(D =30)
Full size table

For most of the meta-heuristic optimization algorithms, their performances sharply decrease when the search space is enlarged and dimensionality increases [42]. As shown in Table 7, the solution accuracy of all of the HS variants are reduced when the dimension of the functions increases from 30 to 50. However, from Table 7, it can be seen that the MHS algorithm still performs better than the other HS variants. As a whole, out of the 19 functions studied, MHS has outperformed all other variants of HS in 11 benchmark functions for the “best” fitness values, 13 benchmark functions for the “worst” fitness values, and 12 benchmark functions for the 50-dimensional “mean” fitness values. Furthermore, for the cases of functions f 3, f 6, f 17 and f 19, the performance of MHS ranked in 2nd place among the compared HS variants. The worst performance of MHS occurs in solving function f 8, for which it ranked in 4th place among all of the compared algorithms.

Table 7 The optimization results of all variants of HS for test functions f 1- f 19(D =50)
Full size table

4.2.3 Rank based analysis

In this section, a rank based analysis method is utilized to evaluate the performance of the compared HS variants. The rank rules are as follows: all of the algorithms obtain a rank value based on their performance on “best”, “worst” and “mean” values, and algorithms receive the same rank if they show the same performance. The next algorithms will be assigned with a gap determined by the number of algorithms that show the same performance. The ranks of the HS variants and the average rank for all of the functions based on both the cases of the 30 and 50-dimensional best performances are shown in Table 8. Based on the average ranking, the order of performance obtained is MHS, followed in order by NGHS, SGHS, GHS, GSHS, LAHS, IHS, i-HS and HS in the 30-dimensional case, and it is MHS followed in order by NGHS, SGHS, GSHS, LAHS, i-HS, HS, GHS and IHS in the 50-dimensional case.

Table 8 Rank table for the best values of 30-dimensional and 50-dimensional
Full size table

Figure 7 shows the histograms that indicate the number of times each HS variant achieved ranks in the range of 1 to 9. In detail, Fig. 7a shows the results for the 30-dimensional case, and Fig. 7b shows the same for the 50-dimensional case. The performance of an algorithm can be judged by the height of the histogram: a higher rectangle with cool colors indicates better performance, while a higher rectangle with warm colors indicates worse performance. It can be seen that MHS achieves the top rank five times more than NGHS, which is the second best algorithm in the 30-dimensional case. For the 50-dimensional case, MHS is the top ranked algorithm four times more than the second best algorithm, which is NGHS again.

Fig. 7
figure 7

Histogram of individual best ranks (a) 30-dimensional, (b) 50-dimensional

Full size image

Next, the compared algorithms are ranked based on their performances in the competition of “worst” and “mean” value. The rankings of the compared algorithms and the average rank based on all of the functions for both the 30-dimensional and 50-dimensional mean performances are presented in Tables 9 and 10. As can be seen from Table 9, MHS is ranked first based on the average rank in the 30 dimensional case, followed by NGHS, SGHS, GSHS, i-HS, HS, LAHS, GHS and IHS. The rank order in the 50 dimensional case is MHS, NGHS, SGHS, GSHS, i-HS, GHS, LAHS, HS and IHS.

Table 9 Rank table for the worst values of 30-dimensional and 50-dimensional
Full size table
Table 10 Rank table for the mean values of 30-dimensional and 50-dimensional
Full size table

As with the “best” value rank analysis, the histograms of the “worst” and “mean” values ranks are depicted in Figs. 8 and 9, respectively. It is again clear that MHS outperforms the other HS variants.

Fig. 8
figure 8

Histogram of individual worst ranks (a) 30-dimensional, (b) 50-dimensional

Full size image
Fig. 9
figure 9

Histogram of individual mean ranks (a) 30-dimensional, (b) 50-dimensional

Full size image

4.2.4 Statistical comparison by Wilcoxon’s rank sum test

A rank based analysis method has been applied to validate the superiority of MHS, but it is not a conclusive measure. Hence, in this section, a nonparametric statistical test called Wilcoxon’s rank sum test for independent samples is conducted at the significance level of 5 % to judge whether the results obtained using the MHS algorithm differ from the final results of the other competitors in a statistically significant way.

The P-values calculated through the rank sum between MHS and other HS variants over all 19 benchmark functions are provided in Tables 11 and 12, for the 30 dimensional case and the 50 dimensional case, respectively. In these tables, NA appears when the related algorithms obtained the same solution with MHS. It can be observed from Table 11 that MHS achieved statistically superior performance compared to all of the other HS variants for 16 functions out of 19 in the 30 dimensional case. The differences among MHS, SGHS, NGHS, and GSHS are not statistically significant for test function f 4; the differences among MHS, SGHS, and GSHS are not statistically significant for test function f 8; the differences among MHS, SGHS and NGHS are not statistically significant for test function f 14. Similar observations can be found in Table 12 for the 50 dimensional case, where MHS also achieved statistically superior performance compared to all of the other HS variants for 16 functions out of 19. The differences among MHS, SGHS, NGHS, and GSHS are not statistically significant for test function f 4; the differences between MHS and NGHS are not statistically significant for test function f 6; the differences among MHS, SGHS, and NGHS are not statistically significant for test function f 14.

Table 11 P-values calculated for Wilcoxon’s Rank Sum Test for all of the benchmarks problems(30D)
Full size table
Table 12 P-values calculated for Wilcoxon’s Rank Sum Test for all of the benchmarks problems(50D)
Full size table

4.2.5 Comparison of the convergence properties

In this section, the convergence properties of all of the compared HS variants in 30 dimensional case are investigated. To save space, only some of the benchmark functions with different characteristics are performed. Figures 10, 11 and 12 give the convergence graphs of unimodal functions, multimodal functions and shifted and rotated functions, respectively. From Fig. 10, it can be seen that NGHS converges faster than other other algorithms in the first half of FEs, while MHS catches up during the second half. The same situation happens for function f 9, which is depicted in Fig. 11a. For function f 12, GHS and SGHS converge faster than other algorithms during the initial stage of iteration, but they are then trapped into the local optima, while MHS can jump out of the local optima and continue converging. Finally, for the shifted and rotated functions, MHS converges faster than the other algorithms for function f 18 (Fig. 12a) while converging slower than NGHS for function f 19 (Fig. 12b).

Fig. 10
figure 10

Convergence graphs of the nine compared algorithms on unimodal functions (in 30 D). a Sphere function (f 1). b Schewefel’s function 2.22. (f 2)

Full size image
Fig. 11
figure 11

Convergence graphs of the nine compared algorithms on multimodal functions (in 30D). a Ackley function (f 9). b Shaffer function (f 12)

Full size image
Fig. 12
figure 12

Convergence graphs of the nine compared algorithms on shifted and rotated functions (in 30D). a Shifted rotated Griewank function (f 18). b Shifted rotated Rastrigin function (f 19)

Full size image

4.3 Comparison of MHS and other meta-heuristic algorithms

To further evaluate the performance of MHS, 28 benchmarks of CEC2013 are tested, and the results are compared with the following algorithms which include ABC, two PSO variants, and three DE variants:

  1. 1.

    The latest Standard PSO 2011 [52] with Np = 40, acceleration coefficients c 1, c 2 = 0.5+ln(2) and constant inertia weight ω = 1/(2*ln(2));

  2. 2.

    Self-adaptive Heterogeneous PSO (SaHPSO) [53] with Np = 50, other parameters such as the stagnation threshold, k and the tournament size are self-adapted during the search process;

  3. 3.

    Artificial bee colony algorithm (ABC) [6] with Np = 40, percentage of onlooker bees p = 50 %;

  4. 4.

    DE/rand1/bin [54]with Np = 50, F = 0.5 and Cr = 0.90;

  5. 5.

    JADE [55] with Np = 100, c = 0.1, p = 0.05, and optional external archive;

  6. 6.

    SHADE [56] with Np = 100, memory size H = Np = 100.

All of the results are taken from the referenced literature except ABC. The ABC code was download from the website (http://sci2s.ugr.es/eamhco/src/ABC.C). All of the benchmarks are tested in 10 and 30 dimensions. The maximum number of FEs was set to 1×105 for 10-D and to 3×105 for 30-D, according to the guidelines provided in CEC2013 special session.

Tables 13 and 14 show the mean and standard deviation of the best-of-run errors for 51 independent runs of each of the seven algorithms for D =10 and D =30, respectively. Note that the best-of-run error corresponds to the absolute difference between the best-of-run value\(f(\vec {{X}}_{\text {best}} )\) and the actual global optimum f ∗ of a particular objective function |f(X best) − f ∗|. When the error value is smaller than 10−8, it is taken as 0.

From Table 13 we can see that, considering the mean of the error values for 10D problems, MHS outperformed all of the other contestant algorithms, obtaining 17 best solutions out of 28 test functions, followed by ABC, obtaining nine best solutions. Moreover, for f 1 and f 5, all the contestant algorithms obtain the global optimum for every run. For function f 11, four algorithms obtain the global optimum, including SHADE, JADE, ABC, and MHS. For f 2 and f 4, three algorithms obtain the global optimum, including SHADE, JADE and MHS.

Table 13 Mean and standard deviation (±S D) of CEC2013 optimization results (D =10)
Full size table

Table 14 shows that the superiority of MHS is more evident when the dimensionality increases. MHS obtains the best solutions for 18 test functions out of 28 in this case, followed by JADE, which obtained seven of the best solutions; SHADE, which obtained six, and ABC obtained five. The performance of DE/rand/1 is not good when dealing with 30-D problems, obtaining only one best solutions.

Table 14 Mean and standard deviation (±S D) of CEC2013 optimization results (D =30)
Full size table

From the experiment showed above, we can see that the MHS algorithm, which maintains a good balance between exploration and exploitation, outperforms the state-of-the-art HS variants and several other meta-heuristic algorithms. The success of MHS could come from two aspects: first, the intersect mutation operation in MHS maintains the diversity of harmonies well; second, the local search based on the CA mechanism further enhances the local exploitation ability of MHS.

5 Conclusions

A modified HS algorithm with intersect mutation operator and cellular local search (MHS) is presented in this paper. First, the MHS algorithm utilizes an intersect mutation operation. In the MHS algorithm, all harmonies in the harmony memory are divided into a better part and a worse part according to their fitness, and then novel mutation and crossover operations are developed to generate new-harmony vectors. Second, a cellular local search is adopted to further enhance the local exploitation ability of MHS. From the experimental results listed in Section 4, we can see that the proposed MHS algorithm performs better than the state-of-the-art HS variants and is competitive with other meta-heuristic algorithms in terms of solution accuracy and efficiency. The superiority of MHS in both efficiency and accuracy could come from the intersect mutation strategy, cellular local search, and a better balance of global exploration and local exploitation.

The following are the main contributions of this study:

  1. 1.

    It proposes a new variant of the HS algorithm in which intensification and diversification are well balanced.

  2. 2.

    The proposed MHS algorithm is successfully applied to function optimization in this paper. It could be applied to other problems.

  3. 3.

    MHS may also provide a new improvement strategy for other algorithms.

In the future, intelligent tuning strategies for MHS algorithm parameters can be studied for seeking further improvements. Furthermore, the proposed MHS algorithm will be expanded to solve certain constrained optimization problems, multi-objective problems, and optimization problems with high computational cost. Some engineering applications of MHS will also be investigated in the near future.