Як мурахи знаходять їжу?
У мурашиної колонії немає ватажка, немає GPS, немає карти — а проте мурахи надійно знаходять найкоротший шлях до їжі й назад. Секрет? Хімічна система обміну повідомленнями, настільки розумна, що комп'ютерні науковці скопіювали її для маршрутизації даних в інтернеті.
Феромони: хімічні стікери
Коли мураха йде, вона може виділяти крихітні кількості хімічної речовини під назвою феромон із залоз у своєму черевці. Інші мурахи виявляють цю речовину своїми вусиками й приваблюються до неї.
Мурахи використовують феромони так, як ми використовуємо дорожні знаки, тільки невидимо. Мураха-розвідниця блукає навмання, доки не знайде їжу. На шляху назад до гнізда вона прокладає феромонну стежку. Повідомлення, яке вона лишає, просте: «Їжа в цей бік — і ось як далеко вона».
Інші мурахи йдуть стежкою, підсилюють її новим феромоном, і незабаром між гніздом і джерелом їжі утворюється чіткий шлях.
Позитивний зворотний зв'язок: більше мурах → міцніша стежка
Це створює петлю позитивного зворотного зв'язку:
- 1 Розвідниця знаходить їжу і прокладає феромонну стежку додому.
- 2 Більше мурах ідуть стежкою, кожна додає ще феромону, повертаючись.
- 3 Стежка стає міцнішою, приваблюючи ще більше мурах.
- 4 Слабші стежки згасають (феромон випаровується), і мурахи їх полишають.
Окрема мураха не може вирішити, яка стежка найкраща. Але колонія в цілому надійно збігається до найефективнішого маршруту завдяки цьому децентралізованому процесу.
Як перемагає найкоротший шлях
Уяви два шляхи до їжі: один короткий, один довгий. Вирушає однакова кількість мурах. Мурахи, що йдуть коротшим шляхом, повертаються швидше, тож вони роблять більше повних подорожей за годину. Кожна зворотна подорож лишає більше феромону за одиницю часу.
За кілька хвилин коротший шлях накопичує більше феромону. Мурахи, обираючи, яким шляхом іти, схиляються до вищих концентрацій феромону, тож більше мурах ідуть коротким шляхом, що підсилює його ще дужче.
Зрештою, майже всі мурахи користуються найкоротшим маршрутом. Колонія знайшла мінімальний шлях, при цьому жодна мураха ніколи не міряла відстань, не робила обчислень і не зверталася до карти.
Випаровування: забування старих шляхів
Найрозумніша частина системи є водночас і найважливішою: феромони випаровуються. Якби вони цього не робили, кожен колись використаний шлях залишався б назавжди, і мурахи ніколи не пристосовувалися б до змін.
Коли їжа закінчується, мурахи перестають лишати феромон на тій стежці. Без підсилення випаровування стирає стежку за кілька годин. Тепер колонія вільна досліджувати інші напрямки.
Оптимізація мурашиною колонією (ACO)
У 1992 році комп'ютерний науковець Марко Доріго опублікував свою докторську дисертацію, засновану на спостереженні за мурахами. Він створив сімейство алгоритмів під назвою Оптимізація мурашиною колонією (ACO).
Достоту як справжні мурахи, віртуальні «мурахи» в комп'ютерній програмі:
- Спершу подорожують навмання, будуючи розв'язки крок за кроком
- Лишають «віртуальний феромон» на добрих розв'язках
- Частіше користуються міцнішими феромонними стежками (з певною випадковістю)
- Дають феромону випаровуватися, щоб старі розв'язки не панували вічно
ACO використовують для розв'язання задачі комівояжера (пошуку найкоротшого маршруту, що проходить через багато міст), складання графіків маршрутів доставки і — так — маршрутизації пакетів даних в інтернеті.
Спробуй сам
- Симуляція мурашиної колонії — Розмісти джерела їжі й спостерігай, як тисячі мурах знаходять найкоротші шляхи й збігаються до них. Налаштовуй силу феромону й швидкість випаровування.