close

Вход

Забыли?

вход по аккаунту

?

Y - Amazon S3

код для вставкиСкачать
Визуализация границы
Парето в задачах
многокритериальной
оптимизации
(Лекции в МФТИ, февраль 2013 г.)
А. В. Лотов
Вычислительный Центр
им. А.А.Дородницына РАН
ВМК МГУ им. М.В.Ломоносова
Часть I. Методы многокритериальной
оптимизации. Содержание
• А. Этапы выбора стратегического решения и задача скрининга
• Б. Принципиальное отличие задачи многокритериальной
оптимизации от задачи оптимизации единственного критерия.
Основные понятия многокритериальной оптимизации
• В. Три источника теории принятия решений и их влияние на
концепции многокритериальной оптимизации. Роль
психологических исследований
• Г. Элементы теории многокритериальной оптимизации:
существование и устойчивость границы Парето, оптимизация
скалярных сверток критериев и т.д.
• Д. Основные классы методов многокритериальной оптимизации:
а) Методы, не учитывающие предпочтения ЛПР
б) Методы, основанные на моделировании предпочтений ЛПР
в) Интерактивные (итеративные) методы
г) Методы паретовой границы
А. Этапы выбора стратегического
решения и задача скрининга
О выборе стратегических решений
Стратегические решения – это решения,
имеющие серьезное долгосрочное воздействие
(проектные и плановые решения, решения о
формах и параметрах регулирования экономики,
о стратегии бизнеса, финансовые решения,
решения о выборе места учебы или работы и
т.д.). Поэтому стратегические решения
заслуживают тщательного анализа, в том числе
математического моделирования и разработки
систем поддержки принятия решений (СППР).
Системы поддержки принятия решений и
информационные системы
Определение СППР
Система поддержки принятия решений – это
система компьютерных программ и процедур,
предназначенная для того, чтобы помочь
лицам, принимающим решения,
проанализировать сложные проблемы
принятия решений на основе использования
знаний, данных, моделей.
Автоматический выбор и принятие
решения с участием человека
Принятие стратегических решений обычно
осуществляется с участием людей; этим
принятие стратегических решений
принципиально отличается от
автоматического выбора решений, скажем,
автопилотом или искусственным
интеллектом. Поэтому при анализе методов
поддержки принятия стратегических
решений приходится учитывать сложные
психические (а при коллективном выборе –
и социальные) процессы.
Стадии процесса принятия
стратегического решения
(Г. Саймон)
Оптимизация – это методика выделения одного или
нескольких наиболее предпочтительных решений из
большого или бесконечного числа допустимых решений
на основе использования математических моделей.
Наиболее часто встречается однокритериальная
(скалярная) оптимизация – единственный критерий
описывает предпочтения. Такое свойство задачи
встречается далеко не всегда: имеется большое число
задач, в которых имеется несколько критериев,
значения каждого из которых желательно увеличить
(или уменьшить) при неизменных других. К таким
проблемам относятся, например, задачи
проектирования технических систем или систем,
оказывающих воздействие на окружающую среду. При
принятии финансовых решений наряду с доходом
требуется учитывать риски. В таких случаях требуется
использовать многокритериальные методы.
Рассматриваемая проблема:
Разработка многокритериальных методов
поддержки принятия стратегических решений на
этапе отбора малого числа альтернатив (этап
скрининга вариантов).
При этом предполагается, что с помощью
математической модели задано большое или
бесконечное число альтернативных вариантов
решения.
Б. Принципиальное отличие
задачи многокритериальной
оптимизации от задачи
оптимизации единственного
критерия
Оптимизация с единственным
критерием
( x1 , x 2 ,..., x n ) решения
X множество
например,
допустимых
X x R
В общем случае
n
решений,
: Ax b
X W
y f ( x ) - критерий оптимизации
Задача оптимизации. Требуется найти
x* X :
f ( x *) min
f ( x ) , где
x X.
Или, другими словами, требуется найти
x * X : f ( x *) f (x),
x X
Эта проблема обозначается как
f ( x ) min
Многокритериальная оптимизация
Множество допустимых решений
X W
Решения отображаются
в многомерное
векторное пространство
y f ( x ) min
Условная запись,
означающая, что желательно
уменьшать значения каждого
из критериев при неизменных
других.
Предпочтение (доминирование)
по Парето
y2
y y y
y y y1
Доминирование по Парето и
граница Парето
Доминирование по Парето
Пусть
Y f (X )
множество достижимых
значений критериев
• Граница Парето
P (Y ) { y Y : { y ' Y : y ' y } }
Оболочка Эджворта-Парето
Имеет место
Y* Y R
m
Решение задачи МКО
Математическое (теоретическое) решение
задачи МКО – множество в пространстве
критериев (граница Парето)
P (Y )
и множество в пространстве решений
(множество решений, оптимальных по
Парето)
P ( X ) { x X : f ( x ) P (Y )}
Главное отличие МКО от задачи
скалярной оптимизации
Главное отличие – решением задачи МКО
является не точка x X , а множество таких
точек, что
f ( x ) P (Y )
Теоретическое решение, однако, не
представляется удовлетворительным с
практической точки зрения, которая требует
разработки методов выделения единственной
точки
x P(X )
Как решается эта проблема?
Лицо, принимающее решение
В рамках методов МКО считается, что выбор
единственного решения, оптимального по Парето,
осуществляется лицом, принимающим решение (ЛПР).
Очень часто ЛПР – это только удобная абстракция,
поскольку при принятии стратегических решений на
выбор оказывают влияние и другие люди (советники,
эксперты, лоббисты и т.д.). Считается важным
использовать информационные технологии для
привлечения к принятию решений всех тех, на кого эти
решения могут оказать влияние (e-democracy).
Далее мы отвлекаемся от этого вопроса и считаем, что в
рассматриваемых задачах участвует единственный
человек – ЛПР.
Вопросы, возникающие в связи с наличием ЛПР
• То, что при разработке методов МКО приходится учитывать
присутствие человека, выводит эту проблему за рамки чисто
математической задачи о нахождении множества Парето и
включает ее в контекст теории принятия решений,
существенным элементом которой является учет наличия
человека в процессе принятия решения.
• В настоящее время теория принятия решений, включающая в
себя наряду с чисто математическими утверждениями
результаты исследований в области психологии, является
совокупностью концепций, зачастую не только не связанных
между собой, но и противоречащих друг другу. Такая ситуация
объясняется тем, что теория принятия решений возникла, по
крайней мере, из трех источников – экономической теории,
психологических экспериментов и практики принятия
решений. Эти источники отличаются и языком, и методами
исследования.
В. Три источника теории принятия
решений и их влияние на концепции
многокритериальной оптимизации.
Роль психологических исследований
Экономическая теория объясняет и предсказывает экономическое поведение
людей, т.е. поведение в области производства, обмена и потребления. Эта
теория привнесла в теорию принятия решений такие базовые понятия, как
рациональное поведение и функция полезности. Простейшая иллюстрация
использования функции полезности: потребитель в магазине выбирает набор
товаров y на основе решения задачи
U ( y ) max при
p i y i b , где y 0 , p вектор цен.
Производители и торговцы максимизируют свою прибыль, цены
устанавливаются на основе равновесия спроса и предложения.
К теории принятия решений экономическая теория имеет лишь
косвенное отношение, так как ее задача – описание характерного поведения
человека (а вовсе не его поддержка в процессе принятия решений). Поэтому
экономическая теория имеет право использовать простую модель
рационального человека – ограниченного логичного существа, действия
которого направлены на максимизацию функции полезности. Эта модель
показала свою эффективность при анализе экономических проблем. В то же
время, при разработке методов поддержки принятия решений использование
функции полезности – это лишь одно из возможных направлений работы.
Заранее функция полезности не известна, а ее существование для
отдельного человека часто вызывает сомнение.
Психология – наука о закономерностях, механизме и фактах психической
жизни человека, изучает психику человека, в том числе и его поведение.
Одной из целей психологии является построение адекватных моделей
принятия решений человеком в различных ситуациях, так что простые
модели человеческого поведения (типа максимизации полезности) хотя и
встречаются в психологических исследованиях, не определяют основные
направления этих исследований. В настоящее время психология включает
совокупность конкурирующих моделей человека, от простейшей модели
поведения в виде простой реакции на стимулы до сложнейших концепций
ментальных моделей, используемых человеком для предсказания реакции
окружающего мира на его возможные действия. При этом часто учитывается
социальная обусловленность предпочтений и привычек отдельного человека.
Психологические модели в значительной степени являются
обобщением результатов экспериментов с человеком, которые получили
широкое распространение (особенно в области психологии рекламы и
инженерной психологии). Надо, однако, признать, что анализировать знания,
добытые экспериментальной и теоретической психологией в рамках
концепции ментальных моделей, значительно труднее, чем изучать простую
математическую модель максимизации функции, поэтому концепция
функции полезности также используется психологами.
Прикладное (инженерное) направление связано с практическим
применением методов поддержки принятия решений. Систематическая
разработка таких методов началась после второй мировой войны, а с
появлением компьютеров началось создание компьютерных систем
поддержки принятия решений. Для инженерного подхода главным является
не теоретический результат, а работающая система, которая успешно
используется при принятии решений. Начав с применения методов
однокритериальной оптимизации простейших форм функции полезности,
создатели СППР были вынуждены обратиться к более сложным
постановкам, в том числе и к таким, в которых выбор решения
осуществляется человеком на основе нескольких критериев. СППР стали
источником важного (часто негативного) опыта, который требует своего
осмысления. Этим определяется усиление влияния прикладного
направления на теорию и практику поддержки принятия решений в
настоящее время.
Остановимся на некоторых важнейших концепций, возникших в
результате проведения психологических экспериментов. Прежде всего – это
представление об ограниченности памяти и понятие ментальной
(мысленной) модели, на основе которой человек оценивает ситуацию и
планирует свою деятельность.
Ограниченность памяти
Психологические исследования показали, что
• 1) объем информации, который человек способен одновременно
держать в так называемой быстрой памяти, составляет около 7
единиц. Так, если называть отдельные буквы, то человек
запоминает в среднем 7 букв, если слова – 7 слов, если фразы – 7
фраз и т.д. Поэтому при принятии решений человек может
оперировать одновременно лишь с небольшим числом
альтернатив, и то только в том случае, если он воспринимает их
как целое;
• 2) в силу ограниченности памяти человеческий выбор может
быть нелогичен;
• 3) многие люди упрощают задачу: вместо того, чтобы принять во
внимание несколько характеристик решений, они рассматривают
лишь две, являющиеся наиболее важными для них, наложив на
остальные достаточно произвольные ограничения.
Структура ментальной модели
(на основе работ Б.Ф.Ломова)
• В модели сознания человека выделяются уровни логического
мышления, образного мышления и подсознательный.
Экспериментально подтверждено, что в принятии решений
участвуют все три уровня, причем влияние их может быть
несогласованным. В таком случае реакция человека на вопросы
может отклоняться от ожидаемых логичных ответов.
Важно, что обычно имеют место противоречия между уровнями –
выбор решения требует времени для согласования уровней
(подсознательный уровень проявляется наиболее часто во сне).
Отметим, что Бенджамин Франклин (1706-1790), который первым
предложил многокритериальный метод выбора (из двух
альтернатив), учитывал временные требования. Метод
Б.Франклина состоит в следующем:
1) составляется список, содержащий все существенные достоинства
и недостатки альтернатив, и
2) вычеркиваются строки, компенсирующие одна другую.
Б.Франклин рекомендовал, чтобы составление списка и процесс
исключения осуществлялись как минимум два-три дня !!!
Таким образом, требуется учитывать сложность человеческого
мышления и временные требования, о которых многие авторы
методов МКО, к сожалению, забывают.
Возможности человека в МКО
На основе анализа многочисленных психологических
экспериментов О.И.Ларичев (Теория и методы принятия решений.
– М.: Логос, изд. 3, 2006) сделал следующие выводы о некоторых
операциях, используемых в методах МКО:
• Назначение весов (важности) критериев является сложным;
• Построение функции полезности даже по одному критерию
является слишком сложным;
• Выбор из группы альтернатив с более, чем двумя-тремя
критериями, является слишком сложным;
• Назначение целевой точки является слишком сложным;
• Указание критерия, по которому в первую очередь хотелось бы
улучшить решение (за счет других) является допустимым;
• Определение количества одного критерия, которым человек
готов пожертвовать для улучшения значения другого критерия
является допустимым при однократном использовании.
Г. Элементы теории
многокритериальной оптимизации:
существование и устойчивость
границы Парето, оптимизация
скалярных сверток критериев и т.д.
(подробнее см. в книге
В.В.Подиновского и В.Д.Ногина).
Более сложный пример f(X)
y2
Y=f(X)
y1
Напомним, что
• Доминирование по
Парето
• Граница Парето
P (Y ) { y Y : { y ' Y : y ' y } }
Граница Парето
y2
y
y y P(Y)
f(X)
y1
Граница Парето легко заметна на рисунке
y2
y1
ОЭП и идеальная точка
y2
P(Y)
f(X)
y*
y1
О существовании границы Парето
y y y i
y i, i 1, 2 ,..., m Граница Слейтера
Определение. Границей Слейтера называется
S (Y ) { y Y : { y ' Y : y ' y } }
y2
P (Y ) S (Y )
A
Y
B
C
P(Y)
S(Y)
y1
Устойчивость границы Парето
В этом примере множества S(Y) и P(Y) не
совпадают. Пусть множествоY было немного
возмущено.
A
Y
B
P(Y)
C
Множество P(Y) качественно изменилось.
Если выполняются некоторые естественные
предположения о классе возмущений
множества Y, условие S(Y) = P(Y) является
необходимым и достаточным условием
устойчивости границы Парето
(Sawaragi Y., Nakayama H., Tanino T., 1985).
Заранее трудно сказать, устойчива ли граница
Парето в конкретной задаче; опыт показывает,
что в прикладных задачах граница Парето, как
правило, неустойчива.
Устойчивость оболочки Эджворта-Парето
Рассмотрим ОЭП, обозначенную здесь как Yp ,
в той же самой задаче.
A
Yp
Y
B
C
ОЭП для возмущенной задачи: как видим, ОЭП
изменилась мало. В выпуклом случае достаточным
условием устойчивости ОЭП по отношению к
возмущению параметров задачи является наличие
внутренней точки множества Y.
A
Yp
Y
B
C
Свертки критериев – средство
нахождения точек границы Парето
Пусть h(y) – скалярная функция (свертка) критериев.
Пусть y0 – точка максимума h(y) на Y.
Вопрос 1. Принадлежит ли y0 границе Парето?
Ответ. Если из y y следует h(y’’) > h(y’)
(т.е. функция h(y) – возрастающая по отношению к
доминированию по Парето), то y0 принадлежит
границе Парето.
Вопрос 2. Может ли любая точка границы Парето
быть найдена при максимизации возрастающей
функции h(y) на множестве Y ?
Ответ. Далеко не всегда.
Наиболее часто используемые
функции критериев
1) Линейная функция h (y) = <c, y>, где c <0
(напомним, что рассматривается задача
минимизации), является возрастающей по
отношению к доминированию по Парето;
2) Отклонение по Чебышёву от идеальной
точки y*
h (y) = max { i (yi - yi*) : i=1,2,...,m},
где i : i=1,2,...,m - неотрицательные
коэффициенты, является убывающей по
отношению к доминированию по Слейтеру.
Свойства линейных сверток
1) Точка максимума линейной функции
h (y) = <c, y>, где c <0, на множестве Y
принадлежит границе Парето.
2) Если ОЭП выпукло, то любая точка
границы Слейтера является
максимумом на множестве Y
некоторой линейной функции h (y) =
<c, y> с неположительным вектором c.
Пример
y2
P(Y)
f(X)
c
y1
Свойства расстоянию по Чебышёву
1) Точка минимума функции Чебышёва
h (y) = max { i(yi - yi*) : i=1,2,...,m},
где i 0: i=1,2,...,m, на множестве Y
принадлежит границе Слейтера.
2) любая точка границы Слейтера является
минимумом функции Чебышёва
h (y) = max { i (yi –(yi*-eps)) : i=1,2,...,m},
где i 0: i=1,2,...,m, на множестве Y при
некотором eps>0.
Пример
y2
P(Y)
f(X)
y*
y1
Д. Основные классы методов
многокритериальной
оптимизации
Старые простые подходы
Априорные ограничения: ЛПР
выбирает наиболее важный критерий,
назначает ограничения на величины
остальных и решает задачу: y i min
*
~
y i y i , i 1, 2 ,..., m ; i i* ; y f ( x ), x X
Априорные веса: ЛПР указывает веса
для всех критериев и решает проблему
w
i
y i min
y f ( x ), x X
Классификация современных методов
в соответствии с ролью ЛПР
Методы МКО
No-preference
methods
A priori
preference
methods
A posteriori
methods
Interactive
methods
Методы, не учитывающие
предпочтения ЛПР
(No-preference methods)
Методы, не учитывающие
предпочтения ЛПР
Проблема решается экспертом на основе
решения некоторой задачи скалярной
оптимизации, которая формулируется
на основе использования некоторых
свойств множества достижимых
критериальных векторов или границы
Парето. Найденное решение
передается ЛПР, которое принимает
или отвергает его.
Пример
Решается задача: минимизировать h (y) на Y,
где h (y) = max {(yi - yi*)/(yi** - yi*): i=1,2,...,m}, а
y** -- это некоторая «наихудшая» точка (скажем,
набор самых плохих значений критериев на
границе Парето или на множестве Y). Возможно,
что y** -- это самые плохие значения критериев
из приемлемых для ЛПР. Решение в
значительной степени зависит от самой плохой
точки, хотя этого быть не должно. Меняя y**,
можно получить любую точку P(Y).
Рассмотренный подход прост для ЛПР,
но он игнорирует его предпочтения и
выбирается, по существу, произвольное
решение, принадлежащее множеству
Парето. Методы этого типа могут быть
приемлемы для ЛПР, особенно если ЛПР
желательно избежать ответственности за
принятое решение.
Методы основанные на
моделировании предпочтений
ЛПР
(A priori preference methods)
Методы основанные на
моделировании предпочтений ЛПР
• Методы, основанные на многокритериальной теории полезности (MAUT)
• Методы, основанные на прямом
назначении весов критериев
• Методы, основанные на сложных
процедурах построения весов критериев
(пример: Analytic Hierarchy Process)
• Целевые методы
• Методы, основанные на других
эвристических концепциях
Использование MAUT: аппроксимация кривых
безразличия аддитивной функции полезности
(R.Keeny and H.Raifa)
y max
y2
v(y1, y2)=v1(y1)+v2(y2)
v2(y2)=2
v2(y2)=1
v=0
v1(y1)=1
v1(y1)=2
y1
Требуется большое число сравнений критериальных
точек. В случае более чем двух критериев такой
картины использовать не удается.
Методы, основанные на прямом
назначении весов критериев
ЛПР назначает положительные веса для
каждого из критериев и решает задачу
m
h( y) w
i
y i min
y f ( x ), x X
i 1
Важный недостаток линейных сверток:
ухудшение значения одного критерия
может быть компенсировано улучшением
значения другого
Более сложные свертки
m
h( y) wg
i
i
( y i ) min
y f ( x ), x X
i 1
• Функции gi(yi) задаются ЛПР с
помощью графиков.
• Метод противоречит MAUT, согласно
которому вид свертки определяется
ответами на вопросы о предпочтениях.
Методы, основанные на сложных
процедурах построения весов критериев
(пример: Analytic Hierarchy Process
by T.Saaty)
ЛПР должен ответить на m(m-1)/2 вопросов
об относительной важности критериев.
Находятся веса (важности), в наибольшей
степени соответствующие, вообще
говоря, противоречивым ответам ЛПР.
Возможно использование качественных
критериев, а также принятие решения в
отсутствии модели.
Целевой подход – 1
ЛПР должен указать предпочтительную
критериальную точку без информации о
множестве Y=f(X).
y2
0
y1
Целевой подход – 2
Затем, с использованием достаточно
произвольной метрики, находится
ближайшая к цели точка множества Y=f(X).
y2
y0
0
Y=f(X)
y1
Целевой подход – 3
Целевой поход– наиболее часто
используемый метод МКО. Он, однако,
имеет существенные недостатки:
• ЛПР назначает цель без знания того, где
же проходит граница множества Y=f(X);
• если цель далека от множестваY=f(X), то
ближайшая к ней точка y0 зависит более
от метрики, а не от цели.
Из методов, основанных на
моделировании предпочтений,
используются эвристические
методы, поскольку теоретически
обоснованные методы оказались
слишком сложны
Интерактивные (итеративные)
методы
Интерактивные
(итеративные) методы
Методы основаны на решении задач скалярной
оптимизации с целью нахождения решений,
оптимальных по Парето. Методы включают
взаимодействие ЛПР с компьютером, в рамках
которого ЛПР оценивает найденное решение и
модифицирует задачу оптимизации. Таким
образом, методы состоят из итераций, каждая из
которых включает в себя два шага:
а) ЛПР назначает параметры задачи оптимизации;
б) компьютер решает задачу оптимизации.
Общая схема итеративных методов
После k-й итерации ЛПР получает решение x
и критериальный вектор y ( k ) f ( x ( k ) ) , а также
вспомогательную информацию.
• Шаг 1. ЛПР изучает результаты, полученные
на k-й итерации и, если он не удовлетворен
ими, формулирует новую задачу скалярной
оптимизации.
• Шаг 2. Компьютер находит новое решение
( k 1)
( k 1)
( k 1)
y
f
(
x
),
x
и критериальный вектор
а также вспомогательную информацию.
(k )
Простейший итеративный метод
Метод основан на использовании линейной
свертки h (y) = <c, y>. Итерация метода
состоит из следующих шагов:
a) На первой итерации ЛПР просто задает
параметр c<0. На следующих итерациях он
это делает после изучения решения и
критериального вектора, найденного на
предыдущей итерации.
б) Компьютер находит решение задачи
максимизации свертки <c, f(x)> на X.
Недостатки: сложность назначения c,
неустойчивость решения по c, сложная связь
решения с вектором c.
Структуризованные итеративные
методы
Структуризованные методы – это такие
итеративные методы, в рамках которых
ЛПР отвечает на вопросы только о своих
предпочтениях, скажем:
• какой из нескольких критериальных
векторов более предпочтителен;
• значения какого из критериев ЛПР
желает улучшить, а какого готов
ухудшить.
Требования к
структуризованным методам
1. Если ЛПР отвечает на вопросы в соответствии с
некоторой функцией полезности, то имеет место
сходимость последовательности решений к
решению, оптимальному в смысле функции
полезности;
2. Сходимость достаточно быстрая;
3. ЛПР должен иметь право на ошибку;
4. Вопросы, задаваемые ЛПР, должны быть
достаточно простые.
Метод Джоффриона-Дайера
• Метод основан на перенесении в МКО градиентного
итеративного метода Фрэнка-Вулфа.
• Метод ФВ. Задача f ( x ) min при x X , где X
выпукло, а функция f ( x ) -- скалярная. Метод
основан на расчете градиента в текущей точке,
выбора луча L и нахождении min f ( x ) на x X L .
• Метод ДД. Та же задача, но функция векторная.
Для применения метода ФВ предполагается, что
ЛПР заинтересован в U ( f ( x )) max , где U () -неизвестная функция. Из-за этого для расчета
градиента ЛПР приходится отвечать на вопросы о
градиенте U (). Далее, от ЛПР требуется найти
max U ( f ( x )) на образе x X L в пр-ве критериев.
Анализ метода ДД
• Этот метод структуризованный. Ответим на
вопросы 1-4.
1) метод сходится при правильных ответах
ЛПР о gradU () и о max U ( f ( x )) на x X L ;
2) сходимость быстрая;
3) ЛПР имеет право на ошибку;
4) вопросы сложные.
• Последний недостаток определил судьбу
метода: он не используется.
Метод STEM (О.И.Ларичев и др.),
модифицированный D.P.Loucks
На k-й итерации ЛПР получает решение x ( k ) и
критериальный вектор y ( k ) f ( x ( k ) ).
• Шаг 1. ЛПР изучает результаты k-й итерации и,
если он не удовлетворен ими, указывает
*
критерий i , по которому он не удовлетворен в
наибольшей степени, а также критерии i1 ,…, i L ,
которыми он готов пожертвовать, и
соответствующие уступки 1 ,…, L.
• Шаг 2. Компьютер находит решение y i* min
при
(k )
y i * f i * ( x ), f il ( x ) f il ( x
) il , l 1,..., L , x X
Метод достаточно прост, но
не является
структуризованным, поэтому
изучен быть не может.
Графические методы. Метод Pareto Race
Методы требуют огромной
работы ЛПР, поскольку
обычно сходятся медленно, а
задаваемые вопросы сложны
Методы паретовой границы
(A posteriori preference
methods )
Методы паретовой границы
Методы паретовой границы основаны на
аппроксимации границы Парето и информировании
ЛПР относительно границы Парето. При этом ЛПР
не задаются вопросы о его предпочтениях. От ЛПР
требуется указать наиболее предпочтительную
точку границы Парето уже после изучения
информации о границе. Благодаря этому процесс
назначения наиболее предпочтительную точку
границы Парето может быть разделен во времени
с изучением границы.
Два вопроса, которые должны быть
решены при применении методов
границы Парето при m>2
• Как и в каком виде аппроксимировать
границу Парето
• В каком виде представлять ЛПР информацию
о границе Парето
При m=2 ЛПР может получить рисунок с
изображением границы Парето и указать
предпочтительную критериальную точку прямо
на изображении. При m>2 в большинстве
методов строится список точек, в совокупности
аппроксимирующих границу Парето.
Первый метод границы Парето
(S.Gass and T.Saaty,1955)
Рассматривается двумерная задача
y min y Cx, Ax b
Для построения P(Y) применяется
параметрический метод ЛП, где 0 1
y1 (1 ) y 2 min y Cx, Ax b
С использованием симплекс-метода
решается задача ЛП при 0 , а затем с
использованием симплекс-таблицы
последовательно находятся эффективные
вершины ОЭП.
y2
ЛПР получает
рисунок с
изображением
вершин и
соединяющих их
ребер
y1
Параметрические методы ЛП
для линейных проблем m>2
Прямое развитие метода Gass and Saaty на
линейные модели с m>2. Эти методы
предназначены для нахождения всех
эффективных вершин множества Y на основе
перехода от вершины к вершине.
Недостаток: огромное число вершин в
прикладных задачах, что приводит к
• неустойчивости процедуры, усугубляемой
неустойчивостью границы Парето;
• невозможности проанализировать эту
совокупность точек, представляемую списком
Метод ограничений
y2
y1
y i * min y f ( x ), x X ,
y i li , i i *, p 0 ,1 ,...,P i
p
Метод взвешенной функции Чебышёва
y2
y1
y*
h ( y ) max i ( y i y i *) : i 1, 2 ,..., m min
y f ( x ), x X
i 0, m
i 1 i 1
Недостатки обоих методов:
• Необходимость решать большое число
задач оптимизации (может быть,
многоэкстремальных);
• Результат: список точек (хотя и не такой
большой, как в параметрических методах);
• Точки расположены на границе
неравномерно.
Эволюционные методы МКО
y2
y1
Алгоритм: 1) мутация; 2) кроссовер; 3) отбор.
Результат: список точек, составляющих фронт Парето,
связь которого с границей Парето не всегда ясна.
Двухкритериальные задачи
Цитата
In a general two-criterion case, it has a sense to
display all efficient decisions by computing and
depicting the associated criterion points; then,
decision maker can be invited to identify the best
point at the compromise curve.
B.Roy
Decisions avec criteres multiples.
Metra International, v.11(1), 121-151 (1972)
Изображение границы Парето в задаче улучшения
качества воды в реке: стоимость проекта (F)
загрязнение реки (Z5)
Объективные (критериальные)
замещения (objective tradeoffs) для двух
критериев
Объективное замещение – это величина, служащая для
сравнения двух критериальных векторов y1=(y11, y12)
и y2=(y21, y22) при y12– y22 ≠0
1
2
T1, 2 ( y , y ) 1
y1
1
y2
2
y1
2
y2
Для точек границы Парето y1 и y2 величина T1,2 (y1, y2)
является отрицательной. Объективное замещение важно
для понимания того, какая из двух критериальных точек
более предпочтительна.
Замещения видны на графике
y2
Норма замещения (Tradeoff rate)
d ( y2 )
d ( y1 )
y1
( y *)
Вывод. В случае двух критериев
удобным методом является изображение
на критериальной плоскости границы
Парето, которая в этом случае часто
называется кривой компромиссов. ЛПР
указывает предпочтительное решение
прямо на кривой. При этом он
принимает во внимание не только
значения критериев, но и критериальные
замещения.
Методы визуализации
многомерной границы Парето
Основная идея – перенесение на случай многих
критериев методики, эффективно
использующейся при двух критериях. При этом
важно помнить, что при анализе границы
Парето в двумерном случае важную роль
играют не только сами значения критериев, но и
информация о замещении одного критерия
другим.
Эта идея была реализована в рамках метода
Диалоговых карт решений.
Литература
1. Р.Л.Кини, Х.Райфа. Принятие решений при многих
критериях: предпочтения и замещения.–М.:Радио и связь,1981.
2. О.И.Ларичев. Объективные модели и субъективные
решения. – М.: Наука, 1987.
3. О.И.Ларичев. Теория и методы принятия решений. – М.:
Логос, изд. 3, 2006.
4. А.В.Лотов, И.И.Поспелова. Многокритериальные задачи
принятия решений. М.: изд. МАКС Пресс, 2008
5. В.В.Подиновский, В.Д.Ногин. Парето-оптимальные решения
многокритериальных задач. – М.: Физматлит, 2007.
6. Р.Штойер. Многокритериальная оптимизация: теория,
вычисления и приложения. – М.: Радио и связь, 1992.
7. J.Branke, K.Deb, K.Miettinen, R.Slowinski (eds.) Multiobjective
Optimization. Interactive and Evolutionary Approaches, Lecture
Notes in Computer Science, V. 5252, Springer, 2008.
Документ
Категория
Презентации
Просмотров
27
Размер файла
1 052 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа