Research on the searching performance of flower pollination algorithm with three random walks

Abstract

Flower pollination algorithm is a new type of heuristic algorithm, which uses Lévy random walk as the key element for high efficiency of global searching. In order to explore the search performance of pollination algorithms under different random walk models, three random walk models are taken into account, including levy random walk model used by original flower pollination algorithm and two new random walk models based on McCulloch algorithm introduced in this paper. The analysis of searching performance and adaptive of Flower Pollination Algorithm with three random walks from two aspects of the model structure and the numerical simulation is given. The result shows that Cauchy random has a great competitive advantage for the low dimensional searching problem, and the Gauss random is more suitable for dealing with the multi-dimension unimodal case, while the Lévy random is able to provide better performance of solving the multi-dimension multimodal case. Simulation results and analysis will have a significant impact on the design of the randomness mechanism of the meta-heuristics algorithm and the improvement of Classical algorithms.

Keywords

Flower pollination algorithm meta-heuristic algorithm random walk multi-dimension multimodal

1 Introduction

Randomization, one of the most needed features to consider when designing heuristic and meta-heuristic algorithms, has great theoretical significance to improve the diversity, precision, convergence speed and global searching capability of the algorithm [1]. The randomization mechanism of the algorithm is generally implemented by using pseudo-random numbers generated through some stochastic process methods and random walk model plays an important role in the stochastic design of heuristic algorithms. From the view of the heuristic algorithm, the random walk model uses some typical probability distribution functions to generate random numbers as the walking step for updating the ‘position’ of the current solution vectors in whole solution domain, so as to guarantee the global searching capability of the algorithm.

Levy flight, first discovered in the study of foraging behavior of ant colony [1 –5], is a special type of random walk. The walking step, in this case, is drawn from a power-law distribution called Levy distribution which can effectively demonstrate the randomness of intelligent algorithms. Since Levy flight shows competitive in large-scale searching capability [6 –8], it has been widely used in the stochastic optimization design of the algorithm, such as, Flower Pollination Algorithm (FPA) [12], Improved Particle Swarm with Levy flight (PSL) [11], Levy inspired grey wolf Algorithm (LGWA) [13], Cuckoo search (CS) [10] and some improved intelligent algorithms [14 –19] with levy characteristic etc. Among them, the Flower Pollination Algorithm, proposed by Yang et al. in 2013, has a powerful global searching ability by using Levy flight to simulate the process of remote pollination. Since this algorithm fully reflects the randomness of levy flight, it is often regarded as a typical meta-heuristic algorithm for studying the impact of Levy flight on the global search. In recent researches of the randomness design of the meta-heuristic algorithm, there are two main questions about Levy flight should be answered.one is whether the Levy flight is the best scheme of randomness design of a meta-heuristic algorithm for now. The other is what the differences in the global search ability of the algorithms based on the random walk model with different distributions are.

In our previous research, the optimal performance analysis of the cuckoo algorithm with different random walk models has been studied, but it should be concerned in detail whether this analysis method and the comparison result mentioned before can be equally applicable for other levy flight based algorithms. Therefore, this paper focuses on the global optimization performance of FPA with three different random walks. The content of this paper is arranged as follows: section 2 gives a brief introduction of the basic principle and algorithm framework of FPA. In section 3, random walks model with Levy case, Gauss case, and Cauchy case are introduced and analyzed from the mathematical point of view respectively. In section IV, detailed comparative analysis of the global optimization performance of FPA with three different random walks is proposed via numerical simulations. In the last section, several conclusions of this work are given.

2 Flower pollination algorithm

Flower pollination algorithm (FPA) is one of the intelligent algorithms that are enlightened by the law of nature. Particularly, its idea comes from the pollination of plants, which consists of self-pollination and cross-pollination in terms of different plants. In self-pollination, the plants pollinate their own pistil or Pollination between congeneric plants. On the contrast, If the pollination is achieved through intermediates, e.g. insects transmit pollen among flower plants, this process can be referred to the cross-pollination. By analyzing the above two pollination processes, Yang et al. [12] abstracted four basic rules from pollination of flower plants to establish the conceptual model of flower pollination algorithm.

Define the cross-pollination as global pollination, and the Intermediary subjects to Levy flight.

Define the self-pollination as local pollination.

Define the flower constancy as the replicative probability, which is proportional to the similarity between the two flowers involved in the pollination.

Switch between the global pollination and local pollination according to a probability parameter. Due to the physical adjacency and with the consideration of winds, the local pollination is the dominant process during the pollination.

Following these rules above, one can achieve the basic framework of FPA. Obviously, the mathematical definition of global and local pollination is the key component of FPA.

The formula for the global pollination is described by Equation (1) $x_{i}^{t + 1} = x_{i}^{t} + L (x_{i}^{t} - g_{*})$ (1)

Where $x_{i}^{t}$ is the solution vector at the t-th iteration, g_* is the best solution vector of the current iteration. L is the step length that the Intermediary has moved, which represents the global random walk in mathematics. The step length of L can be effectively stimulated by the Lévy flight. Here, the parameter L is a positive real number and obeys the Lévy distribution which showed in Equation (2)

