Analysing the Performance of Migrating Birds Optimisation Approaches for Large Scale Continuous Problems

Abstract

We present novel algorithmic schemes for dealing with large scale continuous problems. They are based on the recently proposed population-based meta-heuristics Migrating Birds Optimisation (mbo) and Multi-leader Migrating Birds Optimisation (mmbo), that have shown to be effective for solving combinatorial problems. The main objective of the current paper is twofold. First, we introduce a novel neighbour generating operator based on Differential Evolution (de) that allows to produce new individuals in the continuous decision space starting from those belonging to the current population. Second, we evaluate the performance of mbo and mmbo by incorporating our novel operator to them. Hence, mbo and mmbo are enabled for solving continuous problems. A set of well-known large scale functions is used for comparison purposes.

1 Introduction

Nature-inspired computing counts with an extensive variety of algorithms mimicking natural processes and events from the universe that are frequently used for tackling real-world optimisation problems. Along these algorithms, those inspired by the collective living and travelling of animals have attracted a considerable interest from the related research community [11]. In this regard, the collective behaviour and swarm intelligence of migratory birds and its algorithmic translation have been recently studied by Duman et al. [2], and Lalla-Ruiz et al. [4]. Authors exploit, by means of their corresponding proposed algorithmic approaches, the advantage of sharing information and cooperating among a group of individuals. While Migrating Birds Optimisation (mbo), which is inspired by the V-flight formation of migratory birds with one leader, was proposed in [2], in [4], based on field studies, Multi-leader Migrating Birds Optimisation (mmbo) was introduced, which allows different types of flight formation shapes, as well as several leading individuals, to be managed.

Recently, mbo has shown its good performance for combinatorial problems, such as the Quadratic Assignment Problem (qap) [2], the Dynamic Berth Allocation Problem (dbap) [5], and Hybrid Flow-shop Scheduling [8], among others. In regard to continuous optimisation, an initial adaptation to low-dimensional problems, which uses sphere-shaped neighbourhoods, was developed in [1]. Results provided by said scheme, however, did not show a high performance. Regarding mmbo, it showed to provide better quality results than those achieved by mbo for the qap [4]. Concerning its performance for continuous optimisation, as far as we know, this is the first time that mmbo is enabled for dealing with these types of problems, as well as the first time that mbo is assessed when solving large scale continuous problems.

The main goal of this work is to propose suitable adaptations of mbo and mmbo for tackling continuous optimisation problems. For doing that, we propose a novel neighbourhood structure based on the well-known Differential Evolution (de) [10], which is able to generate solutions in a continuous decision space. The computational experimentation provided in this work, which involves the use of a set of well-known large scale continuous problems [7], indicates that our proposals are able to improve, for some cases, the results obtained by one of the best performing variants of de considering that set of large scale functions [3].

The remainder of this paper is organised as follows. Section 2 describes our proposed mbo and mmbo approaches. Afterwards, in Sect. 3, the experimental evaluation carried out in this paper is exposed. Finally, Sect. 4 draws the main conclusions extracted from this work and provides some lines for further research.

2 Schemes Based on Migrating Birds Optimisation for Continuous Problems

This section focuses on describing our algorithmic proposals. Section 2.1 is devoted to describe the scheme mbo, while the approach mmbo is depicted in Sect. 2.2. Finally, in Sect. 2.3 we introduce our novel neighbour generating operator based on de.

2.1 Migrating Birds Optimisation

Migrating Birds Optimisation (mbo) is a population-based algorithm based on the V-formation flight of migrating birds. It considers a population or flock, of individuals or birds, that are aligned in a V-flight formation. Following that formation, the first individual corresponds to the leader of the flock and the other ones define the rest of the flock. The birds maintain a cooperative relationship among them by means of sharing information. The way the flow of information is shared is unidirectional. Namely, one individual sends information and the other receives it. The direction of the information shared starts from the leader bird and goes to the rest of the flock by following the V-shape flight formation.

Algorithm 1 depicts the pseudocode of mbo. The input parameters are: (i) the number of birds in the flock (n), (ii) the maximum number of neighbours generated by the flock of birds (K), (iii) the number of iterations performed before changing the leader bird (m), (iv) the number of neighbours generated by each bird (k), and (v) the number of best discarded neighbours to be shared among birds (x). The first step consists of generating n individuals or birds (line 1). The current number of neighbours generated by the flock of birds, i.e. g, is initially set to zero (line 2). During the search process, firstly, k neighbours are generated starting from the leader bird. In case the best neighbour leads to an improvement of the leader in terms of the objective function value, the latter is replaced by the former (line 5). Secondly, for each non-leader bird s, $k-x$ neighbours are generated. Additionally, the neighbourhood of s receives x unused best neighbours from those birds in front of it (lines 7–10). If s is improved by its best neighbour, then the former is replaced by the latter (line 8). The V-formation is maintained until a prefixed number of iterations $m > 0$ is reached. Once that, the leader bird becomes the last bird in the V-formation and one of its immediate successors becomes the new leader (line 12). The above steps are executed until a maximum number of neighbours, i.e. K, is generated (line 3). Finally, we should mention that, in our case, neighbours are created (lines 5 and 8) by using the operator described in Sect. 2.3.

