Интерактивные карты решений

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

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

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

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

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

Аппроксимация EPH

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

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

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

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

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

Поиск предпочтительного решения

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

См. также

Многокритериальный анализ решений

Ссылки

^ Jump up to: ^а ^б ^с ^д A. V. Lotov; V. A. Bushenkov; G. K. Kamenev (29 February 2004). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier . Springer. ISBN 978-1-4020-7631-2 . Проверено 29 мая 2012 г.
^ Кайса Миеттинен (1999). Нелинейная многокритериальная оптимизация . Спрингер. ISBN 978-0-7923-8278-2 . Проверено 29 мая 2012 г.
^ Юрген Бранке; Калянмой Деб; Кайса Миеттинен; Роман Словински (21 ноября 2008 г.). Многокритериальная оптимизация: интерактивный и эволюционный подходы . Спрингер. ISBN 978-3-540-88907-6 . Проверено 1 ноября 2012 г.
^ Калянмой Деб (23 марта 2009 г.). Многокритериальная оптимизация с использованием эволюционных алгоритмов . Джон Уайли и сыновья. ISBN 978-0-470-74361-4 . Проверено 1 ноября 2012 г.
^ Березкин В.Е.; Каменев, Г.К.; Лотов, А.В. (2006). «Гибридные адаптивные методы аппроксимации невыпуклой многомерной границы Парето». Вычислительная математика и математическая физика . 46 (11): 1918. Бибкод : 2006CMMPh..46.1918B . дои : 10.1134/S096554250611008X . S2CID 121051510 .

[LotovBushenkov2004-1] Jump up to: ^а ^б ^с ^д A. V. Lotov; V. A. Bushenkov; G. K. Kamenev (29 February 2004). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier . Springer. ISBN 978-1-4020-7631-2 . Проверено 29 мая 2012 г.

[Miettinen1999-2] Кайса Миеттинен (1999). Нелинейная многокритериальная оптимизация . Спрингер. ISBN 978-0-7923-8278-2 . Проверено 29 мая 2012 г.

[BrankeDeb2008-3] Юрген Бранке; Калянмой Деб; Кайса Миеттинен; Роман Словински (21 ноября 2008 г.). Многокритериальная оптимизация: интерактивный и эволюционный подходы . Спрингер. ISBN 978-3-540-88907-6 . Проверено 1 ноября 2012 г.

[Deb2009-4] Калянмой Деб (23 марта 2009 г.). Многокритериальная оптимизация с использованием эволюционных алгоритмов . Джон Уайли и сыновья. ISBN 978-0-470-74361-4 . Проверено 1 ноября 2012 г.

[BerezkinKamenev2006-5] Березкин В.Е.; Каменев, Г.К.; Лотов, А.В. (2006). «Гибридные адаптивные методы аппроксимации невыпуклой многомерной границы Парето». Вычислительная математика и математическая физика . 46 (11): 1918. Бибкод : 2006CMMPh..46.1918B . дои : 10.1134/S096554250611008X . S2CID 121051510 .

[1]

[2]

[3]

[4]

[5]