$L \sim \frac{λ Γ (λ) sin (π λ / 2)}{π} \frac{1}{s^{1 + λ}}$ (2)

Where Γ (λ) represents the standard gamma function. And it’s valid when s > 0.

The local pollination can be represented by the following equation:

$x_{t}^{t + 1} = x_{i}^{t} + ɛ (x_{j}^{t} + x_{k}^{t})$ (3)

Where $x_{j}^{t}$ and $x_{k}^{t}$ are the pollens from different flower instances in the congeneric plant, used to simulate the constancy of nearby flowers. Mathematically, when $x_{j}^{t}$ and $x_{j}^{t}$ come from the same population, the Equation (3) can be considered as the local random walk process, and subjects to the uniform distribution between [0, 1]. Based on the rules and notation above, the pseudo code of FPA is given in Fig. 1.

Fig. 1

Pseudo code of the FPA.

3 Random walk model

Random walk model is one of the forms of random process. In algorithms, it is commonly represented by a path consists of a set of continuous random step length in a certain space. Every individual step is an independent random variable. The common expression of random walk model can be described by Equation (4) $S_{n} = \sum_{i = 1}^{n - 1} s_{i} + s_{n} = S_{n - 1} + s_{n}$ (4)

Where s_i is an independent random variable, and s_n represents a random process subject to Equation (4). Note that, the random walk is a typical Markov chain. In FPA, the Lévy flight is employed as a pseudorandom number generator, its step lengths are randomly generated by the Mantegna’s algorithm, and they subject to the uniform Levy steady-state distribution. In this paper, another two random number generators based on McCulloch’s algorithm [20] are proposed, to study how random walk model affects the performance of global optimization of FPA. In the following section, we will address these three generators in detail.

3.1 Lévy random

Yang et al. proposed a random number generator based on Mantegna algorithm in 2014, see in Equations (5–7). $s = u / | v |^{1 / β}$ (5) $u \in N (0, σ_{u}), v \in N (0, σ_{v})$ (6) $σ_{u} (β) = {[\frac{Γ (1 + β) \cdot sin (π β / 2)}{Γ ((\frac{1 + β}{2}) β \cdot 2^{(\frac{β - 1}{2})})}]}^{1 / β}, σ_{v} = 1$ (7)

Where u and v are normal random variables, β ∈ [0.3, 1.99] is the adjustable parameter of the distribution function. In FPA, the parameter β of Levy distribution can be set to 3/2. To distinguish between other two random cases, It can be called Levy random or Levy step in the whole paper.

3.2 Gaussian and Cauchy random

The symmetric a-stable distribution function which generated by McCulloch algorithm can be expressed by Equation (8) $s = c {\frac{cos [(1 - θ) φ]}{w}}^{1 / θ - 1} \cdot {[\frac{sin (θ φ)}{cos (φ)}]}^{1 / θ} + τ$ (8)

Where ω and φ are independent random variables, subjects to the uniform distribution within [- π/2, π/2] and the standard exponential distribution, respectively. c denotes the scale factor and parameter θ reflects the characteristic exponent in the probability distribution. According to Equation (8), two special cases including Gauss and Cauchy case can be obtained by adjusting parameter θ.

In the Gauss case, the Equation (9) can be obtained from Equation (8) by setting the parameter θ to 2. $s = 2 c \sqrt{w} \cdot sin (φ)$ (9)

Similarly, the Cauchy case can be formulated in Equation (10) by setting the parameter θ to 1. $s = c tan (φ)$ (10)

By observing Equation (10), it can be obviously found that the range of a random parameter s is from -c to c. To enhance the diversity of the Cauchy model, a modified Cauchy case with standard Gaussian noise is proposed in Equation (11). $s = c tan (φ) + τ, τ \in N (0, 1)$ (11)

Similar to Levy random, we can call the Equations (9 and 11) as Gaussian random and Cauchy random, or Gaussian step and Cauchy step. Moreover, the Fig. 2 and the Fig. 3 show the migration path and amplitude variation of 50 sets of random variables, which are generated by these three Random walk models.

Fig. 2

Trajectory of three random walks in 2D space.

Fig. 3

2-D Step change curves of three random walks.

3.3 Character analysis of three random walk

