Новое поколение алгоритмов, вдохновленных муравьями-решателями задач
Исследователи из Сиднейского университета показали, что обычные муравьи способны решать сложные математические задачи.
Результаты, опубликованные в Journal of Experimental Biology, углубляют понимание того, как даже простые животные преодолевают сложные и динамичные задачи в природе. Это поможет компьютерным ученым разработать более совершенное программное обеспечение для решения логистических проблем и повышения эффективности во многих отраслях.
Крис Рид и доцент Мадлен Бикман из Школы биологических наук совместно с профессором Дэвидом Самптером из Уппсальского университета (Швеция) протестировали, могут ли аргентинские муравьи (Linepithema humile) решить задачу динамической оптимизации. Для этого классическую математическую головоломку «Ханойские башни» превратили в лабиринт.
Алгоритмы, вдохновленные природой
Для решения подобных задач оптимизации программными средствами компьютерные ученые часто обращаются за вдохновением к муравьиным колониям, создавая алгоритмы, имитирующие их поведение. Самый распространенный из таких алгоритмов — Ant Colony Optimisation (ACO).
«Хотя эти алгоритмы и вдохновлены природой, они часто не отражают реальный мир, поскольку статичны и предназначены для решения единственной, неизменной проблемы», — говорит ведущий автор Крис Рид.
Эксперимент с «Ханойскими башнями»
Исследователи использовали версию головоломки с тремя стержнями и тремя дисками. Поскольку муравьи не могут перемещать диски, головоломку преобразовали в лабиринт, где кратчайший путь соответствовал решению с наименьшим количеством ходов. Муравьи на входе в лабиринт могли выбрать из 32 768 возможных путей к источнику пищи, только два из которых были кратчайшими и оптимальными.
Муравьям дали час на решение лабиринта, после чего исследователи блокировали пути и открывали новые участки, чтобы проверить способность муравьев к динамическому решению задач.
Результаты и адаптация
- Через час муравьи решили задачу, найдя кратчайший путь по краю лабиринта.
- Когда этот путь заблокировали, муравьи сначала обогнули препятствие, создав более длинный субоптимальный маршрут.
- Однако спустя еще час муравьи успешно перестроились, отказавшись от неоптимального пути и проложив новый оптимальный маршрут через центр лабиринта.
Роль «исследовательского феромона»
Навыки решения задач различались: муравьи, которым до теста разрешили исследовать лабиринт без пищи в течение часа, допускали меньше ошибок и быстрее находили решение по сравнению с «наивными» муравьями. Это говорит о том, что «исследовательский феромон», оставляемый муравьями при поиске на новой территории, играет ключевую роль в адаптации к меняющимся условиям.
«Даже простые муравьи, использующие массовый рекрутинг, обладают гораздо более сложными и изменчивыми навыками решения задач, чем мы думали. Вопреки прежним представлениям, феромонная система муравьев не заставляет их застревать на одном пути. Наличие по крайней мере двух отдельных феромонов дает им гораздо больше гибкости и помогает находить хорошие решения в меняющейся среде», — заключает Крис Рид.