Алгоритъм на прилепа

Алгоритъмът на прилепа (Шаблон:Lang) е метаевристичен алгоритъм за глобална оптимизация, вдъхновен от ехолокационното поведение на насекомоядните прилепи с вариращи честоти и височина на издавания звук. Алгоритъмът на прилепа е разработен през 2010 година от британския математик Син-Шъ Ян, разработил също и метаевристичните алгоритми на светулката (firefly algorithm), на кукувицата (cuckoo search) и на опрашването (flower pollination algorithm).

Описание на алгоритъма

Метафората за ехолокацията на прилепите, използвана в тази биологично вдъхновена изчислителна парадигма, може да се резюмира по следния начин: Всеки виртуален „прилеп“ (агент) се движи на случаен принцип със скорост $v_i$ до позиция (решение) $x_i$ с вариращи параметри честота (дължина на вълната) и височина на издавания звук $A_i$. Докато търси и открива плячката си, прилепът променя честотата, височината и пулсацията $r$. Търсенето на решение става по-интензивно при локално случайно блуждаене. Изборът на най-добро решение продължава докато не бъдат удовлетворени определени критерии за край. Алгоритъмът основно използва техника за настройване на честотата, контролираща динамичното поведение на рояк от прилепи, и намира баланс между проучване и експлоатация (exploration and exploitation), контролирайки настройките на зависимите от алгоритъма параметри.

Детайлно въведение в метаевристичните алгоритми, включително алгоритъма на прилепа, е дадено от Ян с предоставено демо на Matlab/Octave. Демо на Matlab е налично и от портала Matlab exchange.

Псевдокод

Алгоритъмът на прилепа е обобщен като псевдокод по следния начин.

1  Parameters: $n,\alpha ,\gamma$

2  Initialise the bats population ${\overrightarrow{x}}_i$ and ${\overrightarrow{v}}_i$ randomly

3  Define pulse frequency ${\overrightarrow{f}}_i$ at ${\overrightarrow{x}}_i$

4  for $i$ = 1 to $n$ do

5     Initialise pulse rates $r_i$ and loudness $A_i$

6  end for

7  Compute $f({\overrightarrow{x}}_i)$

8  Find the current best ${\overrightarrow{x}}_{*}$

9  while stop condition not met do

10    for $i$ = 1 to $n$ do

11       Generate new solutions by adjusting:

12          Frequency: ${\overrightarrow{f}}_i={\overrightarrow{f}}_{min}+({\overrightarrow{f}}_{max}-{\overrightarrow{f}}_{min})\beta ,\beta \in [0,1]$

13          Velocity: ${\overrightarrow{v}}_i^t={\overrightarrow{v}}_i^{t-1}+(\stackrel{t}{\overrightarrow{x}}-{\overrightarrow{x}}_{*}^t){\overrightarrow{f}}_i$

14          Location: $\stackrel{t}{\overrightarrow{x}}={\overrightarrow{x}}_i^{t-1}+{\overrightarrow{v}}_i^t$

15       if $rand>r_i$ 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 $rand<A_i\mathrm{\&}f({\overrightarrow{x}}_i)<f({\overrightarrow{x}}_{*})$

21          Accept the new solutions

22          Increase: $r_i:r_i^{t+1}=r_i^0[1-\exp (-\gamma t)]$

23          Decrease: $A_i:A_i^{t+1}=\alpha A_i$

24       end if

25    end for

26    Find the current best $x_{*}$

27 end while

28 Postprocess results and visualisation