Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях

Стигмергія, дослід із подвійним мостом, мурашина система Доріго, роль параметрів α, β і ρ та вдосконалені варіанти — на маршруті через обласні центри Чехії і на 60 містах, у порівнянні з відпалом.

13 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 29 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Окрема мурашка не має мапи, не вміє рахувати й бачить ледве на кілька сантиметрів уперед. Колонія проте надійно знаходить найкоротший шлях від мурашника до їжі. Жодна мурашка його не знає — він виникає з того, як усі разом позначають місцевість. На початку дев’яностих Марко Доріго з Міланської політехніки помітив, що той самий трюк можна застосувати до задачі комівояжера. Так виникла оптимізація мурашиною колонією, а з нею й ціла галузь ройового інтелекту.

Стаття продовжує частину Локальний пошук та імітація відпалу. Розв’язуємо ту саму задачу — маршрут через обласні центри з оптимумом 1 060,4 км —, тож побачимо, як мурахи впораються проти відпалу.

1. Спілкування через слід

Означення — стигмергія

Стигмергія — це непряме спілкування через середовище: особина змінює середовище, і ця зміна впливає на те, що згодом зроблять інші (або вона сама). Поняття запровадив П’єр-Поль Грассе 1959 року, вивчаючи будівництво термітників.

2. Дослід із подвійним мостом

1989 року Ґосс, Денебур і їхні колеги збудували аргентинським мурахам між мурашником і їжею два мости — один удвічі довший за інший. Згодом більшість колонії ходила коротшим. Чому? Мурашка, яка обрала коротку гілку, дістається їжі раніше, а коли повертається, коротка гілка біля їжі вже позначена. Короткий шлях позначається швидше й починає вигравати.

Означення — модель вибору гілки (Денебур та ін.)

Якщо на початку на короткій і довгій гілці є кількості феромону A і B, мурашка обирає коротку гілку з імовірністю

P = (k + A)^h / ((k + A)^h + (k + B)^h),

де k визначає, як сильно мурашка реагує на слабкий слід, а h > 1 підсилює різниці. Мурашка відкладає феромон на початку обраної гілки і на її кінці, коли туди дістанеться.

P = (k + A)^h / ((k + A)^h + (k + B)^h)

P

імовірність, що наступна мурашка піде короткою гілкою — мурашка вирішує не напевно, лише з вагою; довга гілка дістає решту 1 − P

A

феромон на короткій гілці — єдине, що мурашка «знає» про шлях; що більше його там, то сильніше тягне коротка гілка

B

феромон на довгій гілці — у знаменнику він змагається з короткою, тож вирішує відношення слідів, а не їхня абсолютна кількість

k

«поріг уваги» — додається до обох гілок однаково, тож кілька перших молекул феромону майже не змінюють відношення; без нього за всю колонію вирішила б перша мурашка

h

підсилювач — степінь, більший за 1, перебільшує різницю; саме він робить із малої випадкової переваги додатний зворотний зв’язок

Приклад — як вирішують k = 30 і h = 2

На короткій гілці A = 20, на довгій B = 10 одиниць феромону:

P = (30 + 20)² / ((30 + 20)² + (30 + 10)²) = 2 500 / (2 500 + 1 600) = 2 500 / 4 100 ≈ 0,610.

• Однакові сліди (A = B, скажімо обидва нульові): P = 0,500 — чиста випадковість.
• П’ять одиниць проти нуля: P = 35² / (35² + 30²) ≈ 0,576 — малий слід майже нічого не вирішує, це робота k.
• A = 60, B = 10: P = 8 100 / (8 100 + 1 600) ≈ 0,835 — уже явна перевага.
• Без підсилення (h = 1) при A = 20, B = 10 вийшло б лише 50 / 90 ≈ 0,556 замість 0,610.

Симуляція моделі (k = 30, h = 2, десять мурах за крок, коротка гілка 5 кроків, довга 10) показує частку феромону на короткій гілці у восьми колоніях:

Сім колоній усталилися на короткій гілці, одна — на довгій: кілька перших мурах випадково обрали довгу гілку, і додатний зворотний зв’язок її «замкнув». Зі ста колоній 85 закінчили на короткій гілці і 9 на довгій. Коли обидві гілки однаково довгі, колонії діляться приблизно навпіл (46 і 42) — симетрію порушує випадок. Довжина шляху, отже, зсуває результат, але не гарантує його. Ту саму слабкість побачимо в алгоритмі.

3. Мурашина система

