Бджолиний алгоритм

Бджола збирає нектар

Бджолиний алгоритм (в англомовних статтях також зустрічаються назви Artificial Bee Colony (ABC) Algorithm та Bees Algorithm) є доволі молодим алгоритмом для знаходження глобальних екстремумів (максимумів чи мінімумів) складних багатовимірних функцій.

В інформатиці та дослідженні операцій, бджолиний алгоритм на основі алгоритму пошуку вперше розроблений в 2005 році. Він імітує поведінку харчування зграї бджіл. У базовій версії, алгоритм виконує свого роду сусідній пошук в поєднанні з випадковим пошуком і може використовуватися для комбінаторної оптимізації і функціональної оптимізації.

Загальні принципи

Для розгляду принципів роботи бджолиного алгоритму, або методу бджолиної сім'ї (МБС) вдамося до аналогії з реальною бджолиною сім'єю.

Уявімо собі вулик бджіл у природі. Їх мета — знайти в радіусі льоту робочої бджоли область з найвищою щільністю квітів. Без якого-небудь уявлення про поле апріорі, бджоли починають пошук квітів з випадкових позицій з випадковими векторами швидкості. Кожна бджола може пам'ятати позиції, де вона знайшла найбільшу кількість квітів і порівнювати знайдені джерела найбільшої щільністі квітів з іншими, які виявили інші бджоли-розвідниці. Вибираючи між поверненням до місця, де бджола сама виявила найбільшу кількість квітів, або дослідженням місця, визначеного іншими, як місце з найбільшою кількістю квітів, бджола спрямовується в напрямку між двома точками в залежності від того, що надасть більший вплив на її рішення — персональний спогад або соціальний рефлекс. По дорозі бджола може знайти місце з більш високою концентрацією квітів, ніж було знайдено раніше. Надалі воно може бути позначено як нове місце з найбільшою концентрацією квітів, а також як місце найбільшого скупчення квітів, знайдене бджолами-розвідницями цієї сім'ї. Випадково бджола може пролетіти повз місця, з великою кількістю квітів, ніж було знайдено будь-якою іншою бджолою сім'ї. Всі робочі бджоли сім'ї потім будуть прагнути до цього місця в додаток до власних спостережень кожної бджоли (інформація іншим бджолам передається всередині вулика, за допомогою «бджолиного танцю»). Таким чином, бджоли досліджують поле: перелітаючи місця з найбільшою концентрацією, вони сповільнюються в їхньому напрямку. Безперервно вони перевіряють місця, які пролетіли, порівнюючи з знайденими раніше місцями з найбільшою концентрацією квітів сподіваючись знайти абсолютну найбільшу концентрацію квітів. В підсумку, бджола закінчує рух на місці поля з найбільшою концентрацією квітів. Незабаром всі робочі бджоли сім'ї зосереджується в околицях цієї позиції. Не маючи можливості виявити місця з більшою концентрацією квітів, бджоли безперервно літають в райони найбільшої щільності квітів. Ця поведінка бджіл і була покладена в основу цього методу оптимізації.

Мова методу

Частинка або Агент — кожна бджола в сім'ї розглядається як частинка або агент. Всі частинки сім'ї діють індивідуально відповідно до одного керуючого принципу: прискорюватися в напрямку найкращої персональної і найкращої спільної позиції, постійно перевіряючи значення поточної позиції. Позиція — аналогічно розташування бджоли на полі представлені координатами на площині xy. Однак, в загальному випадку можна розширити цю ідею в будь-який N-мірний простір відповідно до поставленого завдання. Цей N-мірний простір є областю рішень для задачі, що оптимізується, де кожний набір координат представляє рішення. Придатність — за аналогією з прикладом бджолиної сім'ї функція придатності буде щільність квітів: чим більша щільність, тим краща позиція. Функція придатності служить засобом зв'язку між фізичною проблемою і алгоритмом оптимізації. Персональна найкраща позиція — за аналогією з бджолиною сім'єю, кожна бджола пам'ятає позицію, де вона сама виявила найбільшу кількість квітів. Ця позиція з найбільшим значенням придатності виявлена бджолою відома як персональна найкраща позиція (ПНП). Кожна бджола має власне ПНП, яке визначається шляхом, який вона пролетіла. У кожній точці вздовж шляху руху бджола порівнює значення придатності поточної позиції зі значенням ПНП. Якщо поточна позиція має значення придатності вище, значення ПНП замінюється на значення поточної позиції. Глобальна найкраща позиція — кожна бджола сім'ї також дізнається про область найбільшої концентрації квітів за допомогою «бджолиного танцю», результуюче рішення визначається вік конкуруючих танців кожної з бджіл-розвідниць. Якщо одна із розвідниць бачить, що джерело квітів, знайдене іншою розвідницею значно краще, ніж знайдене нею, вона летить, і перевіряє дані. Якщо це дійсно так, то по прильоту до вулика, вона підключається до заохочування бджіл збирати нектар (або пилок) в новій області найбільшої концентрації квітів. Ця позиція найбільшої придатності відома як глобальна найкраща позиція (ГНП). Для всієї сім'ї це одна ГНП, до якої прагне кожна бджола. У кожній точці протягом всього шляху кожна бджола порівнює придатність її поточної позиції з ГНП. У разі якщо будь-яка бджола виявить позицію з більш високою придатністю, ГНП замінюється поточною позицією цієї бджоли.

