Flower Pollination Algorithm for Global Optimization – Xin-She Yang 2013

The last of the optimisation algorithms we’ll look at for now, today’s paper is the most recent (2013) and also by Xin-She Yang. Once more, we only get comparisons to genetic algorithms and PSO, and once more the comparison is favourable.

In many design applications in engineering and industry, we have to try to find the optimal solution to a given problem under highly complex constraints. Such constrained optimization problems are often highly nonlinear, to find the optimal solutions is often a very challenging task if it is not impossible. Most conventional optimization do not work well for problems with nonlinearity and multimodality. (The) current trend is to use nature-inspired metaheuristic algorithms to tackle such difficult problems, and it has been shown that metaheuristics are surprisingly very efficient. For this reason, the literature of metaheuristics has expanded tremendously in the last two decades. Up to now, researchers have only used a very limited characteristics inspired by nature, and there is room for more algorithm development.

Flower pollination can be viewed as a ‘survival of the fittest’ optimization process for plant species. Pollination can be abiotic or biotic. 90% of all plants use biotic pollination, in which pollen is transferred by pollinators such as insects and other animals. The other 10% use abiotic pollination which uses mechanisms such as wind and water to transfer pollen. Flower constancy is the tendency of certain pollinators to exclusively visit certain flowering plant species.

Such flower constancy may have evolutionary advantages because this will maximize the transfer of flower pollen to the same or conspecific plants, and thus maximizing the reproduction of the same flower species.

Pollination can be via cross-pollination or self-pollination. Cross-pollination is the transfer of pollen from a different plant, whereas self-pollination is the transfer of pollen from a flower of the same plant. Biotic cross-pollination (transfer of pollen across different plants by insects and other animals) can occur at a long distance, and thus can be considered as global pollination.

In addition, bees and birds may behave as Lévy flight behaviour, with jump or fly distance steps obeying a Lévy distribution. Furthermore, flower constancy can be used an increment step using the similarity or difference of two flowers.

The two key steps in the Flower Pollination Algorithm represent global pollination (biotic cross-pollination) and local pollination (abiotic and self-pollination). Which of the two pollination processes is used on a particular iteration for a particular flower is controlled by a probability p.

Due to the physical proximity and other factors such as wind, local pollination can have a significant fraction p in the overall pollination activities.

For simplicity, it is assumed that each plant has a single flower, and each flower produces only one pollen gamete. Thus plant, flower, pollen gamete, and problem solution are all identified with each other.

Global pollination is modelled by the following process:

x_i^t+1 = x_i^t + L(x_i^t – g_best)

x_i^t is the pollen i or solution vector x_i at iteration t. g_best is the globally best solution. The parameter L is a step size, and is drawn from a Lévy distribution as we saw with the Cuckoo Search algorithm. This models insects moving over a long distance with various distance steps.

Local pollination is represented by:

x_i^t+1 = x_i^t + ε(x_j^t – x_k^t)

where x_j^t and x_k^t represent pollens from different flowers of the same plant species. This becomes a local random walk if we draw ε from [0,1].

The whole algorithm comes together as follows:

• Initialize a population with random solutions
• For each iteration, for each flower in the population:
  • Draw a random variable rand in [0,1]
  • If rand < p, then perform global pollination
  • Else perform local pollination with j and k chosen randomly from among all solutions
  • Evaluate the new solutions, and if they are better update the population
• The winner is the global best solution at the end of the prescribed number of iterations

p = 0.8 was found to work well in simulations.

Our simulation results have shown that the the proposed flower pollination algorithm is very efficient and can outperform both genetic algorithm and particle swarm optimization. The convergence rate is essentially exponential as we have seen from the convergence comparison in the previous section. The reasons that FPA is efficient can be twofold: long-distance pollinators and flower consistency. Pollinators such as insects can travel long distances, and thus they introduce the ability (into the algorithm) that they can escape any local landscape and subsequently explore a larger search space. This acts as exploration moves. On the other hand, flower consistency ensures that the same species of the flowers (thus similar solutions) are chosen more frequently and thus guarantee convergence more quickly. This step is essentially an exploitation step. The interplay and interaction of these key components and the selection of the best solution g_best ensures that the algorithm is very efficient.