Flower Pollination
Algorithm
The Flower Pollination Algorithm (FPA) is a nature-inspired
metaheuristic optimization algorithm. Inspired by the pollination
process of flowering plants, FPA simulates the movement of pollen
grains to find optimal solutions to complex problems.
by 21bcs094
21bcs103
Key Concepts of the
Flower Pollination
Algorithm
1 Pollination 2 Flower Population
The transfer of pollen A set of potential
from the anther of a solutions represented by
flower to the stigma of flowers in the algorithm.
the same or another
flower.
3 Global Pollination 4 Local Pollination
Simulates the long- Represents the local
distance movement of search around a flower,
pollen grains, exploring refining the solution in
the search space broadly. the neighborhood.
The FPA is inspired by two main types of pollination
processes observed in nature:
Biotic Pollination (Cross-Pollination):
This involves pollinators (such as insects) carrying pollen
from one flower to another. In optimization terms, this
resembles global search, where solutions can jump to new
regions in the search space.
Abiotic Pollination (Self-Pollination):
This is a local pollination process where pollen is
transferred within the same flower or plant. This
resembles a local search, where solutions are refined
locally within the current region.
The algorithm also incorporates Levy Flights, a mathematical model that captures
the movement patterns of pollinators as they explore various flowers. Levy flights
help model long-distance movements, supporting global search and helping the
algorithm escape local optima.
Types of Pollination in FPA
Global Pollination Local Pollination
Global pollination is inspired by biotic pollination, where Local pollination is modeled as abiotic, where pollination
pollen is transferred over longer distances by external occurs within the same plant or nearby plants.
pollinators (e.g., bees, birds).
In FPA, local pollination mimics local refinement, with each
In FPA, global pollination is represented mathematically flower being updated based on the positions of its
using Levy flights, allowing the algorithm to explore distant neighboring flowers.
areas of the solution space.
During local pollination, the update formula is
During global pollination, each solution Xi is updated as
follows
Switching Probability (p)
Switching Probability
The FPA includes a switching probability p to determine whether a
solution should undergo global or local pollination at each iteration. The value
of p is typically set between 0.1 and 0.3, balancing between exploration
(global search) and exploitation (local search).
Global Search
Higher p values favor global search, exploring diverse
regions of the search space.
Local Search
Lower p values focus on local search, refining
solutions within a neighborhood.
Algorithm
Initialization of Flower
Pollen Populations
1 Random Initialization
Flowers are randomly distributed within the search
space, creating a diverse initial population.
2 Heuristic Initialization
Flowers are initialized based on domain knowledge
or previous solutions, providing a good starting
point.
Global Pollination Step
Step 1 Randomly select a flower.
Step 2 Generate a new flower by
adding a random vector to
the selected flower.
Step 3 Update the flower population
with the new flower.
Local Pollination Step
Local Search Cross-Pollination
Refines the current flower by Combines genetic material from
exploring its neighborhood. neighboring flowers to generate
new solutions.
Mathematical Problem
Formulation
FPA can be used to solve a wide range of mathematical
optimization problems.
The problem is formulated as a function to be minimized or maximized.
Consider the following simple minimization problem:
Minimize:
f(x) = x2
Subject to:
−10 ≤ x ≤10
Step-by-Step Calculations
and Solution
Let's take an example of minimizing a function using FPA.
The steps involve initializing the flower population, applying global and
local pollination, and iteratively updating the solutions until
convergence.
Parameters for FPA
To simplify, we'll use a small population size and a low number of iterations:
•Population size (n): 3
•Maximum iterations (MaxIter): 5
•Switch probability (p): 0.5 (so there’s a 50% chance of performing global pollination)
•Step size (γ): 0.1
Step 1: Initialization
[Link] initialize 3 values for x within the interval [−10,10].
1. Let's say our initial population is
x1= −8, x2 = 5, x3 = −3
[Link] the fitness f(x) for each initial solution:
f(x1) = (−8)2 = 64, f(x2)= (5)2 = 25, f(x3) = (−3)2 = 9
[Link] the best solution g* in the initial population:
The best solution so far is x3 = −3 with f(g* ) = 9
Step-by-Step Calculations
and Solution
Step 2:Iteration 1
For each iteration, apply either global pollination or local pollination based on the switch
probability p=0.5
For x1 : Global Pollination (randomly chosen based on p):
x1new = x1 + γ × L(x1 −g∗ )
Assume L=1.2 from the Lévy distribution:
x1new = −8 + 0.1 × 1.2 × (−8+3)
=−8−0.6 =−8.6
Evaluate f(x1new)
f(x1new) = (-8.6) 2 =73.96
For x2: Local Pollination:
Select two other solutions xj= xi and xk= x3from the population:
x2new = x2 + ϵ (xj − xk )
Assume ϵ=0.6:
x2new = 5 + 0.6 × (−8+3)= 5−3= 2
Evaluate f(x2new)
f(x2new) = (2) 2 =4
Step-by-Step Calculations
and Solution
For x3 : Global Pollination
x3new = x3 + γ × L(x3 −g∗ )
Assume L=1.3 from the Lévy distribution:
x3new = −3 + 0.1 × 1.3 × (−3+3)
=−3
So, x3new remains the same, and:
f(x3new) = (-3) 2 =9
After Iteration 1, the new solutions are:
f(x1new) =73.96 f(x2new) =4 f(x3new) =9
The best solution after this iteration is x2new = 2 with f(x2new) =4
Step 3: Iteration 2
Using the updated values from Iteration 1, proceed with the next iteration.
For x1: Local Pollination:
Select two other solutions xj= x2 and xk= x3
x1new = x1 + ϵ (xj − xk )
Assume ϵ=0.4:
x1new = −8+0.4×(2+3)=−8+2=−6
Evaluate f(x1new) :
f(x1new) = (-6) 2 =36
Step-by-Step Calculations
and Solution
For x2 : Global Pollination
x2new = x2 + γ × L(x2 −g∗ )
Assume L=1.1 from the Lévy distribution:
x2new =2+0.1×1.1×(2−2)=2
So, x2new remains the same, and:
f(x2new) = (2) 2 =4
For x3 : Local Pollination
Select two other solutions xj= x1 and xk= x2
x3new = x3 + ϵ (xj − xk )
Assume ϵ=0.7:
x3new = −3+0.7×(−6−2)=−3−5.6=−8.6
Evaluate f(x3new) :
f(x1new) = (-8.6) 2 =73.96
After Iteration 2, the new solutions are:
f(x1new) =36 f(x2new) =4 f(x3new) = 73.96
The best solution after this iteration is x2new = 2 with f(x2new) =4
Step-by-Step Calculations
and Solution
Step 4: Subsequent Iterations
Continue applying global and local pollination for the remaining iterations (3, 4, and 5),
keeping track of the best solution found so far.
After 5 iterations, the algorithm should move closer to x=0, where f(x)=0. The FPA
algorithm finds an optimal or near-optimal solution by balancing global and local
pollination methods.
Final Outcome
After 5 iterations, the algorithm will converge to a solution close to x=0 with f(x)=0,
demonstrating the effectiveness of FPA in finding the minimum of the function f(x)= x2 .