Интерактивные карты решений - Interactive Decision Maps

В Интерактивные карты решений техника многокритериальная оптимизация основан на приближении Эджворт -Парето Халл (EPH) допустимого целевого набора, то есть допустимого целевого набора, расширенного за счет целевых точек, в которых он доминирует. Кроме того, этот набор известен как Free Disposal Hull. Важно, чтобы ОЭП имел тот же фронт Парето, что и допустимый набор целей, но двуцелевые срезы ОЭП выглядят намного проще. Границы двуцелевых срезов ОЭП содержат срезы фронта Парето. Важно, что, в отличие от самого фронта Парето, ОЭП обычно устойчив к возмущениям данных. В методе IDM применяется быстрое онлайн-отображение двухобъективных срезов заранее аппроксимированного EPH.

Поскольку двуцелевые срезы ОЭП для двух выбранных целей монотонно расширяются (или сужаются), в то время как значение одной из других целей («третья» цель) изменяется монотонно, границы срезов ОЭП для которой меняются только значения «третьей» цели, не пересекаются. Вот почему фигура с наложенными двуцелевыми срезами EPH выглядит как обычная топографическая карта и также называется картой решений. Для изучения влияния других (четвертой, пятой и др.) Целей можно использовать анимацию карт решений. Такая анимация возможна благодаря предварительной аппроксимации ОЭП. Как вариант, можно изучить различные коллекции снимков анимации. Компьютеры могут визуализировать фронт Парето в виде карт решений для линейных и нелинейных задач принятия решений для трех-восьми целей. Компьютерные сети могут предоставлять, например, апплеты Java, которые отображают графики фронтов Парето по запросу. Реальные приложения метода IDM описаны в.[1]

Иллюстрация техники IDM

Полутоновая копия дисплея компьютера с применением технологии IDM.

На рисунке выше представлена ​​полутоновая копия цветного компьютерного дисплея для реальной проблемы качества воды.[1] с пятью целями. Карта решений состоит из четырех наложенных друг на друга двухцелевых срезов разного цвета. Палитра показывает соотношение между значениями «третьей» цели и цветами. Две полосы прокрутки относятся к значениям четвертой и пятой целей.

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

Приближая EPH

EPH должен быть аппроксимирован методом IDM перед отображением карт решений. Способы аппроксимации EPH зависят от свойств выпуклости EPH. Методы аппроксимации обычно основаны либо на приближении ОЭП выпуклый многогранник множества или аппроксимации ОЭП большим, но конечным числом конусов доминирования в целевом пространстве с вершинами, близкими к фронту Парето. Первая форма применима только к выпуклым задачам, а вторая форма универсальна и может использоваться в общих нелинейных задачах.[1]

Аппроксимация и визуализация в случае выпуклой ОЭП

ОЭП, аппроксимируемая многогранным множеством, описывается системой конечного числа линейных неравенств, которые должны быть построены методом аппроксимации. Математическая теория оптимальной полиэдральной аппроксимации выпуклых тел была развита в последнее время, и ее результаты могут быть применены для разработки эффективных методов аппроксимации ОЭП.[1] Большое количество двуцелевых срезов таких приближений можно вычислить и отобразить в виде карты решений за несколько секунд.

Точечная аппроксимация фронта Парето и его визуализация.

Аппроксимация ОЭП большим, но конечным числом конусов доминирования может быть построена на основе любой точечной аппроксимации Парето фронт, который можно найти, используя широкий спектр методов из классических методов одноцелевой оптимизации [2][3] до современных эволюционных методов[4] Также можно использовать гибридные методы аппроксимации ОЭП, основанные на сочетании классических и эволюционных методов.[5] Двухцелевые срезы такого приближения также могут быть вычислены очень быстро. Применение этих методов приводит к картам решений, которые выглядят достаточно понятными, если количество аппроксимирующих точек достаточно велико.

Найдите предпочтительное решение

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

Смотрите также

Рекомендации

  1. ^ а б c d А. В. Лотов; Бушенков В.А.; Каменев Г.К. (29 февраля 2004 г.). Интерактивные карты принятия решений: аппроксимация и визуализация границы Парето. Springer. ISBN  978-1-4020-7631-2. Получено 29 мая 2012.
  2. ^ Кайса Миеттинен (1999). Нелинейная многокритериальная оптимизация. Springer. ISBN  978-0-7923-8278-2. Получено 29 мая 2012.
  3. ^ Юрген Бранке; Калянмой Деб; Кайса Миеттинен; Роман Словинский (21 ноября 2008 г.). Многокритериальная оптимизация: интерактивный и эволюционный подходы. Springer. ISBN  978-3-540-88907-6. Получено 1 ноября 2012.
  4. ^ Калянмой Деб (23 марта 2009 г.). Многоцелевая оптимизация с использованием эволюционных алгоритмов. Джон Вили и сыновья. ISBN  978-0-470-74361-4. Получено 1 ноября 2012.
  5. ^ Березкин, В.Е .; Каменев, Г.К .; Лотов, А. В. (2006). «Гибридные адаптивные методы аппроксимации невыпуклой многомерной границы Парето». Вычислительная математика и математическая физика. 46 (11): 1918. Дои:10.1134 / S096554250611008X.