Загальна характеристика ройових алгоритмів.

За останні 40-60 років людство дуже стрімко почало розвивати інформаційні технології, зокрема їх застосування для вирішення проблем досить різного складу і походження. Таким чином виникли різноманітні алгоритми, призначені для автоматизації виробництва, ретельної діагностики, спрощення життєвих(буденних) ситуацій, розв’язування задач різного типу тощо. Проте на практиці, не завжди вдається побудувати початкову модель або встановити конкретну кінцеву мету, невизначеність, не лінійність задачі або відсутність реального досвіду розв’язку такого типу задач. Саме для таких випадків були відкриті генетичні алгоритми. Принцип їх роботи, очевидно, запозичений з явищ природи: імунні та нейронні мережі взаємозв’язки між видами та в межах популяції, закономірності поведінки тварин, як колективної, так і індивідуальної та реалізують процес випадкового пошуку. Проте слід враховувати, що такі алгоритми є здебільшого хаотичні, тоді як ми прагнемо зробити всі процеси максимально точними і ефективними для досягнення результату якнайшвидше. Такі методи частіше називають метаеврестичними. Цей термін вказує на те, що евристика, яка застосовується, не є завершеною, а лише створює певний алгоритм для побудови кінцевої евристики для кожної конкретно вирішуваної задачі.

Такими алгоритмами є і ройові алгоритми або PSO(Particle Swarm Organization). Вперше алгоритм був відкритий і сформульований Дж. Кеннеді та Р. Ебенхартом, але сама ідея використання “природних” алгоритмів існувала раніше, приваблюючи людей абсолютною точністю і злагодженістю.

В основу ройового алгоритму покладений колективний інтелект, наприклад стаї хижаків, що полюють на здобич, зграя птах, що точно летить в одному напрямі, не зіштовхуючись одне з одним, міграція риб тощо. Якщо розглядати конкретніше, то принцип роботи заклечається в передачі інформаціями між одиницями рою, тобто частками(звірі в стаї, птахи в зграї тощо) під час кожної ітерації. Ітерація – це повторення певних дій. Таким чином, після кожної ітерації, передається інформація про найкраще місцезнаходження часток в даний момент і попередні найкращі позиції(координати).

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

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

 

Огляд ройових алгоритмів

Ройові алгоритми(PSO алгоритми) характеризуються стохастичністю, тобто кожен агент цієї системи в кожній наступній ітерації рухається випадково. Рух всього рою слід розглядати, як окремий рух кожного агента, знаходження найбільш оптимального значення під час кожної ітерації(локального мінімуму), а загальний процес являє собою аналіз кожним агентом отриманої інформації про оптимальне місцезнаходження кожного з усіх інших агентів. Такий процес можна визначити як взаємоаналіз, де кожна частка отримує вигоду з дослідів і попереднього досвіду всіх інших часток. Таким чином, цей алгоритм має найбільше шансів на отримання переваги над іншими алгоритмами, особливо коли оптимум невідомий, або розташований випадково.

Задачу оптимізації можна сформувати як пошук глобального екстремуму(мінімуму чи максимуму) цільової функції f(X), визначеній на проміжку D:

f(X) → min(max), X∈D = { x ∈ R^d},

де область D – суттєвий гіперкуб з розмірністю d, X – векторний аргумент функції f, що оптимізується, а її глобальний розв’язок знаходиться в точці X^*

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

Позначимо сукупність часток рою через

 

X = { x ₁, x ₂,…, x _s},

де s – кількість елементів рою. I-та позиція позначає сукупність ії координат(x_i1,x_i2,…,x_id), в d-розмірному просторі. Практично доведено, що найбільш раціонально використовувати 20-30 часток.

На початковому етапі алгоритму відбувається ініціалізація рою часток. Якщо ж інформація про початкові дані про цільову функцію, то доцільно визначити за формулою

 

x_ij = rand(x_{j min}, x_{j max}),

де x_i,j – i-та частка j-ої координати(розмірності), rand(x_{j min}, x_{j max}) – випадково згенероване число в інтервалі [ x_{j min}, x_{j max}] j-ого простору, рівномірно розподілені на всьому інтервалі.

Очевидно, що частки певним чином змінюють своє положення в просторі, тобто рухаються. Такий рух можна описати масивом V ={ v ₁, v ₂,…, v _s}, де v_s – вектор переміщення для s-ої частки. Такі вектори на початку можна вважати нульовими, але досвід встановив, що краще їх розраховувати по формулі

 

v_i,j=[rand(x_jmin,x_jmax)-x_i,j]/2,

де v_i,j – j-ий вектор руху i-ї частки. Такий спосіб гарантує, що під час завдання наступного вектора частки не вийдуть за межі пошуку.

На наступних ітерація вектори розраховуються по формулі

V’_i,j = wv_i,j + c₁r₁(p_i,j – x_i,_j) + c₂r₂ (g_j – x_i,j),

а наступна координата(позиція) кожної частки за формулою

x’_i,j = x_i,j + v’_i,j,

де v'_i x'_I - новий вектор і положення і-ії частки; p_i – найкраще положення, визначене попередньо(personal best); g – найкраще рішення, знайдене всім роєм(global best); w – інерційний коефіцієнт; c₁,c_{2 -} відповідно когнітивний і соціальні коефіцієнти; - випадкові числа, r₁,r₂ - генеровані випадково на інтервалі [0;1] для кожної координати.

Якщо ж під час виконання частка виходить за межі простору пошуку, то її відповідний вектор набуває нульового значення, а частка отримує відповідно граничні координати, тобто переходить на край “поля” пошуку.

Інерційний коефіцієнт w визначає вплив попереднього вектору частки на її нове значення. Величина коефіцієнта c₁ показує ії індивідуальну поведінку і “прагнення” рухатися до напрямку найкращого рішення, знайденого нею до цього. Коефіцієнт c₂ задає ступінь її колективної реакції і прагнення рухатися в напрямку до найкращого колективного рішення