As can be seen in Fig. 2, the Fig. 2(a-c) reflect the trajectory created by levy random, Gaussian random and Cauchy random walk in two-dimensional space, respectively. Among them, the trajectory in Fig. 2(a) shows existing mutation point in the walk step generating process, which can ensure that the algorithm avoids falling into the local optimum. But the number of its mutation point is small and the step size of the mutation point changes drastically, which directly influence the overall convergence rate. In Fig. 2(b), the trajectory generated by Gauss random changes steadily, which can effectively search the neighborhood of the optimal position of each iteration in the optimization process, which ensures the fast convergence of the algorithm, But the step size changes more evenly, cannot guarantee that the algorithm jumps out of the local optimum. Compared with the above two random walk models, Fig. 2(c) shows the dual characteristics of large-scale local search and partial mutation of the Cauchy random. It not only ensures that the algorithm can search the near domain of the current optimal point in each iteration but also relies on some mutation points to achieve the global search capability, which effectively balances the algorithm’s performance in exploration and exploitation. However, the upper bound of step-size variation generated by Cauchy random is almost determined by the parameter c, In Cauchy case, the step size is very sensitive to the parameter c, the mutation point cannot play the role of jumping out of the local optimum without properly setting. Combined with the step change curves in Fig. 3, the above conclusions have been further confirmed. Moreover, the optimization performance of FPA with these three random walks will also be discussed in Section 4.

4 Experiment and analysis

4.1 Test function

To analyze and verify the consequence of the three random walk models on the optimization performance of FPA, there are 23 different standard test functions has been selected and shown in Table 1 [20 , 21–24], evaluating the converge speed and accuracy of the algorithm. All the results are shown in Tables 1 and 2. (F10 - F10) are based on the fixed-dimensional multi-modal test functions, (F11–F17) are based on the multi-dimensional unimodal functions, and (F18 - F23) are based on the fixed-dimensional multi-modal functions and Dim, Range, f_min represents the dimension of test function, solution domain, and global optimal value, respectively.

Table 1
Fixed-dimension multimodal benchmark functions

Function Formula Dim Range f _min

F1 $f_{1} (\vec{x}) = {1 / 500 + \sum_{j = 1}^{25} 1 / [j + \sum_{i = 1}^{2} (x_{i} - a_{ij})^{2}]}^{- 1}$ D = 2 [−65,65]² Min = 1

F2 $f_{2} (\vec{x}) = \sum_{i = 1}^{11} {[a_{i} - x_{1} \cdot (b_{i}^{2} + b_{i} \cdot x_{2}) / (b_{i}^{2} + b_{i} \cdot x_{3} + x_{4})]}^{2}$ D = 4 [−5,5]⁴ Min = 0.000 30

F3 $f_{3} (\vec{x}) = 4 x_{1}^{2} - 2.1 x_{1}^{4} + x_{1}^{6} / 3 + x_{1} \cdot x_{2} - 4 x_{2}^{2} + 4 x_{2}^{4}$ D = 2 [−5,5]² Min = −1.031 6

F4 $f_{4} (\vec{x}) = (x_{2} - 5.1 x_{1}^{2} / 4 π^{2} + 5 x_{1} / π - 6)^{2} + 10 (1 - 1 / 8 π) cos x_{1} + 10$ D = 2 [−5,5]² Min = 0.398

F5 $\begin{matrix} f_{5} (\vec{x}) = [1 + (x_{1} + x_{2} + 1)^{2} \cdot (19 - 14 x_{1} + 3 x_{1}^{2} - 14 x_{2} + 6 x_{1} \cdot x_{2} + 3 x_{2}^{2})] \times \\ [30 + (2 x_{1} - 3 x_{2})^{2} \cdot (18 - 32 x_{1} + 12 x_{1}^{2} + 48 x_{2} - 36 x_{1} \cdot x_{2} + 27 x_{2}^{2})] \end{matrix}$ D = 2 [−2,2]² Min = 3

F6 $f_{6} (\vec{x}) = - \sum_{i = 1}^{4} c_{i} \cdot exp [- \sum_{j = 1}^{3} a_{ij} \cdot (x_{j} - p_{ij})^{2}]$ D = 3 [1,3, 1,3]³ Min = −3.86

F7 $f_{7} (\vec{x}) = - \sum_{i = 1}^{4} c_{i} \cdot exp [- \sum_{j = 1}^{6} a_{ij} \cdot (x_{j} - p_{ij})^{2}]$ D = 6 [0,1]⁶ Min = −3.32

F8 $f_{8} (\vec{x}) = - \sum_{i = 1}^{5} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$ D = 4 [0,10]⁴ Min = −10.153 2

F9 $f_{9} (\vec{x}) = - \sum_{i = 1}^{7} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$ D = 4 [0,10]⁴ Min = −10.402 8

F10 $f_{10} (\vec{x}) = - \sum_{i = 1}^{10} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$ D = 4 [0,10]⁴ Min = −10.536 3

