Max Home IndustryПрежде чем вы начнете фантазировать о муравьях, сидящих за столом и планирующих, как направлять машины, я лучше скажу вам, что их муравьиные алгоритмы, отвечающие за эту задачу, не настоящие. Конечно, они все еще вдохновлены муравьями, поэтому название точное.
Если честно, это один из тех вопросов, о которых «я не совсем уверен, что и думать». Группа исследователей из Астонского университета (Великобритания) попыталась сократить выбросы и сократить время за счет оптимизации маршрутов транспортных средств доставки в городах, и им удалось добиться заявленного сокращения выбросов на 50%.
Новаторская часть подхода — использование муравьиной оптимизации. Это один из многих алгоритмов, вдохновленных биологией, которые мы часто не понимаем полностью. Полагаю, вы можете видеть, что все алгоритмы, основанные на муравьях или любых других алгоритмах, основанных на роях, происходят от полного генетического алгоритма, то есть моделируемой эволюции. Только в этом случае симуляция реальна. С течением времени стаи развиваются, позволяя отсеивать методы, которые не работают, и сохранять методы, которые работают.
В данном случае используется метаэвристический алгоритм — оптимизация колоний муравьев (ACO). В чистом ACO муравьи блуждают по ошибке и иногда находят пищу. Оставляя следы феромонов, муравьи медленно сходятся на лучшем маршруте, чтобы найти лучшую пищу. Характеристики алгоритма зависят от того, насколько быстро имитируемый феромон испаряется, заставляя исследовать новые маршруты. Например, проблема коммивояжера, аналогичная задаче маршрутизации, может быть решена путем предоставления муравьям возможности исследовать сеть, выбора городов с вероятностью, которая уменьшается с увеличением расстояния, и выбора маршрутов с высоким содержанием феромонов. Завершив путешествие, муравей затем отступает и откладывает больше феромона — больше, если путешествие было коротким, и меньше, если оно было долгим. Феромон испаряется с постоянной скоростью.
Фактически используемый алгоритм состоит в том, чтобы примерно использовать ACO для маршрутизации в небольших подсетях, а затем использовать их для построения полного маршрута. Также изменяется способ депонирования феромона — только первый край, который посещает каждый муравей. Если это расплывчато или я ошибся, то вините тот факт, что газета находится за платным доступом — постыдный способ получить прибыль и ограничить доступ к исследованиям, оплачиваемым за счет государственных средств.
Исследование очень благородное, и мы все согласны с тем, что улучшение качества воздуха — это хорошо, но использование электромобилей для таких перевозок было бы даже лучше, чем сокращение выбросов на 20%. Публичность исследования придает большое значение успеху, но ничего не говорит о том, чего могут достичь более классические методы оптимизации.
Больше информации
Методика оптимизации гибридных колоний муравьев для динамической маршрутизации транспортных средств: https://link.springer.com/chapter/10.1007/978-3-540-24854-5_5 Paywalled.
Статьи по Теме
Объявлен победитель конкурса Ants AI Challenge
Примите вызов AI Ants
Килоботы работают вместе
Искусственные муравьи
Чтобы быть в курсе новых статей на I Programmer, подпишитесь на нашу еженедельную новостную рассылку, подпишитесь на RSS-канал и подпишитесь на нас в Twitter, Facebook или Linkedin.
Комментарии
Оставьте комментарий или просмотрите существующие комментарии с помощью Disqus
или отправьте свой комментарий по адресу: comments@i-programmer.info