Skip to content
Назад к результатам поиска

Многокритериальный поиск с запретами (MOTS) — Метаэвристика для Парето-оптимальных решений

Автор метода
Hansen, M. P.; building on Glover (1989) Tabu Search
Год
1997
Тип
Metaheuristic multi-objective optimization
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Многокритериальный поиск с запретами (MOTS) — это метаэвристический алгоритм, который расширяет классическую структуру поиска с запретами для одновременной оптимизации двух или более конфликтующих целевых функций.

Вместо единственного оптимума он стремится аппроксимировать Парето-фронт — множество решений, в котором ни одна цель не может быть улучшена без ухудшения другой, — что делает его подходящим для сложных комбинаторных и непрерывных задач оптимизации в инженерии, логистике и исследовании операций.

Интуиция метода

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

История

Многокритериальный поиск с запретами расширяет однокритериальный поиск с запретами, представленный Фредом Гловером в 1989 году. Первая систематическая формулировка MOTS — включая Парето-архивирование и многокритериальные критерии аспирации — была представлена М. П. Хансеном на конференции MCDM в 1997 году. Последующие работы Гандиблё, Тегема и других формализовали варианты для комбинаторных задач, и с тех пор MOTS применяется в задачах планирования, логистики и проектирования в качестве конкурентоспособной альтернативы эволюционным многокритериальным алгоритмам.

Когда применять

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

Ограничения и замечания

  • Производительность сильно зависит от длины списка запретов, определения окрестности и стратегии диверсификации — требуется тщательная настройка параметров.
  • Нет гарантии сходимости к истинному Парето-фронту; качество решения зависит от длины прогона и структуры задачи.
  • Вычислительно затратен на каждой итерации, когда окрестности велики или оценки целей дороги.
  • Поддержание и обновление Парето-архива может стать дорогостоящим по мере роста числа целей и размера архива.
  • Параллельная реализация нетривиальна из-за последовательной природы механизма запретов, основанного на памяти.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Избегает повторного посещения недавних решений с помощью списка запретов, снижая риск зацикливания в сложных ландшафтах.
  • Критерии аспирации позволяют отменить ограничения запретов, когда перемещение приводит к исключительному улучшению, балансируя память с гибкостью.
  • Не требует информации о градиенте, что делает его применимым к недифференцируемым, дискретным или «черным ящикам» целевых функций.
  • Производит аппроксимацию всего Парето-фронта за один прогон, поддерживая многокритериальное принятие решений.
  • Гибкая конструкция окрестности и операторов перемещения позволяет настраивать алгоритм под конкретную задачу.
  • Механизмы диверсификации позволяют избежать локальных оптимумов и улучшить покрытие Парето-фронта.

Применение

  • Многокритериальная маршрутизация транспортных средств и планирование логистики (одновременное минимизация стоимости и времени доставки)
  • Двухкритериальное планирование проектов: минимизация времени выполнения и стоимости ресурсов при ограничениях предшествования
  • Оптимизация портфеля: балансировка ожидаемой доходности против риска по нескольким классам активов
  • Проектирование сети: минимизация стоимости установки при одновременном максимизации надежности или пропускной способности
  • Планирование производственных процессов: совместная оптимизация времени цикла, энергопотребления и метрик качества
  • Экологический менеджмент: балансировка экономического вывода против загрязнения или экологического воздействия

Как это работает

Как это работает

1

Инициализировать поиск одним или несколькими начальными решениями (случайно сгенерированными или построенными эвристически). Установить пустой список запретов фиксированной длины L и инициализировать Парето-архив недоминируемыми решениями из начальной популяции.

2

Сгенерировать окрестность N(s) текущего решения s, применяя операторы перемещения (обмены, вставки, возмущения). Оценить все соседние решения по каждой целевой функции, чтобы определить кандидатов для продвижения.

3

Применить фильтр запретов: исключить соседей, чьи определяющие перемещения появляются в списке запретов, если только они не удовлетворяют критерию аспирации — обычно тому, что сосед доминирует над всеми текущими членами архива или улучшает лучшее известное значение хотя бы по одной цели. Это предотвращает зацикливание и стимулирует исследование.

4

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

5

Применять стратегии диверсификации, когда поиск стагнирует: долговременная память частоты определяет редко посещаемые области; перезапуск из элитных решений архива или случайно возмущенных решений для расширения охвата Парето-фронта.

6

Повторять шаги генерации окрестности, фильтрации и обновления архива до тех пор, пока не будет достигнут критерий остановки — обычно максимальное количество итераций, оценок функции или затраченное процессорное время. Вернуть Парето-архив как аппроксимированный Парето-оптимальный фронт.

Частые ошибки

  • Установка слишком короткого списка запретов вызывает зацикливание; установка слишком длинного чрезмерно ограничивает поиск и приводит к упущению хороших решений — необходима эмпирическая калибровка.
  • Пренебрежение диверсификацией приводит к преждевременной сходимости в одной области Парето-фронта, давая плохую аппроксимацию.
  • Применение MOTS с более чем тремя целями снижает производительность, поскольку управление архивом и поддержание разнообразия становятся вычислительно обременительными; для задач с множеством целей следует рассматривать методы, основанные на декомпозиции.
  • Использование общих операторов перемещения без специфического для задачи дизайна существенно снижает качество решения по сравнению с адаптированными реализациями.
  • Отчетность только о конечном архиве без изучения истории сходимости может маскировать преждевременную стагнацию.

Часто задаваемые вопросы

Как MOTS обрабатывает список запретов при наличии нескольких целей?

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

Что такое Парето-архив и какого он должен быть размера?

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

Как MOTS сравнивается с NSGA-II для многокритериальных задач?

NSGA-II использует популяционный эволюционный подход с кроссовером и мутацией, что делает его лучше в глобальном исследовании на ранних этапах поиска. MOTS полагается на перемещения по окрестности и память, что часто дает более точное качество локального поиска. На практике MOTS, как правило, превосходит в комбинаторных задачах с сильной структурой окрестности, в то время как NSGA-II чаще используется для непрерывных задач.

Сколько итераций обычно требуется?

Универсального правила нет. Общепринятой практикой является бюджетирование оценок функции, а не итераций — обычно от 10 000 до 100 000 оценок в зависимости от размера задачи — и выполнение нескольких независимых запусков для оценки качества решения и стабильности Парето-фронта.

Может ли MOTS обрабатывать более двух целей?

Да, но эффективность снижается по мере роста числа целей сверх трех («проклятие размерности» в пространстве целей). Для четырех или более целей размер архива взрывообразно растет, и поддержание разнообразия становится трудным; часто предпочитаются подходы, основанные на декомпозиции или индикаторах.

Похожие методы

Источники

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    Открыть ссылку на публикацию
    Скопировано.
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Открыть ссылку DOI
    Скопировано.