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

Алгоритъмът на прилепа (на английски: bat algorithm) е метаевристичен алгоритъм за глобална оптимизация, вдъхновен от ехолокационното поведение на насекомоядните прилепи с вариращи честоти и височина на издавания звук. Алгоритъмът на прилепа е разработен през 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}+({\overrightarrow {x}}^{t}-{\overrightarrow {x}}_{*}^{t}){\overrightarrow {f}}_{i}$

14          Location: ${\overrightarrow {x}}^{t}={\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}\ \ \&\ \ 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

Източници

Тази страница частично или изцяло представлява превод на страницата Bat algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​