Function	Formula	Dim	Range	f _min
F1	$f_{1} (\vec{x}) = {1 / 500 + \sum_{j = 1}^{25} 1 / [j + \sum_{i = 1}^{2} (x_{i} - a_{ij})^{2}]}^{- 1}$	D = 2	[−65,65]²	Min = 1
F2	$f_{2} (\vec{x}) = \sum_{i = 1}^{11} {[a_{i} - x_{1} \cdot (b_{i}^{2} + b_{i} \cdot x_{2}) / (b_{i}^{2} + b_{i} \cdot x_{3} + x_{4})]}^{2}$	D = 4	[−5,5]⁴	Min = 0.000 30
F3	$f_{3} (\vec{x}) = 4 x_{1}^{2} - 2.1 x_{1}^{4} + x_{1}^{6} / 3 + x_{1} \cdot x_{2} - 4 x_{2}^{2} + 4 x_{2}^{4}$	D = 2	[−5,5]²	Min = −1.031 6
F4	$f_{4} (\vec{x}) = (x_{2} - 5.1 x_{1}^{2} / 4 π^{2} + 5 x_{1} / π - 6)^{2} + 10 (1 - 1 / 8 π) cos x_{1} + 10$	D = 2	[−5,5]²	Min = 0.398
F5	$\begin{matrix} f_{5} (\vec{x}) = [1 + (x_{1} + x_{2} + 1)^{2} \cdot (19 - 14 x_{1} + 3 x_{1}^{2} - 14 x_{2} + 6 x_{1} \cdot x_{2} + 3 x_{2}^{2})] \times \\ [30 + (2 x_{1} - 3 x_{2})^{2} \cdot (18 - 32 x_{1} + 12 x_{1}^{2} + 48 x_{2} - 36 x_{1} \cdot x_{2} + 27 x_{2}^{2})] \end{matrix}$	D = 2	[−2,2]²	Min = 3
F6	$f_{6} (\vec{x}) = - \sum_{i = 1}^{4} c_{i} \cdot exp [- \sum_{j = 1}^{3} a_{ij} \cdot (x_{j} - p_{ij})^{2}]$	D = 3	[1,3, 1,3]³	Min = −3.86
F7	$f_{7} (\vec{x}) = - \sum_{i = 1}^{4} c_{i} \cdot exp [- \sum_{j = 1}^{6} a_{ij} \cdot (x_{j} - p_{ij})^{2}]$	D = 6	[0,1]⁶	Min = −3.32
F8	$f_{8} (\vec{x}) = - \sum_{i = 1}^{5} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$	D = 4	[0,10]⁴	Min = −10.153 2
F9	$f_{9} (\vec{x}) = - \sum_{i = 1}^{7} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$	D = 4	[0,10]⁴	Min = −10.402 8
F10	$f_{10} (\vec{x}) = - \sum_{i = 1}^{10} {[(X - a_{i}) \cdot (X - a_{i})^{T} + c_{i}]}^{- 1}$	D = 4	[0,10]⁴	Min = −10.536 3

Table 2

Benchmark functions with multi-dimension unimodal and multimodal

Function	Formula	Dim	Range	f _min
F11	$f_{11} (\vec{x}) = \sum_{i = 1}^{D} x_{i}^{2}$	D = 30	[−100,100]³⁰	Min = 0
F12	$f_{12} (\vec{x}) = \sum_{i = 1}^{D} \| x_{i} \| + \prod_{i = 1}^{D} \| x_{i} \|$	D = 30	[−10,10]³⁰	Min = 0
F13	$f_{13} (\vec{x}) = \sum_{i = 1}^{D} {(\sum_{j = 1}^{i} x_{j})}^{2}$	D = 30	[−100,100]³⁰	Min = 0
F14	$f_{14} (\vec{x}) = max_{i} (\| x_{i} \|, 1 ⩽ i ⩽ n)$	D = 30	[−100,100]³⁰	Min = 0
F15	$f_{15} (\vec{x}) = \sum_{i = 1}^{D - 1} [100 (x_{i + 1} - x_{i}^{2})^{2} + (x_{i} - 1)^{2}]$	D = 30	[−30,30]³⁰	Min = 0
F16	$f_{16} (\vec{x}) = \sum_{i = 1}^{D} (x_{i} + 0.5)^{2}$	D = 30	[−100,100]³⁰	Min = 0
F17	$f_{17} (\vec{x}) = \sum_{i = 1}^{D} i \cdot x_{i}^{4} + random [0, 1)$	D = 30	[−1.28,1.28]³⁰	Min = 0
F18	$f_{18} (\vec{x}) = \sum_{i = 1}^{D} {- x}_{i} \cdot sin \sqrt{\| x_{i} \|}$	D = 30	[−500,500]³⁰	Min = −12 569.5
F19	$f_{19} (\vec{x}) = \sum_{i = 1}^{D} [x_{i}^{2} - 10 cos (2 π x_{i}) + 10]$	D = 30	[−5.12,5.12]³⁰	Min = 0
F20	$f_{20} (\vec{x}) = - 20 exp (- 0.2 \sqrt{\sum_{i = 1}^{D} x_{i}^{2} / n}) - exp [\sum_{i = 1}^{D} cos (2 π x_{i}) / n] + 20 + e$	D = 30	[−32,32]³⁰	Min = 0
F21	$f_{21} (\vec{x}) = \frac{1}{4000} \sum_{i = 1}^{D} x_{i}^{2} - \prod_{i = 1}^{D} cos (x_{i} / \sqrt{i}) + 1$	D = 30	[−600,600]³⁰	Min = 0
F22	$f_{22} (\vec{x}) = \frac{π}{D} {\begin{matrix} 10 sin (π y_{1}) + \\ \sum_{i = 1}^{D - 1} (y_{i} - 1)^{2} \cdot [1 + 10 {sin}^{2} (π y_{i + 1})] + (y_{D} - 1)^{2} \\ y_{i} = 1 + (x_{i} + 1) / 4 \end{matrix}} + \sum_{i = 1}^{D} u (x_{i}, 10, 100, 4)$	D = 30	[−50,50]³⁰	Min = 0
F23	$f_{23} (\vec{x}) = 0.1 {{sin}^{2} (3 π x_{1}) + \sum_{i = 1}^{D} \begin{matrix} (x_{i} - 1)^{2} \cdot [1 + {sin}^{2} (3 π x_{i} + 1)] \\ + (x_{D} - 1)^{2} \cdot [1 + {sin}^{2} (2 π x_{D})] \end{matrix}} + \sum_{i = 1}^{D} u (x_{i}, 5, 100, 4)$	D = 30	[−50,50]³⁰	Min = 0
u (x_i, a, k, m) ={ x_i < - a : k · (- x_i - a) ^m; - a < x_i < a : 0; x_i > a : k · (x_i - a) ^m }

