Агентный поиск с запретами — распределенная мультиагентная метаэвристическая оптимизация
- Автор метода
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- Год
- 1989–1995
- Тип
- Hybrid metaheuristic — agent-based distributed tabu search
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Агентный поиск с запретами (ABTS) встраивает метаэвристику поиска с запретами в мультиагентную структуру, где автономные агенты запускают независимые или совместно работающие потоки поиска с запретами, обмениваясь перспективными решениями для выхода из локальных оптимумов и более эффективного коллективного исследования больших комбинаторных или непрерывных пространств поиска, чем реализация с одним потоком.
Интуиция метода
Классический поиск с запретами может застрять, исследуя узкую область, даже с механизмом кратковременной памяти. Развертывая несколько автономных агентов, каждый из которых поддерживает свой собственный список запретов и окрестность, поиск расходится по разнообразным начальным точкам. Агенты периодически обмениваются элитными решениями (интенсификация) и намеренно рассеиваются по неисследованным областям (диверсификация). Эта кооперативная, но независимая структура отражает биологическое поведение роя — ни один агент не имеет полной картины, но коллектив находит высококачественные решения гораздо быстрее, чем любой отдельный искатель.
История
Поиск с запретами был формализован Фредом Гловером в 1986–1989 годах. Распределенные и параллельные варианты появились в начале 1990-х годов, когда исследователи стремились использовать многопроцессорные архитектуры. Verhoeven и Aarts (1995) провели систематическое исследование параллельного локального поиска, включая кооперативные стратегии запретов. Агентный подход стал заметным в 2000-х годах, когда лексика агентного моделирования вошла в исследования операций.
Когда применять
Использовать агентный поиск с запретами при решении сложных комбинаторных или смешанно-целочисленных задач оптимизации (планирование, маршрутизация, проектирование сетей, распределение ресурсов), где однопоточный поиск с запретами стагнирует и доступны ресурсы параллельных вычислений. Он особенно эффективен, когда ландшафт поиска имеет множество локальных оптимумов схожего качества. Избегать его, когда задача достаточно мала для точных решателей (MILP, ветвей и границ), когда одна оценка вычислительно непомерна (делая многие параллельные оценки невыполнимыми) или когда требования к воспроизводимости конфликтуют с недетерминированной динамикой взаимодействия агентов.
Ограничения и замечания
- Накладные расходы на синхронизацию и стоимость связи между агентами могут свести на нет выигрыш от параллелизма в тесно связанных системах или медленных сетях.
- Больше гиперпараметров, чем в однопоточном поиске с запретами: количество агентов, топология связи, частота синхронизации и триггеры диверсификации — все это требует настройки.
- Теоретические гарантии сходимости слабее, чем у точных методов; качество решения сильно зависит от настройки и структуры задачи.
- Воспроизводимость труднодостижима, поскольку взаимодействие агентов вносит дополнительную стохастичность помимо случайной инициализации.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Параллельное исследование значительно сокращает время до получения решения для больших комбинаторных задач по сравнению с однопоточным поиском с запретами.
- Мультиагентная структура естественным образом поддерживает диверсификацию, снижая риск преждевременной сходимости к плохим локальным оптимумам.
- Гибкая архитектура позволяет использовать гетерогенных агентов с различными структурами окрестности, стратегиями времени жизни запретов или даже смешанными метаэвристиками.
- Совместный обмен решениями передает открытия между агентами, ускоряя интенсификацию вокруг высококачественных областей.
- Хорошо масштабируется с доступными вычислительными ядрами, что делает его подходящим для современных многоядерных и распределенных вычислительных сред.
Применение
- Маршрутизация транспортных средств и логистика: координация нескольких агентов, каждый из которых оптимизирует подзадачи маршрута.
- Планирование производственных процессов и гибких производственных систем: агенты совместно обрабатывают подмножества станков.
- Проектирование телекоммуникационных сетей: распределенное назначение каналов и оптимизация топологии.
- Планирование цепочек поставок: оптимизация многоуровневых запасов и распределения.
- Предсказание структуры белков: параллельный поиск по окрестности в конформационных пространствах.
- Составление академических расписаний и расписаний курсов с распределенными агентами на уровне кафедр.
Как это работает
Как это работает
Определить популяцию автономных агентов. Каждому агенту назначается роль: некоторые фокусируются на интенсификации (глубокий локальный поиск вокруг перспективных областей), другие — на диверсификации (выход в неисследованные области). Каждый агент поддерживает свой собственный список запретов для недопустимых ходов, текущее решение и структуру окрестности, адаптированную к типу задачи (например, ходы swap, insertion или 2-opt для комбинаторных задач).
Инициализировать агентов различными начальными решениями, либо сгенерированными случайным образом, либо заданными с помощью конструктивной эвристики (например, ближайшего соседа для маршрутизации). Разнообразие начальных решений имеет решающее значение — идентичные старты приводят к избыточным параллельным поискам. Оценить целевую функцию для каждого начального решения и записать глобально лучшее решение среди всех агентов.
Каждый агент выполняет свой собственный цикл поиска с запретами: генерирует окрестность текущего решения, оценивает все (или подмножество) соседних решений, выбирает лучший не запрещенный сосед в качестве следующего хода (критерий аспирации позволяет переопределить список запретов, если кандидат превосходит глобально лучшее решение) и обновляет список запретов, добавляя обратный ход с временем жизни, взятым из фиксированного или адаптивного диапазона.
Агенты обмениваются информацией через определенные интервалы синхронизации или триггеры событий. Распространенные стратегии включают трансляцию текущего глобально лучшего решения всем агентам (которые могут перезапуститься с него), помещение элитного решения в общий пул, который агенты периодически проверяют, или обмен решениями между соседними агентами в топологии (кольцо, полносвязная или случайная). Контроль разнообразия предотвращает преждевременную сходимость, наказывая агентов с идентичными решениями.
Прекратить поиск при достижении максимального бюджета итераций, лимита времени выполнения или критерия стагнации (например, отсутствие улучшения глобально лучшего решения за заданное количество итераций). Выбрать глобально лучшее решение, найденное всеми агентами за все итерации, в качестве окончательного результата. При необходимости сообщить о Парето-фронте, если отслеживаются множественные цели.
Частые ошибки
- Назначение всем агентам идентичных начальных решений приводит к пустой трате параллельных мощностей — обеспечьте разнообразную инициализацию.
- Слишком частая связь заставляет агентов попадать в один и тот же бассейн решений, устраняя преимущества диверсификации и фактически сводя поиск к одному потоку.
- Игнорирование критерия аспирации при проектировании списка запретов может привести к тому, что агенты упустят очевидно лучшие решения, особенно на ранних этапах поиска.
- Применение ABTS к задачам, где оценка окрестности чрезвычайно затратна без суррогатной модели, приведет к непомерным временам выполнения.
Часто задаваемые вопросы
Чем агентный поиск с запретами отличается от простого запуска нескольких потоков поиска с запретами?
Ключевое отличие — кооперация. При независимых параллельных запусках потоки никогда не обмениваются информацией. В ABTS агенты активно обмениваются решениями, обновляют общий элитный пул или используют триггеры диверсификации на основе коллективного состояния — порождая эмерджентное поведение поиска, отсутствующее в независимых запусках.
Сколько агентов следует использовать?
Обычная отправная точка — один агент на доступное ядро ЦП. Исследования показывают убывающую отдачу при количестве агентов более 8–16 для большинства комбинаторных задач, поскольку накладные расходы на связь растут. Пилотные эксперименты с 4, 8 и 16 агентами помогают определить оптимальное значение для данной задачи.
Может ли ABTS обрабатывать многокритериальные задачи?
Да. Агенты могут поддерживать локальные приближения Парето-фронта и обмениваться недоминируемыми решениями через общий архив. Это иногда называют многокритериальным агентным поиском с запретами и оно отличается от стандартного однокритериального ABTS.
Какая топология связи лучше всего подходит?
Полносвязные топологии быстрее всего распространяют хорошие решения, но создают высокие затраты на связь. Кольцевые или малосвязные топологии обеспечивают баланс между диффузией информации и автономией. Для большинства практических задач кольцевая или случайная разреженная топология хорошо подходит в качестве значения по умолчанию.
Когда следует предпочесть генетический алгоритм или роевое поведение частицам вместо ABTS?
Предпочитайте популяционные методы (GA, PSO), когда задача имеет непрерывный, гладкий ландшафт или когда операторы кроссовера/рекомбинации хорошо определены. ABTS преуспевает в дискретных, комбинаторных задачах с хорошо определенными операторами окрестности, где память запретов обеспечивает сильное преимущество в поиске.
Похожие методы
Источники
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Открыть ссылку DOIСкопировано.Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
Открыть ссылку DOIСкопировано.