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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

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

Описание на алгоритъма[редактиране | редактиране на кода]

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

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

Псевдокод[редактиране | редактиране на кода]

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

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

Източници[редактиране | редактиране на кода]

  1. J. D. Altringham, Bats: Biology and Behaviour, Oxford University Press, (1996).
  2. P. Richardson, Bats. Natural History Museum, London, (2008)
  3. Yang, X. S.. A New Metaheuristic Bat-Inspired Algorithm, in: Nature Inspired Cooperative Strategies for Optimization (NISCO 2010). // Studies in Computational Intelligence 284. 2010. с. 65–74.
  4. Yang, X. S., Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010).
  5. Parpinelli, R. S. и др. New inspirations in swarm intelligence: a survey,Int. // J. Bio-Inspired Computation 3. 2011. DOI:10.1504/ijbic.2011.038700. с. 1–16.
  6. Bat algorithm (demo), Xin-She Yang, 20 юли 2012
  7. 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.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Bat algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.