FPA Algorithm
Flower Pollination Algorithms
The flower pollination algorithm (FPA) was developed by Xin-She Yang in 2012,
inspired by the pollination process of flowering plants. FPA has been extended to multiobjective
optimization with promising results. This chapter provides an introduction to
FPA and its basic implementation.
11.1 Introduction
Real-world design problems in engineering and industry are usually multi-objective or
multicriteria. These multiple objectives often conflict with one another, which makes it
impossible to use any single design option without compromise. Common approaches
are to provide good approximations to the true Pareto fronts of the problem of interest so
that decision makers can rank different options, depending on their preferences or their
utilities [1,5,15]. Compared with single-objective optimization, multi-objective optimization
has its additional challenging issues such as time complexity, inhomogeneity,
and dimensionality. It is usually more time consuming to obtain the true Pareto fronts
because it typically requires us to produce many points on the Pareto front for good
approximations.
In addition, even if accurate solutions on a Pareto front can be obtained, there is
still no guarantee that these solution points will distribute uniformly on the front. In
fact, it is often difficult to obtain the whole front without any part missing. For singleobjective
optimization, the optimal solution can often be a single point in the solution
space, whereas for bi-objective optimization, the Pareto front forms a curve, and for
tri-objective cases it becomes a surface. In fact, a higher-dimensional problem can
have an extremely complex hypersurface as its Pareto front [11,20]. Consequently, it
is typically more challenging to solve such high-dimensional problems.
In the current literature of engineering optimization, a class of nature-inspired algorithms
have shown their promising performance and have thus become popular and
widely used. These algorithms are mostly swarm intelligence based [5,7,9,15,14], as
we have seen in this book.
The main aim of this chapter is to first introduce the basic flower pollination algorithm
(FPA), developed by Xin-She Yang in 2012 [19], and then extend it to solve
multi-objective optimization. We then discuss the results for solving function optimization
benchmarks and design benchmarks in engineering.
11.2 Flower Pollination Algorithm
11.2.1 Characteristics of Flower Pollination
It is estimated that there are over a quarter of a million types of flowering plants in nature
and that about 80% of all plant species are flowering species. It still remains a mystery
how flowering plants came to dominate the landscape from the Cretaceous period [17].
Flowering plants have been evolving for at least 125 million years, and flowers have
become so influential in evolution that, it is unimaginable what the plant world would
look like without them. The main purpose of a flower is ultimately reproduction via
pollination. Flower pollination is typically associated with the transfer of pollen, and
such transfer is often linked with pollinators such as insects, birds, bats, and other
animals. In fact, some flowers and insects have co-evolved into a very specialized
flower-pollinator partnership. For example, some flowers can only attract and can only
depend on a specific species of insect or bird for successful pollination.
Pollination can take two major forms: abiotic and biotic. About 90% of flowering
plants belong to the biotic pollination group. That is, pollen is transferred by pollinators
such as insects and animals. About 10% of pollination takes abiotic form, which does
not require any pollinators.Wind and diffusion help with pollination of such flowering
plants. Grass is a good example of abiotic pollination [5,17]. Pollinators, sometimes
called pollen vectors, can be very diverse. It is estimated that there are at least 200,000
varieties of pollinators such as insects, bats, and birds. Honeybees are a good example
of pollinators, and they have also developed the so-called flower constancy. That is,
these pollinators tend to visit certain flower species exclusively, bypassing other flower
species. Such flower constancymay have evolutionary advantages because itmaximizes
the transfer of flower pollen to the same or conspecific plants, thus maximizing the
reproduction of the same flower species. Such flower constancy may be advantageous
for pollinators as well because they can be sure that nectar supply is available with their
limited memory and minimum cost of learning, switching, or exploring. Rather than
focusing on some unpredictable but potentially more rewarding new flower species,
pollinators might find that flower constancy requires minimum investment costs and
more likely guaranteed intake of nectar [18].
Pollination can be achieved by self-pollination or cross-pollination. Cross-pollination,
or allogamy, means that pollination can occur from the pollen of a flower of a different
plant; self-pollination is the fertilization of one flower, such as peach flowers, from
pollen of the same flower or different flowers of the same plant, which often occurs
when no reliable pollinator is available. Biotic cross-pollination may occur at a long
distance; pollinators such as bees, bats, birds, and flies can fly a long distance, so they
can be considered global pollination. In addition, bees and birds may exhibit Lévy
flight behavior with jump or fly distance steps obeying a Lévy distribution. Furthermore,
flower constancy can be considered an incremental step using the similarity or
difference of two flowers.
From the biological evolution point of view, the objective of flower pollination is
the survival of the fittest and the optimal reproduction of plants in terms of numbers
as well as the most fittest. This can be considered an optimization process of plant species. All of these factors and processes of flower pollination interact to achieve
optimal reproduction of the flowering plants. This natural behavior may motivate us to
design new optimization algorithms.
11.2.2 Flower Pollination Algorithm
FPA was developed by Xin-She Yang in 2012 [19], inspired by the flow pollination
process of flowering plants. FPA has been extended to multi-objective optimization
[20]. For simplicity, the following four rules are used:
1. Biotic and cross-pollination can be considered processes of global pollination, and
pollen-carrying pollinators move in a way that obeys Lévy flights (Rule 1).
2. For local pollination, abiotic pollination and self-pollination are used (Rule 2).
3. Pollinators such as insects can develop flower constancy, which is equivalent to a
reproduction probability that is proportional to the similarity of two flowers involved
(Rule 3).
4. The interaction or switching of local pollination and global pollination can be controlled
by a switch probability p ∈ [0, 1], slightly biased toward local pollination
(Rule 4).
To formulate the updating formulas, these rules have to be converted into proper
updating equations. For example, in the global pollination step, flower pollen gametes
are carried by pollinators such as insects, and pollen can travel over a long distance
because insects can often fly and move in a much longer range. Therefore, Rule 1 and
flower constancy (Rule 3) can be represented mathematically as
where xt
i is the pollen i or solution vector xi at iteration t, and g∗ is the current best
solution found among all solutions at the current generation/iteration. Here γ is a
scaling factor to control the step size.
In essence, L(λ) is a step-size parameter, more specifically the Lévy-flights-based
step size, that corresponds to the strength of the pollination. Since insects may travel
over a long distance with various distance steps, a Lévy flight can be used to mimic
this characteristic efficiently. That is, L > 0 is drawn from a Lévy distribution
11.2 Flower Pollination Algorithm
11.2.1 Characteristics of Flower Pollination
It is estimated that there are over a quarter of a million types of flowering plants in nature
and that about 80% of all plant species are flowering species. It still remains a mystery
how flowering plants came to dominate the landscape from the Cretaceous period [17].
Flowering plants have been evolving for at least 125 million years, and flowers have
become so influential in evolution that, it is unimaginable what the plant world would
look like without them. The main purpose of a flower is ultimately reproduction via
pollination. Flower pollination is typically associated with the transfer of pollen, and
such transfer is often linked with pollinators such as insects, birds, bats, and other
animals. In fact, some flowers and insects have co-evolved into a very specialized
flower-pollinator partnership. For example, some flowers can only attract and can only
depend on a specific species of insect or bird for successful pollination.
Pollination can take two major forms: abiotic and biotic. About 90% of flowering
plants belong to the biotic pollination group. That is, pollen is transferred by pollinators
such as insects and animals. About 10% of pollination takes abiotic form, which does
not require any pollinators.Wind and diffusion help with pollination of such flowering
plants. Grass is a good example of abiotic pollination [5,17]. Pollinators, sometimes
called pollen vectors, can be very diverse. It is estimated that there are at least 200,000
varieties of pollinators such as insects, bats, and birds. Honeybees are a good example
of pollinators, and they have also developed the so-called flower constancy. That is,
these pollinators tend to visit certain flower species exclusively, bypassing other flower
species. Such flower constancymay have evolutionary advantages because itmaximizes
the transfer of flower pollen to the same or conspecific plants, thus maximizing the
reproduction of the same flower species. Such flower constancy may be advantageous
for pollinators as well because they can be sure that nectar supply is available with their
limited memory and minimum cost of learning, switching, or exploring. Rather than
focusing on some unpredictable but potentially more rewarding new flower species,
pollinators might find that flower constancy requires minimum investment costs and
more likely guaranteed intake of nectar [18].
Pollination can be achieved by self-pollination or cross-pollination. Cross-pollination,
or allogamy, means that pollination can occur from the pollen of a flower of a different
plant; self-pollination is the fertilization of one flower, such as peach flowers, from
pollen of the same flower or different flowers of the same plant, which often occurs
when no reliable pollinator is available. Biotic cross-pollination may occur at a long
distance; pollinators such as bees, bats, birds, and flies can fly a long distance, so they
can be considered global pollination. In addition, bees and birds may exhibit Lévy
flight behavior with jump or fly distance steps obeying a Lévy distribution. Furthermore,
flower constancy can be considered an incremental step using the similarity or
difference of two flowers.
From the biological evolution point of view, the objective of flower pollination is
the survival of the fittest and the optimal reproduction of plants in terms of numbers
as well as the most fittest. This can be considered an optimization process of plant species. All of these factors and processes of flower pollination interact to achieve
optimal reproduction of the flowering plants. This natural behavior may motivate us to
design new optimization algorithms.
11.2.2 Flower Pollination Algorithm
FPA was developed by Xin-She Yang in 2012 [19], inspired by the flow pollination
process of flowering plants. FPA has been extended to multi-objective optimization
[20]. For simplicity, the following four rules are used:
1. Biotic and cross-pollination can be considered processes of global pollination, and
pollen-carrying pollinators move in a way that obeys Lévy flights (Rule 1).
2. For local pollination, abiotic pollination and self-pollination are used (Rule 2).
3. Pollinators such as insects can develop flower constancy, which is equivalent to a
reproduction probability that is proportional to the similarity of two flowers involved
(Rule 3).
4. The interaction or switching of local pollination and global pollination can be controlled
by a switch probability p ∈ [0, 1], slightly biased toward local pollination
(Rule 4).
To formulate the updating formulas, these rules have to be converted into proper
updating equations. For example, in the global pollination step, flower pollen gametes
are carried by pollinators such as insects, and pollen can travel over a long distance
because insects can often fly and move in a much longer range. Therefore, Rule 1 and
flower constancy (Rule 3) can be represented mathematically as
where xt
i is the pollen i or solution vector xi at iteration t, and g∗ is the current best
solution found among all solutions at the current generation/iteration. Here γ is a
scaling factor to control the step size.
In essence, L(λ) is a step-size parameter, more specifically the Lévy-flights-based
step size, that corresponds to the strength of the pollination. Since insects may travel
over a long distance with various distance steps, a Lévy flight can be used to mimic
this characteristic efficiently. That is, L > 0 is drawn from a Lévy distribution
Comentarios
Publicar un comentario