Мурашина система Доріго (Ant System, 1992) посилає віртуальних мурах графом міст. Кожна будує цілий маршрут і, залежно від того, наскільки він короткий, відкладає феромон на його ребрах.

Означення — маршрут і його довжина

Задано n міст і відстані d_ij = d_ji > 0. Маршрут — це порядок міст π = (π₁, …, π_n), у якому кожне місто трапляється рівно один раз; його довжина —

L(π) = d_π1π2 + d_π2π3 + … + d_πnπ1

— останній доданок повертає мандрівника додому. Ребро (i, j) належить маршруту, якщо i і j йдуть у ньому безпосередньо одне за одним. Задача комівояжера шукає маршрут найменшої довжини.

Означення — правило переходу

Мурашка в місті i іде до ще не відвіданого міста j з імовірністю

p_ij = τ_ij^α · η_ij^β / ∑_l τ_il^α · η_il^β,

де τ_ij — феромон на ребрі, η_ij = 1 / d_ij — видимість (близькі міста привабливіші), а сума береться за всіма невідвіданими містами l. Параметри α і β зважують слід проти відстані.

p_ij = τ_ij^α · η_ij^β / ∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

імовірність кроку з i до j — ми тягнемо жереб, а не обираємо найкраще, щоб колонія весь час пробувала й інші маршрути

τ_ij^α

пам’ять колонії — феромон несе досвід попередніх мурах; показник α каже, наскільки йому довіряти (α = 0 вимикає його повністю)

η_ij^β

жадібність — η = 1 / d надає перевагу близьким містам; це порада, яку маємо задарма вже з першої ітерації, коли феромон ще нічого не знає

∑ … за N_i

сума ваг усіх ще не відвіданих міст — діленням ваги перетворюються на ймовірності із сумою 1; відвіданих міст у ній немає, тож мурашка до них не повертається

Приклад — одне рішення мурашки

Мурашка стоїть у місті i, і їй лишилося три міста: на відстані 50, 100 і 150 км, із феромоном τ = 1, 3 і 2. Стала у видимості в дробі скорочується, тож рахуймо з η = 100 / d, тобто 2, 1 і 2/3. При α = 1 і β = 3:

• ваги: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• їхня сума 11,593;
• імовірності 0,690, 0,259 і 0,051.

Виграє найближче місто, хоча має найменше феромону. При β = 1 вийшло б 0,316, 0,474 і 0,211 — веде феромон. А при β = 0 вирішує лише слід: 0,167, 0,500 і 0,333 (частки 1 : 3 : 2).

Означення — оновлення феромону

Після кожної ітерації феромон усюди вивітрюється, і кожна мурашка m додає на ребра свого маршруту довжини L_m кількість, пропорційну 1 / L_m:

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ маршрут m} Q / L_m,

де ρ ∈ (0, 1) — швидкість вивітрювання.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ маршрут m} Q / L_m

τ_ij ліворуч

новий феромон на ребрі — те, за чим вирішуватимуть мурахи наступної ітерації

(1 − ρ)

вивітрювання — кожна ітерація забирає з кожного сліду ту саму частку ρ; старий досвід так слабне геометрично, і колонія може перевчитися

τ_ij праворуч

дотеперішній феромон — пам’ять лише виправляється, а не починається з нуля

∑_m

сума за мурахами, які пройшли ребром — кожна мурашка додає лише на ребра свого маршруту; ребро, яким пройде більше мурах, дістане більше — тут підраховується «голосування» колонії

Q / L_m

винагорода, обернено пропорційна довжині маршруту — коротший маршрут = сильніший слід; стала Q лише задає масштаб

Приклад — одне оновлення

Ребро має τ = 1, ρ = 0,3, Q = 1 000, і ним пройшли дві мурашки з маршрутами завдовжки 1 100 і 1 300 км:

τ ← 0,7 · 1 + 1 000 / 1 100 + 1 000 / 1 300 ≈ 0,700 + 0,909 + 0,769 = 2,378.