Алгоритм

Першим кроком в реалізації МБС є вибір параметрів, які необхідно оптимізувати, і визначення допустимого інтервалу для пошуку оптимальних значень. Потім в допустимої області випадковим чином розташовуються бджоли, а також задаються вектори і швидкості їх руху. Потім кожна частка повинна переміщатися через простір рішень, так якщо б вона була бджолою в сім'ї. Алгоритм діє на кожну частку окремо, переміщаючи її на невелику величину, циклічно рухаючи її через всю сім'ю. Наступні кроки виконуються для кожної частки:
Оцінка придатності для частинки, порівняння з ПНП і ГНП. Функція придатності, використовуючи координати частинки в просторі рішень, повертає значення придатності для поточної позиції. Якщо це значення більше, ніж значення ПНП, відповідне цій частці, або ГНП, тоді відповідні позиції замінюються поточної позицією.

Коригування швидкості частинки. Маніпуляції зі швидкістю частинки є основним елементом усієї оптимізації. Точне розуміння рівняння, використовуваного для визначення швидкості, є ключем до розуміння всього процесу оптимізації. Швидкість частинки змінюється відповідно до взаємним розташуванням позицій ПНП і ГНП. Вона прагне в напрямку цих позицій найбільшої придатності згідно з наступним рівнянням:

           $v_{n}^{i+1}=w\cdot v_{n}^{i}+c_{1}rand()(p_{n}-x_{n})+c_{2}rand()\cdot (g_{n}-x_{n})$

   де:

        $v_{n}^{i}$— це швидкість частинки в n-том вимірі на попередньому кроці,

        $x_{n}$— це координата частинки в n-том вимірі,

        $p_{n}$— ПНП,

        $g_{n}$— ГНП.

Розрахунок проводиться для кожного з N. З цього рівняння видно, що нова швидкість виходить зі старої швидкості шляхом простого масштабування на $w$, і додавання напрямків ГНП і ПНП для цього конкретного напряму.

$c_{1}$ і $c_{2}$— це масштабні коефіцієнти, які визначають відносне взаємне «тяжіння» до ПНП і ГНП. Вони іноді розглядаються як пізнавальний і соціальний фактори. $c_{1}$— це коефіцієнт, що визначає який вплив на частку надає її пам'ять про ПНП, $c_{2}$ — коефіцієнт, що визначає який вплив на частку надають інші члени сім'ї. Збільшення передбачає дослідження простору рішень шляхом руху кожної частинки в напрямку свого ПНП; збільшення передбачає дослідження передбачуваного глобального максимуму.

Функція випадкових чисел $rand()$ повертає число в інтервалі між -1 і 1. Загалом випадку два появи функції $rand()$ являє собою два різних виклику функції. Більшість реалізацій використовують дві незалежні випадкові величини для стохастичного зміни відносного тяжіння ГНП і ПНП. Це введення випадкового елемента в оптимізацію призначено для моделювання незначного непередбачуваного компонента реальної поведінки сім'ї. $w$ називають «інерційним вагою» і це число (вибране в інтервалі між 0 і 1) відображає в якій мірі частка залишається вірною своєму первісному курсом, не зазнавши впливу ГНП і ПНП.

Граничні умови

Межі ми поставили спочатку, але ніде в формулах і методах про них не згадувалося. Так як же все-таки їх враховувати? Існує декілька варіантів.

Наприклад, можна зробити стіни поглинаючими. Коли частка вдаряється об кордон простору рішень в одному з вимірів, швидкість в цьому вимірі обнуляється, і частка в кінцевому підсумку буде повернена в заданий простір рішень. Це означає, що кордони — «стіни» поглинають енергію частинок, що намагаються покинути дозволену область. Або ж відображати швидкість частинки, коли та підлітає до «стіни». Але найефективнішим рішенням виявилися «невидимі стіни». Частка може спокійно вилітати за їх межі, але перебуваючи поза дозволеною областю, значення, отримані нею значення просто не враховуються, до тих пір, поки вона не повернеться назад.

Висновок

Метод бджолиної сім'ї можна ефективно розподілити на декілька паралельних процесів, за рахунок чого значно збільшиться його швидкість. У порівнянні з генетичним алгоритмом, оператори якого можуть бути реалізовані різним чином, МБС має лише один оператор — обчислення швидкості, що робить його простішим у використанні.

У методі бджолиної сім'ї можна легко визначити досягнення точки глобального мінімуму, в той час як в генетичних алгоритмах це значно ускладнено. Концепція цих методів ґрунтується на двох зовсім різних природних процесах: МБС ґрунтується на соціальній поведінці бджолиної сім'ї, а генетичний алгоритм імітує процес еволюції і природного відбору. За рахунок цього є можливість об'єднати два цих методи.

Див. також

• Колективний інтелект
• Мурашиний алгоритм
• Метод рою часток
• Алгоритм гравітаційного пошуку
• Штучна імунна система
• Алгоритм зозулі

Посилання

• Природні алгоритми. Алгоритм поведінки рою бджіл [Архівовано 14 лютого 2012 у Wayback Machine.]
• Бджолиний алгоритм для оптимізації функції [Архівовано 17 березня 2012 у Wayback Machine.]