Оптимізація роєм частинок: інерція, власний досвід і досвід рою
Боїди та зграї, алгоритм PSO, три складові швидкості, запуск на функції Растригіна порівняно з еволюційною стратегією, роль інерції, стійкість частинки, топологія рою і теорема про відсутність безкоштовних обідів.
Серія Основи ШІ Частина 30 з 52
- Мапа штучного інтелекту: що є що і як усе це пов’язано
- Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
- Дані, модель, тренування, інференс: основні поняття на одному прикладі
- Як читати математичний запис: символи, індекси, суми та квантори
- Множини й відношення: конструктор, з якого складаються означення в ШІ
- Функції й відображення: чому кожна модель у ШІ — це функція
- Логіка й доведення: правила, за якими міркують у ШІ
- Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
- Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
- Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
- Градієнтний спуск: як навчається модель
- Що таке ймовірність: від кидка кубика до аксіом Колмогорова
- Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
- Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
- Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
- Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
- Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
- Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
- Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
- Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
- Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
- Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
- Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
- Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
- Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
- Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
- Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
- Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
- Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
- Оптимізація роєм частинок: інерція, власний досвід і досвід рою
- Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
- Нечіткі множини й функції належності: як записати «трохи тепло»
- Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
- Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
- Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
- Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
- Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
- Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
- Приховані марковські моделі: алгоритм Вітербі й нечесне казино
- Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
- Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
- Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
- Промпти, контекст і RAG: як дати моделі правильну інформацію
- Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
- Генеративні змагальні мережі (GAN): фальшувальник проти детектива
- Дифузійні моделі: як із чистого шуму постає зображення
- Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
- Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
- Policy gradient і PPO: навчання безпосередньо політики
- Як працює ШІ-агент: мовна модель у циклі з інструментами
- Програмування з AI-агентами: завдання, тести й перевірка
- Оцінювання і безпека систем ШІ: як вимірювати і як стежити
Повна програма серії Готово: 52 з 83 тем
- Як частинка рою поєднує інерцію, власне найкраще місце і найкраще місце рою.
- Чому важать інерція і рівновага складових і коли рій заспокоюється.
- Чому не існує оптимізатора, найкращого для всього, і на що зважати в алгоритмах, «натхненних природою».
Що варто знати заздалегідь: Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
Зграя шпаків над вечірнім містом переливається, мов одна жива істота, — і при цьому не має ватажка. Кожен птах стежить лише за кількома найближчими сусідами. 1995 року соціальний психолог Джеймс Кеннеді та інженер-електрик Расселл Еберхарт поставили собі запитання: а що, якби птахи, окрім положення сусідів, передавали одне одному ще й те, де знайшли найбільше їжі? З їхньої симуляції народився один із найпростіших і найуживаніших оптимізаційних алгоритмів узагалі — оптимізація роєм частинок (particle swarm optimization, PSO).
Вона продовжує частини Еволюційні стратегії і генетичне програмування і Оптимізація мурашиною колонією. Випустимо рій на ту саму функцію Растригіна, що й еволюційну стратегію, з тим самим стартом і бюджетом.
1. Зграї в природі та в комп’ютері
Ще 1987 року Крейг Рейнольдс показав, що для правдоподібного руху зграї досить трьох локальних правил. Його «боїди» уникають зіткнень із найближчими сусідами, вирівнюють із ними напрям польоту і тримаються біля центру групи. Ніхто не керує цілим; форма зграї виникає з локальних правил. Кеннеді з Еберхартом додали четверту річ — пам’ять про добрі місця — і з анімації вийшов оптимізатор.
Означення — три правила боїдів (спрощено)
Рейнольдс описав правила словами; сьогодні їх зазвичай записують так. Боїд i має положення xi, швидкість vi і окіл Si — боїди, ближчі за заданий радіус. До своєї швидкості він додає зважену суму трьох векторів:
- розділення −∑j ∈ Si (xj − xi) / ‖xj − xi‖2 — відштовхування, тим сильніше, чим ближче сусід;
- вирівнювання v̄i − vi, де v̄i — середня швидкість сусідів;
- згуртованість x̄i − xi, де x̄i — середнє положення сусідів.
Отже, кожен боїд використовує лише інформацію зі свого околу. Рівняння PSO нижче мають ту саму форму «швидкість ← швидкість + тяжіння до цілей», тільки цілями є не сусіди, а найкращі знайдені місця.
2. Алгоритм
Означення — оптимізація роєм частинок
Мінімізуємо f : ℝn → ℝ. Рій складається з N частинок; частинка i має положення xi, швидкість vi і своє досі найкраще положення pi. Рій знає найкраще положення з усіх, g. На кожній ітерації для кожної частинки:
vi ← w · vi + c1 r1 (pi − xi) + c2 r2 (g − xi),
xi ← xi + vi,
де r1, r2 — випадкові числа з [0, 1), які розігрують для кожної координати окремо. Якщо f(xi) < f(pi), оновлюється pi, а можливо, і g.
Звичні значення (Клерк і Кеннеді, 2002): w = 0,7298, c1 = c2 = 1,49618.
Кожна частинка — це птах, що летить над краєвидом і пам’ятає, де йому було найкраще. Крім того, він чує, де найкраще було всій зграї. Його наступний крок — компроміс трьох речей: летіти далі, куди летів, повернутися до свого найкращого місця і взяти курс на найкраще місце зграї. Випадкові числа r забезпечують, що кожен птах укладе цей компроміс трохи інакше.
vi ← w · vi + c1 r1 (pi − xi) + c2 r2 (g − xi)
- vi ліворуч
- нова швидкість — на стільки частинка зсунеться в цьому кроці (xi ← xi + vi); рій керує не положенням напряму, а через швидкість, і завдяки цьому рух плавний
- w · vi
- інерція — частина старої швидкості залишається; w < 1 водночас її гасить, щоб рух із часом заспокоївся
- c1 r1, c2 r2
- сила тяжіння — c задає середню силу, випадкове r з [0, 1) щоразу по-іншому її вкорочує, тож частинка не приземляється точно в ціль і дорогою пробує й місця довкола
- pi − xi
- вектор від частинки до її найкращого місця — що воно далі, то сильніше тягне частинку назад (як пружина)
- g − xi
- вектор до найкращого місця рою — єдиний канал, яким до частинки доходить чужий досвід
Означення — обмеження швидкості
Після обчислення кожну координату швидкості обрізають до інтервалу [−vmax, vmax]: vid ← min(vmax, max(−vmax, vid)). Наша реалізація бере vmax = 5,12, тобто половину ширини квадрата пошуку [−5,12; 5,12]2 — частинка не перелетить за один крок більше ніж пів мапи.
Приклад — один крок однієї частинки
Частинка стоїть у x = (4,2; −3,8) зі швидкістю v = (0,5; 0,4). Її найкраще місце — p = (4,0; −3,1), найкраще місце рою — g = (1,1; −2,0). Випали випадкові числа r1 = (0,6; 0,3) і r2 = (0,5; 0,8). Перша координата:
- інерція 0,7298 · 0,5 = 0,365,
- когнітивна 1,49618 · 0,6 · (4,0 − 4,2) = −0,180,
- соціальна 1,49618 · 0,5 · (1,1 − 4,2) = −2,319,
- нова швидкість 0,365 − 0,180 − 2,319 = −2,134, нове положення 4,2 − 2,134 = 2,066.
Друга координата так само: 0,292 + 0,314 + 2,154 = 2,761, нове положення −3,8 + 2,761 = −1,039. Обидві складові швидкості менші за vmax, обмеження не спрацьовує. Значення функції (Растригіна, див. нижче) знизилося з 45,90 до 6,51. Соціальна складова тут найбільша, бо g далеко; когнітивна мала, бо p лежить зовсім поруч із частинкою.
import random
def pso(f, n, castic=40, iteraci=200, w=0.7298, c1=1.49618, c2=1.49618):
x = [[random.uniform(-5, 5) for _ in range(n)] for _ in range(castic)]
v = [[0.0] * n for _ in range(castic)]
p = [xi[:] for xi in x] # найкраще місце кожної частинки
g = min(p, key=f)[:] # найкраще місце рою
for _ in range(iteraci):
for i in range(castic):
for d in range(n):
v[i][d] = (w * v[i][d]
+ c1 * random.random() * (p[i][d] - x[i][d])
+ c2 * random.random() * (g[d] - x[i][d]))
x[i][d] += v[i][d]
if f(x[i]) < f(p[i]):
p[i] = x[i][:]
if f(p[i]) < f(g):
g = p[i][:]
return g
Вартість алгоритму вимірюють кількістю обчислень f — у справжніх задачах кожне дороге (симуляція, навчання моделі). Кожну частинку оцінюють на старті, а потім один раз за ітерацію, разом N + N · T = 40 + 40 · 200 = 8 040 для N = 40 частинок і T = 200 ітерацій. (Псевдокод вище для наочності викликає f кілька разів; справжня реалізація запам’ятовує значення f(pi).)
3. Три сили
- Інерція w · v — частинка не хоче різко змінювати напрям. Завдяки їй рій перелітає мілкі ямки, замість падати в кожну.
- Когнітивна складова c1 r1 (p − x) — власний досвід: «там мені було добре». Зберігає різноманітність, бо кожна частинка пам’ятає щось інше.
- Соціальна складова c2 r2 (g − x) — досвід рою: «там найкраще, що будь-хто знайшов». Стягує рій докупи.
На відміну від генетичних алгоритмів, тут ніхто не вмирає і ніщо не схрещується. Інформація поширюється лише завдяки тому, що частинки бачать чужий успіх. А на відміну від еволюційних стратегій, частинка має швидкість — імпульс, який несе її далі, навіть коли саме не щастить.
4. Рій на функції Растригіна
Функція Растригіна з минулої частини: чаша з правильною сіткою ямок, глобальний мінімум у початку координат. 40 частинок стартують навколо точки (4,2; −3,8), де f ≈ 45,9, — там, де стартувала еволюційна стратегія:
Означення — функція Растригіна
Для x = (x1, …, xn) ∈ [−5,12; 5,12]n
f(x) = 10n + ∑d=1n (xd2 − 10 cos(2πxd)).
Глобальний мінімум — f(0, …, 0) = 0; локальні мінімуми лежать поблизу кожної точки з цілими координатами, у межах квадрата їх у двох вимірах 11 · 11 = 121.
f(x) = 10n + ∑d (xd2 − 10 cos(2πxd))
- f(x)
- значення, яке рій мінімізує, — тестовий краєвид, мінімум якого ми знаємо, тож уміємо розпізнати успіх
- 10n
- зсув — у початку координат косинус дорівнює 1 і кожна координата дає −10; цей член це вирівнює, щоб мінімум мав значення рівно 0
- ∑d
- сума за координатами — кожна робить внесок незалежно, тож кількість ямок зростає з вимірністю експоненційно (11n)
- xd2
- чаша — загальний нахил до початку координат; без неї всі ямки були б однаково глибокі й жодного глобального мінімуму не було б
- − 10 cos(2πxd)
- хвилястість із періодом 1 — видовбує ямку біля кожного цілого числа, а амплітудою 10 робить їх досить глибокими, щоб локальний метод у них застряг
Приклад — значення в стартовій точці
Для x = (4,2; −3,8): cos(2π · 4,2) = cos(8,4π) = cos(0,4π) ≈ 0,309 і cos(2π · (−3,8)) = cos(7,6π) = cos(1,6π) ≈ 0,309. Отже,
f = 20 + (17,64 − 3,090) + (14,44 − 3,090) = 20 + 14,550 + 11,350 ≈ 45,9.
Старт лежить на схилі ямки біля (4; −4), де f = 20 + (16 − 10) + (16 − 10) = 32; справжнє дно на волосину ближче до початку координат, зі значенням близько 31,84. Значення 31,9 після першої ітерації (нижче) отже означає, що рій з’їхав майже на дно стартової ямки. Далі до мінімуму він дістанеться лише через гребені між ямками.
Після першої ітерації найкраще місце рою має значення 31,9. Потім відбувається те, чого еволюційна стратегія не робила: рій розлітається. Розкид частинок зростає з 0,7 до 1,3 на десятій ітерації — частинки проскакують свої найкращі місця й дорогою відкривають нові ямки. На 25-й ітерації найкраще місце має значення 1,06, за одну ямку від мінімуму, а на 50-й ітерації рій знаходить глобальний мінімум. Потім він стягується до нього.
Означення — розкид рою та успішний запуск
Розкид рою — це корінь із середнього квадрата відстані частинок від їхнього центру мас x̄ = (1/N) ∑i xi:
σ = √( (1/N) ∑i=1N ‖xi − x̄‖2 ).
Запуск знайшов глобальний мінімум, якщо наприкінці f(g) < 0,01. Найближчі локальні мінімуми мають значення близько 1 (тому 1,06 на 25-й ітерації означає «сусідня ямка»), тож цей поріг чітко їх відрізняє.
σ = √( (1/N) ∑i ‖xi − x̄‖2 )
- σ
- одне число для «наскільки рій розлетівся» — в одиницях координат, тож його можна порівняти з відстанню між ямками (1)
- (1/N) ∑i
- середнє за частинками — результат не залежить від розміру рою
- ‖xi − x̄‖2
- квадрат відстані від центру мас — міряємо від центру рою, а не від мінімуму, бо нас цікавить форма рою, а не те, де він; квадрат надає більшої ваги віддаленим розвідникам, а корінь потім повертає початкові одиниці
Трасування того самого запуску за ітераціями:
| Ітерація | Найкраще значення f(g) | Розкид σ |
|---|---|---|
| 1 | 31,927 | 0,70 |
| 2 | 31,927 | 0,74 |
| 3 | 31,927 | 0,53 |
| 5 | 25,625 | 0,75 |
| 10 | 5,904 | 1,29 |
| 25 | 1,064 | 1,01 |
| 50 | 0,007 | 0,96 |
| 100 | < 0,001 | 0,51 |
| 200 | < 0,001 | 0,28 |
Чотири ітерації найкраще значення не зрушує, а рій тим часом стягується в стартову ямку (на третій ітерації σ лише 0,53); потім інерція і тяжіння до g знову його розтягують, і найкраще значення падає від ямки до ямки — 31,9, 25,6, 5,9, 1,06. Мінімум знайдено на 50-й ітерації, але σ тоді ще 0,96: довкола мінімуму рій згортається лише згодом.
Зі ста запусків із різними зернами рій знайшов глобальний мінімум у 97 — з бюджетом 8 040 обчислень. Еволюційна стратегія (15, 100) з 8 000 обчислень тієї самої задачі досягла успіху в 32 випадках. Коли рій стартує не з кута, а розподіленим по всьому квадрату, він успішний в усіх ста.
5. Інерція і рівновага сил
Що станеться, якщо змінити лише інерцію? Графік показує, наскільки далеко одна від одної частинки (вертикальна вісь логарифмічна):
З w = 0,4 рій стискається в одну точку, перш ніж устигне роззирнутися, — застрягає в ямці зі значенням 24,9. З w = 0,9 він увесь час лишається розлетілим: мінімум знаходить, але ніколи довкола нього не згортається і не доводить його до ладу. Зі ста запусків для кожного налаштування:
| Налаштування | Знайшов мінімум | Середнє найкраще значення |
|---|---|---|
| w = 0,7298, c1 = c2 = 1,49618 | 97 зі 100 | 0,18 |
| w = 0,9 | 93 зі 100 | 0,003 |
| w = 0,4 | 0 зі 100 | 24,2 |
| лише соціальна (c1 = 0) | 55 зі 100 | 3,0 |
| лише когнітивна (c2 = 0) | 0 зі 100 | 18,6 |
Без соціальної складової рій — це лише сорок самотніх альпіністів, які нічого не знають одне про одного, — жоден не вибереться з кута. Без когнітивної всі женуться за єдиним ватажком і половину часу застрягають разом із ним. Лише обидві складові разом дають рівновагу між дослідженням і використанням, яку ми вже зустрічали при відпалі.
6. Чому рій не шаленіє
Швидкість увесь час додається. Чому вона не зростає до нескінченності? Відповідь дає аналіз однієї частинки, якщо на мить забути про випадковість.
Теорема — стійкість частинки
Розгляньмо одновимірну частинку зі сталими p і g та замість c1r1, c2r2 — сталі числа із сумою φ. Тоді положення підлягає лінійній рекурентності
xt+1 = (1 + w − φ) xt − w xt−1 + const,
і частинка збігається (до зваженого середнього p і g) тоді й лише тоді, коли |w| < 1 і 0 < φ < 2 (1 + w).
Частинка поводиться як тягарець на пружині із загасанням: її притягує точка між її власним і роєвим найкращим місцем, інерція проносить її повз цю точку, а потім знову назад. Якщо загасання достатнє, а пружина не надто жорстка, коливання зменшуються і частинка заспокоюється. Зі значеннями w = 0,7298 і c1 + c2 ≈ 2,99 умова виконується (2 · 1,7298 ≈ 3,46), тож рій поступово згортається — але досить повільно, щоб дорогою роззирнутися. До того ж швидкість зазвичай обмежують згори, щоб частинка не вилетіла з області пошуку.
Доведення — звідки беруться рекурентність і умови
Без випадковості одновимірний крок — це vt+1 = wvt + φ1(p − xt) + φ2(g − xt) і xt+1 = xt + vt+1. Позначмо φ = φ1 + φ2 і P = (φ1p + φ2g)/φ (зважене середнє обох найкращих місць). Тоді φ1(p − x) + φ2(g − x) = φ(P − x), і після підстановки vt = xt − xt−1:
xt+1 = (1 + w − φ) xt − w xt−1 + φP.
Відхилення et = xt − P задовольняє ту саму рекурентність без сталої, тож et = aλ1t + bλ2t, де λ1,2 — корені характеристичного рівняння λ2 − (1 + w − φ)λ + w = 0. Частинка заспокоюється в P тоді й лише тоді, коли |λ1|, |λ2| < 1. Для квадратного рівняння λ2 + aλ + b = 0 це буває саме тоді, коли |b| < 1 і 1 ± a + b > 0 (критерій Джурі). Тут b = w, a = −(1 + w − φ):
- |w| < 1,
- 1 − (1 + w − φ) + w = φ > 0,
- 1 + (1 + w − φ) + w = 2(1 + w) − φ > 0. ∎
xt+1 = (1 + w − φ) xt − w xt−1 + φP
- xt+1
- наступне положення — залежить від двох попередніх, бо швидкість є різницею двох положень; тому частинка поводиться як коливне тіло, а не як куля, що котиться схилом
- (1 + w − φ) xt
- поточне положення, зсунуте інерцією (+w) і стягнуте притяганням (−φ), — двобій «летіти далі» проти «повернутися»
- − w xt−1
- пам’ять про попередній крок — цей член приносить імпульс; його коефіцієнт w — добуток коренів, і тому загасання визначає саме інерція
- φP
- якір — притягання зваженого середнього p і g; довкола нього частинка коливається і в ньому заспокоюється
Як швидко вона заспокоїться? Для звичних φ обидва корені виходять комплексними (частинка коливається) і мають однаковий модуль √w, бо їхній добуток дорівнює w. Амплітуда відхилення, отже, на кожній ітерації множиться на √w і зменшується вдвічі за ln 2 / (−ln √w) ітерацій. Із середнім φ = (c1 + c2)/2 = 1,49618 (випадкове r має середнє ½):
| Інерція w | Загасання за ітерацію √w | Період напіврозпаду відхилення |
|---|---|---|
| 0,4 | 0,632 | 1,5 ітерації |
| 0,7298 | 0,854 | 4,4 ітерації |
| 0,9 | 0,949 | 13,2 ітерації |
Це точно відповідає графіку розкиду вище: з w = 0,4 рій згортається за кілька ітерацій, з w = 0,9 коливання стихають десятки ітерацій. Це спрощення — справжні r розігрують на кожному кроці, а p, g змінюються, — але порядок сходиться. І увага: з w = 0,4 межа 2(1 + w) = 2,8 менша за найбільше можливе φ = c1 + c2 ≈ 2,99, тож надзвичайно сильне випадкове тяжіння на один крок розгойдує частинку (загасання 1,280 > 1).
7. Хто кого чує: топологія
Означення — топологія рою
Топологія — це граф, який визначає, чиї найкращі місця бачить частинка. У глобальній топології (gbest) кожна бачить усіх, і g спільне. У кільцевій (lbest) частинки лежать у кільці, і частинка i бачить лише i − 1, i та i + 1; замість g вона використовує найкраще місце свого околу.
У глобальній топології кожен одразу знає про найкращу знахідку — рій швидкий, але легко дає одному щасливчику затягти себе в локальний мінімум. У кільці новина поширюється від сусіда до сусіда; різні частини рою тим часом досліджують різні місця. Повільніше, зате обережніше.
Формально кожна частинка i має окіл S(i) і в правилі швидкості замість спільного g використовує gi = pk, де k = arg minj ∈ S(i) f(pj). Глобальна топологія має S(i) = {1, …, N}, кільцева S(i) = {i − 1, i, i + 1} (індекси за модулем N). Скільки ітерацій минає, доки новина про нову знахідку дійде до всіх? У глобальній топології одна. У кільці вона просувається за ітерацію щонайбільше на одного сусіда в кожен бік, а найвіддаленіша частинка в кільці з 40 частинок розташована за 20 місць — новина дійде до неї щонайраніше за 20 ітерацій. Стільки часу віддалені частини рою можуть досліджувати самостійно.
На нашій двовимірній задачі кільце знайшло мінімум в усіх 100 запусках, глобальна топологія — у 97. Різниця помітніша в десяти вимірах, де ямок астрономічно багато: після 2 000 ітерацій глобальна топологія закінчила в середньому на значенні 5,84, кільцева — на 4,57. Глобального мінімуму не знайшла жодна — десятивимірна функція Растригіна для 40 частинок справді важка.
8. Обережно з метафорами
Теорема — безкоштовних обідів не буває (Вулперт і Макреді, 1997)
Усереднені за всіма можливими цільовими функціями на скінченній множині, усі алгоритми, які не обчислюють ту саму точку двічі, мають однакову очікувану ефективність.
Точніше: нехай X і Y — скінченні множини, f : X → Y — цільова функція, а dmy — послідовність значень, які алгоритм побачить під час m різних обчислень. Тоді для будь-яких двох алгоритмів a1, a2
∑f P(dmy | f, m, a1) = ∑f P(dmy | f, m, a2),
де сума береться за всіма |Y||X| функціями. Отже, кожна міра ефективності, що залежить лише від побачених значень (наприклад, найкращого знайденого), має за всіма функціями однакове середнє.
Універсально найкращого оптимізатора не існує. Алгоритм, що блищить на одному типі задач, мусить бути гіршим деінде. Рій чудово справляється з гладкими функціями з правильною структурою, як-от функція Растригіна; на задачі комівояжера без доробок він би не встояв.
Після успіху мурах і рою прорвало греблю алгоритмів, «натхненних природою»: світлячки, зозулі, кажани, сірі вовки, гармонія в джазовому гурті. Кеннет Серенсен 2015 року звернув увагу, що багато з них — старі ідеї в новому костюмі: метафора замінила математичний опис і ускладнила порівняння. Тож добре запитання до кожного нового алгоритму звучить не «чим він натхненний», а «що він робить інакше, ніж відомі, і на чому це видно».
9. Рої на практиці
- Налаштування параметрів. PSO популярна там, де параметрів мало, градієнт невідомий, а одне обчислення — це симуляція: налаштування регуляторів, форма антен, керування енергомережами чи гіперпараметри моделей машинного навчання.
- Роботи в рої. У Гарварді 2014 року 1 024 маленькі роботи Kilobot за локальними правилами склали задані фігури — без центрального керування, лише спілкуючись із сусідами.
- А як щодо дронів на феєрверках? Світлові шоу з тисячами дронів — це не ройовий інтелект: кожен дрон летить заздалегідь обчисленою траєкторією з центрального плану. Рій у справжньому сенсі ухвалює рішення сам, за сусідами.
10. Підсумок
- Частинка в PSO змінює швидкість відповідно до інерції, власного найкращого місця і найкращого місця рою.
- На функції Растригіна рій знайшов мінімум у 97 зі 100 запусків — еволюційна стратегія з тим самим стартом і бюджетом у 32.
- Інерція визначає, як довго рій досліджує: мала змушує його передчасно стиснутися, велика не дає довести результат до ладу. Без соціальної, як і без когнітивної складової рій зазнає невдачі.
- Частинка схожа на пружину із загасанням; для |w| < 1 і 0 < φ < 2(1 + w) вона заспокоюється.
- Кільцева топологія поширює інформацію повільніше і на важких задачах буває надійнішою; а за теоремою про відсутність безкоштовних обідів оптимізатора, найкращого для всього, не існує.
Хочете спробувати самі? Попросіть ШІ-агента написати PSO з візуалізацією рою, дайте йому власний краєвид — скажімо, функцію з двома віддаленими долинами — і стежте, чи рій розділиться.
Маєте іншу думку? Напишіть на support@coden-app.com.