Exploiting flower constancy in flower pollination algorithm: improved biotic flower pollination algorithm and its experimental evaluation

Nature-inspired metaheuristics constitute an important element of Computational Intelligence revolution, due to their high performance and reasonable quality of obtained results. Recent years brought intensive growth of this field. A variety of new methods have been introduced, which—while being criticized for lack of methodological novelty and relying only on attractive metaphors [30]—were often demonstrated to perform very well for benchmark optimization problems. The inspiration for these algorithms typically comes from one of four types of natural phenomena: evolution, swarm behavior, physical processes or human activity. Common example of the first class is the Genetic Algorithm [29]; however, more recent Differential Evolution technique [31] can also be named in this context. Swarming behaviors exhibited by a variety of living organisms serve as a foundation for a large number of techniques such as: Grey Wolf Optimizer [19], Grasshopper Optimization Algorithm [25], Krill Herd Algorithm [12] or standard Particle Swarm Optimization [9] to name just a few. As typical representatives of the third class—techniques inspired by physical processes—along the most commonly known Simulated Annealing algorithm [15] more recent methods of Gravitational Search Algorithm [23] or Sine Cosine Algorithm [18] can be presented. Finally, analyzing human behavior and activities lead to the creation of, inter alia, Fireworks Algorithm [32] and Brainstorming [27]. For a more extensive overview of nature-inspired optimization algorithms, one could refer to a recent extensive survey [11].

The natural phenomena, which became the core of algorithm presented in this paper, is one of the flower pollination processes, more accurately—the flower constancy mechanism. Flower constancy [8] allows the insects, which are able to carry a pollen (e.g., honey bees), to remember the paths between best-known pollen sources. The original optimization technique based on flower pollination, called Flower Pollination Algorithm (FPA), comes from 2012 and has been introduced by Yang [37]. This algorithm imitated two different variants of flower pollination and classified them into local pollination—where all actions occurred locally, and global pollination—where the pollen was moved to partly random, often distant location [20]. With more insightful approach, local pollination could be compared to flower constancy, being responsible for pollen carriers attraction to advantageous flower types, which were positively scrutinized in the past. Thus, local pollination imitated carriers communication and tendency to remain at lucrative habits. In practice, conjunction of this mechanism and randomized global pollination led to creation of interesting optimization method, which quickly explores the given function landscape to get to its optimal domain, simultaneously preventing the algorithm from getting stuck in local extremes. Since the foundation of the original FPA, many researchers have studied it with different results [1, 17, 34], and also modified standard algorithm’s structure [26, 28], but the basic idea behind FPA has remained unchanged. The goal of this article is to present improved and simplified FPA version, which has been created to increase algorithm performance, and to reduce computational cost and total time of algorithm’s execution. It is not a new swarm intelligence technique but a modification of the existing algorithm inspired by experimental studies on its behavior. This work is motivated by the fact that in the most recent comparative experimental studies [2, 4], the FPA proved to be highly competitive—even in reference to the more recent algorithms. It has also been successfully adopted in many engineering and scientific applications [21].

This paper is constructed as follows. Firstly, the natural process of pollination—which has become an archetype of the algorithm—is described. Then, the structure of the algorithm itself, as well as the changes introduced by authors of this paper are presented. Subsequently, the performance of modified algorithm with regard to other known algorithms (PSO, original FPA, slightly modified FPA with improved random factor—LEFPA [28] and Symbiotic Organism Search (SOS) [7]) is demonstrated. It is followed by use-case example of application of the proposed algorithm. Finally, further possible improvements are communicated.

Plant pollination in nature can occur as a consequence of several different mechanisms. First of these is self-pollination, where the pollen comes from the same flower or different flower of the same plant. In contrast to that, cross-pollination takes place when the pollen comes from different plant [14]. In original FPA, inspired by pollination, all flowers were assumed to be of the same type [37], so all events could be classified into self-pollination category.

Another classification type divides pollination processes into two groups, biotic and abiotic. Biotic pollination occurs while insects, also called pollinators, carry pollen between consecutive flowers. Abiotic pollination in turn is done through the presence of independent and random factors like wind or water. It was established through biological research that over \(80\%\) of all pollinations occurring in nature are in fact biotic [3]. Abiotic pollination can be considered as the one introducing more randomness to the process of pollen transfer and, as we suggest later, this behavior could be neglected in building algorithm structure.

