Цифровой журнал «Компьютерра» № 166

Малоизвестный факт: персонажи игры Sims спроектированы по образу и подобию муравьёв. Уилл Райт, придумавший Sims, разрабатывал симулятор муравейника SimAnt, и результат настолько впечатлил его, что он решил воспроизвести удачный подход в новом проекте. Каждый предмет в игре распускает невидимые «феромоны» определённого типа: еда, энергия, гигиена, общение или развлечения. Когда у персонажа возникает какая-то потребность, он направляется по самой сильной феромонной дорожке соответствующего типа.

Один из пионеров в этой области — швейцарская компания AntOptima, в 2001 году отпочковавшаяся от располагающегося в Лугано Института Далле Молле по изучению искусственного интеллекта. За прошедшее с тех пор время она успела внедрить продукты, основанные на алгоритме муравьиной колонии, в несколько европейских компаний.

Один из крупнейших клиентов AntOptima — главная швейцарская сеть супермаркетов Migros. Муравьиный алгоритм используется для организации движения 1200 грузовиков, которые развозят товары по 600 магазинам, разбросанным по всей Швейцарии. Задача усложняется тем, что, во-первых, автопарк Migros неоднороден и состоит из трёх видов грузовиков разной вместительности и, во-вторых, часть магазинов не приспособлена для разгрузки некоторых типов грузовиков.

В AntOptima разработали замысловатую модификацию алгоритма муравьиной колонии, учитывающую все эти тонкости. Используется не один «муравейник», а два: один оптимизирует расстояние, а другой — сроки доставки. Чтобы учесть разнотипность транспорта, муравьям случайным образом присваивается один из типов грузовиков. Алгоритм запускают каждое утро, чтобы получить маршруты для каждого грузовика на весь день.

Схожая проблема стояла перед корпорацией Air Liquide, занимающейся производством сжиженных газов, используемых в промышленности и медицине. У корпорации около сотни заводов в Соединённых Штатах, ежедневно отправляющих продукцию в шесть тысяч пунктов, находящихся в разных частях континента. Для доставки применяются четыре сотни грузовиков, железная дорога и трубопроводы. Кроме того, для полноты картины нужно учитывать стоимость электроэнергии. Она не только везде своя, но ещё и постоянно меняется.

Систему, ежедневно планирующую эффективную доставку с учётом всех этих факторов, для Air Liquide написали в компании BiosGroup. Любопытный побочный эффект: идеальные маршруты оказались настолько противоестественными, что поначалу вызвали ропот у водителей. Алгоритм запросто мог отправить машину к дальнему заводу, пропустив завод, который находится рядом с клиентом. При ближайшем рассмотрении неизменно оказывалось, что прав он, а не люди: если учесть не только расстояние, но и все прочие факторы, сделать крюк бывает выгоднее.

Во France Telecom муравьиный алгоритм попытались применить для маршрутизации информации в сети. Проектом руководил эксперт в области сложных систем Эрик Бонобо. «Компьютерра» рассказывала об этом в 2004 году:

Бонобо разработал специальные программные агенты, которые могут пересылаться по сети от маршрутизатора к маршрутизатору как сообщения. Когда агент достигает маршрутизатора, он оставляет на нём особую пометку. Если там побывал не один агент, а несколько, их пометки скапливаются. Одним словом, всё как у муравьёв.

Как ни странно, этот подход сработал. И даже ошибки, которые неизбежно возникают поначалу, постепенно сами собой исчезли. «У общественных насекомых ошибки и случайное поведение не приводят к сбоям, — объясняет Бонобо. — Наоборот, делая ошибки, они добиваются успеха и отыскивают новые способы решения проблем в дополнение к старым».

Есть и другие примеры. Подражание муравьям неплохо помогает и в управлении группами автономных роботов (в этой области экспериментировал Виджай Кумар из университета Пенсильвании, сейчас более известный своими роящимися квадрокоптерами), и в борьбе с пробками на дорогах, и даже при решении некоторых задач в области искусственного интеллекта (впрочем, чему тут удивляться: специалисты подозревают, что между взаимодействиями нейронов в мозге и отдельных особей в рое есть много общего).