Як мурахи знаходять їжу?

Феромони: хімічні стікери

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

Мурахи використовують феромони так, як ми використовуємо дорожні знаки, тільки невидимо. Мураха-розвідниця блукає навмання, доки не знайде їжу. На шляху назад до гнізда вона прокладає феромонну стежку. Повідомлення, яке вона лишає, просте: «Їжа в цей бік — і ось як далеко вона».

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

Позитивний зворотний зв'язок: більше мурах → міцніша стежка

Це створює петлю позитивного зворотного зв'язку:

1. 1 Розвідниця знаходить їжу і прокладає феромонну стежку додому.
2. 2 Більше мурах ідуть стежкою, кожна додає ще феромону, повертаючись.
3. 3 Стежка стає міцнішою, приваблюючи ще більше мурах.
4. 4 Слабші стежки згасають (феромон випаровується), і мурахи їх полишають.

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

Як перемагає найкоротший шлях

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

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

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

Доведено в лабораторії: експеримент з подвійним мостом

Це не просто правдоподібна історія — її перевірили експериментально. У 1989 році команда біолога Жана-Луї Денебура з Брюссельського вільного університету провела тепер уже класичний дослід з аргентинськими мурахами (Linepithema humile). Вони з'єднали гніздо з джерелом їжі двома гілками містка: одна вдвічі довша за іншу, тож у мурах був справжній вибір між коротким і довгим маршрутом.

Спочатку, коли феромону майже не було на жодній гілці, мурахи розділялися приблизно порівну — просто випадково. Але оскільки коротка гілка вимагає меншого часу на повний оберт, мурахи, що йшли нею, поверталися додому раніше й починали підсилювати її, поки мурахи довгої гілки ще йшли шляхом. За 15–20 хвилин понад 90% руху колонії перемістилося на коротший маршрут — не тому, що якась мураха порівняла два шляхи, а тому, що феромон на коротшому шляху просто накопичувався швидше.

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

Випаровування: забування старих шляхів

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

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

Оптимізація мурашиною колонією (ACO)

У 1992 році комп'ютерний науковець Марко Доріго опублікував свою докторську дисертацію, засновану на спостереженні за мурахами. Він створив сімейство алгоритмів під назвою Оптимізація мурашиною колонією (ACO).

Достоту як справжні мурахи, віртуальні «мурахи» в комп'ютерній програмі:

• Спершу подорожують навмання, будуючи розв'язки крок за кроком
• Лишають «віртуальний феромон» на добрих розв'язках
• Частіше користуються міцнішими феромонними стежками (з певною випадковістю)
• Дають феромону випаровуватися, щоб старі розв'язки не панували вічно

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

Математика вибору стежки

Модель Денебура дає конкретну формулу того, як окрема мураха на роздоріжжі з двома стежками, що містять кількість феромону A і B, вирішує, куди йти. Спрощену версію, яку часто використовують для пояснення й симуляції, можна записати так:

P(обрати A) = Aⁿ ÷ (Aⁿ + Bⁿ)

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

Підставмо числа: припустимо, 3 ранні розвідниці повернулися стежкою A, а лише 1 — стежкою B, тобто A = 3, B = 1. При n = 2:

P(обрати A) = 3² ÷ (3² + 1²) = 9 ÷ 10 = 90%.

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

Спробуй сам

• Симуляція мурашиної колонії — Розмісти джерела їжі й спостерігай, як тисячі мурах знаходять найкоротші шляхи й збігаються до них. Налаштовуй силу феромону й швидкість випаровування.