Ребро, яким ніхто не пройшов, має після тієї самої ітерації лише 0,7. Мурашка з коротшим маршрутом додала більше (0,909 проти 0,769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # вивітрювання
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # коротший маршрут, сильніший слід
            tau[b][a] += Q / L

Уся мурашина система потім лише чергує побудову маршрутів і оновлення та пам’ятає найкращий маршрут, який будь-коли будь-хто збудував:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # на початку всюди однаково
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # вивітрювання + новий слід
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Мурахи на обласних центрах

Випустімо 13 мурах (з кожного міста одну) на 100 ітерацій з α = 1, β = 3 і ρ = 0,3. Мапа показує феромон на ребрах після 1-ї, 5-ї, 20-ї і 100-ї ітерації — що товща лінія, то більше феромону:

У першій ітерації слід розподілений майже всюди, і найкращий маршрут має 1 292,6 км. Уже в п’ятій ітерації одна з мурах знаходить оптимум 1 060,4 км. Феромон потім зосереджується на ребрах добрих маршрутів — слабкі лінії зникають, сильні лишаються, — а пересічна мурашка будує маршрут завдовжки приблизно 1 250 км. Колонія не збігається повністю, вона весь час трохи пробує.

Перебіг запуску за ітераціями — найкращий досі знайдений маршрут і середній маршрут тринадцяти мурах у даній ітерації:

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

Не завжди все закінчується так добре. З двадцяти запусків із різними зернами оптимум знайшли лише 7, середнє було 1 073,9 км, а найгірший результат 1 083,0 км. Відпал на тій самій задачі з результатом 98 зі 100 був надійнішим. Для порівняння: жадібний «найближчий сусід», який завжди йде до найближчого невідвіданого міста, дає залежно від старту від 1 120 до 1 336 км. Мурахи помітно кращі, але базова мурашина система сама по собі не чемпіон — тому й виникли її вдосконалені варіанти.

5. Навіщо α, β і ρ

На тринадцяти містах багато можна розв’язати й без феромону. Різницю покаже лише більша задача — ті самі 60 випадкових міст, що й у частині про відпал, 30 мурах, 150 ітерацій, середнє з трьох запусків:

• Без феромону (α = 0) мурахи — лише випадкові жадібні мандрівники й нічого не навчаються — маршрути на третину довші.
• Без відстаней (β = 0) колонії нема від чого відштовхнутися: перші маршрути цілком випадкові, і феромон із них веде до наступних випадкових.
• Повільне вивітрювання надто довго тримає сліди перших, поганих маршрутів, і колонія вчиться повільно. Швидке вивітрювання, навпаки, забуває й добре.

Як довго колонія пам’ятає, можна обчислити точно. Досить стежити за одним ребром.

Теорема — усталений феромон і період напіввивітрювання

Якщо ребро в кожній ітерації дістає той самий приріст Δ ≥ 0, тобто τ_t+1 = (1 − ρ) τ_t + Δ, то

τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ) → Δ/ρ при t → ∞.

Без приросту (Δ = 0) слід спадає до половини за t_½ = ln 2 / (−ln(1 − ρ)) ітерацій.

Доведення. Віднявши Δ/ρ від обох боків рекурентного співвідношення, дістанемо τ_t+1 − Δ/ρ = (1 − ρ)(τ_t − Δ/ρ), бо (1 − ρ)Δ/ρ + Δ = Δ/ρ. Відхилення від Δ/ρ тож щоітерації множиться на число 1 − ρ ∈ (0, 1) і геометрично спадає до нуля. Період напіввивітрювання — розв’язок рівняння (1 − ρ)^t = ½. ∎

τ^* = Δ / ρ

τ^*

рівень, на якому усталюється феромон ребра — додавання і вивітрювання врівноважені

Δ

скільки ребро дістає за ітерацію — ребра з частих і коротких маршрутів мають велике Δ, а тому й високий рівень

ρ

у знаменнику: повільне вивітрювання дає слідам вирости високо, і різниці між ребрами вирівнюються довго; швидке тримає їх низько й залежними лише від кількох останніх ітерацій

Ребро з τ₀ = 1 і ρ = 0,3: одне дістає в кожній ітерації Δ = 1, другим ніхто не користується.

Використовуване ребро наближається до 1/0,3 ≈ 3,33, невикористовуване за десять ітерацій падає нижче трьох сотих. Період напіввивітрювання для рядків таблиці вище: при ρ = 0,3 це 1,94 ітерації, при ρ = 0,02 цілих 34,31 ітерації — сліди перших випадкових маршрутів, отже, панують ще десятки ітерацій, — а при ρ = 0,9 лише 0,30 ітерації, тож колонія пам’ятає практично лише останній раунд.

Найкраще налаштування дало від 2 194 до 2 314 км — порівнянно з відпалом із попередньої частини, який на тих самих містах закінчив між 2 210 і 2 270 км.

6. Кращі мурахи

