Материал: 2488

Основные шаги интерактивного метода: 1) инициализация; 2) формирование Парето-оптимальной исходной точки; 3) запрос информации предпочтения от ЛПР; 4) формирование новых Паретооптимальных решений в соответствии с информацией предпочтения; 5) ЛПР выбирает лучшее пока решение; 6) останов или переход к 3). Интерактивные методы преодолевают слабости априорных и апостериорных методов, потому что из-за структуры итерационного подхода ЛПР может не иметь глобальную структуру предпочтений и может учиться во время принятия решений. Интерактивные методы формируют только те Парето-оптимальные решения, которые предпочтительны для ЛПР.

Цель применения многокритериального метода оптимизации состоит в нахождении единственного, наиболее предпочтительного решения. Однако в некоторых случаях предпочтительнее нахождение нескольких решений. Существует большая разновидность интерактивных методов и трудно указать один метод, который превосходит другие. Самое важное предположение, лежащее в основе успешного применения интерактивных методов, – это доступность для ЛПР и его участие при принятии решений в соответствии с его предпочтениями.

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

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

Ниже рассмотрены три типа информации предпочтения в интерактивных методах: информации компромисса, подходы опорной точки и классификационные методы.

Концепции компромиссных решений. Интуитивно компро-

миссное решение – это потеря в одном аспекте задачи для получения выгоды. На языке многокритериальной оптимизации компромиссное решение – это отказ в одной из целей для повышения значений другой, насколько необходимо уступить в определенной цели для получения требуемого выигрыша в другой. Компромиссные решения могут измеряться, отслеживая структуру задачи, связи между целями.

146

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

Рассмотрим два допустимых решенияx1,x2 и соответствующие целевые векторы f x1 и f x2 . Тогда отношение изменения между

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

ленное Tij x1,x2 , может быть изменено тенденцией бесконечно малого изменения, двигаясь от определенного оптимального по Парето решения x0 вдоль выполнимого направления d. Это приводит к следующей концепции.

Для заданного допустимого решения x0 и допустимого направления d из x0 определяем общую норму компромиссных решений в x0,

Далее рассмотрим субъективные концепции принятия компромиссных решений, то есть предпочтения ЛПР принимаются во внимание. Будем считать, что существует неявная функция стоимости

147

v z1,...,zk , которая определяет субъективные предпочтения ЛПР среди допустимых решений.

(полное или частичное) известно как компромиссное решений безразличия, включающее fi и fj между x1,x2 .

Пусть все функции fi непрерывно дифференцируемы, рассмотрим компромиссное решение безразличия между fi и fj в фиксиро-

ванной точке x0 с целевым вектором z0 f x0 , который лежит на кривой безразличия v z1,...,zk v0. Если v z0 zi 0, мы можем вы-

разить zi как неявную функцию оставшихся целей (включая zj ): zi zi z1,...,zi 1,zi 1,...,zk .

Для решения x0 и соответствующего z0 норма компромиссного решения безразличия или предельная норма замещения между fi и fj :

инфинитезимальный декремент значения целевой функции fi, который компенсирует инфинитезимальный инкремент значения целевой функции fj , в то время как значения всех других целевых функций остаются неизменными.

Получение компромиссных решений на Парето-оптимальном множестве. Решая многокритериальную задачу оптимизации с использованием интерактивного метода, важно знать объективные (целевые) компромиссные решения, когда двигаешься от одних Парето оптимальных решений к другим. Это знание может позволить ЛПР решать, искать ли более предпочтительные Парето-оптимальные решения в определенных направлениях. Ключевой вопрос для компромиссных решений, основанных на интерактивных методах, – получение частичных норм компромиссных решений для Парето-

148

оптимальных решений; при этом задача -ограничений играет ключевую роль.

N* x0 *i1,..., *i,i 1, 1, *i,i 1,..., *ik может быть интерпретирован как вектор-нормаль к границе Парето оптимального множества.

вектор к границе Парето-оптимального множества в z0 .

3.1.3. Методы, основанные на компромиссе

Метод Z-W основан на кусочных линеаризациях задачи и использовании свойств Парето оптимальных решений линейных задач. Метод предполагает: 1) существует вогнутая неявная функция стоимости v; 2) целевые функции и область допустимых решений выпуклые. Удобным (но не обязательным) свойством является аддитивная сепарабильность целевых функций.

Идея метода следующая: Парето-оптимальные решения находятся с помощью метода взвешенных сумм. Затем идентифицируются смежные к текущему решению Парето-оптимальные вершины, соответствующие компромиссные решения представляются ЛПР для

149

формирования его предпочтений по отношению к текущему решению. По этой информации реализуются веса и находится новое решение.

Метод ISWT (interactive surrogate worth trade-off) является инте-

рактивным вариантом метода замещения стоимости принятия компромиссных решений ценности идентификатора объекта. Основная концепция метода основана на замещении стоимости оценки желательности принимаемых компромиссных решений ЛПР полученных Парето-оптимальных решений. Метод предполагает: 1) существует непрерывно дифференцируемая и монотонно уменьшающаяся неявная функция стоимости υ; 2) все функции дважды непрерывно дифференцируемы; 3) область допустимых решений компактная; 4) оптимальные KKK множители обеспечивают частичные компромиссные решения. Метод выполняется следующим образом: определяют Парето-оптимальные решения, используя ε-ограничения; в текущем решении получают целевые компромиссы и показывают ЛПР для оценивания желательности; эта информация формирует вектор верхних пределов и производит новые решения.

Основная идея алгоритма GDF следующая: предполагается существование неявной функции стоимости v, которую ЛПР желает максимизировать в области допустимых решений; применяется алгоритм Franke-Wolfe для решения промежуточных задач. Метод предполагает: 1) область допустимых решений компактная и выпуклая; 2) целевые функции непрерывно дифференцируемы и выпуклы; 3) неявная функция стоимости непрерывно дифференцируемая, монотонно уменьшающаяся и вогнутая.

В методе GDF запрашивают информацию ЛПР о предельных нормах замещений, которые используются для определения восходящего направления функции стоимости; затем используется аппроксимация оптимальной длины шага при оценивании и формируется следующая итерация.

Метод SPOT (sequential proxy optimization technique) – интерак-

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

150