4.2 Experiment

By setting specific terminal condition, variable-controlling approach (VCA) is able to indicate the accuracy, converge speed and multi-dimension process efficiency of the algorithm. This makes VCA be the main methodology for verifying the performance of optimization algorithm. Therefore, to compare the difference between the performances of the FPAs based on the three random walk models, this paper adopts a fixed iteration times and loss tolerance as the terminal condition, building two experiments respectively. In the first experiment, the iteration times is 500 and 5000, the corresponding dimension of test function are D = 2–6 and D = 30. The comparison results are shown in Table 3. In the second experiment, the loss tolerance e is 10-3, whose results show in Tables 4 and 5. Our hardware is a Lenovo laptop, with 2.90 GHz dual-core I5 CPU, 8GB memory, the software is Matlab 2012a under Windows 7. However, since the variation of experiment executor, optimization algorithm and the configuration of computers, the consumed time of the algorithm is not constant. Therefore, we use the average cost of time to do the comparison only.

Table 3
Comparison result of fixed-dimension functions

Function Strategy Best Mean STD Time/s

F1 Levy 0.998 0.999 4.34E-03 3.38

Gauss 0.998 0.998 1.05E-04 3.14

Cauchy 0.998 0.998 1.39E-03 2.82

F2 Levy 0.00033 0.00065 1.02E-04 1.82

Gauss 0.00034 0.00059 9.19E-05 1.41

Cauchy 0.00039 0.00060 9.03E-05 0.95

F3 Levy −1.0316 −1.0316 2.26E-09 1.62

Gauss −1.0316 −1.0316 7.40E-09 1.24

Cauchy −1.0316 −1.0316 9.44E-09 0.80

F4 Levy 0.398 0.398 1.26E-08 1.63

Gauss 0.398 0.398 5.75E-08 1.22

Cauchy 0.398 0.398 3.06E-08 0.80

F5 Levy 3.00 3.00 1.23E-06 1.61

Gauss 3.00 3.00 9.07E-08 1.21

Cauchy 3.00 3.00 2.23E-07 0.78

F6 Levy −3.863 −3.863 8.27E-07 1.90

Gauss −3.863 −3.863 1.04E-07 1.53

Cauchy −3.863 −3.863 1.87E-07 1.06

F7 Levy −3.322 −3.320 1.79E-03 1.96

Gauss −3.322 −3.321 7.49E-04 1.54

Cauchy −3.322 −3.320 1.09E-03 1.09

F8 Levy −10.1490 −10.0952 4.79E-02 2.17

Gauss −10.1523 −10.1425 9.38E-03 1.73

Cauchy −10.1519 −10.1261 2.37E-02 1.27

F9 Levy −10.3980 −10.3115 7.05E-02 2.18

Gauss −10.4022 −10.3795 2.35E-02 1.76

Cauchy −10.4001 −10.3575 4.59E-02 1.29

F10 Levy −10.5271 −10.3532 1.61E-01 2.29

Gauss −10.5324 −10.4786 5.24E-02 1.87

Cauchy −10.5299 −10.4244 1.08E-01 1.43

Function	Strategy	Best	Mean	STD	Time/s
F1	Levy	0.998	0.999	4.34E-03	3.38
	Gauss	0.998	0.998	1.05E-04	3.14
	Cauchy	0.998	0.998	1.39E-03	2.82
F2	Levy	0.00033	0.00065	1.02E-04	1.82
	Gauss	0.00034	0.00059	9.19E-05	1.41
	Cauchy	0.00039	0.00060	9.03E-05	0.95
F3	Levy	−1.0316	−1.0316	2.26E-09	1.62
	Gauss	−1.0316	−1.0316	7.40E-09	1.24
	Cauchy	−1.0316	−1.0316	9.44E-09	0.80
