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

Многокритериальная имитация отжига (MOSA)

Автор метода
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
Год
1992–1998
Тип
Metaheuristic / Pareto-based optimizer
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

Имитация отжига была предложена Kirkpatrick et al. в 1983 году. Serafini (1992) одним из первых формально предложил её расширение на несколько критериев. Czyzak и Jaszkiewicz (1998) разработали Pareto Simulated Annealing (PSA), который установил Парето-архив в качестве центральной выходной структуры и предоставил формулировку критерия принятия, широко используемую сегодня. С тех пор MOSA применялся в проектировании, планировании и логистике.

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

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

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

  • Качество решения и охват фронта Парето чувствительны к выбору начальной температуры, скорости охлаждения и оператора соседства, что требует настройки под конкретную задачу.
  • Сходимость к высококачественному фронту Парето может потребовать множества оценок критериев, что делает его медленным для дорогостоящих симуляций типа «чёрный ящик».
  • Поддержание и обновление Парето-архива вносит накладные расходы, и архив может стать большим, увеличивая затраты на память и сравнение.
  • В отличие от популяционных методов (например, NSGA-II), однотраекторная природа базового MOSA может привести к неравномерному покрытию фронта Парето.
  • Теоретические гарантии сходимости требуют бесконечно медленного графика охлаждения, что непрактично; конечные графики жертвуют гарантией оптимальности.

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

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

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

Применение

  • Многокритериальное планирование производственных процессов (job-shop и flow-shop) с одновременной минимизацией времени выполнения и опозданий
  • Задачи проектирования сетей и маршрутизации с критериями стоимости и надёжности
  • Оптимизация инженерных конструкций (например, минимизация веса и напряжений в конструктивных элементах)
  • Оптимизация портфеля с балансировкой ожидаемой доходности и риска
  • Планирование землепользования и территориальное планирование с конкурирующими экономическими и экологическими целями
  • Распределение медицинских ресурсов с балансировкой стоимости, охвата и качества обслуживания

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

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

1

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

2

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

3

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

4

Применить многокритериальный критерий принятия. Если сосед недоминируем по отношению к текущему решению, он принимается. Если он доминируется, он всё ещё может быть принят с вероятностью P = exp(−ΔF / T), где ΔF агрегирует ухудшение критериев, позволяя выйти из локальных фронтов Парето.

Формула
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

Снизить температуру согласно графику охлаждения, обычно геометрическому: T_{k+1} = α · T_k с α ∈ (0.8, 0.99). Более низкие температуры сужают диапазон принятия неоптимальных ходов, постепенно интенсифицируя поиск вблизи перспективных областей фронта Парето.

Формула
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

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

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

  • Установка начальной температуры слишком низкой приводит к преждевременной сходимости к локальной области фронта Парето; всегда калибруйте T_0 так, чтобы начальная частота принятия составляла около 70–90%.
  • Использование скорости охлаждения α, слишком близкой к 1.0, делает прогон непомерно долгим; слишком близкое к 0 значение вызывает быструю сходимость до адекватного исследования фронта Парето.
  • Определение ΔF для вероятности принятия путём наивного суммирования разностей критериев смешивает несравнимые масштабы — нормализуйте каждый критерий перед агрегацией.
  • Пренебрежение периодическим удалением доминируемых решений из архива раздувает его и снижает качество конечного результата.
  • Оценка успеха по одному прогону вводит в заблуждение из-за стохастической вариации; всегда агрегируйте результаты по нескольким независимым прогонам.

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

Чем MOSA отличается от NSGA-II?

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

Как следует устанавливать начальную температуру T_0?

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

Может ли MOSA обрабатывать более двух критериев?

Да, но производительность снижается с ростом числа критериев. Увеличиваются накладные расходы на управление Парето-архивом, и доля недоминируемых решений быстро растёт, делая критерий принятия менее дискриминирующим. Для задач с более чем четырьмя или пятью критериями обычно предпочтительнее методы на основе гиперобъёмного индикатора или декомпозиции (например, MOEA/D).

Как узнать, когда остановить алгоритм?

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

Подходит ли MOSA для дорогостоящих симуляционных моделей?

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

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

Источники

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    Открыть ссылку DOI
    Скопировано.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

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