• Елітна стратегія додає додатковий феромон на досі найкращий маршрут, щоб він не загубився.
• MAX–MIN Ant System (Штюцле і Гоос, 2000) дозволяє відкладати феромон лише найкращій мурашці й тримає τ між нижньою і верхньою межею. Нижня межа гарантує, що жодне ребро повністю не зникне, і колонія так передчасно не застигне — як та, що в досліді з мостом закінчила на довгій гілці.
• Ant Colony System (Доріго і Гамбарделла, 1997) з певною ймовірністю обирає одразу найкраще ребро і забирає феромон уже під час побудови маршруту, щоб інші мурахи пробували деінде.
• Локальний пошук. На практиці кожен маршрут, збудований мурашкою, ще доводять ходами 2-opt із частини про відпал. Мурахи знаходять добру ділянку, сходження на пагорб її доточує — у дев’яностих ця комбінація належала до найкращих методів для задачі комівояжера.

Означення — елітна стратегія і MAX–MIN Ant System

Елітна стратегія додає до звичайного оновлення ще e · Q / L^best на кожне ребро досі найкращого маршруту довжини L^best; e — кількість «елітних мурах».

MAX–MIN Ant System відкладає феромон лише за одним найкращим маршрутом і обрізає результат до проміжку [τ_min, τ_max]:

τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), де Δ_ij = 1 / L^best для ребер найкращого маршруту, інакше 0.

Верхню межу Штюцле і Гоос обирають як τ_max = 1 / (ρ L^best) — рівно усталене значення Δ/ρ з теореми вище для ребра, яке щоразу лежить у найкращому маршруті. Нижня межа — мала частка верхньої; феромон до того ж на початку встановлюють на τ_max, щоб перші ітерації досліджували якомога ширше.

Означення — правила Ant Colony System

Псевдовипадкове пропорційне правило: мурашка в місті i витягує q з [0, 1). Якщо q ≤ q₀, вона йде одразу до міста з найбільшою вагою, j = arg max_{l ∈ Ni} τ_il · η_il^β; інакше обирає жеребом за правилом переходу мурашиної системи.

Локальне оновлення: одразу після переходу ребром (i, j) τ_ij ← (1 − ξ) τ_ij + ξ τ₀, тож використане ребро трохи слабне в напрямку початкового значення τ₀.

Глобальне оновлення після ітерації лише на ребрах найкращого маршруту: τ_ij ← (1 − ρ) τ_ij + ρ / L^best.

Доріго і Гамбарделла (1997) в оригінальній статті використовують q₀ = 0,9, β = 2 і ρ = ξ = 0,1 — у дев’яти кроках із десяти мурашка, отже, бере найкраще ребро і лише в десятому пробує.

7. Де працюють мурахи

• Маршрутизація в мережах. Алгоритм AntNet (Ді Каро і Доріго, 1998) посилає мережею малі пакети-мурахи, які вимірюють затримки й оновлюють таблиці маршрутизації. Мережа так безперервно пристосовується до перевантаження.
• Маршрути транспорту й розклади. Розвезення товарів, вивезення відходів чи порядок замовлень у виробництві — задачі, споріднені із задачею комівояжера, де мурашині алгоритми застосовують разом із локальним пошуком.
• Ройовий інтелект. Мурашина колонія — один із прикладів того, як із простих особин і місцевих правил виникає розумна поведінка цілого. Інший, рій частинок, — тема наступної частини.

8. Підсумок

• Мурахи спілкуються через слід у середовищі (стигмергія): коротший шлях позначається швидше, і додатний зворотний зв’язок його посилює.
• У моделі подвійного мосту 85 зі 100 колоній усталюються на короткій гілці — але випадок може замкнути й довгу.
• Мурашина система обирає наступне місто за феромоном τ^α і відстанню η^β; феромон вивітрюється зі швидкістю ρ, а короткі маршрути додають його більше.
• На обласних центрах вона знайшла оптимум, але лише в 7 із 20 запусків; на 60 містах впоралася порівнянно з відпалом. Без феромону і без відстаней — помітно гірше.
• Варіанти, що використовуються на практиці (MAX–MIN, ACS), запобігають передчасному застиганню й поєднують мурах із локальним пошуком.

Хочете спробувати самі? Попросіть ШІ-агента написати симуляцію подвійного мосту і спробуйте, що станеться, коли коротку гілку посеред досліду «закриєте», — чи зуміє колонія перейти назад на довгу?

Маєте іншу думку? Напишіть на support@coden-app.com.