F4	Levy	0.398	0.398	1.26E-08	1.63
	Gauss	0.398	0.398	5.75E-08	1.22
	Cauchy	0.398	0.398	3.06E-08	0.80
F5	Levy	3.00	3.00	1.23E-06	1.61
	Gauss	3.00	3.00	9.07E-08	1.21
	Cauchy	3.00	3.00	2.23E-07	0.78
F6	Levy	−3.863	−3.863	8.27E-07	1.90
	Gauss	−3.863	−3.863	1.04E-07	1.53
	Cauchy	−3.863	−3.863	1.87E-07	1.06
F7	Levy	−3.322	−3.320	1.79E-03	1.96
	Gauss	−3.322	−3.321	7.49E-04	1.54
	Cauchy	−3.322	−3.320	1.09E-03	1.09
F8	Levy	−10.1490	−10.0952	4.79E-02	2.17
	Gauss	−10.1523	−10.1425	9.38E-03	1.73
	Cauchy	−10.1519	−10.1261	2.37E-02	1.27
F9	Levy	−10.3980	−10.3115	7.05E-02	2.18
	Gauss	−10.4022	−10.3795	2.35E-02	1.76
	Cauchy	−10.4001	−10.3575	4.59E-02	1.29
F10	Levy	−10.5271	−10.3532	1.61E-01	2.29
	Gauss	−10.5324	−10.4786	5.24E-02	1.87
	Cauchy	−10.5299	−10.4244	1.08E-01	1.43

Table 4

Comparison result of multi-dimension functions

Function	Strategy	Best	Mean	STD	Time/s
F11	Levy	3.86E-06	7.00E-05	5.65E-05	16.00
	Gauss	4.77E-06	7.81E-05	7.25E-05	11.50
	Cauchy	1.18E-02	4.15E-01	4.80E-01	7.09
F12	Levy	1.09E-02	2.79E-02	1.13E-02	14.01
	Gauss	9.38E-03	2.59E-02	1.33E-02	10.51
	Cauchy	6.61E-02	1.54E-01	6.44E-02	6.67
F13	Levy	3.91E-05	1.06E-03	2.88E-03	29.20
	Gauss	5.24E-06	2.42E-04	9.80E-04	24.42
	Cauchy	9.84E-04	1.51E-01	2.19E-01	19.93
F14	Levy	1.27	2.65	0.77	16.56
	Gauss	0.93	2.94	1.03	12.16
	Cauchy	2.66	4.96	1.27	7.80
F15	Levy	14.32	24.43	2.79	17.47
	Gauss	5.79	24.16	4.40	12.98
	Cauchy	12.94	57.25	46.35	8.65
F16	Levy	8.03E-06	6.34E-05	6.38E-05	16.86
	Gauss	4.11E-06	7.89E-05	9.97E-05	12.40
Cauchy		3.78E-02	4.11E-01	3.59E-01	8.00
F17	Levy	7.41E-03	1.89E-02	7.23E-03	18.46
	Gauss	6.27E-03	1.92E-02	6.01E-03	14.06
	Cauchy	4.71E-03	2.82E-02	1.17E-02	9.72
F18	Levy	−10427.32	−9806.47	247.30	20.27
	Gauss	−9660.60	−8939.64	323.03	15.68
	Cauchy	−10016.00	−9090.13	397.68	10.84
F19	Levy	41.06	63.00	7.58	20.39
	Gauss	55.38	95.85	23.77	15.28
	Cauchy	48.74	97.53	22.22	10.46
F20	Levy	0.28	2.30	0.66	21.09
	Gauss	1.30	3.02	0.75	15.87
	Cauchy	1.38	3.31	0.98	10.88
F21	Levy	1.65E-04	4.64E-03	4.26E-03	21.64
	Gauss	1.47E-04	9.86E-03	8.95E-03	16.42
	Cauchy	1.08E-01	3.68E-01	1.62E-01	11.53
F22	Levy	1.50E-04	9.44E-02	1.70E-01	27.15
	Gauss	2.30E-04	3.81E-01	5.18E-01	22.26
	Cauchy	1.80E-02	1.25E+00	7.24E-01	17.49
F23	Levy	6.45E-04	1.72E-02	3.17E-02	26.30
	Gauss	1.98E-04	7.41E-01	1.10E+00	21.42
	Cauchy	4.03E-01	6.28E+00	3.97E+00	16.64

Table 5

Comparison result of partial benchmark functions

Function	Strategy	Parameter	D = 5	D = 10	D = 15	D = 20	D = 25	D = 30	D = 40
F11	Lévy	Iterations	725.45	1447.70	2065.45	2675.90	3336.10	4207.05	4878.85
	Time/s	2.33	3.79	6.27	8.45	11.09	14.61	17.86
	Gauss	Iterations	638.05	1248.05	1809.00	2376.05	3153.05	4116.55	5130.50
		Time/s	1.49	2.43	4.00	5.44	7.53	10.10	13.04
		Cauchy	Iterations	665.95	1199.75	1665.40	2807.85	5721.20	8773.20	11383.45
		Time/s	0.97	1.41	2.30	4.01	8.48	13.23	17.42
