Алгоритъмът на прилепа () е метаевристичен алгоритъм за глобална оптимизация, вдъхновен от ехолокационното поведение на насекомоядните прилепи с вариращи честоти и височина на издавания звук.J. D. Altringham, Bats: Biology and Behaviour, Oxford University Press, (1996).P. Richardson, Bats. Natural History Museum, London, (2008) Алгоритъмът на прилепа е разработен през 2010 година от британския математик Син-Шъ Ян, разработил също и метаевристичните алгоритми на светулката (firefly algorithm), на кукувицата (cuckoo search) и на опрашването (flower pollination algorithm).
Описание на алгоритъма Метафората за ехолокацията на прилепите, използвана в тази биологично вдъхновена изчислителна парадигма, може да се резюмира по следния начин: Всеки виртуален „прилеп“ (агент) се движи на случаен принцип със скорост до позиция (решение) с вариращи параметри честота (дължина на вълната) и височина на издавания звук . Докато търси и открива плячката си, прилепът променя честотата, височината и пулсацията . Търсенето на решение става по-интензивно при локално случайно блуждаене. Изборът на най-добро решение продължава докато не бъдат удовлетворени определени критерии за край. Алгоритъмът основно използва техника за настройване на честотата, контролираща динамичното поведение на рояк от прилепи, и намира баланс между проучване и експлоатация (exploration and exploitation), контролирайки настройките на зависимите от алгоритъма параметри.
Детайлно въведение в метаевристичните алгоритми, включително алгоритъма на прилепа, е дадено от Ян Yang, X. S., Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010). с предоставено демо на Matlab/Octave. Демо на Matlab е налично и от портала Matlab exchange.Bat algorithm (demo), Xin-She Yang , 20 юли 2012
Псевдокод Алгоритъмът на прилепа е обобщен като псевдокод по следния начин.Parpinelli, R. S., Lopes, H. S. New inspirations in swarm intelligence: a survey. Int. J. Bio-Inspired Computation, Vol. 3, No. 1, 2011, 1-16.
1 Parameters:
2 Initialise the bats population and randomly
3 Define pulse frequency at
4 for = 1 to do
5 Initialise pulse rates and loudness
6 end for
7 Compute
8 Find the current best
9 while stop condition not met do
10 for = 1 to do
11 Generate new solutions by adjusting:
12 Frequency:
13 Velocity:
14 Location:
15 if then
16 Select a solution among the best solutions
17 Generate a local solution around the selected best solution
18 end if
19 Generate a new solution by flying randomly
20 if
21 Accept the new solutions
22 Increase:
23 Decrease:
24 end if
25 end for
26 Find the current best
27 end while
28 Postprocess results and visualisation
Източници
Категория:Метаевристични алгоритми