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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Бджолиний алгоритм (в англомовних статтях також зустрічаються назви 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) відображає в якій мірі частка залишається вірною своєму первісному курсом, не зазнавши впливу ГНП і ПНП.

Граничні умови[ред.ред. код]

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

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

Висновок[ред.ред. код]

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

Дивись також[ред.ред. код]

Посилання[ред.ред. код]