The algorithm inspired by pollination introduces third categorization of pollination process—based on its range: local or global. It is worth to mention that original FPA employs both of them. The first—local pollination theoretically could be considered as either biotic or abiotic, because the flowers are in this case located close to each other. It means that both natural factors such as wind and pollinator activities could be perceived as of significant importance. Still local pollination used in the original FPA technique was limited to be only biotic and represents the flower constancy, mentioned in the previous section. It is based on random walks between flowers. Global pollination, which is a second part of the algorithm, is the long-distance pollination. In this case, FPA focuses mainly on abiotic pollination as successful long-range wind pollination can also be observed in Nature, e.g., for open areas where pollen can be carried far without any obstruction. In FPA, the trajectories of pollen displacement are in this case being rolled using Levy distribution [22]. Angular part of Levy distribution is symmetric; thus, direction of displacement must be simultaneously rolled from uniform distribution. It means that simulation of abiotic global pollination modeled by FPA brings more randomness and unpredictability to the pollination process.

Optimization deployment of described processes is based on locating flowers on functional landscape. The function value reflecting flower position determines the amount of pollen produced by this flower. Detailed description of algorithms based on aforementioned natural processes is provided in the following sections.

The population in Flower Pollination Algorithm consists of N flowers of the same type. Each flower is denoted a vector \(x_n,\; n=1, \ldots , N\) and represents exactly one solution in the domain of tested function f. The goal of the optimization is to find a value of \(x_n\)—within the feasible search space \(S\subset R^D\)—denoted as \(x^*\) such as \(x^*=\hbox {argmin}_{x\in S} \,f(x)\), assuming that the goal is to minimize cost function f. Population in FPA is at first initialized randomly. After initialization, in every step of algorithm’s main iteration k, all flowers in sequence are selected to be pollinated. It is controlled by parameter p, named as switch probability, which determines the probability of global pollination. If a flower is chosen not to be pollinated this way, a local pollination is executed instead. The whole process is repeated iteratively until predetermined termination criterion is found to be fulfilled.

Let us denote \(x_n(k)\) as solution n in iteration k, \(x^*(k)\)—as the best solution found so far and \(s_0, \gamma\) as global pollination parameters. Furthermore, let \(x_{n,\mathrm{trial}}\) to represent a new candidate solution obtained through the pollination phase. It becomes a new location of solution n if its quality—in terms of cost function f—is better than the quality of the original one. Algorithm 1 provides the description of pollination process in FPA using this notation.

Flower Pollination Algorithm as an effective optimizer found variety of modifications—enhancing its capabilities and improving performance. Besides, more specific FPA variants for combinatorial [33] and binary optimization [10] more generic changes—related to the structure of the algorithm have been proposed [26]. It includes newly introduced Linear–Exponential Flower Pollination Algorithm [28] based on customized switching of probability p. In addition to that adding a chaotic component in a form of chaotic maps [13] was also considered—it is one of the popular approaches used recently in heuristic optimization. An improvement in new mutation operators and modified local search was also under investigation [24]. A list of modifications also includes new population initialization methods [36]. For a more extensive overview of changes proposed for the standard FPA, one could refer to recent state-of-art reviews [5, 21].

As already demonstrated in original FPA, the probability of local and global pollination for single flower is defined by the probability factor p, for which the optimal value of 0.8 was suggested, according to the contributions of algorithm’s developer Yang [37] and other sources [17]. However, our intensive experimentation exhibited that in most cases FPA produces the best results while the value of p drifts to 0—in other words, when the system tends to eliminate completely the global pollination process. As it was presented in Sect. 2, random walks have the strict nature of randomness that interferes the methodical, intuitive behavior of pollinators. Removing global pollination process also simplifies the scheme of FPA, because rolling random numbers from Levy distribution (which has the infinite variance) might be problematic and it slightly extends the algorithm execution time. In addition to that, in this way an elimination of two algorithm’s parameters: \(s_0\) and \(\gamma\) is achieved. Computational cost of algorithm remains at O(k, N), where k is iteration number, N is the size of flower population. By removing global pollination and forcing the flowers to only pollinate by flower constancy mechanism, simplified variant of FPA is created, which can be naturally called Biotic Flower Pollination Algorithm (BFPA). The complete structure of BFPA is presented as Algorithm 2.

Another modification taken into consideration was the factor of local pollination \(\epsilon\). Adding the sign of its value does not change the structure of the algorithm—and at the same time, it causes the pollination steps to be extended. In practice, modifying \(\epsilon\) value heavily influences received results, and it can be helpful if we want to obtain the best possible solution for given problem. Through our experimentation—selection of which will be enclosed in subsequent part of the paper—we established that as the best universal value C equal to 1 can be used.

The results of BFPA optimization performed on benchmark continuous problems, with regard to other exemplary and indicative algorithms are presented in the next section.

