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

Алгоритъмът на опрашването (на английски: flower pollination algorithm) е метаевристичен алгоритъм, предложен от Син-Шъ Ян основан на метафората на процеса на опрашване на цъфтящите растения. Създателят на алгоритъма е автор и на още три други известни метаевристики: Алгоритъм на светулката (2008), Алгоритъм на кукувицата (2009) и Алгоритъм на прилепа (2010).

Алгоритъмът борави с четири правила (допускания):

1. Биотичното опрашване (от насекоми, птици и др.) и кръстосаното опрашване (алогамия) се смятат за процедури за глобално опрашване, т.е. метафори за глобално търсене, където агентите, извършващи опрашването (полинатори), изпълняват полети на Леви.
2. Абиотичното опрашване и самоопрашването се смятат за процедури за локално опрашване, т.е. процедури по локално търсене.
3. Може да се приеме, че цветята са константни, тъй като вероятността за репродукция (оплождане) е пропорционална на подобието между двата цвята, участващи в опрашването.
4. Локалното и глобалното опрашване се управляват с вероятностна променлива $p\in [0,1]$. Поради физически близкото разположение и други фактори като вятър, локалното опрашване може да съставлява значителен дял $p$ от цялото опрашване.

Правилата могат да се преведат в термините на следните уравнения:

$x_{i}^{t+1}=x_{i}^{t}+L(x_{i}^{t}-g_{*})$

$x_{i}^{t+1}=x_{i}^{t}+\epsilon (x_{i}^{t}-x_{k}^{t})$

където $x_{i}^{t}$ е векторът на решението и $g_{*}$ е текущото най-добро решение, открито с досегашните итерации. Вероятността, определяща избора на едно от двете уравнения, equations during iterations is $p$. В добавка, $\epsilon$ е случайно число, получено от равномерно разпределение, а $L$ е размер на стъпката, получен от разпределението на Леви.

Полетът на Леви, използващ стъпка на Леви, е мощен метод за случайно обхождане, защото едновременно се проверяват възможностите и за глобално, и за локално търсене. За разлика от стандартното случайно обхождане, полетът на Леви понякога прави големи скокове, което позволява на алгоритъма да излезе от регион на локален оптимум.

Стъпките на Леви се подчиняват на следното апроксимационно условие:

$L\sim {\frac {1}{s^{1+\beta }}},$

където $\beta$ е експонента на Леви. Точното определяне на стъпките на Леви може да се трудна задача, затова прост начин за генериране на полетите на Леви $s$ е да се използват две нормални разпределения $u$ и $v$ при

$s={\frac {u}{|v|^{1+\beta }}},$

където $u\sim N(0,\sigma ^{2}),\quad v\sim N(0,1),$, $\sigma$ е функция на $\beta$.

Източници

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