F13	Lévy	Iterations	673.00	1397.75	2138.35	2780.30	3580.85	4713.75	6977.80
		Time/s	2.25	5.31	9.15	13.48	19.08	28.30	32.87
		Gauss	Iterations	565.40	1173.65	1795.20	2392.00	3145.10	4200.90	6220.25
		Time/s	1.43	3.52	6.19	9.51	13.91	21.45	25.44
		Cauchy	Iterations	613.90	1116.50	1543.55	2134.15	3682.95	7457.05	10295
		Time/s	1.03	2.41	4.00	6.59	12.96	30.61	66.65
F22	Lévy	Iterations	1044.20	2458.25	3532.15	4468.70	5276.60	6376.05	7235
		Time/s	4.64	7.71	11.70	22.91	18.25	24.33	47.73
	Gauss	Iterations	948.05	2422.00	3550.15	4601.40	6636.00	6983.50	7523
		Time/s	3.35	6.45	9.89	18.29	19.20	25.10	52.92
	Cauchy	Iterations	994.75	2615.65	4410.95	5732.10	8009.75	9783	12154
		Time/s	2.61	5.62	10.07	17.23	19.31	28.67	57.50
F23	Lévy	Iterations	287.40	706.45	1059.70	1509.65	2704.45	4391.94	6212
		Time/s	0.90	2.23	3.51	5.12	9.90	16.45	40.67
	Gauss	Iterations	287.05	687.15	1056.50	1939.70	3383.65	6975.00	9318
		Time/s	0.78	1.91	3.10	6.01	12.19	23.65	50.69
	Cauchy	Iterations	279.05	674.10	1011.95	1705.50	4991.15	8366.00	14893
		Time/s	0.67	1.64	2.59	4.57	14.24	24.79	58.04

At last, to explore the convergence property of the three random walk models, Fig. 4 shows the searching-path and converge curve of the first particle of certain test functions in the 1D space. The first column of Fig. 4 is the 3D visualization of the optimization process, showing the complexity of the test function. The second column is the searching-path of the first particle, showing the random variation of the step. The third and fourth columns of the figure illustrate the convergence curves of single and all particles, indicating the speed of the convergence. Though these four result, one can easily tell how difficult these algorithms are, and how good the optimizing capacity of the three random walk models is.

Fig. 4

Trajectory of the first agent in 1st dimension and Convergence curves.

4.3 Result and analysis

Experiment 1: From Table 3, we can analyze the optimizing capacity of these three random walk models with the same iteration times, when dealing with fixed-dimensional search problem.

Firstly, FPA can find the global optimization of fixed-dimensional multi-modal test function under all the three random walk models. Meanwhile, there is no obvious difference between the optimal value, mean and standard deviation. Then, from the average time of these algorithms cost, we can see the Cauchy random has a faster searching progress compared to other two models. That means Cauchy outperforms the rest models over the fixed-dimensional multi-modal optimization in terms of speed. The conclusion is also verified in Fig. 4 by the global convergence curve of F1, F3, and F5. At last, when dealing with low-dimensional test function, the optimal value, mean, standard deviation from Cauchy random based FPA can be found within the shortest time, compared to the other two models.

Experiment 2: From Table 4, we can analyze the optimizing capacity of these three random walk models with the same loss tolerance constraint, when dealing with multi-dimensional search problem. Overall, Levy and Gaussian random walk models have better performance than Cauchy in terms of multi-dimensional unimodal and multi-modal problem, except the efficiency. Then, we can learn from the converge curve of F11, F13, F22, F23 in Fig. 4 and the experiment data in Table 4 that Levy and Gaussian SSM have the similar converge speed and accuracy, which are way better than Cauchy. To compare the performance of the three models over the multi-dimensional unimodal, multi-dimensional multi-modal search problem, we compare the iteration times and average searching time of F11, F13, F22, F23 (F11, F13 are unimodal, F22, F23 are multi-modal) in Table 5. From this table, when the dimension is under 30, Cauchy SSM has the fast searching time. However, when the dimension is larger than 30, there is a huge increase of the time. On the contrast, Gaussian SSM has a short searching time when dealing with the unimodal searching problem whose dimension is above 30. And Levy is the best solution for the high-dimensional multi-modal searching problem.

Through the analysis of experiment 1 and 2, we have the following three conclusions of FPA with three different random walk models.

Cauchy random based FPA can achieve the global optimal solution in the fast speed over low-dimensional test function.

Gaussian random based FPA can achieve the best balance between accuracy and time over multi-dimensional unimodal test function.

Levy random based FPA is the best strategy for the multi-dimensional unimodal test function.

5 Conclusion