The source of all benchmark functions used in performance tests was the CEC17 Special Session and Competition on Single Objective Real-Parameter Numerical Optimization [6]. It contains a variety of different black-box continuous benchmark problems. A short summary of full suite is presented in Table 1, and its detailed specification can be found in [6]. First nine functions are shifted and rotated common and well-known optimization problems, from the simplest with only one local minimum, e.g., Bent Cigar function (F1), to more complex with extremely high number of local minima, e.g., Schaffer function (F6). Functions of number 10–20 are hybrids, that are the linear combination of several basic functions (mostly of these already used in a basic set F1–F9). The last 10 functions are compositions, that in turn represent couplings between several previous functions in different frames of optimization domain.

All functions are assumed to be 10-dimensional and stretched on domain \(S \in [-\,100,100]^{10}\). During performance tests, we assumed that number of evaluation of single function is limited to 100,000, as the CEC17 competition rules prescribe. This pool was divided into 2850 iterations of the main algorithm loop and the population of 35 agents. It is equivalent to 99750 evaluations of a specific black-box problem, which is within the limits of competition rules.

As the alternative optimization algorithms—used to evaluate the performance of BFPA—besides FPA (with \(p=0.8\)), standard Particle Swarm Optimization, state-of-art FPA variant—linear–exponential Flower Pollination Algorithm (LEFPA), and Symbiotic Organism Search (SOS) were used. For PSO, as the C1 and C2 parameters typical values of \(C1=C2=2\) were employed [9]. For LEFPA \(p_\mathrm{initial}\) and \(p_\mathrm{final}\) inner parameters, values 0.8 and 0.6 were used, respectively, as the creators of LEFPA recommend [28]. SOS algorithm used in our experiments employ default settings as described in [7].

For every benchmark problem, all algorithms were run 60 times and the average of optimization error, as well as its standard deviation and the best result from 60 consecutive runs were noted and are presented in Table 2. As an optimization error, the difference between final result and known global minimum value was chosen. To compare results, t Student Test for different variances, also known as Welch Test [35], was used. Resulting value from Welch Test is p value, which represents probability of null hypothesis that expected values of two populations are equal. If p value is low, null hypothesis is rejected and both expected values; thus, both populations are considered as statistically different. Adoption of 0.95 confidence interval determines p value needs to be lower than 0.05 to recognize the results of two algorithms as different. After calculating p value for all cases, for majority of benchmark functions, we can state—even with probability 0.9999—that BFPA method gives significantly better results than other tested algorithms, which is shown in Table 3. It is worth to observe as well that the advantage of the proposed algorithm exhibits on all types of functions, their hybrids and compositions. Above all, for hybrid functions, BFPA was significantly better than any other variant of FPA for all considered benchmark instances. In addition to that, it was observed that FPA execution time was on average 20% longer than running time of BFPA.

In order to investigate algorithms’ dynamics, the best minimum values found so far for all iterations were noted. Sample of 200 independent runs with the same initial population and random number generator seed for all algorithms were arranged, to avoid the effect of randomization. The average best solution of gradient comparison for all examined algorithms, calculated for F8 function, are presented in Fig. 1. Both FPA and LEFPA, which is FPA with improved global pollination process, acted similarly, with LEFPA converging a bit faster. SOS provided better results and was the leading algorithm over first 1000 iterations, however eventually was overtaken by PSO and BFPA. PSO algorithm most of times terminated reaching the actual position of global minimum. Finally, BFPA tended to global minimum quicker and more regularly, discovering desirable global minimum position every time. This result signifies that even though BFPA reduces random decisions during simulation, population does not remain in a local minima and always looks for the better position. This is most likely caused by removing usage of current best-known position in algorithm structure—that surprisingly often pulls the population into a local minimum trap. Similar experiments executed for selected CEC17 optimization problems with \(D=30\) demonstrated that this positive feature is also observed for search spaces of higher dimensionality.

The differences between FPA and its modified version BFPA might be seen in diversity plots, presenting the average distance between solutions during optimization process for both FPA and BFPA in Fig. 2. The random walk contribution in FPA manifests in the form of the distance fluctuations. In the BFPA case, the exploration process is shortened and algorithm steps into desired area very quickly, continuing the exploitation phase with a linear decrease of the average distance between population agents. FPA keeps large distances between solutions over all iterations, which is the main reason of its worse exploitation abilities.

