Flower pollination algorithm: Difference between revisions
Content deleted Content added
m Dating maintenance tags: {{Afd-merge to}} |
←Redirected page to List of metaphor-inspired metaheuristics#Flower pollination |
||
| Line 1: | Line 1: | ||
#REDIRECT [[List of metaphor-inspired metaheuristics#Flower pollination]] |
|||
{{Afd-merge to|Swarm intelligence#Algorithms|Flower pollination algorithm|6 August 2016|date=August 2016}} |
|||
{{Expert-subject|Computer science|talk=|reason=needs appropriate Wiki links and definitions for laymen|date=July 2015}} |
|||
'''Flower pollination algorithm''' (FPA) is a meta[[Heuristic (computer science)|heuristic]] [[algorithm]] that was developed by [[Xin-She Yang]],<ref>Xin-She Yang. Flower pollination algorithm for global optimization, Unconventional Computation and Natural Computation. Lecture Notes in Computer Science. Volume 7445, pp. 240-249 (2012).</ref> based on the [[pollination]] process of flowering [[plants]]. |
|||
== Main characteristics == |
|||
This algorithm has 4 rules or assumptions: |
|||
1. Biotic and cross-pollination is considered as global pollination process with |
|||
pollen carrying pollinators performing Levy flights. |
|||
2. Abiotic and self-pollination are considered as local pollination. |
|||
3. Flower constancy can be considered as the reproduction probability is proportional |
|||
to the similarity of two flowers involved. |
|||
4. Local pollination and global pollination is controlled by a switch probability <math>p \in [0, 1]</math>. |
|||
Due to the physical proximity and other factors such as wind, local pollination can |
|||
have a significant fraction p in the overall pollination activities. |
|||
These rules can be translated into the following updating equations: |
|||
:<math> x_i^{t+1}=x_i^t + L (x_i^t-g_*)</math> |
|||
:<math> x_i^{t+1}=x_i^t + \epsilon (x_i^t-x_k^t)</math> |
|||
where <math>x_i^t</math> is the solution vector and <math>g_*</math> is the current best found so far during iteration. The switch probability between two equations during iterations is <math>p</math>. In addition, <math>\epsilon</math> is a random number drawn from a uniform distribution. <math>L</math> is a step size drawn from a Lévy distribution. |
|||
Lévy flights using Lévy steps is a powerful random walk because both global and local search capabilities can be carried out at the same time. |
|||
In contrast with standard Random walks, Lévy flights have occasional long jumps, which enable the algorithm to jump out any local valleys. |
|||
Lévy steps obey the following approximation: |
|||
:<math> L \sim \frac{1}{s^{1+\beta}}, </math> |
|||
where <math>\beta</math> is the Lévy exponent.<ref>I. Pavlyukevich, Lévy flights, non-local search and simulated annealing, J. Computational Physics, Vol. 226, 1830-1844 (2007).</ref> It may be challenging to draw Lévy steps properly, and a simple way of generating Lévy flights <math>s</math> is to use two normal distributions <math>u</math> and <math>v</math> by a transform<ref>X. S. Yang, Nature-Inspired Optimization Algorithms, Elsevier, (2014).</ref> |
|||
:<math> s = \frac{u}{|v|^{1+\beta}}, </math> |
|||
with |
|||
:<math> u \sim N(0, \sigma^2), \quad v \sim N(0,1), </math> |
|||
where <math>\sigma</math> is a function of <math>\beta</math>. |
|||
A matlab demo program is available for function optimization.<ref>X. S. Yang. http://www.mathworks.com/matlabcentral/fileexchange/45112-flower-pollination-algorithm</ref> |
|||
== References == |
|||
{{Reflist|50em}} |
|||
[[Category:Nature-inspired metaheuristics]] |
|||