2.2 Multi-leader Migrating Birds Optimisation

Multi-leader Migrating Birds Optimisation (mmbo) is a novel population-based meta-heuristic inspired by the flight formation of migratory birds which tries to improve its predecessor mbo. In mmbo, birds are distributed in a line formation mimicking the flight formation of migratory birds, which is determined according to given relationship criteria, e.g. by means of the objective function of the problem at hand. Depending on those criteria, we can have birds located at positions that are closer than others regarding the front of the migratory formation during the flight. Starting from each bird, a given number of feasible neighbours are generated through a predefined neighbourhood structure. The neighbourhoods reflect the particular points of view about the solution space of each individual. As mentioned above, depending on the relationship criteria and how information is shared among individuals, different roles arise in mmbo:

• Leader. It is that bird with the best objective value when compared to the adjacent ones. Therefore, it does not receive information from any bird, but shares x neighbours with each adjacent one. Moreover, starting from a leader, k neighbours are generated. Since the objective value determines the position within the formation, a leader is the best performing bird, and consequently, the most advanced one in its corresponding group within the formation. The set of leaders is denoted as $P_{L}$.

• Follower. It is that bird which explores the search space considering its own information and the information received from the birds in front of it within the formation. It generates $k-x$ neighbours and receives x neighbours from the adjacent birds. The set of followers is denoted as $P_{F}$.

• Independent. It is that bird which is not included into any other of the above categories. It does not exchange information with any other individual, but generates k neighbours. The set of independent birds is denoted as $P_{I}$.

The pseudocode of mmbo is depicted in Algorithm 2. The first step is to obtain the initial flock P which consists of n birds generated at random (line 1). While the stopping criterion is not met, mmbo iterates (line 2). In this work, we consider a stopping criterion based upon a maximum number of neighbours to be generated (K). The relationship criteria among birds are based on the objective function value. This allows to recognise groups, as well as the formation (line 3). Then, the search process starts (lines 4–13) and it is executed until a stopping formation criterion is met. In case said criterion is satisfied, the search process is stopped in order to establish a new formation. During the search process, firstly, k neighbours are obtained starting from each bird $b \in P_{L} \cup P_{I}$ (line 5). Then, sets $P_{L}$ and $P_{I}$ are updated (lines 6–7). Secondly, for each follower $f \in P_{F}$, $k - x$ neighbours are generated (line 9), and it receives x neighbours from the adjacent birds according to the formation (line 10). Afterwards, if f is improved by its best neighbour, the former is replaced by the latter (line 11). The unused best neighbours of f are shared with the adjacent birds. In this work, neighbours are obtained (lines 5 and 9) by applying the operator introduced in Sect. 2.3.

2.3 Neighbour Generating Operator Based on Differential Evolution

This work presents a novel neighbour generating operator to be used with mbo and mmbo in order to enable their operation with continuous optimisation problems. This operator is based on the well-known Differential Evolution (de), a search algorithm which was specifically proposed for global optimisation [10].

For encoding individuals, a vector of D real-valued decision variables or dimensions $x_i$ is used, i.e. $\mathbf {X} = [x_1, x_2, \ldots , x_i, \ldots , x_D]$. The objective function $f(\mathbf {X})(f:\varOmega \subseteq \mathbb {R}^{D} \rightarrow \mathbb {R})$ determines the quality of every vector $\mathbf {X}$. Hence, finding a vector $\mathbf {X*} \in \varOmega$, where $f(\mathbf {X*}) \le f(\mathbf {X})$ is satisfied for all $\mathbf {X} \in \varOmega$, is the goal in a global optimisation problem. Considering box-constrained problems, the feasible region $\varOmega$ is defined by $\varOmega = \prod _{i=1}^{D} [a_i, b_i]$, where $a_i$ and $b_i$ represents the lower and upper bounds of variable i.

Regarding the most widely used nomenclature for de [10], i.e. de /x/y/z, where x is the vector to be mutated, y defines the number of difference vectors used, and z indicates the crossover approach, our neighbour generating operator is inspired by the scheme de/rand/1/bin. We selected this variant due to its simplicity and popularity and because it was able to provide the best performance in previous work with the set of large scale problems we consider herein [3].