In order to examine the impact of the algorithm’s parameters on the optimizing performance, a number of different parameters set were chosen and examined in the same way as for the comparison of the algorithms, with 6 selected functions. All the results are collated in Table 4. The first three sets of parameters we have considered include different values taken for C—the gain of local pollination step—the middle, proposed value of \(C=1\) and two marginal of \(C=0.5\) and \(C=1.5\). At the same time, the population was fixed to \(N=35\). The results of this test are included in columns 3, 5 and 7 of the Table. The suggested value of \(C=1\) gave the best result in 3 out of the other 6 cases; however, it was also the second best in the other 3 cases.

Another performance variability test concerned studying the effect of different number of flowers in the population with fixed value of C. A population lower than 18 flowers showed a tendency to stuck in one place, with an identical location vector. Since the full function suite was run for a population of 35 flowers, versions with 25 flowers and 50 flowers were added to the performance test, the results of which are also presented in Table 4. Once again, the proposed value of 35 flowers for 100, 000 function evaluations gave the best results, however the differences were not as significant, as for the different values of C provided. The most suitable number of flowers also depends on the dimensionality of a given problem. The C parameter, however, is independent of the number of dimensions, and if the initial population is randomly deployed over the function landscape, again its value of \(C=1\) may be safely assumed.

BFPA’s simplicity allows it to be implemented in a wide range of applications. One of the functionalities we have already developed is fitting function models to the data, which follows combination of analytically defined distributions. If the function model consists of a huge number of independent variables, this task becomes impossible to complete swiftly through standard fitting techniques. Usage of BFPA is based on employing an objective function defined as of Mean Square Error (MSE) between data and current function fit, designated by a temporary set of model parameters of the best flower position vector. The algorithm minimizes objective function in relation to model parameters. These parameters are contingent on the model and might be simple, e.g., when fitting a Gaussian distribution or more complex when a mixture of different distributions is considered. The nature of MSE cost function, due to its high complexity and difference in contribution of parameters, can be compared to composition functions that were part of CEC performance test. This means that fitting a function model to data points is often difficult and the global optimum cannot always be found. Nonetheless, it is a common task in data analysis and developing an algorithm which is simple and understandable is highly desirable.

As an example of application, fit to the model M(x) consisting of two independent Landau–Gauss distributions is presented (1):where \((G \,\circledast\, L)(x)\) is a convolution of Gauss and Landau distribution (2):and G(x) and L(x) are (3), (4):The Landau–Gauss convolution is then given by (5):and \(O(\xi )\) is the numeric error of calculating a double improper integral within Landau–Gauss distribution, which is dependent on integrating technique and has a random character.

Since Landau distribution describes energy loss of the charged particle in a material, this model is often used in many fields of technology, starting with electronics, where it describes the energy loss of ionizing particles in silicon, ending with nuclear and high-energy physics, where particles with high momentum cross the detector material and lose energy. Convolution with Gauss distribution is not necessary when only energy loss prediction is the subject of consideration, yet it is essential if deposited energy is measured in non-zero time. To make the optimization task more challenging, another Landau–Gauss distribution was added to the model. As consequence of double improper integral in Landau–Gauss distribution, calculation cost of each function evaluation is significant. Hence, number of cost function evaluations should be as low as possible to avoid a long lasting optimization process. In the proposed model, the following parameters take part in optimization:for each of Landau–Gauss distribution; thus, in summary we have 8 parameters that lead to 8 argument MSE-based cost functions.

The BFPA algorithm achieved a final result after an average of 422 iterations. The original FPA has also been tested and it needed more than 750 iterations; however, the final result was identical in both attempts. The result of the model fitting using BFPA was demonstrated in Fig. 3.

The proposed modified variant of the Flower Pollination Algorithm has exhibited excellent results in the course of the experimental test procedure covered in previous sections, with both high-quality results and a decent time of execution being identified. BFPA proved to perform much better than the original FPA, which itself is a highly effective optimization technique. In addition to that, Biotic Flower Pollination Algorithm is not complicated in structure and consists of only one non-iterational equation, which leads to its easy and fast implementation in every programming environment. In conclusion, the BFPA performance allows this technique to be used both for simple tasks as well as in more complicated optimization projects. To allow the replication of our result, the code of BFPA along with the short example of its usage was published on [16].

Since it has been observed that BFPA usually quickly finds the right region where the global minimum is located and most of the time looks for the most attractive point, further research concerning the BFPA’s structure with special emphasis on exploitation process reinforcement, should be performed. It is also worth mentioning that obliteration of Levy flights in the BFPA excluded from the algorithm the best global solution found so far, which is quite often used in strengthening the exploitation process and its inclusion to BFPA in alternative way might also be the theme of future studies.