As an important meta-heuristic searching algorithm proposed in recent years, FPA shows a great capability for fast global searching relies on the random walk model validates the important role of stochastic mechanisms in meta-heuristic algorithms for solving complex optimization problems. In this paper, the impact of meta-heuristic algorithms with different random walk models on global search capabilities is well studied. Through the analysis of the motion characteristics of different random walk models in two-dimensional search space and the numerical simulation of 23 benchmark functions based on the modified FPA with different random walk models, there are three main conclusions can be given. Cauchy random can achieve the global optimal solution in the fast speed over low-dimensional test function. Gaussian random can achieve the best balance between accuracy and time over multi-dimensional unimodal test function. Levy random is the best strategy for the multi-dimensional unimodal test function. These results will contribute to the optimization design of the intelligent algorithm, and also provide a new idea for exploring the randomness mechanism of the algorithm.

Future research will mainly focus on the analysis of diversity and variability of populations in meta-heuristic algorithms since these results will help to further explore the impact of algorithmic stochastic mechanisms on global optimization performance. Other optimization strategies such as Orthogonal Learning Strategies and Rotation Learning Strategies will also be considered for improvement and optimization of algorithms.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 71601183.

References

Viswanathan

G.M.

, Afanasyev

, Buldyrev

S.V.

et al., Lévy flight search patterns of wanderingalbatrosses[J], Nature381(6581) (1996), 413–415.

Viswanathan

G.M.

, Buldyrev

S.V.

, Havlin

et al., Optimizing the success of random searches[J], Nature401(6756) (1999), 911–914.

Turchin

Quantitative Analysis of Movement: Measuring and Modeling Population Redistribution in Animals and Plants, Sinauer, Sunderland, Massachusetts, 1998.

Shlesinger

M.F.

Search research, Nature443 (2006), 281–282.

Bardou

, Bouchaud

J.-P.

, Aspect

, Cohen-Tannoudji

Levy Statistics and Laser Cooling: How Rare Events Bring Atoms to Rest, Cambridge Univ. Press Cambridge, 2002.

Bartumeus

, Peters

, Pueyo

, Marrasé

, Catalan

Helical Levy walks: Adjusting searchingstatistics to resource availability in microzooplankton, Proc Natl Acad Sci USA100 (2003), 12771–12775.

Klafter

, Sokolov

I.M.

Anomalous diffusion spreads its wings, Phys World18 (2005), 29–32.

Barthelemy

, Bertolotti

, Wiersma

D.S.

A Lévy flight for light[J], Nature453(7194) (2008), 495–498.

Yang

X.S.

Cuckoo Search[M]// Nature-Inspired Optimization Algorithms, 2014.

10.

Yang

X.S.

, Deb

Cuckoo search via levy flights[J], Mathematics (2010), 210–214.

11.

, Ying

Improved particle swarm optimization based on lévy flights[J], Journal of SystemSimulation (2017).

12.

Yang

X.S.

Flower pollination algorithm for global optimization[C], International Conference on Unconventional Computation and Natural Computation, Springer-Verlag (2012), pp. 240–249.

13.

Heidari

A.A.

, Pahlavani

An efficient modified grey wolf optimizer with Lévy flight for optimizationtasks[J], Applied Soft Computing60 (2017), 115–134.

14.

Aydogdu

, Çarbaş

and Akin

, Effect of Levy Flight on the discrete optimum design of steel skeletal structures using metaheuristics[J], Steel & Composite Structures24(1) (2017), 93–112.

15.

Vallaeys

, Tyson

R.C.

, Lane

W.D.

et al., A Lévy-flight diffusion model to predict transgenic pollendispersal[J], Journal of the Royal Society Interface14(126) (2017), 20160889.

16.

Zhao

, Aranha

, Kanoh

Solving facility layout problems using evolutionary strategy based on levy flight[C], IEEE, International Workshop on Computational Intelligence and Applications IEEE (2017), pp. 39–44.

17.

Bai

Z.W.

, Hu

Escape of an inertial Lévy flight particle from a truncated quartic potential well[J], Physica A Statistical Mechanics & Its Applications479 (2017), 91–98.

18.

Shatnawi

Data clustering using levy flight and local memory bees algorithm[J], International Journal of Business Intelligence & Data Mining12(1) (2017), 1.

19.

Liu

, Cao

Improving Ant Colony Optimization algorithm with Levy Flight[C], MISTA 2017 Conference, 2017.

20.

Pantaleo

, Facchi

, Pascazio

Simulations of Lévy flights[J], Physica Scripta2009(T135) (2009), 014036.

21.

Yang

X.S.

Test problems in optimization[J], Mathematics2010(2), 63–86.

22.

Mirjalili

, Lewis

S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization[J], Swarm & Evolutionary Computation9 (2013), 1–14.

23.

Mirjalili

, Mirjalili

S.M.

, Yang

X.S.

Binary bat algorithm[J], Neural Computing and Applications25(3) (2014), 663–681.

24.

Mirjalili

, Lewis

The whale optimization algorithm [J], Advances in Engineering Software95 (2016), 51–67.