Given a particular individual $\mathbf {X}_{j = 1 \ldots NP}$ (target vector) from a flock of either mbo or mmbo with size NP, a neighbour is obtained as follows. First, the mutant generation strategy rand/1 is applied for obtaining a mutant vector ($\mathbf {V}_j$). Thus, the mutant vector is generated as Eq. 1 shows. We should note that $r_1$, $r_2$, and $r_3$ are mutually exclusive integers randomly selected from the range [1, NP], all of them different from the index j. Finally, F denotes the mutation scale factor.

$$\begin{aligned} \mathbf {V}_j = \mathbf {X}_{r_3} + F \times (\mathbf {X}_{r_1} - \mathbf {X}_{r_2}) \end{aligned}$$

(1)

After obtaining the mutant vector, it is combined with the target vector to produce the trial vector ($\mathbf {U}_j$) through a crossover operator. The combination of the mutant vector generation strategy and the crossover operator is usually referred to as the trial vector generation strategy. One of the most commonly applied crossover operators, which is considered in this work, is the binomial crossover (bin). The crossover is controlled by means of the crossover rate CR, and uses Eq. 2 for producing a trial vector, where $x_{j,i}$ represents decision variable i belonging to individual $\mathbf {X}_j$. A random number uniformly distributed in the range [0, 1] is given by $rand_{j,i}$, and $i_{rand} \in [1, 2, ..., D]$ is an index selected at random that ensures that at least one variable belonging to the mutant vector is inherited by the trial one. Variables are thus inherited from the mutant vector with probability CR. Otherwise, variables are inherited from the target vector.

$$\begin{aligned} u_{j,i} = \left\{ \begin{array}{ll} v_{j,i} &{} if\ (rand_{j,i}\ \le \ CR\ or\ i\ =\ i_{rand}) \\ x_{j,i} &{} otherwise \end{array} \right. \end{aligned}$$

(2)

It can be observed that the trial vector generation strategy may generate vectors outside the feasible region $\varOmega$. In this work, unfeasible values are reinitialised at random in their corresponding feasible ranges, being this approach one of the most frequently used in the related literature. Finally, we should note that the trial vector becomes the newly generated neighbour.

3 Experimental Evaluation

In this section we describe the experiments carried out with both algorithms depicted in Sect. 2. In addition to those schemes, we also considered the variant de/rand/1/bin as an independent approach for comparison purposes.

Experimental Method. mbo and mmbo, as well as de/rand/1/bin, were implemented by using the Meta-heuristic-based Extensible Tool for Cooperative Optimisation (metco) [6]. Experiments were run on a debian gnu/linux computer with four amd® opteron™ processors (model number 6164 he) at 1.7 ghz and 64 gb ram. Every execution was repeated 30 times, since all experiments used stochastic algorithms. Bearing the above in mind, comparisons were carried out by applying the following statistical analysis [9]. First, a Shapiro-Wilk test was performed to check whether the values of the results followed a normal (Gaussian) distribution or not. If so, the Levene test checked for the homogeneity of the variances. If the samples had equal variance, an anova test was done. Otherwise, a Welch test was performed. For non-Gaussian distributions, the non-parametric Kruskal-Wallis test was used. For all tests, a significance level $\alpha = 0.05$ was considered.

Problem Set. A set of scalable continuous optimisation functions proposed in the 2013 ieee Congress on Evolutionary Computation (cec’13) for its Large Scale Global Optimization (lsgo) competition [7] was considered as the problem set. We should note that this suite is the latest proposed for large scale global optimisation in the field of the cec, and therefore, it was also used for the lsgo competitions organised in cec’14 and cec’15. The suite consists of 15 different problems ($f_1$–$f_{15}$) with different features: fully-separable functions ($f_1$–$f_3$), partially additively separable functions ($f_4$–$f_{11}$), overlapping functions ($f_{12}$–$f_{14}$), and non-separable functions ($f_{15}$). By following the suggestions given for different editions of the lsgo competition, we fixed the number of decision variables D to 1000 for all the above functions, with the exception of functions $f_{13}$ and $f_{14}$, where 905 decision variables were considered due to overlapping subcomponents.

Table 1. Configuration of the approaches mbo, mmbo, and de/rand/1/bin

Parameters. Table 1 shows parameter values considered in this work for mbo and mmbo. They were selected by carrying out a previous parameter setting study. As it can be observed in Sect. 2, parameter m is only considered by mbo. In past research, a configuration of the scheme de/rand/1/bin, from among a candidate pool with more than 80 different parameterisations of said approach, was able to provide the best overall results for problems $f_1$–$f_{15}$ [3]. This is the main reason why our neighbour generating operator is based on de/rand/1/bin. Moreover, that best performing configuration, whose parameter values (NP, F, and CR) are also shown in Table 1, is considered herein as an independent method for measuring the performance attained by mbo and mmbo. Our operator also makes use of those parameter values. Finally, the stopping criterion was fixed to a maximum amount of $3 \times 10^6$ evaluations, following the recommendations provided by the lsgo competition.

Fig. 1.

Box-plots showing the results obtained by different schemes for functions $f_1$–$f_{15}$

Results. Figure 1 shows box-plots reflecting the results obtained by the considered schemes. It can be observed that, for some problems ($f_2$, $f_3$, $f_5$, $f_9$, and $f_{11}$) mbo and/or mmbo were able to obtain better solutions than those provided by the best performing variant of de/rand/1/bin found for the large scale problems we consider in this work, thus showing the benefits that can be obtained from our hybridisation between mbo/mmbo and our novel neighbour generating operator based on de. Since our neighbour generating operator is based on de/rand/1/bin, it was expected that results obtained by mbo and mmbo were very similar to those provided by the former scheme executed independently. However, the features of mbo and mmbo for sharing information among individuals, as well as for establishing a structure among them, combined with the the exploration and exploitation abilities of our neighbour generating operator based on de/rand/1/bin, were able to obtain even better results in 5 out of 15 problems. Taking into account the remaining functions, we should note that mbo and/or mmbo were able to achieve similar solutions than those attained by the best performing variant of de, with except to some cases, such as $f_1$, where de provided better solutions.

In order to give the aforementioned conclusions with statistical confidence, Table 2 shows, for each problem, the p-values obtained from the statistical comparison between the approach mbo and the rest of schemes, by following the statistical procedure explained at the beginning of the current section. It also shows cases for which mbo was able to statistically outperform other strategy ($\uparrow$), cases where other strategy outperformed mbo ($\downarrow$), and cases where statistically significant differences between mbo and the corresponding method did not arise ($\leftrightarrow$). Scheme A statistically outperforms method B if there exist statistically significant differences between them, i.e. if the p-value is lower than $\alpha = 0.05$, and if at the same time, A provides a lower mean and median of the objective value than B, since we are dealing with minimisation problems. Finally, Table 3 shows the same information, but regarding mmbo.

With respect to mbo, it is worth mentioning that it was able to outperform de in 4 out of 15 problems ($f_2$, $f_3$, $f_5$, and $f_9$). Additionally, it was not outperformed by de in any test case. For remaining problems, mbo and de did not present statistically significant differences. Concerning mmbo, we should note that it was able to beat de in problems $f_2$ and $f_{11}$, it was beaten by de considering functions $f_1$ and $f_{12}$, and both approaches did not show statistically significant differences when dealing with remaining test cases. Bearing the above in mind, mbo/mmbo were able to provide better solutions than those achieved by de in 5 out of 15 problems. However, de was able to outperform mbo/mmbo in 2 out of 15 functions. This means that mbo/mmbo were able to attain similar or even better solutions than de in 13 out of 15 problems.

If we compare mbo with respect to mmbo we can make the following observations. mbo provided statistically better results than mmbo in 4 problems ($f_1$, $f_3$, $f_5$, and $f_9$), while the latter was not statistically better than the former in any case. Taking into account the remaining problems, statistically significant differences did not appear between both schemes.

Table 2. Statistical comparison between mbo and remaining schemes considering problems $f_1$–$f_{15}$

Table 3. Statistical comparison between mmbo and remaining schemes considering problems $f_1$–$f_{15}$

4 Conclusions and Future Work

Algorithms inspired by the nature comprise an important type of solution approaches used for solving practical problems. Some of these approaches have been successfully applied to combinatorial problems, such as mbo and mmbo. Nevertheless, to our best knowledge, they had not been used for tackling large scale continuous problems. Hence, in this work we propose novel adaptations of both population-based meta-heuristics for solving relevant problems in this research area. For doing that, we developed a novel neighbour generating operator based on de that allows new individuals to be generated in the continuous decision space. The experimental evaluation carried out indicates that our proposals are suitable and competitive for performing the optimisation of large scale continuous problems. In this regard, results demonstrate that mbo and mmbo are able to obtain similar solutions, and even better for some cases, than those provided by one of the best performing variants of de considering the set of large scale continuous problems at hand.

Bearing in mind the contributions of this work, our research agenda will be focused on the assessment of the influence that the different parameters of mbo and mmbo have over their performance when solving continuous problems. Additionally, an analysis about the impact that different neighbourhood structures have over the behaviour of mbo and mmbo might also be of great interest.